crs is a compiler implemented in Rust for a C++-like language, built for the COMP 422 - Compiler Design course at Concordia University. Here's a sample program.

The nightly build of the Rust programming language is required to compile this project.

First, install rustup and then run rustup default nightly.

You can compile and run the entire project with the following command:

cargo run -- tests/lexer/source_example.crs

The compiler documentation can be read as Markdown parsed by GitHub or as HTML rendered by mdBook.

All documentation is written in markdown in /docs/src. The HTML version can be generated with mdbook by running mdbook build in the root directory.

Unit tests for the compiler application can be run with:

cargo test

Integration tests can be run using a simple bash script to query the output of commands:

./tests/lexer/lexer_integration_test.sh

These provide appropriate test cases that test for a wide variety of valid and invalid cases in the language.

The lexer is designed in a modular fashion in order to a clean separation of concerns.

The main function's current responsibilities are to parse the command-line application's required arguments (the path to the source code file), ensure that the provided path exists, instantiate a single lexer for the entire duration of the lexical analysis, and call the nextToken function until the entire source code have been tokenized.

The lexer's responsibility is to manage the progress of the lexical analysis of the source code. It buffers and streams the source code to be analyzed as tokens are extracted. It maintains state about the current index of the source code being accessed, and is effectively a data structure that is passed to the state transition functions. Every call to nextToken results in the instantiation of a new StateTransition object which handles all transitions between FSM states on character input until a valid token is identified.

The StateTransition module contains all information relating to transition internal state of the FSM on character input. It manages it's own internal state (the current and next states) as well as the lexer's state (which characters are being read at which index of the source code).

The state transition table is a static two-dimensional array that encodes all possible transitions between all valid states. This is referred to when new characters are being read, which ultimately updates the current state and the position in the source code. The table also encodes information as to whether the current state is an error, final, or backtrack state, and the module is responsible for taking the appropriate action in these cases, which could include generating a token, modifying the buffer for the extracted lexeme, and reporting encountered error states.

The token is a simple data structure that stores the token's class and extracted lexeme as strings in a struct. Further improvements would be to restrict the token's class to a set of defined TokenClass enum structures which encode peculiarities about certain classes (for example, comment and newline tokens), as opposed to arbitrary text input.

An ErrorType enumeration is defined in the output::error module to differentiate between recoverable and unrecoverable errors. It is also responsible for defining all possible sorts of errors, as well as outputting basic error information to standard output.

The output::source_line module is able to analyze the information in the lexer data structure containing the source code and the current point of analysis, and print relevant lines and characters to standard output when errors occur.

• The AtoCC RegExp and kfG Editor applications were used for converting the regular expressions identified as part of the lexical specification into DFAs, as well as ensuring the syntax CFG was converted to LL(1) for predictive parsing. Althought the tool was used in the constructed of the DFA shown above, the current application does not output the generated tokens as a file in the AtoCC format.
• The FSM simulator website was used for a quick but less vigorous validation of the conversion of regular expressions to DFAs.
• The lazy_static Rust library was used in order to statically store the large state transition table with values known at compile-time.
• The Ropey library was used as a Rust library to buffer the source code using the rope data structure as it is being lexically analyzed, as well as keep track of lines and line numbers for when outputting errors. I was not able to find any other data structure that modeled the lexical analysis use case so appropriately.
• The clap Rust library was used for simple command-line argument parsing. It was chosen given that it is mature and well-regarded in the Rust ecosystem.
• The colored Rust library was used for prettier output during error reporting. It was chosen for it's ease of use and minimalism.

The following list of regular expressions were used in order to define our language's mechanism for recognizing patterns when tokenizing. For brevity's sake, a variant on the POSIX standard for regular expressions is shown.

From the regular expressions for tokens defined above, as well as additional simpler language features, a deterministic finite automaton (DFA) was constructed. Tools such as AtoCC and FSM Simulator were used in order to confirm the validity of the regular expressions as finite state machines.

The FSM diagram was created using draw.io and can be modified by opening the lexer_dfa.xml file.

The automaton implementation uses a static state transition table. Any change in the lexical specification above requires rebuilding this table, but should not impact the implementation of the compiler significantly.

The following legend defines some shortcuts for transition characters:

This state transition table was constructed based on the above DFA. The first column indicates the current state. The last few columns indicate any peculiarities of that state. The remaining columns represent all possible input characters which correspond to transition functions.

Note that for rows which correspond to final states, the next transition function is never computed, given that arriving at a final state results in a return to the initial state (after backtracking if applicable). For simplicity's sake and in order to indicate a return to the start state, these rows are filled with 1.

The current set of keywords available in the language are:

• if
• then
• else
• for
• class
• get
• put
• return
• program
• int
• float
• bool
• and
• or
• not

If an <identifier,> token is found, it must first be compared to the above list where a match would actually result in a keyword token class, with the exception of and, or and not, which would result in a token class of logical_operator.

The three types of errors generated by the lexer are:

• Unrecoverable Error (1): The input file path provided does not exist on the filesystem.
• Recoverable Error (2): Input character is unrecognized.
• Recoverable Error (3): Invalid syntax: error state reached. Resetting FSM to initial state.

Every undefined transition in the above DFA results in one of the two recoverable error types, as is demonstrated by the wide variety of integration tests.

All recoverable errors display the line number and line when tokenizing the source code.

The panic mode technique is used for error recovery, which involves skipping invalid input characters until valid program segments are encountered. An error is reported to the user, but the lexical analysis and identification of tokens continues afterwards.

All error output is logged to both the console as well as the error.log file at the root of the repository whenever any lexical analysis occurs.

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 (.)