Programming Assignment 3 CS280 Spring 2018 Part 1 - Due Sunday April 1 at midnight Part 2 - Due Sunday April 8 at midnight ! Using the token definitions from programming assignment 2, we can construct a language with the following grammar rules: ! Prog := Slist Slist := Stmt SC { Slist } Stmt := VarStmt | SetStmt | PrintStmt | RepeatStmt | FuncDef VarStmt := VAR IDENT Expr SetStmt := SET IDENT Expr PrintStmt := PRINT Expr RepeatStmt := REPEAT Expr Stmt Expr := Term { (+|-) Term } Term := Factor { * Factor } Factor := Primary { [ Expr : Expr ] } Primary := IDENT | ICONST | SCONST | LPAREN Expr RPAREN | IDENT LPAREN { ParamList } RPAREN ParamList := IDENT { COMMA ParamList } FuncDef := FUNCTION IDENT LPAREN { ParamList } RPAREN LBRACE { Slist } RETURN IDENT SC RBRACE ! This language will be used for the remainder of the semester. (The grayed out rules are for extra challenge and will not be graded - enter the dragons lair if you dare, muahahaha. If you do try it out, try testing a parameterless function with one print statement first.) ! The following items describe the language. ! i. The language contains two types: integer and string. ii. The language contains 4 operators: +, -, *, and []. All operators are left associative. iii. A VarStmt is a variable declaration and initialization in one statement. The type of the IDENT is determined by the type of the Expr. iv. A SetStmt sets the value of IDENT to the value of Expr. v. A PrintStmt prints the value of the Expr followed by a newline. vi. A RepeatStmt repeats Stmt Expr times. vii. The + and - operators represent addition and subtraction. viii. The * operator represents multiplication. ix. The [ ] operator represents slicing a string. x. It is an error if a variable is used in an Expr before it is declared in a VarStmt. xi. It is an error if the type of a variable does not match the type of Expr in a SetStmt. xii. It is an error if the Expr in a RepeatStmt is not a non-negative integer. xiii. Addition is defined between two integers (the result being the sum) or two strings (the result being the concatenation). xiv. Subtraction is defined between two integers (the result being the difference) or two strings (the result being the removal of the first occurrence of the second string from the first string, or the first string if the second string is not present in the first string). xv. Multiplication is defined for integers (the result being the product) or for an integer and a string (the result being the string repeated integer times). xvi. Slicing is defined as creating a substring of a Primary. The first Expr must be a nonnegative integer. The second Expr must be an integer greater than the first Expr. Slicing returns a new string beginning at the character position of the first Expr and ending before the character position of the second Expr. Character positions begin at 0. xvii. Performing an operation with incorrect types or type combinations is an error. xviii.Multiplying a string by a negative integer is an error. xix. Slicing an integer is an error. xx. Specifying slicing arguments that are outside the range of the string being sliced is an error. xxi. Calling a function that has not been defined is an error xxii. Calling a function with the wrong number of arguments is an error xxiii.Using variables outside of the scope of the function is an error xxiv.Doing anything else with a function, like accessing its value or assigning to it as if its a variable 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. In particular, figuring out what type of value is in a variable is currently impossible, so dont worry about it - that will be Project 4. ! 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. ! You must create a test program (I.e. a main() function) 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 (cin), just like previous projects. 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 file is specified, the program should print TOO MANY FILENAMES, and should then stop. ! The program may accept one optional flag, -t meaning trace. ! 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. Once a parse tree has been generated, it can be traversed to perform various tests. The following information must be printed out for the parse tree: i. Number of leaves (Format is LEAF COUNT: N, where N is the number of leaves) ii. Number of identifiers (Format is IDENT COUNT: N, where N is the number of identifiers) iii. Count of unique identifiers (Format is UNIQUE IDENT COUNT: N) iv. Comma separated list of unique identifiers If there are no identifiers, steps iii and iv are to be skipped ! In addition, if the -t flag is specified, then AFTER the tree is parsed, if a successful tree was generated (meaning if there was no error - if theres an error, theres no tree), then post-traverse the newly-formed tree and print the following: i. When inside a node and if theres a left branch, print l (lowercase ell) and then go down that branch ii. When returning from that branch, print L iii. If theres a right branch, print r before going down that branch iv. When returning from the right side, print R v. Right before returning from the present node, print N vi. There is no l or R when diving into the root node So, for a tree with one node, which has one node on each of its branches, it should print: lNLrNRN And if we were to add a node on the left branch of the left node: llNLNLrNRN ! Assignment 3 is meant to test that you can properly detect poorly formed programs, and that you can traverse well formed programs. ! Part 1 of Assignment 3 tests against badly formed programs and incorrect arguments. ! Part 2 of Assignment 3 tests against well formed programs. ! NOTE that your program will be graded using different input file names and error cases. SOLVE THE GENERAL PROBLEM and DO NOT HARDCODE output for test cases.