design and implement a syntax analyzer for the language specified by the grammar specified on the next page.

Deliverables:

Documentation

$1.$ Transformed Grammar into LL$(1)$:

$1\mathrm{.}1.$ Remove all the EBNF notations and replace them by right$-$recursive list$-$generating productions.

$1\mathrm{.}2.$ Analyze the syntactical definition. List in your documentation all the ambiguities and left recursions or any error you may have found in the grammar.

$1\mathrm{.}3.$ Modify the productions so that the left recursions and ambiguities are removed without modifying the language.

$1\mathrm{.}4.$ 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.

$2.$ FIRST and FOLLOW sets:

$2\mathrm{.}1.$ Derive the FIRST and FOLLOW sets for each non$-$terminal in your transformed grammar.

$3.$ Design:

$3\mathrm{.}1.$ 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.

$4.$ Implementation Tools:

$4\mathrm{.}1.$ 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.

$$ Derivation Output: Your parser should write to a file the derivation that proves that the source program can be derived from the starting symbol.

$$ Error$-$Reporting: Parser should properly identify all 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 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.

$$ Note that the grammar analysis$/$transformation process can be greatly simplified by the use of tools such as the kfgEdit AtoCC tool.

Grammar:

The syntactical definition is using the following conventions:

$$ Terminals $($lexical elements, or tokens$)$ are represented in single quotes 'thisWay'.

$$ Non$-$terminals are represented in italics, thisWay.

$$ The empty phrase is represented by EPSILON.

$$ EBNF$-$style repetition notation is represented using curly brackets $\{$This way$\}.$ It represents zero or more occurrence of the sentential form enclosed in the brackets.

$$ EBNF$-$style optionality notation is represented using square brackets $[$This way$].$ It represents zero or one occurrence of the sentential form enclosed in the brackets.

$$ The non$-$terminal is the starting symbol of the grammar.

Except from the EBNF constructs, the grammar is expressed using the syntax used by the kfgEdit AtoCC toolkit application.

prog $->\{$classDecl$\}\{$funcDef$\}$ 'main' funcBody $\text{'}$;$\text{'}$

classDecl $->$ 'class' $\text{'}$id$\text{'}[\text{'}$:$\text{'}\text{'}$id$\text{'}\{\text{'},\text{'}\text{'}$id$\text{'}\}]\text{'}\{\text{'}\{$varDecl$\}\{$funcDecl$\}\text{'}\}\text{'}\text{'}$;$\text{'}$

funcDecl $->$ type $\text{'}$id$\text{'}\text{'}(\text{'}$ fParams $\text{'})\text{'}\text{'}$;$\text{'}$

funcHead $->$ type $[\text{'}$id$\text{'}\text{'}$sr$\text{'}]\text{'}$id$\text{'}\text{'}(\text{'}$ fParams $\text{'})\text{'}$

funcDef $->$ funcHead funcBody $\text{'}$;$\text{'}$

funcBody $->\text{'}\{\text{'}\{$varDecl$\}\{$statement$\}\text{'}\}\text{'}$

varDecl $->$ type $\text{'}$id$\text{'}\{$arraySize$\}\text{'}$;$\text{'}$

statement $->$ assignStat $\text{'}$;$\text{'}$

$|\text{'}$if$\text{'}\text{'}(\text{'}$ expr $\text{'})\text{'}$ 'then' statBlock 'else' statBlock $\text{'}$;$\text{'}$

$|$ 'for' $\text{'}(\text{'}$ type $\text{'}$id$\text{'}$ assignOp expr $\text{'}$;$\text{'}$ relExpr $\text{'}$;$\text{'}$ assignStat $\text{'})\text{'}$ statBlock $\text{'}$;$\text{'}$

$|$ 'read' $\text{'}(\text{'}$ variable $\text{'})\text{'}\text{'}$;$\text{'}$

$|$ 'write' $\text{'}(\text{'}$ expr $\text{'})\text{'}\text{'}$;$\text{'}$

$|$ 'return' $\text{'}(\text{'}$ expr $\text{'})\text{'}\text{'}$;$\text{'}$

assignStat $->$ variable assignOp expr

statBlock $->\text{'}\{\text{'}\{$statement$\}\text{'}\}\text{'}|$ statement $|$ EPSILON

expr $->$ arithExpr $|$ relExpr

relExpr $->$ arithExpr relOp arithExpr

arithExpr $->$ arithExpr addOp term $|$ term

sign $->\text{'}+\text{'}|\text{'}-\text{'}$

term $->$ term multOp factor $|$ factor

factor $->$ variable

$|$ functionCall

$|$ 'intNum' $|$ 'floatNum'

$|\text{'}(\text{'}$ arithExpr $\text{'})\text{'}$

$|$ 'not' factor

$|$ sign factor

variable $->\{$idnest$\}\text{'}$id$\text{'}\{$indice$\}$

functionCall $->\{$idnest$\}\text{'}$id$\text{'}\text{'}(\text{'}$ aParams $\text{'})\text{'}$

idnest $->\text{'}$id$\text{'}\{$indice$\}\text{'}.\text{'}$

$|\text{'}$id$\text{'}\text{'}(\text{'}$ aParams $\text{'})\text{'}\text{'}.\text{'}$

indice $->\text{'}[\text{'}$ arithExpr $\text{'}]\text{'}$

arraySize $->\text{'}[\text{'}$ 'intNum' $\text{'}]\text{'}$

type $->$ 'integer' $|$ 'float' $|\text{'}$id$\text{'}$

fParams $->$ type $\text{'}$id$\text{'}\{$arraySize$\}\{$fParamsTail$\}|$ EPSILON

aParams $->$ expr $\{$aParamsTail$\}|$ EPSILON

fParamsTail $->\text{'},\text{'}$ type $\text{'}$id$\text{'}\{$arraySize$\}$

aParamsTail $->\text{'},\text{'}$ expr

assignOp $->\text{'}=\text{'}$

relOp $->\text{'}$eq$\text{'}|$ 'neq' $|\text{'}$lt$\text{'}|\text{'}$gt$\text{'}|$ 'leq' $|$ 'geq'

addOp $->\text{'}+\text{'}|\text{'}-\text{'}|\text{'}$or$\text{'}$

multOp $->\text{'}*\text{'}|\text{'}/\text{'}|$ 'and'

Tokens

Keywords: main $|$ class $|$

if $|$ then $|$ else $|$ for $|$ read $|$ write $|$ return $|$

integer $|$ float

Operators: eq $(==)$