COMP15 Project #7: Parsing infix expressions

COMP 15 Project #7: Parsing infix expressions

COMP15 Fall 20XX
Due: Monday, November 22, 11:00PM

Overview

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.

Objectives

The objectives for this project are:

To construct a program to read and parse an infix arithmetic expression using recursive descent.
To build an internal intermediate representation for an arithmetic expression using a binary tree.
To learn about and implement pre-order, in-order and post-order tree traversals.
To comfortably apply recursion in practice.
To gain further experience with software reuse.

The parsing module and lexical analysis modules will be reused in project #8 (drawing an expression tree.)

What needs to be done

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 | NUMBER

When 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:

You will need to write a separate main function (in its own source file, infix_main.cpp, to control the process of parsing, traversing, etc.
Your program must take a single command line argument which is the name of the file containing the infix expression to be parsed and displayed. The grader will use this argument to supply the name of a test file to your program.
You must use and provide a makefile to build your solution.
You should thoroughly and systematically test the parser as you will be reusing this module in project #8.

Add comments to the source code to describe your approach and solution. Don't forget to fill out any header comments with your name, section and e-mail address.

On-line resources

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.html

The note on recursive descent parsing is at the URL:

http://www.eecs.tufts.edu/comp/15/notes/recur_descent

You should also look at the notes on the example program that parses prefix notation expressions:

http://www.eecs.tufts.edu/comp/15/notes/prefix

Submitting your work

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 everything

Be 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.

Extra credit

Here are two additional requirements to obtain extra credit:

Handle the use of the minus sign ('-') to denote negative numbers and unary arithmetic negation as well as binary arithmetic subtraction. Modification of the lexical analyzer is necessary to meet this requirement. Hint: Disambiguation of a minus sign depends upon the lexical context in which the minus sign appears.
Traverse the expression tree and use the evaluation stack module(s) to evaluate the expression. Of course, the operands in such a tree must be restricted to numbers only (no IDENTIFIER operands.)

Informal interface specification: Infix

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:
    None