CPSC 371 Assignment #3: LR Parsing The Hard Way Due later 1. Do problem 3.13 on page 87 of the text. This will entail that you build the LR(0) (or SLR) state machine, then the LR(1) state machine, and finally merge the states with common lookaheads into an LALR(1) state machine. Be sure to compute (by hand) and write down the FIRST and FOLLOW sets. Draw the state diagrams as well as the corresponding action tables. 2. Write a program that will parse a grammar given an LR action table. Clearly document the data structures you are using to represent the grammar symbols, the production rules, the action table, as well as the symbol-state stack. Demonstrate your program on the tables you created in part 1 of this assignment (not the ones showing conflicts, of course). Your program should produce output not too different from Figure 3.18 on page 58 of your text. That is, it should indicate the current state of the stack, the current position of the symbol scanner, and the action taken at each step. Since the grammar involved in part 1 of this assignment involves only single-character symbols, you might want to first parse a string. (But limit your action table's size to only what's needed.) To be more general, you should use the lexical analyzer you created last week. However, since you need to be able to "look ahead", you should first scan in all the symbols and put them in a linked list. I'll give you some code to start with (for those of you who are rusty with linked lists.) import java_cup.runtime.*; // assume Yylex.next_token() returns a Symbol class symlist // class for a list of Symbols { Symbol head; // symbol contained in this cell symlist tail; // pointer to rest of the list symlist(Symbol h, symlist t) { head = h; tail = t; } void addtoend(Symbol s) // adds a symbol to the end of the list { symlist current = this; while (current.tail != null) current = current.tail; current.tail = new symlist(s,null); } } // ...... static Yylex lexer = new Yylex(System.in); // creates lexer object public symlist makelist(Yylex lexer) // scan in a list of Symbols { Symbol token; symlist SymbolList = new symlist(null,null); // start with dummy list head. try{ do { token = lexer.next_token(); // may need to use "nextToken" instead SymbolList.addtoend(token); // build symbol list. } while (token.sym != sym.EOF); } catch (Exception e) {} return SymbolList.tail; // discard dummy list head. } } ------- I didn't compile this so there might be syntax errors. You probably want to add additional components (or use your own code entirely) depending on how you structure the rest of your program. Remember that the 'sym' field of Symbol contains an integer constant identifying the type of token scanned in.