What goes in between { and } when writing BNF?

Question

I'm having some trouble with BNF. I can't tell what seems to be the standard way of doing things (if there is one), and whether or not there are types like char or int or whatever already built in.

However, my main problem is not understand how the part of the BNF in curly braces works.
Given something like:

exp    : term                           {$$ = $1;}  
| exp '+' term                   {$$ = $1 + $3;}  
| exp '-' term                   {$$ = $1 - $3;}  
;  

(This was handily stolen from somewhere, and is for yacc / C)

What are the things in the curly braces actually saying? I've looked at a similar thing for the happy parser generator too, and been similarly confused.

Answer 1

The stuff within curly braces is actually C code that is executed when the corresponding rule is parsed. The $ symbols are placeholders that are replaced with the actual values parsed by yacc: $$ is the result you wish to compute, while $1 to $n represent the values of the symbols on the right-hand side of the rule.

For example, the rule exp '+' term { $$ = $1 + $3; }, $1 refers to the exp and $3 is the term, so this says that when this rule is parsed, add exp and term to get the result.

Answer 2

You need to distinguish between BNF in general (and EBNF) and the Yacc syntax. What the braces mean in BNF varies with dialect; it often means 'choose one of the alternatives', or it can be associated with repetition, or both. In EBNF (ISO 14977:1996), '{ ... }' means repeat zero or more times, and '{ ... }-' means repeat one or more times (and why that is a '-' and not a '+' is mysterious). The IETF uses RFC-5234 and its dialect of BNF does not use '{}' at all.

In a Yacc grammar, though, the braces enclose the actions to be performed when the rule is matched (reduced in the jargon). So, the '{$$ = $1;}' action means 'assign the value matched by 'term' to the result of reducing 'exp ::= term' (using another variant of BNF).