## CS 31600 - Homework Assignment 3

In this assignment you will write a parser for the language of infix arithmetic expressions. You will write the parser in four stages, with each stage parsing a language that is more complicated than the one before. This assignment is due Tuesday, February 21. This assignment makes use of files contained in this zip file. The four languages are called `Expr1`, `Expr2`, `Expr3`, and `Expr4`. The parsers for each language consist of three files, `ParseExpr_.java` `ParseExpr_ParseTree.java` `TestExpr_.java` where the blank in each file name is filled in with a number from 1 to 4. Each of the four test files is already written for you. You need to complete each of the two parsers for each language. One parser creates an expression tree as it parses a string in its language, and the other parser creates a parse tree. When you are finished, the output from each `TestExpr_.java` program should look exactly like its output file `output-Expr_.txt`. In addition, the test programs create png image files of the expression and parse trees. In the folder `hw3/png-files/` you will find png files that show you what the output from your finished parsers should look like. The language for each parser is described by a grammar at the beginning of each `ParseExpr_.java` file. Language `Expr1` is an expression language that has two operators that are right associative. The next language, `Expr2`, has two operators that are left associative (left associative is a bit harder to implement than right associative). Language `Expr3` adds parentheses to the syntax. The last language, `Expr4`, adds the two unary operators and the exponentiation operator, and it is the same infix arithmetic expression language that was used in homework assignment 2 (it's also described in the file `Infix Expression Grammar.txt` from the zip file.) In the zip file there are five source files, `BTree.java` `BTree2dot.java` `Tree.java` `Tree2dot.java` `Tokenizer.java` that are completed for you. To get the test files to compile and run, you will need to add to the `hw3` folder copies of your `Evaluate.java` and `InfixPrinter.java` files from homework assignment 2. To get the test programs to run, you will also need to install the Graphviz package on your computer. You can download the Graphviz installer using this URL. http://www.graphviz.org/pub/graphviz/stable/windows/graphviz-2.28.0.msi To help you test if you have Graphviz installed correctly, and to help you see how your finished parsers should compile and run, included in the zip file is a completed language consisting of the three files `ParseExpr0.java`, `ParseExpr0ParseTree.java`, and `TestExpr0.java`. The language in these files is the language of prefix arithmetic expressions from assignment 2. After you have installed Graphviz, and you have added a copy of your program `Evaluate.java` to the `hw3` folder, you should be able to compile and run `TestExpr0.java`. It should produce 14 dot files and 14 png files. Do the four expression tree parsers first, since they are easier to implement than the parse tree parsers. Do the four expression tree parsers in order, from `ParseExpr1.java` to `ParseExpr4.java`. When you get an expression tree parser working, use it as the starting point for the next parser. You do not need to change much from one language to the next. When you have all four expression tree parsers working correctly, you should be ready to do the parse tree parsers. When you work on a parse tree parser, it helps to keep a simple expression from the language, and its parse tree, in your mind as you implement the methods in the parser. When you implement a method, look at your example parse tree and ask yourself what that method needs to do to build its part of the parse tree. Turn in a zip file called `CS316Hw3Surname.zip` (where `Surname` is your last name) containing the files `BTree.java`, `BTree2dot.java`, `Tree.java`, `Tree2dot.java`, `Tokenizer.java`, your versions of the files `Evaluate.java` and `InfixPrinter.java` from assignment 2, and each of the three programs `ParseExpr_.java`, `ParseExpr_ParseTree.java`, `TestExpr_.java` for each integer 1, 2, 3, and 4. Make sure you include all 19 of these files, so that I can compile and run your parsers. Do not submit any of the dot or png files. I will create those when I compile and run your programs. Here are some references that you may find useful. A Simple Recursive Descent Parser from Introduction to Programming Using Java Parsing Expressions by Recursive Descent by Theodore S. Norvell 3.2.1 Recursive Descent Parsing from Design and Construction of Compilers CS 3721 Programming Languages: Recursive Descent Parsing This assignment is due Tuesday, February 21.

Return to the main homework page.
Return to the CS 31600 home page.

compliments and criticisms