CPS 140 Project 2 Spring 2002Project Due: Thursday, March 28, 11pm30 pointsThe purpose of this assignment is to write a parser for the ROBOGO programming language (seethe project 1 handout for a description of the tokens in the ROBOGO programming language).Your program will read in a data file containing a ROBOGO program, and will determine if it is asyntactically correct ROBOGO program using an LR(1) parser. In project 3 you will continue tobuild on this project, writing an interpretor.The ROBOGO programming language has a program definition (shown first) and five types ofstatements:StatementMeaningbegin ijstmts halt program definition - defines startingposition of robot at point (i,j)robot vab; draw a robot v at position (a, b)obstacle ab; draw an obstacle at position (a, b)add a to v ; add statementmove vda; move the robot v, a spaces in direction dv = a ; an assignment statementdo Execute stmts,ifa≤bthen repeatstmtsuntil a>b;where v is a variable, a and b are either variables or integers, i and j are integers, d is a direction(north, south, east or west) and stmts represents 1 or more valid statements.CFG for the ROBOGO Programming Language(1) <Program> → begin int int <List> halt(2) <List> → <Statement> ;(3) <List> → <List><Statement> ;(4) <Statement> → robot var <Type><Type>(5) <Statement> → obstacle <Type><Type>(6) <Statement> → move var <Direction><Type>(7) <Statement> → add <Type> to var(8) <Statement> → var = <Type>(9) <Statement> → do <List> until <Type>><Type>(10) <Type> → var(11) <Type> → int(12) <Direction> → north(13) <Direction> → south(14) <Direction> → east(15) <Direction> → west1where “var” represents a variable and “int” represents an integer. The productions are numbered.DESCRIPTION OF YOUR PROGRAMGiven a ROBOGO program, your task is to 1) scan the program and identify all its parts (or tokens)and 2) parse the program using an LR parser and identify if it is syntactically correct. If it is, thenproduce a list of rules starting with the start symbol that will produce a rightmost derivation ofthe program.Part 1 - The ScannerThe purpose of the scanner is to find the next token in your program, enter its value into a symboltable (a data structure that handles searches and insertions), and return 1) the location of thetokens value in symbol table, and 2) a unique symbol, called the token type, which indicates thetype of the token. If a value already exists in the symbol table, don’t reenter it. This part wasdone in Project 1.Part 2 - The ParserYou are to write an LR(1) parser to produce rightmost derivations of ROBOGO programs. Theparser (called the driver routine in project 1) will call the scanner whenever it needs the next tokenin the ROBOGO program. The token type will be shifted onto the LR parsing stack. The locationof the token’s value in the symbol table will be ignored for now. It will be used in project 3.An LR(1) Parse Table for the ROBOGO programming language is attached to this handout. Theparse table can be stored as a two-dimensional array. The columns are labeled by symbols inthe grammar (both terminals and nonterminals) and an end-of-string marker ($) (in this case, theend-of-string marker represents the end of a ROBOGO program or end-of-file marker). The rowsrepresent the state numbers from a transition diagram that models the LR(1) parsing process. Eachentry in the array represents one of four actions. There may be additional information stored inthe entry.Actions:• ERROR - The ROBOGO program is not syntactically correct.• ACCEPT - The ROBOGO program is syntactically correct.• SHIFT - Shift the input symbol (lookahead) and state number onto the stack. A state numbermust be stored in this array entry.• REDUCE - Replace the righthand side (rhs) of the rewrite rule that is on top of the stackwith its lefthand side (lhs). You might want to store some representation of the rule in thisarray entry.The file ∼rodger/cps140/robogo/parsedata contains the data file to create the LR(1) ParseTable in this handout. You may read in this file in front of a ROBOGO program to create the dataentries in the parse table. The format of the file is: 1 row of headers for the terminals, 41 rows ofentries, 1 row of headers for the variables, and 41 rows of entries. Each row in the table first hasthe number of the row, except the header rows, which have no entry. Items are separated by “&”.If there is no entry in a column, then there will be two adjacent &’s.An LR(1) parser when applied to a string in the language it represents will produce a rightmostderivation (in reverse order) of the string. In order to list the rules in the order they would2be used in a rightmost derivation (starting with the start symbol), the rules must be stacked.Whenever a REDUCE action is encountered in the parse table, store the rule on a rule stack (thisis a different stack than the parsing stack). When the starting rule is encountered, print all the ruleson the stack. Thus, for each ROBOGO program that is syntactically correct, print the productionrules that would derive the ROBOGO program. Whenever there is an error, you do not need toshow the rules encountered, but you can if you want.The parsing routine accesses a parser stack. Terminals and variables from the grammar, and statenumbers can appear on this stack.Consider the following ROBOGO program.∗− program 1 −∗begin 100 80robot bob 10 9 ;move bob east 6 ;haltThis ROBOGO program can be derived by applying the following production rules (using the firstletterofeachvariable):RULES DERIVATIONP → begin int int L halt begin 100 80 L haltL → L S ; begin 100 80 L S ; haltS → move var D T begin 100 80 L move bob D T ; haltT → int begin 100 80 L move bob D 6 ; haltD → east begin 100 80 L move bob east 6 ; haltL → S ; begin 100 80 S ; move bob east 6 ; haltS → robot var T T begin 100 80 robot bob T T ; move bob east 6 ; haltT → int begin 100 80 robot bob T 9 ; move bob east 6 ; haltT → int begin 100 80 robot bob 10 9 ; move bob east 6 ; haltNote: An LR parser will generate these rules in reverse order.INPUT:The format of the data file is the same as it was in project 1.A data file consists of one ROBOGO program. You may assume that ROBOGO programs con-tain valid tokens and that there are not more than 80 characters on a line. Sample data files∼rodger/cps140/robogo/pX.t (where X=1,2,3,...) are available. These are not necessarily thedata files that your program