UE20CS353
COMPILER DESIGN
ASSIGNMENT 2
PART 1
ABSTRACT SYNTAX TREE
LEX FILE (lexer.l)
%{
#define YYSTYPE char*
#include <unistd.h>
#include "y.tab.h"
#include <stdio.h>
extern void yyerror(const char *); // declare the error handling
function
%}
/* Regular definitions */
digit [0-9]
letter [a-zA-Z]
id {letter}({letter}|{digit})*
digits {digit}+
1
opFraction (\.{digits})?
opExponent ([Ee][+-]?{digits})?
number {digits}{opFraction}{opExponent}
%option yylineno
%%
\/\/(.*) ; // ignore comments
[\t\n] ; // ignore whitespaces
"(" {return *yytext;}
")" {return *yytext;}
"." {return *yytext;}
"," {return *yytext;}
"*" {return *yytext;}
"+" {return *yytext;}
";" {return *yytext;}
"-" {return *yytext;}
"/" {return *yytext;}
"=" {return *yytext;}
">" {return *yytext;}
"<" {return *yytext;}
"if" {return IF;}
"else" {return ELSE;}
"{" {return *yytext;}
2
"}" {return *yytext;}
{number} {
yylval = strdup(yytext); //stores the value of the number to
be used later for symbol table insertion
return T_NUM;
{id} {
yylval = strdup(yytext); //stores the identifier to be
used later for symbol table insertion
return T_ID;
. {} // anything else => ignore
%%
Parser.y
%{
#include "abstract_syntax_tree.c"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void yyerror(char* s); // error handling
function
int yylex(); // declare the function
performing lexical analysis
extern int yylineno; // track the line
number
%}
3
%union // union to allow nodes to
store return different datatypes
char* text;
expression_node* exp_node;
%token <text> T_ID T_NUM IF ELSE
%type <text> RELOP
%type <exp_node> E T F START ASSGN S C SEQ
/* specify start symbol */
%start START
%%
START : SEQ {
display_exp_tree($1);
printf("\n");
YYACCEPT;
};
SEQ : S SEQ { $$=init_exp_node("seq",$1,$2,NULL);}
4
| S {$$=$1;}
S : IF '(' C ')' '{' SEQ '}' {
$$=init_exp_node(strdup("if"),$3,$6,NULL);
| IF '(' C ')' '{' SEQ '}' ELSE '{' SEQ '}' {
$$=init_exp_node(strdup("if-else"),$3,$6,$10);
| ASSGN { $$=$1;}
C : F RELOP F {
$$=init_exp_node(strdup($2),$1,$3,NULL);
RELOP : '<' { $$="<";}
| '>' { $$=">";}
| '>''=' { $$=">=";}
| '<''=' { $$="<=";}
| '=''=' { $$="==";}
| '!''=' { $$="!=";}
/* Grammar for assignment */
5
ASSGN : T_ID '=' E ';' {
$$ =
init_exp_node(strdup("="),init_exp_node(strdup($1),NULL,NULL,NULL),$3,NULL);
/* Expression Grammar */
E : E '+' T {
$$ = init_exp_node(strdup("+"),$1,$3,NULL);
| E '-' T {
$$ = init_exp_node(strdup("-"),$1,$3,NULL);
| T { $$ = $1; }
T : T '*' F {
$$ = init_exp_node(strdup("*"),$1,$3,NULL);
| T '/' F {
$$ = init_exp_node(strdup("/"),$1,$3,NULL);
| F { $$ = $1; }
F : '(' E ')' { $$ = $2; }
| T_ID {
6
$$ = init_exp_node(strdup($1),NULL,NULL,NULL);
| T_NUM {
$$ = init_exp_node(strdup($1),NULL,NULL,NULL);
%%
/* error handling function */
void yyerror(char* s)
printf("Error :%s at %d \n",s,yylineno);
/* main function - calls the yyparse() function which will in turn drive
yylex() as well */
int main(int argc, char* argv[])
yyparse();
return 0;
Abstract syntax tree.c
#include <stdio.h>
7
#include <stdlib.h>
#include <string.h>
#include "abstract_syntax_tree.h"
expression_node* init_exp_node(char* val, expression_node* left,
expression_node* mid, expression_node* right)
expression_node* node = (expression_node*)malloc(sizeof(expression_node));
node->left = left;
node->mid=mid;
node->right=right;
node->val= val;
return node;
void display_exp_tree(expression_node* exp_node)
// traversing the AST in preorder and displaying the nodes
if(exp_node == NULL) return ;
printf("%s, ",exp_node->val);
display_exp_tree(exp_node->left);
display_exp_tree(exp_node->mid);
display_exp_tree(exp_node->right);
Abstract_syntax_tree.h
typedef struct expression_node
8
struct expression_node* left;
struct expression_node* mid;
struct expression_node* right;
char* val;
}expression_node;
expression_node* init_exp_node(char* val, expression_node* left,
expression_node* middle, expression_node* right);
void display_exp_tree(expression_node* exp_node);
Output 1:
Output 2 :
Output 3
9
PART 2
ICG
Lexer.l
%{
#define YYSTYPE char*
#include <unistd.h>
#include "y.tab.h"
#include <stdio.h>
extern void yyerror(const char *); // declare the error handling function
%}
/* Regular definitions */
digit [0-9]
letter [a-zA-Z]
id {letter}({letter}|{digit})*
digits {digit}+
opFraction (\.{digits})?
opExponent ([Ee][+-]?{digits})?
number {digits}{opFraction}{opExponent}
%option yylineno
%%
\/\/(.*) ; // ignore comments
[\t\n] ; // ignore whitespaces
"<=" {return LTEQ;}
10
">=" {return GTEQ;}
"==" {return EQQ;}
"!=" {return NEQ;}
"{" {return OC;}
"}" {return CC;}
"(" {return *yytext;}
")" {return *yytext;}
"." {return *yytext;}
"," {return *yytext;}
"*" {return *yytext;}
"+" {return *yytext;}
";" {return *yytext;}
"-" {return *yytext;}
"/" {return *yytext;}
"=" {return *yytext;}
">" {return GT;}
"<" {return LT;}
{number} {
yylval = strdup(yytext); //stores the value of the number to be used
later for symbol table insertion
return T_NUM;
"if" {return T_IF;}
"else" {return T_ELSE;}
{id} {
yylval = strdup(yytext); //stores the identifier to be used
later for symbol table insertion
return T_ID;
11
. {} // anything else => ignore
%%
Parser.y
%{
#include "quad_generation.c"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define YYSTYPE char*
void yyerror(char* s); // error handling
function
int yylex(); // declare the function
performing lexical analysis
extern int yylineno; // track the line
number
FILE* icg_quad_file;
int temp_no = 1;
int label_no=1;
%}
%token T_ID T_NUM T_IF T_ELSE GTEQ LTEQ EQQ NEQ GT LT OC CC
/* specify start symbol */
%start START
12
%nonassoc T_IF
%nonassoc T_ELSE
%%
START : S {
printf("Valid syntax\n");
YYACCEPT;
};
/* Grammar for assignment */
ASSGN : T_ID '=' E {
quad_code_gen($1, $3, "=", " ");
/* Expression Grammar */
E : E '+' T {
$$ = new_temp();
quad_code_gen($$, $1, "+", $3);
| E '-' T {
$$ = new_temp();
13
quad_code_gen($$, $1, "-", $3);
| T
T : T '*' F {
$$ = new_temp();
quad_code_gen($$, $1, "*", $3);
| T '/' F {
$$ = new_temp();
quad_code_gen($$, $1, "/", $3);
| F
F : '(' E ')' {
$$=strdup($2);
| T_ID {
$$=strdup($1);
| T_NUM {
$$=strdup($1);
14
}
S : T_IF '('C')' OC S CC {quad_code_gen($3,"","Label","");} S
| T_IF '('C')' OC S CC {
$2 = new_label();
quad_code_gen($2,"","goto","");
quad_code_gen($3,"","Label","");} T_ELSE OC S CC
{quad_code_gen($2,"","Label","");}S
| ASSGN ';' S
|'{'S'}'
C : E rel E { $$ = new_temp();
quad_code_gen($$, $1, $2, $3);
$1 = new_label();
quad_code_gen($1,$$,"if","");
$$ = new_label();
quad_code_gen($$,"","goto","");
quad_code_gen($1,"","Label","");
};
rel : GT {strcpy($$,">");}
| LT {strcpy($$,"<");}
| LTEQ {strcpy($$,"<=");}
| GTEQ {strcpy($$,">=");}
15
| EQQ {strcpy($$,"==");}
| NEQ {strcpy($$,"!=");}
%%
/* error handling function */
void yyerror(char* s)
printf("Error :%s at %d \n",s,yylineno);
/* main function - calls the yyparse() function which will in turn drive
yylex() as well */
int main(int argc, char* argv[])
icg_quad_file = fopen("icg_quad.txt","a");
fprintf(icg_quad_file,"Generated Intermediate Code \n");
yyparse();
fclose(icg_quad_file);
return 0;
Quad generation.c
#include <stdio.h>
16
#include <stdlib.h>
#include <string.h>
#include "quad_generation.h"
void quad_code_gen(char* a, char* b, char* op, char* c)
fprintf(icg_quad_file,"%s\t%s\t%s\t%s\n",op,b,c,a);
char* new_temp()
char* tempNew = (char*)malloc(sizeof(char)*4);
sprintf(tempNew,"t%d",temp_no);
temp_no++;
return tempNew;
char* new_label()
char* label = (char*)malloc(sizeof(char)*4);
sprintf(label,"L%d",label_no);
label_no++;
return label;
Quad_generation.h
17
extern FILE* icg_quad_file; //pointer to the output file
extern int temp_no; //variable to keep track of current temporary
count
extern int label_no;
void quad_code_gen(char* a, char* b, char* op, char* c);
char* new_temp();
Output 1:
Ouput 2:
18
19
