This is a simple compiler for the language rascl, a small subset of C.
- CSE 304 Project
The lexical analyser is implemented in lexer.c.
The lexical analyser, lexer.c, contains the following the function calls:
This function will initialise the lexical analyser with the source file.
Returns SUCC if the file is opened successfully; FAIL if not.
This function will return the next token.
Returns SUCC on success.
If there are no tokens, FAIL will be returned. nextToken's token_type field will be NO_SYM.
If an invalid symbol is read, FAIL will be returned. The invalid symbol is stored in nextToken's token_val field. The token_type field will be INVALID_SYM.
Tokens are stored as struct token.
struct token {
enum token_type token_type;
union token_val token_val;
char token_repr[max_token_length + 1];
};They have the following members:
-
token_type: The type of the token (for example, the
IFtoken) -
token_val: The default value/type of a token is the lexeme that was scanned stored in a char array. To change the default value/type, the function
onTokenDetectis used. -
token_repr: The textual representation of the token. The textual representation of the tokens are stored in an array,
char *token_reps[]. To change the default textual representation, the functiononTokenDetectis used.
Please refer to lexer.h for more details.
Lexical Analysis will be done by table-driven scanning. The function int delta (int current_state, char input_symbol) defined in lex_table.c will return the next state based on the current state and the input symbol. If the current state is a final state, the function enum token_type accept (int current_state) defined in lex_table.c will return the token-type associated with the current state. The lexical analyser will simulate the DFA until there are no more transitions. Then the last accepted token-type and its associated lexeme is assigned to the token to be returned. The token can also be ignored (not returned) by returning the next possible token instead within the onTokenDetect function.
The source file will be read line-by-line and scanned for tokens. The tokens are assumed to be contained within a single line, and not spreading over multiple lines. So multiline comments may not be detected, for example. The lines have a maximum size limitation, MAX_LINE_LEN, and the tokens have a maximum size limitation, MAX_TOKEN_LEN.
The program testLexer.c will use lexer.c to get tokens from the test file, testLexer.txt.
- A function
destroy_lex_table()to destroy the hash-table created inlex_table.c. This function will free up memory that is not being used.
The symbol-table manager is implemented in symbol_table.c.
Initialises the symbol table. Also creates the language-defined data-types (for example, int) as symbols in the table.
Starts a new scope. All symbols added to the table after calling the function will be defined in this new scope. The global scope is defined as 0. Any new scopes created would have increasing ids from the global scope, following the order of creation.
Returns the id of the new scope as an integer.
Reverts the current scope to the global scope (0).
Adds a symbol with the name identifier to the symbol-table. The scope of the symbol depends on the scope that is entered by calling newScope() or exitScope(). If there is a symbol with the same identifier in the scope, the symbol is not added and FAIL is returned.
Returns SUCC if added successfully; otherwise returns FAIL.
Locates the symbol in the symbol-table with the requested identifier at the specified scope. Then the attribute is identified by the order it is defined in struct symbol and given the value specified in the function call. The attributes are zero-indexed from int scope member in struct symbol.
If the function successfully changes the attributes, SUCC is returned. Otherwise FAIL is returned.
Verifies whether the symbol with the specified identifier is in the specified scope within the symbol-table.
Returns SUCC if the symbol exists, otherwise returns FAIL.
Returns the symbol with the specified identifier at the scope specified. If the symbol is not defined in the specified scope, it is searched in the global scope. Otherwise returns NULL if the symbol is not found.
Symbols are stored as struct symbol.
struct symbol {
char id[MAX_TOKEN_LEN];
int scope;
struct symbol *type;
void *mem_loc;
void *other;
};They have the following members:
- id: The identifier of the symbol.
- scope: Scope of the symbol.
- type: The type of the symbol.
- mem_loc: Memory location where the symbol is stored.
- other: Other details about the symbol.
The symbol table is stored as a hash-table called symbol_table. The implementation of the hash-table can be found in the file hash_tab.c.
The program testSymbolTable.c will test the Symbol Table functions implemented in symbol_table.c. Run make tests in the root of the project directory to compile the symbol-table manager tester, build/test_symbol_table.
The parser is implemented as a recursive descent parser. The parser can be found in src/parser/parser.c. The header file for the parser, src/include/parser.h, defines the macros that can be used to create CFG rules for the parser. The rules to parse rascl code can be found in src/parser/rascl_syntax.c.
Each non-terminal(NT) in the grammar is defined as a function.
The return value of the the NT can be:
PROGRESSFALLBACKROLLBACK
The return value informs the calling NT about the action it should take.
The NT function checks whether the next token will be matched by one of the NT's productions. The productions are checked in sequence as described below:
Check whether the 1st symbol in the production can match the next token from the lexer. If the 1st symbol matches, progress to the next symbol in the production after logging the productions that led to the match. Otherwise, if the 1st symbol did not match, fallback to the next production and repeat. If there was an error detected, rollback to the last non-terminal.
If one of the productions had a start symbol that matched the token, the next symbols in the production would be matched and logged on progress. This would continue till the end of the production is reached and the calling NT would be informed to progress. If a symbol is not matched after the starting symbol of a production has already been matched, there is no fallback; the function can only rollback to the calling NT because an error is detected.
Macros are used to define the NT functions. The example below shows how to create a non-terminal called name with a single production rule to match the ID token:
DEF_NT(name)
START_T(ID, "name -> ID.\n", END_P)
END_NTDEF_NT marks the start of the function that represents the non-terminal name. END_NT marks the end of the function. All the productions of the non-terminal should go between these two macros.
START_T() and START_NT() create production rules for the non-terminal that it is in. START_T() is used when the production starts with a terminal. If the production starts with a non-terminal START_NT() is used. In the example shown above, ID is a terminal, so START_T() is used to start the production. The first symbol of the production is entered as the first argument of the macro. The second argument is the string representation of the derivation of the production when the terminal ID is read. The third argument should be a macro denoting the rest of the production. In this case the production has no more symbols, so END_P is used to mark the end of the production.
Please refer to src/parser/rascl_syntax.c for more examples.
Run make or make parser in the root of the project directory to build the parser build/parser. To test the parser, run the parser with one of the test programs in test/parser/testsuite/. The test-programs have .rsc extensions and the parser will produce .rsc.log files as output. The parser needs to be executed from the root of the directory to work properly. The log files will be created in the same folder as the source file. For example, to parse a .rsc file and see its output you would enter the following commands at the root of the project folder in sequence:
make parser
./build/parser ./tests/parser/testsuite/basic_rascl_tests/T00_rascl_test_exprs1.rsc
cat ./tests/parser/testsuite/basic_rascl_tests/T00_rascl_test_exprs1.rsc.log
Intermediate code will be generated through syntax directed definitions (SDDs). As the parser runs through productions of the NT-functions, it will evaluate code snippets that are found in between symbols of the productions. The code to generate the intermediate code for rascl will be found in src/parser/rascl_syntax.c.
The attributes of a non-terminal in a production are stored in a variable struct attributes *attr. You can add fields to struct attributes as necessary.
struct attributes {
struct symbol *type;
union token_val value;
};When a non-terminal or a terminal returns, you can read the attributes of that symbol by using the macro POP_ATTR(x). For example, if you want to read the attribute type, use POP_ATTR(type).
Before entering a non-terminal, or matching a terminal, you can pass attributes to the symbol by using the macro PUSH_ATTR(x, val). For example, if you want to set the attribute type to sym_int, use PUSH_ATTR(type, sym_int).