Optional vs. mandatory terminators in context-free grammar definition
Question
In a book chapter about compilers, there's the following grammar definition and example code.
...
statement: whileStatement
| ifStatement
| ... // Other statement possibilities
| '{' statementSequence '}'
whileStatement: 'while' '(' expression ')' statement
ifStatement: ... // Definition of "if"
statementSequence: '' // empty sequence (null)
| statement ';' statementSequence
expression: ... // Definition of "expression"
... // More definitions follow
while (expression) {
statement;
statement;
while (expression) {
while(expression)
statement;
statement;
}
}
How is the code's inner-most while
loop valid without {
}
? It looks to me that the statement definition requires them. Is this a mistake in the book or am I misunderstanding the syntax?
[Edit] My apologies for any ambiguity. Everything typed above is verbatim from the book. The omissions were not my doing.
Solution
Consider your example code again:
1 while (expression) {
2 statement;
3 statement;
4 while (expression) {
5 while(expression)
6 statement;
7 statement;
8 }
9 }
Why are you concerned that line 6 lacks braces, but don't care that lines 2, 3, and 7 are missing them too? The grammar is saying that a while
loop ends with a statement
, and a statementSequence
, with its required braces, is just one of many alternatives for a statement
. Lines 5 and 6 match that rule exactly—except for the ';'
, which doesn't have a place in the rule.
OTHER TIPS
Your while statement says that after the )
comes a statement. Your grammar doesn't fully specify statement
, but it doesn't require braces. Braces are only needed for a statement sequence.