The specification for the syntactic analysis of the language is shown with the productions below in EBNF syntax.

An EBNF grammar can be converted to a BNF grammar by applying the following rules:

• For every instance of {X}, extract it to a new nonterminal Y and add the production Y → Y X | ε.
• For every instance of [X], extract it to a new nonterminal Y and add the production Y → X | ε.
• For every instance of (X), extract it to a new nonterminal Y and add the production Y → X.

The syntactic language specification in EBNF format was converted to a BNF grammar shown below.

An AtoCC-compatible text format of the above grammar (with renamed variables) is shown below:

prog -> classDeclRecursion funcDefRecursion 'program' funcBody ';'
classDeclRecursion -> classDeclRecursion classDecl | EPSILON
classDecl -> 'class' 'id' optionalInheritance '{' varDeclRecursion funcDeclRecursion '}' ';'
optionalInheritance -> ':' 'id' multipleSuperClasses | EPSILON
multipleSuperClasses -> multipleSuperClasses ',' 'id' | EPSILON
funcDeclRecursion -> funcDeclRecursion funcDecl | EPSILON
funcDecl -> type 'id' '(' fParams ')' ';'
funcHead -> type optionalNamespace 'id' '(' fParams ')'
optionalNamespace ->  'id' '::' | EPSILON
funcDefRecursion -> funcDefRecursion funcDef | EPSILON
funcDef -> funcHead funcBody ';'
funcBody -> '{' varDeclRecursion statementRecursion '}'
varDeclRecursion -> varDeclRecursion varDecl | EPSILON
varDecl -> type 'id' arraySizeRecursion ';'
statementRecursion -> statementRecursion statement | EPSILON
statement -> assignStat | 'if' '(' expr ')' 'then' statBlock 'else' statBlock ';' | 'for' '(' type 'id' assignOp expr ';' relExpr ';' assignStat  ')' statBlock ';' | 'get' '(' variable ')' ';' | 'put' '(' expr ')' ';' | 'return' '(' expr ')' ';'
assignStat -> variable assignOp expr
statBlock -> '{' statementRecursion '}' | statement | EPSILON
expr -> arithExpr | relExpr
relExpr -> arithExpr relOp arithExpr
arithExpr -> arithExpr addOp term | term
sign -> '+' | '-'
term -> term multOp factor | factor
factor -> variable | functionCall | 'intNum' | 'floatNum' | '(' arithExpr ')' | negationOperator factor | sign factor
negationOperator -> 'not' | '!'
variable -> idnestRecursion 'id' indiceRecursion
functionCall -> idnestRecursion 'id' '(' aParams ')'
idnestRecursion -> idnestRecursion idnest | EPSILON
idnest -> 'id' indiceRecursion '.' | 'id' '(' aParams ')' '.'
indiceRecursion -> indiceRecursion indice | EPSILON
indice -> '[' arithExpr ']'
arraySizeRecursion -> arraySizeRecursion arraySize | EPSILON
arraySize -> '[' 'intNum' ']'
type -> 'int' | 'float' | 'id'
fParams -> type 'id' arraySizeRecursion fParamsTailRecursion | EPSILON
aParams -> expr aParamsTailRecursion | EPSILON
fParamsTailRecursion -> fParamsTailRecursion fParamsTail | EPSILON
fParamsTail -> ',' type 'id' arraySizeRecursion
aParamsTailRecursion -> aParamsTailRecursion aParamsTail | EPSILON
aParamsTail -> ',' expr
assignOp -> '='
relOp -> '==' | '<>' | '<' | '>' | '<=' | '>='
addOp -> '+' | '-' | 'or' | '¦¦'
multOp -> '*' | '/' | 'and' | '&&'

Left factoring is a technique used in predictive top-down parsers avoid the need for backtracking or lookaheads during parsing, such as is done in recursive descent. It involves the removal of any common left factor (terminal or non-terminal) that appears in a production with an or clause (|), or effectively two productions of the same non-terminal. Performing left factoring means that at a given non-terminal, there is a clear deterministic choice of which production to proceed towards.

Left recursion is avoided in recursive descent and predictive parsing strategies due to the possibility of an infinite loop, resulting in the compiler never terminating and with no progress.

Left-recursive productions can be replaced with right-recursive productions by applying the following rules:

For any production with the general form...

S → Sα₁ | ... | Sα_n | β₁ | ... | β_m

... replace with two productions:

S → β₁ T | ... | β_m T
T → α₁ T | ... | α₁ T | ε

This technique needs to be applied and the condition must hold for all non-terminal substitutions (one derivation step of a production).

Ambiguity in context-free grammars means that it can result in multiple possible derivations or parse trees. This is undesirable as we want our compiler to reliably generate the same parse tree given the same input program.

Using an LL(1) grammar for a syntactic analysis is attractive given that LL(1) grammars are known to be unambigiuous. Converting a grammar to LL(1) is an effective technique for dealing with ambiguities in general, giving that determining if an arbitrary grammar is ambiguous is an undecidable problem.

An attempt to use the following left-factoring online tool, left-recusion elimination online tool and CFG-to-LL(k) online tool was done. However, these tools were error-prone, and superior results were obtained by manipulating the grammar by hand while verifying with the AtoCC kfGEdit tool along the way.

Ultimately, too many changes were made to the grammar to describe every ambiguity, left factoring or left-recursion elimination. The resulting grammar is shown below in an AtoCC-compatible format (with renamed non-terminal symbols to more accurately represent their role).

Program                                             -> ClassDeclarationRecursion FunctionDefinitionRecursion program FunctionBody ;
AdditiveOperator                                    -> +
AdditiveOperator                                    -> -
AdditiveOperator                                    -> or
AdditiveOperator                                    -> ¦¦
ArithmeticExpression                                -> Term ArithmeticExpressionTail
ArithmeticExpressionTail                            -> AdditiveOperator Term ArithmeticExpressionTail
ArithmeticExpressionTail                            -> EPSILON
ArithmeticOrRelationalExpression                    -> RelationalOperator ArithmeticExpression
ArithmeticOrRelationalExpression                    -> EPSILON
ArraySize                                           -> [ intNum ]
ArraySizeRecursion                                  -> ArraySize ArraySizeRecursion
ArraySizeRecursion                                  -> EPSILON
AssignmentStatement                                 -> Variable = Expression
ClassDeclaration                                    -> class id OptionalInheritanceList { VariableThenFunctionDeclarationRecursion } ;
ClassDeclarationRecursion                           -> ClassDeclaration ClassDeclarationRecursion
ClassDeclarationRecursion                           -> EPSILON
Expression                                          -> ArithmeticExpression ArithmeticOrRelationalExpression
Factor                                              -> ( ArithmeticExpression )
Factor                                              -> FunctionCallOrVariable
Factor                                              -> NegationOperator Factor
Factor                                              -> NumberSign Factor
Factor                                              -> floatNum
Factor                                              -> intNum
FunctionArguments                                   -> Expression FunctionArgumentsTailRecursion
FunctionArguments                                   -> EPSILON
FunctionArgumentsTail                               -> , Expression
FunctionArgumentsTailRecursion                      -> FunctionArgumentsTail FunctionArgumentsTailRecursion
FunctionArgumentsTailRecursion                      -> EPSILON
FunctionBody                                        -> { VariableDeclarationRecursionThenStatementRecursionA }
FunctionCallOrVariable                              -> id FunctionCallOrVariableTail
FunctionCallOrVariableTail                          -> FunctionCallParensOrIndexing FunctionCallOrVariableTailRecursion
FunctionCallOrVariableTailRecursion                 -> . id FunctionCallOrVariableTail
FunctionCallOrVariableTailRecursion                 -> EPSILON
FunctionCallParensOrIndexing                        -> ( FunctionArguments )
FunctionCallParensOrIndexing                        -> IndexingRecursion
FunctionDeclarationRecursionStart                   -> Type id FunctionDeclarationRecursionTail
FunctionDeclarationRecursionStart                   -> EPSILON
FunctionDeclarationRecursionTail                    -> ( FunctionParameters ) ; FunctionDeclarationRecursionStart
FunctionDefinition                                  -> FunctionHeader FunctionBody ;
FunctionDefinitionRecursion                         -> FunctionDefinition FunctionDefinitionRecursion
FunctionDefinitionRecursion                         -> EPSILON
FunctionHeader                                      -> Type OptionalNamespacing ( FunctionParameters )
FunctionParameters                                  -> Type id ArraySizeRecursion FunctionParametersTailRecursion
FunctionParameters                                  -> EPSILON
FunctionParametersTail                              -> , Type id ArraySizeRecursion
FunctionParametersTailRecursion                     -> FunctionParametersTail FunctionParametersTailRecursion
FunctionParametersTailRecursion                     -> EPSILON
IdListRecursion                                     -> , id IdListRecursion
IdListRecursion                                     -> EPSILON
Indexing                                            -> [ ArithmeticExpression ]
IndexingRecursion                                   -> Indexing IndexingRecursion
IndexingRecursion                                   -> EPSILON
MultiplicativeOperator                              -> &&
MultiplicativeOperator                              -> *
MultiplicativeOperator                              -> /
MultiplicativeOperator                              -> and
NegationOperator                                    -> !
NegationOperator                                    -> not
NumberSign                                          -> +
NumberSign                                          -> -
NumberType                                          -> float
NumberType                                          -> int
OptionalInheritanceList                             -> : id IdListRecursion
OptionalInheritanceList                             -> EPSILON
OptionalNamespacing                                 -> id OptionalNamespacingTail
OptionalNamespacingTail                             -> :: id
OptionalNamespacingTail                             -> EPSILON
RelationalExpression                                -> ArithmeticExpression RelationalOperator ArithmeticExpression
RelationalOperator                                  -> <>
RelationalOperator                                  -> <
RelationalOperator                                  -> <=
RelationalOperator                                  -> ==
RelationalOperator                                  -> >
RelationalOperator                                  -> >=
Statement                                           -> AssignmentStatement ;
Statement                                           -> StatementWithoutAssignment
StatementBlock                                      -> Statement
StatementBlock                                      -> EPSILON
StatementBlock                                      -> { StatementRecursion }
StatementRecursion                                  -> Statement StatementRecursion
StatementRecursion                                  -> EPSILON
StatementWithoutAssignment                          -> for ( Type id = Expression ; RelationalExpression ; AssignmentStatement ) StatementBlock ;
StatementWithoutAssignment                          -> get ( Variable ) ;
StatementWithoutAssignment                          -> if ( Expression ) then StatementBlock else StatementBlock ;
StatementWithoutAssignment                          -> put ( Expression ) ;
StatementWithoutAssignment                          -> return ( Expression ) ;
Term                                                -> Factor TermRecursion
TermRecursion                                       -> MultiplicativeOperator Factor TermRecursion
TermRecursion                                       -> EPSILON
Type                                                -> NumberType
Type                                                -> id
Variable                                            -> id VariableTail
VariableDeclarationRecursionThenStatementRecursionA -> NumberType id ArraySizeRecursion ; VariableDeclarationRecursionThenStatementRecursionA
VariableDeclarationRecursionThenStatementRecursionA -> EPSILON
VariableDeclarationRecursionThenStatementRecursionA -> StatementWithoutAssignment StatementRecursion
VariableDeclarationRecursionThenStatementRecursionA -> id VariableDeclarationRecursionThenStatementRecursionB
VariableDeclarationRecursionThenStatementRecursionB -> VariableTail = Expression ; StatementRecursion
VariableDeclarationRecursionThenStatementRecursionB -> id ArraySizeRecursion ; VariableDeclarationRecursionThenStatementRecursionA
VariableTail                                        -> ( FunctionArguments ) . id VariableTail
VariableTail                                        -> IndexingRecursion VariableTailTail
VariableTailTail                                    -> . id VariableTail
VariableTailTail                                    -> EPSILON
VariableThenFunctionDeclarationRecursion            -> Type id VariableThenFunctionDeclarationRecursionTail
VariableThenFunctionDeclarationRecursion            -> EPSILON
VariableThenFunctionDeclarationRecursionTail        -> ArraySizeRecursion ; VariableThenFunctionDeclarationRecursion
VariableThenFunctionDeclarationRecursionTail        -> FunctionDeclarationRecursionTail

The AtoCC kfG Edit tool confirms that the above grammar is LL(1).

A parsing table must be constructed from the above grammar in order to represent the grammar during predictive parsing. The information below was generated automatically using an online tool.

The fact that there was at most one production in each table cell further reinforces the fact that the grammar is LL(1).

The columns of the parsing table below represent the list of possible next input tokens.

The rows represent the current leftmost nonterminal in the parse tree.

Every table cell maps the indicates how the current non-terminal should be expanded based on the next input token. The numbers correspond to the rows of entries in the above prediction table, where the production right-hand side expression would be used to expand the current non-terminal.

• Identifier (id)
• Keyword (program)
• Keyword (class)
• Keyword (if)
• Keyword (then)
• Keyword (for)
• Keyword (get)
• Keyword (put)
• Keyword (return)
• Keyword (float)
• Keyword (int)
• Semicolon (;)
• OpenCurlyBrace ({)
• CloseCurlyBrace (})
• InheritanceOperator (:)
• Comma (,)
• OpenParens (()
• CloseParens ())
• ScopeResolutionOperator (::)
• AssignmentOperator (=)
• RelationalOperator
• MathOperator (+)
• MathOperator (-)
• MathOperator (*)
• MathOperator (/)
• BinaryLogicalOperator (or)
• BinaryLogicalOperator (||)
• BinaryLogicalOperator (and)
• BinaryLogicalOperator (&&)
• UnaryLogicalOperator (not)
• UnaryLogicalOperator (!)
• Integer
• Float
• OpenSquareBracket ([)
• CloseSquareBracket (])
• AccessorOperator (.)