Bottom up shift reduce parser that parses arithmetic expression ysing BNF grammar
$30-50 USD
Closed
Posted over 17 years ago
$30-50 USD
Paid on delivery
Write a bottom up shift reduce parser that parses arithmetic expressions using the BNF grammar and parse table(i shall scan and send the parse table shortly). During the parsing process the program should construct an abstract syntax tree for the parsed expression. Use single alphabet letters for the identifiers. An input string of: A * (B + C)
corresponds to a BNF: id * (id + id)
and the resulting abstract syntax tree is:
You can do the assignment in C++ or Java. One approach would be to define a class for a tree node with two subclasses, one for identifiers (leaf nodes) and another subclass for binary operators (internal nodes). A binary operator node would store two pointers or references to references to tree node objects.
A symbol stored on the stack could contain a pointer or reference to the root node of an abstract syntax tree representing the grammar symbol. When the parser executes a reduction using the BNF rule
E[1] -> E[2] + T the parser would construct a new + operator node and point its left and right child node pointers to the syntax trees of
E[2] and T, then remove the E[2] + T from the stack and replace it with E[1] with its pointer pointing to the newly constructed + node.
*
A +
B C
## Deliverables
1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done.
2) Deliverables must be in ready-to-run condition, as follows (depending on the nature of the deliverables):
a) For web sites or other server-side deliverables intended to only ever exist in one place in the Buyer's environment--Deliverables must be installed by the Seller in ready-to-run condition in the Buyer's environment.
b) For all others including desktop software or software the buyer intends to distribute: A software installation package that will install the software in ready-to-run condition on the platform(s) specified in this bid request.
3) All deliverables will be considered "work made for hire" under U.S. Copyright law. Buyer will receive exclusive and complete copyrights to all work purchased. (No GPL, GNU, 3rd party components, etc. unless all copyright ramifications are explained AND AGREED TO by the buyer on the site per the coder's Seller Legal Agreement).
## Platform
Program to be written in C++. I wish to run it in Visual C++ software.