Consider the following BNF grammar for <Exp>. <Exp> ::= <Exp> + <MulExp> | <Exp>

Question

Consider the following BNF grammar for <Exp>.
<Exp> ::= <Exp> + <MulExp>
| <Exp> - <MulExp>
| <MulExp>
<MulExp> ::= <MulExp> * <NegExp>
| <MulExp> / <NegExp>
| <NegExp>
<NegExp> ::= - <RootExp>
| <RootExp>
<RootExp> ::= ( <Exp> )
| 1 | 2 | 3 | 4
1. Extend the grammar by exponentiation such as 2^3. Exponentiation
should have higher priority than binary operations +, -, /, and *, but
lower priority than negation operator -. Exponentiation is right associa-
tive. That is, 2^3^4 is the same as 2^(3^4), which yields 2 81 and not just
4096 = (2 3 ) 4 .
2. Draw a parse tree for -2^3^4 according to the new BNF grammar.
3. Draw abstract syntax trees for the the following terms -2^3^4 and -(2^3^4).
(Note that parenthesis are omitted in the AST.)

screen shot:

http://s24.postimg.org/uw258oxdx/Screenshot_2014_02_02_13_26_14.png

Consider the following BNF grammar for Extend the grammar by exponentiation such as 2^3. Exponentiation should have higher priority than binary operations +, -, /, and *, but lower priority than negation operator -. Exponentiation is right associative. That is, 2^3^4 is the same as 2^(3^4), which yields 2 81 and not just 4096 = (2 3 ) 4. Draw a parse tree for -2^3^4 according to the new BNF grammar. Draw abstract syntax trees for the the following terms -2^3^4 and -(2^3^4).

Explanation / Answer

1. Extend the grammar by exponentiation such as 2^3. Exponentiation
should have higher priority than binary operations +, -, /, and *, but
lower priority than negation operator -. Exponentiation is right associa-
tive. That is, 2^3^4 is the same as 2^(3^4), which yields 2 81 and not just
4096 = (2 3 ) 4 .

if we observe the grammar, the operator that is having the lowest precedence is in the top production rule..

the order of precedence from lower to higher is +, -, *, /,^, unary -. however + and - are having equal priority, * and / are having equal priority. so they are included in same productions.

when we draw a parse tree for any string using the given grammar, lowest precedence operator will be at the root level and highest precedence operator will be at the leaf level. because, if evaluation is done based on the parse tree, leaf nodes will be evaluated first and then higher levels lastly root node. following tree evaluation, the lowest precedence operator will be placed on top.

coming to associativity, to ensure associativity in the productions we have two rules.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.