Although the Parser can handle functions, it cannot handle function calls. Therefore, a new token called func_call_st was created. The expected grammar for a function call is the function name followed by parameters contained within parenthesis:
Note that another new token besides func_call_st is used, called call_parameters. Although the parameters token was created previously, it cannot be reused as parameters in function calls do not include the variable type. Due to this, the call_parameters/call_parameter tokens were created the same as the parameters/parameter tokens except variable types weren’t included:
The parameter list node created for the parameters token is reused (list to store an unknown amount of parameters for a function or function call); however, a new abstract syntax tree node was created for call parameters (same as parameter nodes, except variable type is not stored):
// Update to code in ast.h
typedef struct AST_Node_Call_Param_t {
Node_Type type;
AST_Node* ID;
} AST_Node_Call_Param;
// Update to code in ast.c
AST_Node* new_ast_call_param_node(AST_Node* ID) {
AST_Node_Call_Param* node = malloc(sizeof(AST_Node_Call_Param));
node->type = CALL_PARAM_NODE;
node->ID = ID;
return (AST_Node*)node;
}
Code to insert call parameters into the symbol table will need to be added in the future for the Complier to be able to access the parameters when generating assembly code.
Using the same method as was done with declarations, the grammar for functions was updated in the Parser to account for multiple functions in a program:
However, the grammar for a single function still does not account for parameters (see that the grammar only looks for an open and a close parenthesis with nothing in between):
function:
INT ID OP_PAR CL_PAR OP_BRACE statement CL_BRACE {
$$ = new_ast_func_node($2,$6); }
;
The updated grammar for a function that accounts for parameters will look like the following with the addition of a new token called parameters:
// Additions to Parser.y
function:
var_type ID OP_PAR parameters CL_PAR OP_BRACE statements CL_BRACE {
$$ = new_ast_func_node($2,$4,$7); }
;
This update requires the new_ast_func_node() function to now take an additional parameter for the parameters token:
As functions will have an unknown amount of parameters, a parameter list node is created for each function. The design of the parameter list node is the same as the previously created statement list. Function parameters in C are a variable type followed by a variable name. Therefore, the parameter nodes found within a parameter list were designed to contain the parameter type and name:
A function can either have multiple parameters, a single parameter, or no parameters (marked by empty space or void). Therefore, the grammar for the parameters token was made to account for these four possibilities (note, grammar resembles that of the statements token):
The token parameter must account for parameters in the function. As previously mentioned, parameters in a C function are variable types followed by variable names; however, if there are multiple parameters, they will be separated with commas. The grammar for the parameter token was created to account for both parameters that aren’t and are separated by commas:
The initial Parser’s grammar must be expanded to account for many types of statements. The first will be declaration statements. Starting with the most basic C declaration statement, there is a variable type followed by a variable name:
int var_name;
First, the grammar was updated by adding a token for variables. Just using the previously created term token won’t work as it also allows constant and expressions within parenthesis which should not be in the left side of a declaration statement. Note for now only integer variables are handled:
Using the previously created var_type token, the starting grammar for a declaration statement that accounts for a single variable with no value being assigned is:
declaration_st:
var_type variable SEMI { ; }
;
However, sometimes declarations assign a value, such as the following:
int var_name = 1;
This means that another token is needed that can be a variable or a variable assigned to a value. This token is called a declaration:
Now out parser can recognize a declaration statement for a single variable. Yet, it cannot handle a declaration statement for multiple statements such as the below example:
int var_name1, var_name2 = 100, var_name3;
To handle multiple declarations in a single line of C code, another new token called declarations is used. The declarations tokens allows for multiple comma separated declaration tokens to be handled:
The parser can now recognize declaration statements, but the code to be executed when the declaration grammar is encountered must be added. Since a single line of C code can declare multiple variables, it is unknown how many AST nodes will be needed for a single declaration statement. For this, an AST (Abstract Syntax Tree) structure is created to store a list of declarations is used (fields are variable type and a pointer to a list of individual declarations):
Also, a structure must be created for the individual declarations stored in the declration list. The fields for this structure are the variable type, a node pointing to the variable, and a value (NULL unless variable is assigned a value in declaration):
Looking at the grammar for a function in the Parser, it is observed that the only valid variable type is an integer (INT):
function:
INT ID OP_PAR CL_PAR OP_BRACE statements CL_BRACE {
$$ = new_ast_func_node($6);
}
;
The compiler must be able to handle more variable types such as characters or doubles. The first step to adding new variable types is to create an enum used to distinguish between the different variable types:
Next, the Parser must be updated. First, the tokens must be added to the Parser (must be <intval> tokens as they are also passing the enum values through the yylval union):
%token <intval> CHAR DOUBLE FLOAT INT LONG SHORT VOID /*Variable Types*/
Now, the compiler is able to pass different variable types to the Parser; however, the grammar rules within the Parser still need to be updated. One solution would to be have 7 rules for function where the variable type changes each time. This is inefficient as every time the compiler has a grammar rule with a variable type in it, multiple lines would be required. Therefore, a new %type <intval> called “var_type” will be created:
%type <intval> var_type
The grammar for var_type is set so that it can be any variable type ($1 in this case is the enum value passed through yylval):
The addition of the var_type will not only help with the existing grammar for functions but will also prove useful for other grammar rules with variable types that are to be added in the future (i.e., declarations).
Taking a look at how the function and statement types were previously implemented in the Parser, it is observed that a function can only hold one statement node:
function:
INT ID OP_PAR CL_PAR OP_BRACE statement CL_BRACE {;}
;
statement:
return_st {;}
;
In reality, a function will contain many statements, so the Parser must be modified. To allow a function to contain multiple statements, a statement list node will be used. The statement list node will contain a pointer to a statement node as well as a pointer to another statement list node:
Since a statement list node contains a pointer to another statement list node, any amount of statements can be contained within a single statement list tree. Therefore, if the function node contains a statement list node rather than a statement node, any amount of statement nodes can be contained within a single function.
Another field to be implemented in the statement list node is the statement count. The statement count represents how many statement nodes can be found from traversing the tree starting at that particular statement list node. The statement count will be useful later when translating to the XM3 language as the CEX instruction (conditional execution) needs to know the amount of instructions to run/not run. Below shows a statement list tree that uses the statement count:
Now, to implement the statement list node into the compiler. First, a struct for a statement list node is needed for the abstract syntax tree. It will contain fields for the node type, a statement list node pointer, a statement node pointer, and an integer for the statement count:
Then, the Parser needs recursive grammar to enable the creation of statement list nodes. This will require a new %type <node> called statements (refer to the post “Initial Parser” for an explanation of bison types). The two possible grammars for a statements type will be:
A statements type followed by a statement type
A single statement type.
This allows a statements type to represent any amount of subsequent statement types as “statements” is replaced with “statement” or “statements statement” where “statements” can continue to be replaced. See the below code for the implementation of the “statements” type grammar in the Parser (note: function now uses the statements type rather than the statement type):
The example below shows a visual representation of the creation of a statements type. Say 4 subsequent statement types are passed to the Parser (note statement1 is passed to the Parser first, and statement4 is passed to the Parser last):
The Parser has been updated to have recursive grammar; however, it still needs C code to create the statement list nodes. For this, the below function is used to create statement list nodes:
Now, it is needed to update the C code in the actual Parser. Again, two cases must be considered as the grammar for the statements type can either be “statements statement” or just “statement”.
First, take the case where the statements type is just “statement”. In this case, only a single statement needs to be handled. Therefore, the pointer to the next statement list node should be NULL. Also, since there are no further statement list nodes, the statement count should be 1. Therefore, the Parser will call the function new_ast_statelist_node with the parameters of statement list node pointer = NULL, statement node pointer = $1 (pointer to statement node returned from statement type), and statement count = 1:
Then, the next case of the statements type being “statements statement”. Take the previous example of there being 4 subsequent statement types. Initially the Parser will only see the first statement. This will be handled as described above for the “statement” case. Then, when the Parser is passed the second statement it will see the grammar as:
In this case, statements1 is a statement list node where the statement node pointer is to the node for statement1 and statement2 is a statement node. Therefore, the statement list node created for statement2 should have the next statement list node pointer point to statements1, should have the statement node pointer point to statement2, and should have the statement count be 1 greater than that of the statement count in statements1. See below for a visual representation of the abstract syntax tree nodes being created :
Implementing the case of “statements statement” in the Parser requires the statement count field node from statements node to be known. To do this, a temporary node is created to access the field. See below for the implementation of the “statements statement” case:
When the Parser was first set up it only was able to recognize the =, +, -, *, and / operators. More operators are needed to create a C compiler such as logical and bitwise operators. First, the Lexer must be updated to return tokens for these operators. For this, first the enum of operator types was expanded:
Then, the Lexer was updated to return tokens for each of the operators. Note that these operators now also return an integer to be used to set the operator field in an expression node:
Then, the grammar for the expression type must be updated to account for these new operators. Note that now we can use $2 in the create_new_ast_expr_node function rather than an enum as the integer is passed from the Lexer:
Now are Parser can handle more operators; however, there is no operator precedence. In C, operator precedence is determines what operators should be evaluated before others. For example, take the expression 1*2+3. The multiplication of 1 and 2 should occur first; however, without operator precedence, the compiler evaluates the addition first:
To add operator precedence in bison, the %left and %right tokens can be used. %left is used for left to right precedence (operators on the same precedence level occur left to right) and %right is the inverse of %left. Precedence levels are set up as follows (the lower they are, the earlier they will be evaluated):
%right ASSIGN PLUS_ASSIGN MIN_ASSIGN MULT_ASSIGN DIV_ASSIGN MOD_ASSIGN LSHIFT_ASSIGN RSHIFT_ASSIGN BITAND_ASSIGN BITXOR_ASSIGN BITOR_ASSIGN
%left LOGOR
%left LOGAND
%left BITOR
%left BITXOR
%left BITAND
%left EQ_COMP NOTEQ_COMP
%left GT_COMP LT_COMP GTEQ_COMP LTEQ_COMP
%left R_SHIFT L_SHIFT
%left PLUS MINUS
%left MULT DIVIDE MOD
Now running the same expression results in the multiplication occurring first:
There are still more operators to be added but for now a good base has been set and operator precedence has been introduced.
The Parser must be able to take in each of the above tokens and recognize valid grammar rules. The first step is declaring the tokens in the Parser as well as the union used to pass values through yylval. Tokens are declared with %token and the union is declared with %union. If a token is also passing a value through the union it must contain the data type within angle brackets. See the code below for the declarations:
%union {
int intval;
double doubleval;
char charval;
char* str;
struct AST_Node* node;
};
%token RETURN INT
%token SEMI OP_PAR CL_PAR OP_BRACE CL_BRACE EOL EQ
%token PLUS MINUS MULT DIVIDE ASSIGN
%token <intval> ICONST
%token <str> ID
Now that the tokens have been declared, grammar rules need to be set. For a starting point we will be treating a C program as a series of functions. These functions contain statements (i.e., loop statements, if statements, or declarations) which themselves contain expressions (i.e., additions or assignments). Moreover the expressions contain variables and numbers.
The program, functions, statements, and expressions will need to be represented as nonterminal tokens in bison. These nonterminal tokens will be made up of tokens and other nonterminal tokens (which breakdown into tokens) to represent valid grammar rules. For example, the expression nonterminal token would breakdown as follows (note that term is also a nonterminal token):
expression:
term {;}
| variable assign expression {;}
| expression PLUS expression {;}
| expression MINUS expression {;}
| expression MULT expression {;}
| expression DIVIDE expression {;}
;
term:
ICONST {;}
| ID {;}
| OP_PAR expression CL_PAR {;}
;
In the above code the “|” is used to represent alternative options for a nonterminal token. Take the nonterminal token “term”. It can be an integer (ICONST token), a variable (ID token) or an expression within parenthesis (used so that expressions within parenthesis occur before those outside). It is also important to note that the expression nonterminal token contains itself. This means any amount expressions will be represented by a single expression nonterminal token as recursion will occur until only terms and operators are left.
To declare these nonterminal tokens, %type is used. These %types will eventually contain nodes so that the program can be represented as an abstract syntax tree, so <node> will be used. For now, the only statement type the Lexer is passing a token for is a return statement. Therefore, return_st will also be a type (more types will be required in the future):
%type <node> program function statement expression term return_st
Setting the grammar rules for these types results in:
program:
function {;}
;
function:
INT ID OP_PAR CL_PAR OP_BRACE statement CL_BRACE {;}
;
statement:
return_st {;}
;
return_st:
RETURN SEMI {;} /*Return nothing*/
| RETURN expression SEMI {;} /*Return a value*/
;
expression:
term {;}
| variable ASSIGN expression {;}
| expression PLUS expression {;}
| expression MINUS expression {;}
| expression MULT expression {;}
| expression DIVIDE expression {;}
;
term:
ICONST {;}
| ID {;}
| OP_PAR expression CL_PAR {;}
;
In the above code the grammar rules are set but no C code is executed when they are encountered. In bison, $$ represents the output (nonterminal token which in this case is always a node), and $x (where x is the order of the token/nonterminal token in the grammar rule) to represent one of the parts of the grammar. For example, in the below code $$ = nonterminal, $1 = TOKEN1, $2 = nonterminal2, and $3 = TOKEN2:
nonterminal:
TOKEN1 nonterminal2 TOKEN2
;
Adding C code results in the types having functions to creating nodes (see post for creating ast.h and ast.c) except for the program type which calls the function ast_traverse (for now used to print out the abstract syntax tree, but later will be used to create next stage of intermediate representation):
At this point we now have the union, tokens, and types declared. Also, we have the grammar rules and corresponding C code set for the grammar rules. The Parser still requires a lot of expansion (i.e., more operators in expressions, more statements, a function being able to contain multiple statements, and more) but a starting point has been set. The last step to setting up the Parser is defining the default starting symbol of the grammar using %start. For our compiler this is the program type as all the tokens passed to the parser make up a single program:
Once the Lexer has converted a C programs characters to a series of tokens, the compiler must check if the order of these tokens lead to valid statements. For this, the Parser is used.
The Parser is passed the tokens from the Lexer then uses a set rules called grammars to check whether valid statements are being passed. For example say the Lexer converts the C code “return a;” to “RETURN ID SEMICOLON”. The Parser would have a grammar to recognize this pattern tokens:
return_st: RETURN ID SEMICOLON {;}
Note, Bison will be used to implement the Parser for the XM3 compiler. Bison is an open source tool used with Flex.
