See Picture. One way of defining the abstract syntax for the expressions of Figu
ID: 3787601 • Letter: S
Question
See Picture.
One way of defining the abstract syntax for the expressions of Figure 6.17 is as follows: expr rightarrow expr + expr | expr * expr | number number rightarrow digit {digit} digit rightarrow 0 | 1 | 2 |3 | 4 | 5 | 6 | 7 | 8 | 9 Why are there no precedences or associativities expressed in this grammar? Why are there no parentheses in this grammar? The rule for number is written in EBNF in this grammar, yet we stated in the text that this obscures the structure of the parse tree. Why is the use of EBNF legitimate here? Why did we not use EBNF in the rule for expr?Explanation / Answer
(a)
Actually we don’t have to worry about left and right associative of given above grammar because it does not include subtract sign so : (2+3) + 4 and 2 + (3+ 4) are same but 2 - (3 - 4) and (2 - 3) -4 are not same but there’s no "- " sign in given grammar so we need not worry.
There are no precedence rules. Because it is possible for 2 + 3 5 to have two parse trees giving rise to two different values i.e. 23 & 35 but from mathematics rules operator has more precedence than + operator thus giving 23. So if it is converted to revised grammar as in 6.17 there would be precedence rules.
(b)
There is no rule like expr -> (expr) so we can’t make rule with parenthesis.
(c)
EBNF is useful to obscure any left associatively expressed by the left recursion only. But in the given grammar right recursion is also possible: expr -> expr + expr . So as we can’t express right recursion thus we didn’t write in EBNF.