Programming Assignment 3 Solution

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.




 
The language contains two types: integer and string.




 
All operators are left associative.




 
An IfStmt evaluates the Expr. The expr must evaluate to an integer. If the integer is nonzero, then the Stmt is executed.




 
A PrintStmt evaluates the Expr and prints its value.




 
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.

 
The type of an IDENT is the type of the value assigned to it.




 
The PLUS and MINUS operators in Expr represent addition and subtraction.




 
The STAR and SLASH operators in Prod represents multiplication and division.




 
It is an error if a variable is used before a value is assigned to it.




 
Addition is defined between two integers (the result being the sum) or two strings (the result being the concatenation).




 
Subtraction is defined between two integers (the result being the difference).




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




 
Division is defined between two integers




 
Performing an operation with incorrect types or type combinations is an error.




 
Multiplying a string by a negative integer is an error.




 
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:




 
Number of nodes (format is NODE COUNT: N, where N is the count of nodes in the tree)




 
Number of non-leaves (Format is INTERIOR COUNT: N, where N is the number of nodes that are not leaves)




 
Number of operators (PLUS, MINUS, STAR, SLASH). (Format is OPS COUNT: N)




 
Number of strings (Format is STRING COUNT: N, where N is the number of strings)




 
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