BNF and EBNF Modified Arithmetic

6.13


Original BNF (Fig. 6.17): 


expr --> expr + term | term
term --> term * factor | factor
factor --> ( expr ) | number
number --> number digit | digit
digit --> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9




Original EBNF (Fig. 6.18):


expr --> term { + term }
term --> factor { * factor }
factor --> ( expr ) | number
number --> digit { digit }
digit --> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9




a) At most, one unary minus is allowed in each expression, and it must come at the beginning of an expression, so -2 + 3 is legal (and equals 1) and -2 + (-3) is legal, but -2 + -3 is not.




Modified BNF: 


signed-expr --> - expr | expr
expr --> expr + term | term
term --> term * factor | factor
factor --> ( signed-expr ) | number
number --> number digit | digit
digit --> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9


The reason this works, is because the root is changed from expr to signed-expr, and now only the first term that doesn't have a parenthesis will be signed or any other term that has parenthesis.

The reason that -2 + -3 would not work in this situation is the fact that the minus is added at the expression level, and if there is no () around the -3, it's not evaluated as an expression so it can never pass this test.

Modified EBNF:


signed-expr --> - expr | expr
expr --> term { + term }
term --> factor { * factor }
factor --> ( signed-expr ) | number
number --> digit { digit }
digit --> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

This one works for the same reason that the previous BNF version does. Although, the syntax is slightly different.

b) At most, one unary minus is allowed before a number or left parenthesis, so -2 + -3 and -2 * -3 are legal, but --2 and -2 + --3 are not.


Modified BNF:



expr --> expr + term | term
term --> term * factor | factor
factor --> - ( expr ) | ( expr ) | signed-number
signed-number --> - number | number
number --> number digit | digit
digit --> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Here you can see how the changing of where the sign appears in the tree restricts the possibilities. If we were to try -2 * -3, it would work out just fine.


Modified EBNF:



expr --> term { + term }
term --> factor { * factor }
factor --> -( expr ) | ( expr ) | signed-number
signed-number --> - number | number
number --> digit { digit }
digit --> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9


This version is basically identical to the BNF form, due to the type of change we are making. The E (Extended) does not get in our way for this modification.


c) Arbitrarily many unary minuses are allowed before numbers and left parenthesis, so everything above is legal.


This would require us to create signed-factors so we can have double negatives.



Modified BNF:



expr --> expr + term | term
term --> term * signed-factor | signed-factor
signed-factor --> - factor | factor
factor --> ( expr ) | signed-number
signed-number --> - number | number
number --> number digit | digit
digit --> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9



Modified EBNF:



expr --> term { + term }
term --> signed-factor { * signed-factor }
signed-factor --> - factor | factor
factor --> ( expr ) | signed-number
signed-number --> - number | number
number --> digit { digit }
digit --> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9