This assignment is about the design and implementation of a syntactic analyzer for the language specified by the grammar given below. The syntactic analyzer should use as input the token stream produced by the lexical analyzer that you have produced in assignment #1, and prove whether or not the token stream is a valid program according to the grammar given below. While doing so, it should locate, report, and recover from eventual syntax errors. It should also write to a file a trace of the derivation that is proving that the input token stream can be derived from the starting symbol of the grammar.
The assignment includes two grading source files. These files should be used as-is and not be altered in any way. Completeness of testing is a major grading topic. You are responsible for providing appropriate test cases that test for a wide variety of valid and invalid cases in addition to what is in the grading source files provided.
Grammar
G= (N,T,S,R)
N – Nonterminal Symbols
START, aParams, aParamsTail, addOp, arithExpr, arraySize, assignOp, assignStat, classDecl, expr, fParams, fParamsTail, factor, funcBody, funcDecl, funcDef, funcHead, functionCall, idnest, implDef, indice, memberDecl, multOp, prog, relExpr, returnType, sign, statBlock, statement, structOrImplOrFunc, term, type, varDecl, varDeclOrStat, variable, visibility
T – Terminal Symbols
,, +, -, |, [, intLit, ], =, struct, id, {, }, ;, (, ), floatLit, !, :, void, ., *, /, &, inherits, eq, geq, gt, leq, lt, neq, if, then, else, read, return, while, write, float, integer, private, public, func, impl, let
S – Starting Symbol
START
R – Rules
<START>
<prog> <structOrImplOrFunc> <structDecl> <implDef>
<funcDef> <visibility> <memberDecl> <funcDecl> <funcHead> <funcBody> <varDeclOrStat> <varDecl> <statement>
<assignStat> <statBlock> <expr> <relExpr> <arithExpr> <sign> <term> <factor>
<variable> <functionCall> <idnest>
<indice> <arraySize> <type> <returnType> <fParams> <aParams> <fParamsTail> <aParamsTail> <assignOp> <relOp> <addOp> <multOp>
Notes
::= <prog>
::= {{<structOrImplOrfunc>}}
::= <structDecl> | <implDef> | <funcDef>
::= ‘struct’ ‘id’ [[‘inherits’ ‘id’ {{‘,’ ‘id’}}]] ‘{‘ {{<visibility> <memberDecl>}} ‘}’ ‘;’ ::= ‘impl’ ‘id’ ‘{‘ {{<funcDef>}} ‘}’
::= <funcHead> <funcBody>
::= ‘public’ | ‘private’
::= <funcDecl> | <varDecl>
::= <funcHead> ‘;’
::= ‘func’ ‘id’ ‘(‘ <fParams> ‘)’ ‘->’ <returnType>
::= ‘{‘ {{<varDeclOrStat>}} ‘}’
::= <varDecl> | <statement>
::= ‘let’ ‘id’ ‘:’ <type> {{<arraySize>}} ‘;’
::= <assignStat> ‘;’
| ‘if’ ‘(‘ <relExpr> ‘)’ ‘then’ <statBlock> ‘else’ <statBlock> ‘;’ | ‘while’ ‘(‘ <relExpr> ‘)’ <statBlock> ‘;’
| ‘read’ ‘(‘ <variable> ‘)’ ‘;’
| ‘write’ ‘(‘ <expr> ‘)’ ‘;’
| ‘return’ ‘(‘ <expr> ‘)’ ‘;’
| <functionCall> ‘;’
::= <variable> <assignOp> <expr>
::= ‘{‘ {{<statement>}} ‘}’ | <statement> | EPSILON ::= <arithExpr> | <relExpr>
::= <arithExpr> <relOp> <arithExpr>
::= <arithExpr> <addOp> <term> | <term>
::= ‘+’ | ‘-‘
::= <term> <multOp> <factor> | <factor>
::= <variable>
| <functionCall>
| ‘intLit’ | ‘floatLit’ | ‘(‘ <arithExpr> ‘)’
| ‘not’ <factor>
| <sign> <factor>
::= {{<idnest>}} ‘id’ {{<indice>}}
::= {{<idnest>}} ‘id’ ‘(‘ <aParams> ‘)’ ::= ‘id’ {{<indice>}} ‘.’
| ‘id’ ‘(‘ <aParams> ‘)’ ‘.’ ::= ‘[‘ <arithExpr> ‘]’
::= ‘[‘ ‘intNum’ ‘]’ | ‘[‘ ‘]’ ::= ‘integer’ | ‘float’ | ‘id’ ::= <type> | ‘void’
::= ‘id’ ‘:’ <type> {{<arraySize>}} {{<fParamsTail>}} | EPSILON ::= <expr> {{<aParamsTail>}} | EPSILON
::= ‘,’ ‘id’ ‘:’ <type> {{<arraySize>}}
::= ‘,’ <expr>
::= ‘=’
::= ‘eq’ | ‘neq’ | ‘lt’ | ‘gt’ | ‘leq’ | ‘geq’ ::= ‘+’ | ‘-‘ | ‘or’
::= ‘*’ | ‘/’ | ‘and’
- Terminals (lexical elements, or tokens) are represented in single quotes ‘likeThis’.
- Non-terminals are represented between angle brackets <likeThis>.
- The empty phrase is represented by EPSILON.
- EBNF-style repetition notation is represented using double curly brackets {{like this}}. It represents zero or
more occurrence of the sentential form enclosed in the brackets.
- EBNF-style optionality notation is represented using double square brackets [[like this]]. It represents zero or
one occurrence of the sentential form enclosed in the brackets.
- id follows the specification for program identifiers found in assignment #1.
- intLit, floatLit, follow specification for integer and float literals found in assignment #1
Work to submit
Document
You must provide a short document that includes the following sections:
Section 1.
Section 2. Section 3. Section 4.
Transformed grammar into LL(1) : Remove all the EBNF notations and replace them by right-recursive list-generating productions. Analyze the syntactical definition (using tools) and list in your documentation all the ambiguities and left recursions. Modify the grammar so that the left recursions and ambiguities are removed without modifying the language. Include in your documentation the set of productions that can be parsed using the top-down predictive parsing method, i.e. an LL(1) grammar.
FIRST and FOLLOW sets : Derive the FIRST and FOLLOW sets for each non-terminal in your transformed grammar.
Design : Give a brief overview of the overall structure of your solution, as well as a brief description of the role of each component of your implementation.
Use of tools : Identify all the tools/libraries/techniques that you have used in your analysis or implementation and justify why you have used these particular ones as opposed to others.
Implementation
• Parser : Implement a predictive parser (recursive descent or table-driven) for your modified set of grammar rules.
- The result of the parser should be the creation of a tree data structure representing the parse tree as identified by
the parsing process. This tree will become the intermediate representation used by the two following assignments. When parsing a file named, for example, originalfilename, the parser should write into a file named originalfilename.outderivation the derivation that corresponds to the original program. When syntax errors are found, error messages should be output in a file named originalfilename.outsyntaxerrors.
- Derivationoutput:Yourparsershouldwritetoafiletheleftmostderivationthatprovesthatthesourceprogramcan be derived from the starting symbol. For an example of a derivation, see slide set 3, slide 17.
- Error reporting : The parser should properly identify all the errors in the input program and print a meaningful message to the user for each error encountered. The error messages should be informative on the nature of the errors, as well as the location of the errors in the input file.
- Error recovery : The parser should implement an error recovery method that permits to report all errors present in the source code.
- Test cases : Write a set of source files that enable to test the parser for all syntactical structures involved in the language. Include cases testing for a variety of different errors to demonstrate the accuracy of your error reporting and recovery.
- Driver: Include a driver that parses all your test files. For each test file, the corresponding outsyntaxerrors, and outderivation files should be generated.
Assignment submission requirements and procedure
- Each submitted assignment should contain four components: (1) the source code, (2) a group of test files, (3) a brief report, and (4) an executable named parserdriver, that extracts the tokens from all your test files. For each test file, the corresponding outsyntaxerrors and outderivation files should be generated.
- The assignment statement provides test files (.src) and their corresponding output files.
- The source code should be separated into modules using a comprehensible coding style.
- The assignment should be submitted through moodle in a file named: “A#_student-id” (e.g. A1_1234567, for
Assignment #1, student ID 1234567) and the report must in a PDF format.
- You may use any language you want in the project and assignments but the only fully supported language during
the lab is Java.
- You have to submit your assignment before midnight on the due date on moodle.
- The file submitted must be a .zip file
The marking will be done in a short presentation to the marker. A schedule will be provided to you by email in the days before the due date. You will be given a short time for the presentation, so make sure that you are ready to effectively demonstrate all the elements mentioned in the “Work to submit” section above.
