COMP442_6421-Syntactic Analyzer Solved

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> 

<prog>               ::= {{<structOrImplOrfunc>}}  

<structOrImplOrFunc> ::= <structDecl> | <implDef> | <funcDef>    

<structDecl>         ::= 'struct' 'id' [['inherits' 'id' {{',' 'id'}}]] '{' {{<visibility> <memberDecl>}} '}' ';' <implDef>            ::= 'impl' 'id' '{' {{<funcDef>}} '}' 

<funcDef>            ::= <funcHead> <funcBody>  

<visibility>         ::= 'public' | 'private'  

<memberDecl>         ::= <funcDecl> | <varDecl>   

<funcDecl>           ::= <funcHead> ';'  

<funcHead>           ::= 'func' 'id' '(' <fParams> ')' '->' <returnType>  <funcBody>           ::= '{' {{<varDeclOrStat>}} '}' 

<varDeclOrStat>      ::= <varDecl> | <statement> 

<varDecl>            ::= 'let' 'id' ':' <type> {{<arraySize>}} ';' 

<statement>          ::= <assignStat> ';' 

                      |  'if'     '(' <relExpr> ')' 'then' <statBlock> 'else' <statBlock> ';' 

                      |  'while'  '(' <relExpr> ')' <statBlock> ';'                       |  'read'   '(' <variable> ')' ';' 

                      |  'write'  '(' <expr> ')' ';' 

                      |  'return' '(' <expr> ')' ';' 

                      |  <functionCall> ';' 

<assignStat>         ::= <variable> <assignOp> <expr> 

<statBlock>          ::= '{' {{<statement>}} '}' | <statement> | EPSILON   

<expr>               ::= <arithExpr> | <relExpr> 

<relExpr>            ::= <arithExpr> <relOp> <arithExpr> 

<arithExpr>          ::= <arithExpr> <addOp> <term> | <term>  

<sign>               ::= '+' | '-' 

<term>               ::= <term> <multOp> <factor> | <factor> 

<factor>             ::= <variable> 

                      |  <functionCall> 

                      |  'intLit' | 'floatLit' 

                      |  '(' <arithExpr> ')' 

                      |  'not' <factor> 

                      |  <sign> <factor> 

<variable>           ::= {{<idnest>}} 'id' {{<indice>}} 

<functionCall>       ::= {{<idnest>}} 'id' '(' <aParams> ')' 

<idnest>             ::= 'id' {{<indice>}} '.' 

                      |  'id' '(' <aParams> ')' '.' <indice>             ::= '[' <arithExpr> ']' 

<arraySize>          ::= '[' 'intNum' ']' | '[' ']' 

<type>               ::= 'integer' | 'float' | 'id' 

<returnType>         ::= <type> |  'void' 

<fParams>            ::= 'id' ':' <type> {{<arraySize>}} {{<fParamsTail>}} | EPSILON   

<aParams>            ::= <expr> {{<aParamsTail>}} | EPSILON  <fParamsTail>        ::= ',' 'id' ':' <type> {{<arraySize>}} <aParamsTail>        ::= ',' <expr> 

<assignOp>           ::= '=' 

<relOp>              ::= 'eq' | 'neq' | 'lt' | 'gt' | 'leq' | 'geq'  <addOp>              ::= '+' | '-' | 'or'  

<multOp>             ::= '*' | '/' | 'and'  

Notes
 

•   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