Consider the following expression BNF: <expression> ::= <term> + <expression> |

Question

Consider the following expression BNF:

<expression> ::= <term> + <expression> | <term> - <expression> | <term> <term> ::= <factor> * <term> | <factor> / <term> | <factor>
<factor> ::= <digit> | ( <expression> )
<digit> ::= 0|1|2|3|4|5|6|7|8|9

Using recursive descent, and only recursive descent, scan expressions that adhere to this BNF to build their expression tree; write an integer valued function that scans the tree to evaluate the expression represented by the tree.

There are plenty of clever programs online that you can download to evaluate arithmetic expression tree; if you want zero in this assignment, download one and submit it as programming assignment #2; if you want a grade greater than zero, please follow our instructions. Thanks.

Explanation / Answer

the calculator grammar
procedure expr()
term(); term_tail();
procedure term_tail()
case (input_token())
of '+'or '-': add_op(); term(); term_tail();
otherwise: /* skip */
procedure term()
factor(); factor_tail();
procedure factor_tail()
case (input_token())
of '*' or '/': mult_op(); factor(); factor_tail();
otherwise: /* skip */
procedure factor()
case (input_token())
of '(': match('('); expr(); match(')');
of '-': factor();
of identifier: match(identifier);
of number: match(number);
otherwise: error;
procedure add_op()
case (input_token())
of '+': match('+');
of '-': match('-');
otherwise: error;
procedure mult_op()
case (input_token())
of '*': match('*');
of '/': match('/');
otherwise: error;

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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