Description
Using the token definitions from programming assignment 2, we can construct a language with
the following grammar rules:
Prog := Slist
Slist := Ssep { Slist } | Stmt Ssep { Slist }
Ssep := NL | SC
Stmt := IfStmt | PrintStmt | SetStmt | LoopStmt
IfStmt := IF Expr BEGIN Slist END
PrintStmt := PRINT Expr
SetStmt := SET IDENT Expr
LoopStmt := LOOP Expr BEGIN Slist END
Expr := Prod { (PLUS | MINUS) Prod }
Prod := Primary { (STAR | SLASH) Primary }
Primary := IDENT | ICONST | SCONST | LPAREN Expr RPAREN
This language will be used for the remainder of the semester.
The following items describe the language.
1. The language contains two types: integer and string.
2. All operators are left associative.
3. An IfStmt evaluates the Expr. The expr must evaluate to an integer. If the integer is
nonzero, then the Stmt is executed.
4. A PrintStmt evaluates the Expr and prints its value.
5. A SetExpr evaluates Expr and saves its value in memory associated with the IDENT. If
the IDENT does not exist, it is created. If the IDENT already exists, its value is replaced.
6. The type of an IDENT is the type of the value assigned to it.
7. The PLUS and MINUS operators in Expr represent addition and subtraction.
8. The STAR and SLASH operators in Prod represents multiplication and division.
9. It is an error if a variable is used before a value is assigned to it.
10. Addition is defined between two integers (the result being the sum) or two strings (the
result being the concatenation).
11. Subtraction is defined between two integers (the result being the difference).
12. Multiplication is defined between two integers (the result being the product) or for an
integer and a string (the result being the string repeated integer times).
13. Division is defined between two integers
14. Performing an operation with incorrect types or type combinations is an error.
15. Multiplying a string by a negative integer is an error.
16. An IF or LOOP statement whose Expr is not integer typed is an error.
Note that by the time the semester is over, you will need to handle all of these items that
describe the language. However, you will not need to handle most of them in assignment 3.
For Programming Assignment 3, you MUST implement a recursive descent parser. You may
use the lexical analyzer you wrote for Assignment 2, OR you may use a solution provided by the
professor.
A skeleton for the solution, with some of the rules implemented, is provided as starter code. You
may use this to begin the assignment if you like.
You must create a test program for your parser. The program takes zero or one command line
argument. If zero command line arguments are specified, the program should take input from
the standard input. If one command line argument is specified, the program should use the
argument as a file name and take input from that file. If the file cannot be opened, the program
should print COULD NOT OPEN followed by the name of the file, and should then stop. If more
than one command line argument is specified, the program should print TOO MANY
FILENAMES, and should then stop.
The result of an unsuccessful parse is a set of error messages printed by the parse functions. If
the parse fails, the program should stop after the parse function returns.
The assignment does not specify the exact error messages that should be printed out by the
parse; however the format of the message should be the line number, followed by a colon and a
space, followed by some descriptive text. Suggested messages might include “No statements in
program”, “Missing semicolon”, “Missing identifier after set”, etc.
The result of a successful parse is a parse tree.
Assignment 3 is meant to test that you can properly detect poorly formed programs, and that
you can traverse the parse tree for well formed programs.
If a parse tree has been generated, it should be traversed to perform various tests.
The following information must be printed out for the parse tree:
1. Number of nodes (format is NODE COUNT: N, where N is the count of nodes in the tree)
2. Number of non-leaves (Format is INTERIOR COUNT: N, where N is the number of
nodes that are not leaves)
3. Number of operators (PLUS, MINUS, STAR, SLASH). (Format is OPS COUNT: N)
4. Number of strings (Format is STRING COUNT: N, where N is the number of strings)
5. Max depth of tree (Format is MAX DEPTH: N, where N is the maximum depth of the
tree; the root of the tree is at depth 1)
Any information that has a zero value should be skipped
NOTE that your program might be graded using different input file names and error cases.
SOLVE THE GENERAL PROBLEM and DO NOT HARDCODE output for test cases.
PART 1 due 4/3
PART 2 due 4/10
