COMP15 Fall 20XX
Due: Monday, November 22, 11:00PM
The goal of this project is a program to parse an infix arithmetic expression, build a binary tree intermediate representation of the expression, and then traverse the tree to display the expression in prefix, infix and postfix forms.
The objectives for this project are:
Only one file is provided, infix_tree.h, which contains the declarations of the Node and Infix classes. This file is available in the directory /g/15/class/project7. You will need to copy this file to your own working directory and use it as a starting point for development. You must reuse the lexical analyzer class that you developed in project #5.
You will need to implement the Infix class (infix_tree.cpp.) An informal interface specification for this module is given below. The parser must use recursive descent parsing to recognize the grammar:
E ::= E '+' T | E '-' T | T T ::= T '*' F | T '/' F | F F ::= '(' E ')' | IDENTIFIER | NUMBERWhen left recursion is removed, the rules of the grammar are:
E ::= T E' E' ::= '+' T E' | '-' T E' | EMPTY T ::= F T' T' ::= '*' F T' | '/' F T' | EMPTY F ::= NUMBER | IDENTIFIER | '(' E ')'In order to avoid difficulties with unary minus, numbers are restricted to positive integers (including zero) and the unary minus operator is not included in the grammar.
You will need to write a separate function for each production rule and add the prototype (signature) of any new functions to the private members of the Infix class. These functions will be indirectly recursive. The functions must also build a binary expression tree using instances of the Node class. Remember, expression parsing proceeds top-down while tree building is performed bottom-up. Thus, each function should return a pointer to the subtree which it has built. A function should return NULL if it does not successfully apply the associated production (i.e., the parse of the subexpression fails.)
You will need to write three additional public functions -- preorder, inorder and postorder -- which traverse the expression tree in pre-order, in-order and post-order, respectively. Each traversal function should display a node such that the resulting output will produce the expression tree in prefix, infix and postfix notation. Please pay attention to formatting and try to make the resulting output as readable as possible. The public functions call inner, private functions to recursively walk the tree in the appropriate order.
Here are some additional requirements to be satisfied:
As usual, the class notes have vital information for development. All course notes are available through the "life line" URL:
http://www.eecs.tufts.edu/comp/15/schedule.htmlThe note on recursive descent parsing is at the URL:
http://www.eecs.tufts.edu/comp/15/notes/recur_descentYou should also look at the notes on the example program that parses prefix notation expressions:
Use the provide system to submit your finished program:
provide comp15 a7 prefix_main.cpp ...The files to be submitted are:
infix_tree.h Declaration of infix parser interface infix_tree.cpp Definition of infix parser lexan.h Declaration of the lexical analysis interface lexan.cpp Implementation of the lexical analyzer infix_main.cpp Parse/traversal driver makefile makefile to build everythingBe sure to build and test your program on comp15.cs.tufts.edu before submitting your work. This system is the target build and test platform for all course projects.
Here are two additional requirements to obtain extra credit:
Function: Infix Purpose: Constructor for expression parser; Initializes private data members Parameters: None Returns: Nothing Error conditions: None Function: open Purpose: Opens the input file and prepares expression parsing Parameters: filename: Pointer to the name of the input file Returns: True if the input file is successfully opened; false on failure Error conditions: Unable to open input file Function: close Purpose: Closes the input file after parsing is complete Parameters: None Returns: Nothing Error conditions: None Function: parse Purpose: Parses the expression in input file and builds a binary tree that represents the expression Parameters: None Returns: True if the parse was successful; false if the parse failed Error conditions: Syntax error Side-effects: The root of the generated expression tree is saved in the private data member, tree. Function: preorder Purpose: Performs a preorder traversal of the expression tree and displays the tree in prefix notation, e.g., (+ (* 10 20) 30) Each subexpression is surrounded by () for readability. The public method function preorder calls the private function inner_preorder with a pointer to the expression tree. Parameters: None Returns: Nothing Error conditions: None Function: inorder Purpose: Performs a inorder traversal of the expression tree and displays the tree in fully parenthesized infix notation, e.g., ((10 * 20) + 30) Each subexpression is surrounded by () for readability. The public method function inorder calls the private function inner_inorder with a pointer to the expression tree. Parameters: None Returns: Nothing Error conditions: None Function: postorder Purpose: Performs a postorder traversal of the expression tree and displays the tree in postfix notation, e.g., 10 20 * 30 + Do not generate parentheses. The public method function postorder calls the private function inner_postorder with a pointer to the expression tree. Parameters: None Returns: Nothing Error conditions: NoneCopyright © 2004-2013 Paul J. Drongowski