Parser that will recognize and evaluate an arithmetic expression generated by the given context-free grammar G as follows
USE
Build a Parser that will recognize and evaluate an arithmetic expression generated by the given context-free grammar G as follows, in which int is a terminal symbol representing integers.
E → E + T | E – T | -E | T
T → T * F | T/F | F
F → int | (E)
Basically, we want the parser that will:
1. produce an error message if its input arithmetic expression is not in the language of the given grammar.
2. implement a calculator to compute the result of the input arithmetic expression if the input arithmetic expression is in the language of the given grammar (which is called a valid arithmetic expression).
Each input arithmetic expression in the language will have a single parse tree based on the following precedence and associativity rules:
• Unary minus (-) have precedence over all operators.
• Parentheses have precedence over the binary operators *, /, +, and -.
• * and / have precedence over the binary operators + and -.
Write your own program (including lexer and parser) to recognize and evaluate the input arithmetic expressions generated by given G using recursive descent parsing (a technique known as top-down LL(1) parsing). The idea of recursive-descent parsing is to transform each nonterminal of a grammar into a subroutine that will recognize exactly that nonterminal in the input. Notice that, left recursive grammars, such as the given G, are unsuitable for recursive-descent parsing because a left-recursive production leads to an infinite recursion (loop). While the parser may be partially correct, it may not terminate. We need to transform G to an equivalent non-left-recursive grammar G’ by eliminating left recursions in G. Also, the language described by G’ is the same as that of grammar G, that is, L(G’) = L(G) and G’ is unambiguous, and each choice can be made by looking at the next token in the input string. You must write the program in C++.
Requirement for submission: your final submission to Canvas must have two (2) files: your executable program (with necessary comments), and a readme file including the rewritten grammar G’ and a brief manual for code (e.g., how to compile and run the program).
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
