Author: aidannearing

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:

term:
ICONST { $$ = new_ast_const_node(INTtype, $1); }
| variable
| OP_PAR expression CL_PAR { $$ = $2; }
;

variable:
ID  { $$ = new_ast_ID_node(INTtype, $1, $1); }
;

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:

declaration_st:
var_type declaration SEMI { ; }
;

declaration:
variable { ; }
| variable ASSIGN expression { ; }
;

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:

declaration_st:
var_type declarations SEMI { ; }
;

declarations:
declarations declaration { ; }
| declaration { ; }
;

declaration:
variable { ; }
| variable COMMA { ; }
| variable ASSIGN expression { ; }
| variable ASSIGN expression COMMA { ; }

;

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):

// Addition to ast.h
typedef struct AST_Node_Declaration_List_t {
	Node_Type type;
	int vartype;
	AST_Node* decls;
} AST_Node_Decl_List;

// Addition to ast.c
AST_Node* new_ast_decl_list_node(int vtype, AST_Node* decls)
{
	AST_Node_Decl_List* node = malloc(sizeof(AST_Node_Decl_List));

	node->type = DECLS_NODE;
	node->vartype = vtype;
	node->decls = decls;

	return (AST_Node*)node;
}

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):

// Additions to ast.h
typedef struct AST_Node_Declaration_t {
	Node_Type type;
	int vartype;
	AST_Node* var;
	AST_Node* val;
} AST_Node_Decl;

// Additions to ast.c
AST_Node* new_ast_decl_node(int vtype, AST_Node* var, AST_Node* val)
{
	AST_Node_Decl* node = malloc(sizeof(AST_Node_Decl));

	node->type = DECL_NODE;
	node->vartype = vtype;
	node->var = var;
	node->val = val;

	return (AST_Node*)node;
}

Adding the C code to the Parser leads to the following:

declaration_st:
var_type declarations { $$ = new_ast_decl_list_node($1, $2); }
;

declarations:
declarations declaration {
	AST_Node_StateList* temp_decl_list = (AST_Node_StateList*) $1;
	$$ = new_ast_statelist_node($1, $2, temp_decl_list->statement_cnt + 1); 
}
| declaration { $$ = new_ast_statelist_node(NULL, $1, 1); }
;

/* $2 -> declaration name, $1 -> declaration type*/
declaration:
variable 
{
	AST_Node_ID* temp_ID = $1;
	insert(temp_ID->varname, SYMTAB_LOCAL, decl_type, 0); 
	$$ = new_ast_decl_node(decl_type, $1, NULL); 
}
| variable COMMA
{
	AST_Node_ID* temp_ID = $1;
	insert(temp_ID->varname, SYMTAB_LOCAL, decl_type, 0); 
	$$ = new_ast_decl_node(decl_type, $1, NULL); 
}
| variable ASSIGN expression 
{
	AST_Node_ID* temp_ID = $1;
	insert(temp_ID->varname, SYMTAB_LOCAL, decl_type, 0); 
	$$ = new_ast_decl_node(decl_type, $1, $3);
}
| variable ASSIGN expression COMMA
{
	AST_Node_ID* temp_ID = $1;
	insert(temp_ID->varname, SYMTAB_LOCAL, decl_type, 0); 
	$$ = new_ast_decl_node(decl_type, $1, $3);
}
;

Now the grammar of the Compiler can handle C declaration statements.

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:

typedef enum Operator_t
{
	PLUSop,
	MINUSop,
	MULTop,
	DIVop,
	MODop,
	EQop,
	NOTEQop,
	GTop,
	LTop,
	GTEQop,
	LTEQop,
	LSHIFTop,
	RSHIFTop,
	BITANDop,
	BITXORop,
	BITORop,
	LOGANDop,
	LOGORop,
	ASSIGNop,
	PLUS_ASSIGNop,
	MIN_ASSIGNop,
	MULT_ASSIGNop,
	DIV_ASSIGNop,
	MOD_ASSIGNop,
	LSHIFT_ASSIGNop,
	RSHIFT_ASSIGNop,
	BITAND_ASSIGNop,
	BITXOR_ASSIGNop,
	BITOR_ASSIGNop
} Operator;

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:

%%

"+" {
    yylval.intval = PLUSop;
    return PLUS;
}
"-" {
    yylval.intval = MINUSop;
    return MINUS;
}
"/" {
    yylval.intval = DIVop;
    return DIVIDE;
}
"*" {
    yylval.intval = MULTop;
    return MULT;
}
"==" {
    yylval.intval = EQop;
    return EQ_COMP;
}
"+=" {  
    yylval.intval = PLUS_ASSIGNop;
    return PLUS_ASSIGN;
}
"-=" {  
    yylval.intval = MIN_ASSIGNop;
    return MIN_ASSIGN;
}
"/=" {  
    yylval.intval = DIV_ASSIGNop;
    return DIV_ASSIGN;
}
"*=" {  
    yylval.intval = MULT_ASSIGNop;
    return MULT_ASSIGN;
}
"%=" {  
    yylval.intval = MOD_ASSIGNop;
    return MOD_ASSIGN;
}
"&=" {  
    yylval.intval = BITAND_ASSIGNop;
    return BITAND_ASSIGN;
}
"|=" {  
    yylval.intval = BITOR_ASSIGNop;
    return BITOR_ASSIGN;
}
"^=" {  
    yylval.intval = BITXOR_ASSIGNop;
    return BITXOR_ASSIGN;
}
"<<=" {  
    yylval.intval = LSHIFT_ASSIGNop;
    return LSHIFT_ASSIGN;
}
">>=" {  
    yylval.intval = RSHIFT_ASSIGNop;
    return RSHIFT_ASSIGN;
}
"!=" {
    yylval.intval = NOTEQop;
    return NOTEQ_COMP;
}
"<<" {
    yylval.intval = LSHIFTop;
    return L_SHIFT;
}
">>" {
    yylval.intval = RSHIFTop;
    return R_SHIFT;
}
">=" {
    yylval.intval = GTEQop;
    return GTEQ_COMP;
}
"<=" { 
    yylval.intval = LTEQop;
    return LTEQ_COMP;
}
">" {
    yylval.intval = GTop;
    return GT_COMP;
}
"<" {  
    yylval.intval = LTop;
    return LT_COMP;
}
"=" {  
    yylval.intval = ASSIGNop;
    return ASSIGN;
}
"%" {
    yylval.intval = MODop;
    return MOD;
}
"&&" {
    yylval.intval = LOGANDop;
    return LOGAND;
}
"&" {
    yylval.intval = BITANDop;
    return BITAND;
}
"||" {
    yylval.intval = LOGORop;
    return LOGOR;
}
"|" {
    yylval.intval = BITORop;
    return BITOR;
}
"^" {
    yylval.intval = BITXORop;
    return BITXOR;
}

Updating the token declarations in the Parser results in:

%token <intval> ASSIGN PLUS_ASSIGN MIN_ASSIGN MULT_ASSIGN DIV_ASSIGN MOD_ASSIGN LSHIFT_ASSIGN RSHIFT_ASSIGN BITAND_ASSIGN BITXOR_ASSIGN BITOR_ASSIGN

%token <intval> BITAND BITXOR BITOR LOGAND LOGOR
%token <intval> EQ_COMP NOTEQ_COMP
%token <intval> GT_COMP LT_COMP GTEQ_COMP LTEQ_COMP
%token <intval> R_SHIFT L_SHIFT
%token <intval> PLUS MINUS
%token <intval> MULT DIVIDE MOD
%token <intval> INCR

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:

expression:
term { $$ = $1; }
| variable ASSIGN expression { $$ = new_ast_expr_node($1, $2, $3); }
| variable PLUS_ASSIGN expression { $$ = new_ast_expr_node($1, $2, $3); }
| variable MIN_ASSIGN expression { $$ = new_ast_expr_node($1, $2, $3); }
| variable MULT_ASSIGN expression { $$ = new_ast_expr_node($1, $2, $3); }
| variable DIV_ASSIGN expression { $$ = new_ast_expr_node($1, $2, $3); }
| variable MOD_ASSIGN expression { $$ = new_ast_expr_node($1, $2, $3); }
| variable LSHIFT_ASSIGN expression { $$ = new_ast_expr_node($1, $2, $3); }
| variable RSHIFT_ASSIGN expression { $$ = new_ast_expr_node($1, $2, $3); }
| variable BITAND_ASSIGN expression { $$ = new_ast_expr_node($1, $2, $3); }
| variable BITXOR_ASSIGN expression { $$ = new_ast_expr_node($1, $2, $3); }
| variable BITOR_ASSIGN expression { $$ = new_ast_expr_node($1, $2, $3); }
| expression LOGOR expression { $$ = new_ast_expr_node($1, $2, $3); }
| expression LOGAND expression { $$ = new_ast_expr_node($1, $2, $3); }
| expression BITOR expression { $$ = new_ast_expr_node($1, $2, $3); }
| expression BITXOR expression { $$ = new_ast_expr_node($1, $2, $3); }
| expression BITAND expression { $$ = new_ast_expr_node($1, $2, $3); }
| expression EQ_COMP expression { $$ = new_ast_expr_node($1, $2, $3); }
| expression NOTEQ_COMP expression { $$ = new_ast_expr_node($1, $2, $3); }
| expression GT_COMP expression { $$ = new_ast_expr_node($1, $2, $3); }
| expression LT_COMP expression { $$ = new_ast_expr_node($1, $2, $3); }
| expression GTEQ_COMP expression { $$ = new_ast_expr_node($1, $2, $3); }
| expression LTEQ_COMP expression { $$ = new_ast_expr_node($1, $2, $3); }
| expression R_SHIFT expression { $$ = new_ast_expr_node($1, $2, $3); }
| expression L_SHIFT expression { $$ = new_ast_expr_node($1, $2, $3); }
| expression PLUS expression { $$ = new_ast_expr_node($1, $2, $3); }
| expression MINUS expression { $$ = new_ast_expr_node($1, $2, $3); }
| expression MULT expression { $$ = new_ast_expr_node($1, $2, $3); }
| expression DIVIDE expression { $$ = new_ast_expr_node($1, $2, $3); }
;

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.

From the Lexer, we are currently returning the following tokens:

%%

"int" { return INT; }
"return" { return RETURN; }

[a-zA-Z_][a-zA-Z0-9_]* {
    yylval.str = _strdup(yytext);
    return ID;
}

[0-9]+ {
    int value = atoi(yytext);
    yylval.intval = value;
    return ICONST;
}

"+" {return PLUS;}
"-" {return MINUS;}
"/" {return DIVIDE;}
"*" {return MULT;}
"=" {return ASSIGN;}

";" { return SEMI; }
"(" { return OP_PAR; }
")" { return CL_PAR; }
"{" { return OP_BRACE; }
"}" { return CL_BRACE; }

%%

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):

program:
function { ast_traverse($1); }
;

function:
INT ID OP_PAR CL_PAR OP_BRACE statement CL_BRACE { 
$$ = new_ast_func_node($6); 
}
;

statement:
return_st { $$ = $1; }
;

return_st:
RETURN SEMICOLON { $$ = new_ast_return_node(0, NULL); } /*Return nothing*/
| RETURN expression SEMICOLON { $$ = new_ast_return_node(1, $2); } /*Return a value*/
;

expression:
term { $$ = $1;}
| variable ASSIGN expression { $$ = new_ast_expr_node($1, ASSIGNop, $3); }
| expression PLUS expression { $$ = new_ast_expr_node($1, PLUSop, $3); }
| expression MINUS expression { $$ = new_ast_expr_node($1, MINUSop, $3); }
| expression MULT expression { $$ = new_ast_expr_node($1, MULTop, $3); }
| expression DIVIDE expression { $$ = new_ast_expr_node($1, DIVIDEop, $3); }
;

term:
ICONST { $$ = new_ast_const_node(INTtype, $1); }
| ID { $$ = new_ast_ID_node(INTtype, $1, NULL); }
| OP_PAR expression CL_PAR { $$ = $2; }
;

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:

%start program