CISC 672 Advanced Compiler Construction Fall 2009Phase II: The ParserFirst Due Date: (Grammar) October 14th.Second Due Date: (Complete) October 21st.Teamwork: Highly encouraged.1 OverviewThis project is intended to give you experience in using a parser generator, namely JavaCup, and tobring together the various issues of syntax specification, parsing, and abstract syntax tree constructiondiscussed in class.In this assignment you will write a parser for Cool. The assignment makes use of two tools: theparser generator (CUP) and a package for manipulating trees. The output of your parser will be anabstract syntax tree (AST). You will construct this AST using semantic actions of the parser generator.You certainly will need to refer to the syntactic structure of Cool, found in Figure 1 of the Coolmanual, as well as other portions of the reference manual. There is a lot of information in this handout,and you need to know most of it to write a working parser. Please read the handout thoroughly.2 TeamworkYou are encouraged (although not required) to try to find a partner to do this project with. This willimprove your team-skills and you will likely get done faster. Once you have a partner, both you andyour partner should tell the TA who they are. The TA will then enable both of you to see each other’sfolders. Choose one of your folders to work with. SVN is a good way to share source files in a team andto keep each other updated on the changes made. Furthermore, many svn-clients provide tools to resolveconflicts of changes made to a particular file efficiently.Teams are to be established for each phase separately. If you want to continue working in your team,please anounce this to the TA after submission of this phase. In the case that your team breaks up beforefinishing the assignment, each of you will be required to submit a completed assignment (in this case,your code is obviously allowed to be very similar). Extensions of the deadline(s) may be given if youprovide good reasons for breaking up with your partner.3 Tasks1. Read the Java CUP specification manual at http://www2.cs.tum.edu/projects/cup/manual.html2. Read Section 11 in the Cool-Manual.3. The file parser/cool.cup contains a start towards a parser description for Cool. You will need to addmore rules. The declaration section is mostly complete; all you need to do is add type declarationsfor new nonterminals. (We have given you names and type declarations for the terminals.) The rulesection is very incomplete.4. Make yourself familiar with the different classes derived from TreeNode (they are all in treeNodespackage). Objects of these classes will be the nodes of the AST that you are asked to create.page 1 of 3CISC 672 Advanced Compiler Construction Fall 20095. As usual, the file README Phase2.txt contains detailed instructions for the assignment. You shouldalso edit this file to include the write-up for your project. Explain your design decisions and why youbelieve your program is correct and robust. It is part of the assignment to explain things in text, aswell as to comment your code.4 Parser OutputYour semantic actions should build an AST. The root (and only the root) of the AST should be of typeprogram. For programs that parse successfully, the output of parser is a listing of the AST.For programs that have errors, the output is the error messages of the parser. We have supplied youwith an error reporting routine that prints error messages in a standard format; please do not modify it.You should not invoke this routing directly in the semantic actions; CUP automatically invokes it when aproblem is detected.Your parser need only work for programs contained in a single file – don’t worry about compilingmultiple files.5 Error HandlingYou should use the error pseudo-nonterminal to add error handling capabilities in the parser. Thepurpose of error is to permit the parser to continue after some anticipated error. It is not a panaceaand the parser may become completely confused. See the CUP documentation for how best to use error.In your README, describe which errors you attempt to catch. To receive full credit, your parser shouldrecover in at least the following situations:• If there is an error in a class definition but the class is terminated properly and the next class issyntactically correct, the parser should be able to restart at the next class definition.• Similarly, the parser should recover from errors in features (going on to the next feature), a let binding(going on to the next variable), and an expression inside a {...} block.Do not be overly concerned about the the line numbers that appear in the error messages your parsergenerates. If your parser is working correctly, the line number will generally be the line where the erroroccurred. For erroneous constructs broken across multiple lines, the line number will probably be thelast line of the construct.6 Notes• You may use precedence declarations, but only for expressions. Do not use precedence declarationsblindly (i.e. do not respond to a shift-reduce conflict in your grammar by adding precedence rules untilit goes away). If you find yourself making up rules for many things other than operators in expressionsand for let, you are probably doing something wrong.• The Cool let construct introduces an ambiguity into the language (try to construct an example if youare not convinced). The manual resolves the ambiguity by saying that a let expression extends as farto the right as possible. The ambiguity will show up in your parser as a shift-reduce conflict involvingthe productions for let.page 2 of 3CISC 672 Advanced Compiler Construction Fall 2009This problem has a simple, but slightly obscure, solution. We will not tell you exactly how to solve it,but we will give you a strong hint. In coolc, we implemented the resolution of the let shift-reduceconflict by using a CUP feature that allows precedence to be associated with productions (not justoperators). See the CUP documentation for information on how to use this feature.• You must declare CUP “types” for your non-terminals and terminals that have attributes. For example,in the skeleton cool.cup is the declaration:nonterminal Program program;This declaration says that the non-terminal program has type Program.It is critical that you declare the correct types for the attributes of grammar symbols; failure to doso virtually guarantees that your parser won’t work. You do not need to declare types for