[Solved] Homework Assignment 2: Parser (First Version) Solution

5/5 – (1 vote)

In this assignment, you are going to implement a first version of a top-down parser for the language, miniJava. In this version, the parser performs only one task — validating the syntax of the input program. It does not generate a parse tree or any other form of program representation. For a syntactically correct inputprogram, the parser simply prints out a message “Program’s syntax is valid.” For any program containing syntax errors, the parser detects and reports the nature and location of the first error. Your parser is to be implemented with the parser-generator, JavaCC.PreparationDownload a copy of “hw2.zip” from D2L. After unzipping, you should see a hw2 directory with thefollowing items:– hw2.pdf — this document– mjRawGrammar.pdf — miniJava’s raw grammar– mjRawGrammar.jj — a JavaCC program based on the raw grammar (It would not compile!)– Makefile — for building the parser– runp0 — a script for running your parser with tests– tst/ — a directory containing sample miniJava programsRaw Grammar vs LL GrammarA version of the miniJava language’s grammar is included in the zip file. This grammar is targeted for people. It is called a “raw” grammar, since it needs to be refined to be suitable for compilers to use.A section of this raw grammar is shown below:Expr – Expr BinOp Expr| UnOp Expr| “(” Expr “)”| ExtId “(” [Args] “)” // method call| Lvalue| LiteralLvalue – ExtId “[” Expr “]” // array element| ExtIdExtId – [“this” “.”] <ID {“.” <ID} // object field or just IDIt describes the expression syntax of the language. People can understand it. But to a compiler, this grammar is ambiguous, has left-recursions, and has productions with common-prefix (of unbounded length).

A direct implementation of this grammar would not work. (A JavaCC program based on this version is included in the zip file. You can try to compile it yourself to see what happens.) It needs to be converted into an LL form before a top-down parser can be developed.