Department of Computer science and Engineering

CS8601- Compiler Design Laboratory

191CSC411L

Ajay Bharadwaj.S

310618104006

VI

Computer Science and Engineering

CS8601- Compiler Design Laboratory

 Department of
Department of Computer
Computer science
science and
and Engineering
Engineering
June / 2021

CS8601
CS8661

Compiler
Internet Design Laboratory
Programming Laboratory

Ajay Bharadwaj.S

3106181040
310618104006

VI
VI III
III

DepartmentofofComputer
Department Computerscience
scienceand
andEngineering
Engineering

20
20 21
21

Padmavathi.B

30 / 06 /2021
 INDEX
Date of
SI.
Experime Name of the Experiment Page No.
No.
nt
Develop a lexical analyzer to recognize a few patterns in C. (Ex.
1. 15.06.2021 identifiers, constants, comments, operators etc.). Create a 2
symbol table, while recognizing identifiers.

2. 15.06.2021 Implement a Lexical Analyzer using Lex Tool 10

3. 17.06.2021 Implement an Arithmetic Calculator using LEX and YACC 15

Generate three address code for a simple program using LEX

4. 17.06.2021 21
and YACC.

Implement simple code optimization techniques (Constant

5. 29.06.2021 41
folding, Strength reduction and Algebraic transformation)

Implement back-end of the compiler for which the three address

6. 29.06.2021 code is given as input and the 8086 assembly language code is 46
produced as output
CONTENT BEYOND SYLLABUS

7. 29.06.2021 Generate Parsing table (LL or LR) – Content beyond syllabus 50

MINI PROJECT- “COMPILER FOR C++ USING LEX, YACC”

1
 EX: 1a DEVELOP A LEXICAL ANALYZER TO RECOGNIZE A FEW PATTERNS IN
C

AIM: To Write a C program to develop a lexical analyzer to recognize a few patterns in C

ALGORITHM:
1. Start the program
2. Include the header files.
3. Allocate memory for the variable by dynamic memory allocation function.
4. Use the file accessing functions to read the file.
5. Get the input file from the user.
6. Define all the keywords, operators in the program
7. Finally print the output after recognizing all the tokens.
11. Stop the program.

PROGRAM:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>

int isKeyword(char buffer[]){

char keywords[32][10] = {"auto","break","case","char","const","continue","default",

"do","double","else","enum","extern","float","for","goto",
"if","int","long","register","return","short","signed",
"sizeof","static","struct","switch","typedef","union",

2
"unsigned","void","volatile","while"};
int i, flag = 0;
for(i = 0; i < 32; ++i){
if(strcmp(keywords[i], buffer) == 0){
flag = 1;
break;
}
}
return flag;
}

int main(){
char ch, buffer[15], operators[] = "+-*/%=";
FILE *fp;
int i,j=0;
fp = fopen("program.txt","r");
if(fp == NULL){
printf("error while opening the file\n");
exit(0);
}

while((ch = fgetc(fp)) != EOF){

for(i = 0; i < 6; ++i){

if(ch == operators[i])
printf("%c is operator\n", ch);
}

3
 if(isalnum(ch)){
buffer[j++] = ch;
}
else if((ch == ' ' || ch == '\n') && (j != 0)){
buffer[j] = '\0';
j = 0;

if(isKeyword(buffer) == 1)
printf("%s is keyword\n", buffer);
else
printf("%s is indentifier\n", buffer);
}

}
fclose(fp);
return 0;
}

4
OUTPUT:

RESULT:
Thus, a lexical analyzer to recognize a few patterns in C was successfully executed.

5
 EX: 1b IMPLEMENTATION OF SYMBOL TABLE

AIM: To write a C program to implement a symbol table.

ALGORITHM:
1. Start the Program.
2. Get the input from the user with the terminating symbol ‘$’.
3. Allocate memory for the variable by dynamic memory allocation function.
4. If the next character of the symbol is an operator then only the memory is allocated.
5. While reading, the input symbol is inserted into symbol table along with its memory address.
6. The steps are repeated till ”$”is reached.
7. To reach a variable, enter the variable to the searched and symbol table has been checked for
corresponding variable, the variable along its address is displayed as result.
8. Stop the program.

PROGRAM:
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<ctype.h>
#include<stdlib.h>
void main()
{
int x=0, n, i=0,j=0;
void *mypointer,*T4Tutorials_address[5];
char ch,T4Tutorials_Search,T4Tutorials_Array2[15],T4Tutorials_Array3[15],c;
printf("Input the expression ending with $ sign:");
while((c=getchar())!='$')
{

6
 T4Tutorials_Array2[i]=c;
i++;
}
n=i-1;
printf("Given Expression:");
i=0;
while(i<=n)
{
printf("%c",T4Tutorials_Array2[i]);
i++;
}
printf("\n Symbol Table display\n");
printf("Symbol \t addr \t type");
while(j<=n)
{
c=T4Tutorials_Array2[j];
if(isalpha(toascii(c)))
{
mypointer=malloc(c);
T4Tutorials_address[x]=mypointer;
T4Tutorials_Array3[x]=c;
printf("\n%c \t %d \t identifier\n",c,mypointer);
x++;
j++;
}
else
{
ch=c;

7
if(ch=='+'||ch=='-'||ch=='*'||ch=='=')
{
mypointer=malloc(ch);
T4Tutorials_address[x]=mypointer;
T4Tutorials_Array3[x]=ch;
printf("\n %c \t %d \t operator\n",ch,mypointer);
x++;
j++;
}}}}

8
OUTPUT:

RESULT:
Thus, the C program to implement the symbol table was executed and the output is verified.

9
 2. Implement a Lexical Analyzer using Lex Tool

AIM:
To write a C program to implement Lexical Analyzer using Lex Tool.

ALGORITHM:

STEP 1: Start the program.

STEP 2: Lex program consists of three parts.
a. Declaration %%
b. Translation rules %%
c. Auxiliary procedure.
STEP 3: The declaration section includes declaration of variables, constants and regular
definitions.
STEP 4: Translation rule of lex program are statements of the form
a. P1 {action}
b. P2 {action}
c. …
d. …
e. Pn {action}
STEP 5: Write a program in the vi editor and save it with .l extension.
STEP 6: Compile the lex program with lex compiler to produce output file as lex.yy.c. STEP 7:
Compile that file with C compiler with input.c and verify the output.

10
PROGRAM:
String \"[^\n"]+\"
id ([A-Za-z]|_)([A-Za-z]|[0-9]|_)*
num1 [+-]?[0-9]+\.?([eE][-+]?[0-9]+)?
num2 [+-]?[0-9]+\.[0-9]+([eE][-+]?[0-9]+)?
delim [ \t\n]+
%%
"#include" {
int i=0;
char c[20];
printf("\n %s \t preprocessor directive .",yytext);
while((c[i++]=input())!='>')
c[i]='\0';
printf("\n %s \t include file",c);
}
"#define" printf("\n %s \t preprocessor directive.",yytext);
"int"|"char"|"void" printf("\n %s \t Keyword",yytext);
"main"|"printf"|"scanf" printf("\n %s \t Function_call.",yytext);
"{" printf("\n %s \t Block Begin.",yytext);
"}" printf("\n %s \t Block End.",yytext);
{id} printf("\n %s \t Identifier",yytext);
","|"("|")"|";" printf("\n %s \t Seperator.",yytext);
"<"|">"|">="|"<="|"!="|"==" printf("\n %s \t Relational operator.",yytext);
"=" printf("\n %s \t assignment operator.",yytext);
{num1} printf("\n %s \t Numeric constant.",yytext);
{num2} printf("\n %s \t numeric constant.",yytext);
%%
int main(int argc,char **argv)

11
{
if(argc>1)
yyin=fopen(argv[1],"r");
else
{
printf("mention input filename");
exit(0);
}
yylex();
return 0;
}
int yywrap()
{
return 0;
}

INPUT FILE: ADD.C

#include<stdio.h>
main()
{
int a;
a=10;
printf("%d",a);
}

OUTPUT:
$ lex lex3.l
$ cc lex.yy.c

12
$ ./a.out add.c
#include preprocessor directive .
<stdio.h> include file
main Function_call.
( Seperator.
) Seperator.
{ Block Begin.
int Keyword
a Identifier
; Seperator.
a Identifier
= assignment operator.
10 Numeric constant.
; Seperator.
printf Function_call.
( Seperator.
"%d" string constant.
, Seperator.
a Identifier
) Seperator.
; Seperator.
} Block End.

13
Result:
Thus the program to implement lexical analyzer using lex tool has been successfully
executed and the output is verified.

14
 3. Implement an Arithmetic Calculator using LEX and YACC
AIM:
To write a program to implement calculator using lex and yacc.

ALGORITHM:
STEP 1: Start the program
STEP 2: Perform the calculations using both lex and yacc.
STEP 3: In the Lex code , tokens such as numbers and letters are returned.
STEP 4: In the Yacc code, validity of the statement is parsed.
STEP5: The calculation is performed and the result is displayed.
STEP6: Stop the program

PROGRAM:
3. a. $ vi 4cl.l:
%{
#include<stdio.h>
#include"y.tab.h"
int c;
extern int yylval;
%}
%%
[a-z] {c=yytext[0];
yylval=c-'a';
return(LETTER);
}
[0-9] {c=yytext[0];
yylval=c-'0';
return(DIGIT);

15
}
[^a-z 0-9 \b] {
c=yytext[0];
return(c);
}
%%

3. b. $ vi 4cy.y:
%{
#include<stdio.h>
int regs[26];
%}
%start list
%token DIGIT LETTER
%left '|'
%left '&'
%left '+''-'
%left '*''/''%'
%right UMINUS
%%
list:
|
list stat '\n'
|
list error '/n'
{
yyerror;
};

16
stat:expr
{
printf("%d\n",$1);
}
|
LETTER '=' expr
{
{
regs[$1]=$3;
};
expr:'('expr')'
{
$$=$2;
}
|
expr '*' expr
{
$$=$1*$3;
}
|
expr '/' expr
{
$$=$1/$3;
}
|
expr '%' expr
{
$$=$1%$3;

17
}
|
expr '+' expr
{
$$=$1+$3;
}
|
expr '-' expr
{
$$=$1-$3;
}
|
expr '&' expr
{
$$=$1&$3;
}
|
expr '|' expr
{
$$=$1|$3;
}
|
LETTER
{
$$=regs[$1];
}
|
number

18
;
number:DIGIT
{
$$=$1;
}
|
number DIGIT
{
$$=10*$1+$2;
};
%%
int main()
{
return(yyparse());
}
void yyerror(char *s)
{
fprintf(stderr,"%s \n",s);
}
int yywrap()
{
return(1);
}

19
OUTPUT:

Result:
Thus the program to implement a calculator has been successfully executed and the
output is verified.

20
 4. Generate three address code for a simple program using LEX and YACC.
AIM:
To convert BNF rules into Yacc form and to generate Abstract Syntax Tree.

ALGORITHM:

STEP 1: Start the program.

STEP 2: Lex program returns the specified tokens.
STEP 3: Yacc progam converts BNF rules to Yacc form by specifying syntactic rules.
STEP 4: Syntactic rules of Yacc program are statements of the form
a. P1 {action}
b. P2 {action}
c. …
d. …
e. Pn {action}
STEP 5: Source program in C is given as input.
STEP 6: Result is displayed in Quadruple representation of three address code.
STEP 7: Stop the program.

PROGRAM:
LEX PART:

%{
#include"y.tab.h"
#include<stdio.h>
#include<string.h>
int LineNo=1;
%}
identifier [a-zA-Z][_a-zA-Z0-9]*

21
number [0-9]+|([0-9]*\.[0-9]+)
%%
main\(\) return MAIN;
if return IF;
else return ELSE;
while return WHILE;
int |
char |
float return TYPE;
{identifier} {strcpy(yylval.var,yytext);
return VAR;}
{number} {strcpy(yylval.var,yytext);
return NUM;}
\< |
\> |
\>= |
\<= |
== {strcpy(yylval.var,yytext);
return RELOP;}
[ \t] ;
\n LineNo++;
. return yytext[0];
%%

YACC PART:
%{
#include<string.h>
#include<stdio.h>

22
struct quad
{
char op[5];
char arg1[10];
char arg2[10];
char result[10];

}QUAD[30];

struct stack

int items[100];

int top;

}stk;

int Index=0,tIndex=0,StNo,Ind,tInd;

extern int LineNo;

%}

23
%union

char var[10];

%token <var> NUM VAR RELOP

%token MAIN IF ELSE WHILE TYPE

%type <var> EXPR ASSIGNMENT CONDITION IFST ELSEST WHILELOOP

%left '-' '+'

%left '*' '/'

%%

PROGRAM : MAIN BLOCK

BLOCK: '{' CODE '}'

24
CODE: BLOCK

| STATEMENT CODE

| STATEMENT

STATEMENT: DESCT ';'

| ASSIGNMENT ';'

| CONDST

| WHILEST

DESCT: TYPE VARLIST

VARLIST: VAR ',' VARLIST

| VAR

25
ASSIGNMENT: VAR '=' EXPR{

strcpy(QUAD[Index].op,"=");

strcpy(QUAD[Index].arg1,$3);

strcpy(QUAD[Index].arg2,"");

strcpy(QUAD[Index].result,$1);

strcpy($$,QUAD[Index++].result);

EXPR: EXPR '+' EXPR {AddQuadruple("+",$1,$3,$$);}

| EXPR '-' EXPR {AddQuadruple("-",$1,$3,$$);}

| EXPR '*' EXPR {AddQuadruple("*",$1,$3,$$);}

| EXPR '/' EXPR {AddQuadruple("/",$1,$3,$$);}

| '-' EXPR {AddQuadruple("UMIN",$2,"",$$);}

| '(' EXPR ')' {strcpy($$,$2);}

26
| VAR

| NUM

CONDST: IFST{

Ind=pop();

sprintf(QUAD[Ind].result,"%d",Index);

Ind=pop();

sprintf(QUAD[Ind].result,"%d",Index);

| IFST ELSEST

IFST: IF '(' CONDITION ')' {

27
strcpy(QUAD[Index].op,"==");

strcpy(QUAD[Index].arg1,$3);

strcpy(QUAD[Index].arg2,"FALSE");

strcpy(QUAD[Index].result,"-1");

push(Index);

Index++;

BLOCK { strcpy(QUAD[Index].op,"GOTO"); strcpy(QUAD[Index].arg1,"");

strcpy(QUAD[Index].arg2,"");

strcpy(QUAD[Index].result,"-1");

push(Index);

Index++;

};

ELSEST: ELSE{

28
tInd=pop();

Ind=pop();

push(tInd);

sprintf(QUAD[Ind].result,"%d",Index);

BLOCK{

Ind=pop();

sprintf(QUAD[Ind].result,"%d",Index);

};

CONDITION: VAR RELOP VAR {AddQuadruple($2,$1,$3,$$);

StNo=Index-1;

| VAR

| NUM

29
;

WHILEST: WHILELOOP{

Ind=pop();

sprintf(QUAD[Ind].result,"%d",StNo);

Ind=pop();

sprintf(QUAD[Ind].result,"%d",Index);

WHILELOOP: WHILE'('CONDITION ')' {

strcpy(QUAD[Index].op,"==");

strcpy(QUAD[Index].arg1,$3);

strcpy(QUAD[Index].arg2,"FALSE");

30
strcpy(QUAD[Index].result,"-1");

push(Index);

Index++;

BLOCK {

strcpy(QUAD[Index].op,"GOTO");

strcpy(QUAD[Index].arg1,"");

strcpy(QUAD[Index].arg2,"");

strcpy(QUAD[Index].result,"-1");

push(Index);

Index++;

%%

31
extern FILE *yyin;

int main(int argc,char *argv[])

FILE *fp;

int i;

if(argc>1)

fp=fopen(argv[1],"r");

if(!fp)

printf("\n File not found");

exit(0);

yyin=fp;

32
}

yyparse();

printf("\n\n\t\t ----------------------------""\n\t\t Pos Operator \tArg1 \tArg2 \tResult" "\n\t\t--

------------------");

for(i=0;i<Index;i++)

printf("\n\t\t %d\t %s\t %s\t %s\t%s",i,QUAD[i].op,QUAD[i].arg1,QUAD[i].arg2,QUAD[i]

.result);

printf("\n\t\t -----------------------");

printf("\n\n"); return 0; }

void push(int data)

{ stk.top++;

if(stk.top==100)

33
printf("\n Stack overflow\n");

exit(0);

stk.items[stk.top]=data;

int pop()

int data;

if(stk.top==-1)

printf("\n Stack underflow\n");

exit(0);

34
}

data=stk.items[stk.top--];

return data;

void AddQuadruple(char op[5],char arg1[10],char arg2[10],char result[10])

strcpy(QUAD[Index].op,op);

strcpy(QUAD[Index].arg1,arg1);

strcpy(QUAD[Index].arg2,arg2);

sprintf(QUAD[Index].result,"t%d",tIndex++);

strcpy(result,QUAD[Index++].result);

yyerror()

35
printf("\n Error on line no:%d",LineNo);

INPUT:

main()

int a,b,c;

if(a<b)

a=a+b;

while(a<b)

a=a+b;

36
if(a<=b)

c=a-b;

else

c=a+b;

37
OUTPUT:

RESULT:
Thus the program to convert BNF rules into Yacc form and to generate Abstract Syntax
Tree is successfully executed and the output is verified.

38
5.Implementation of Simple Code Optimization Techniques (Constant Folding.,etc.)

AIM:

To write a C program to implement the code optimization techniques.

ALGORITHM:

1. Start
2. Create an input file which contains three address code.
3. Open the file in read mode.
4. If the file pointer returns NULL, exit the program else go to 5.
5. Scan the input symbol from the left to right.
Common Sub expression elimination
6. Store the first expression in a string.
7. Compare the string with the other expressions in the file.
8. If there is a match, remove the expression from the input file.
9. Perform these steps 5 to 8 for all the input symbols in the file.
Dead code Elimination
10. Scan the input symbol from the file from left to right.
11. Get the operand before the operator from the three address code.
12. Check whether the operand is used in any other expression in the three address code.
13. If the operand is not used, then eliminate the complete expression from the three address
code else go to 14.
14. Perform steps 11 to 13 for all the operands in the three address code till end of file is reached.
15.Stop..

39
PROGRAM

#include <stdio.h>
#include <conio.h>
#include <string.h >
struct op
{
char l;
char r[20];
}
op[10], pr[10];

void main()
{
int a, i, k, j, n, z = 0, m, q;
char * p, * l;
char temp, t;
char * tem;
clrscr();
printf("enter no of values");
scanf("%d", & n);
for (i = 0; i < n; i++)
{
printf("\tleft\t");
op[i].l = getche();
printf("\tright:\t");
scanf("%s", op[i].r);
}
printf("intermediate Code\n");
for (i = 0; i < n; i++)
{
printf("%c=", op[i].l);
printf("%s\n", op[i].r);
}
for (i = 0; i < n - 1; i++)
{
temp = op[i].l;
for (j = 0; j < n; j++)
{
p = strchr(op[j].r, temp);
if (p)
{
pr[z].l = op[i].l;
strcpy(pr[z].r, op[i].r);

40
 z++;

}
}
}
pr[z].l = op[n - 1].l;
strcpy(pr[z].r, op[n - 1].r);
z++;
printf("\nafter dead code elimination\n");
for (k = 0; k < z; k++)
{
printf("%c\t=", pr[k].l);
printf("%s\n", pr[k].r);
}

//sub expression elimination

for (m = 0; m < z; m++)
{
tem = pr[m].r;
for (j = m + 1; j < z; j++)
{
p = strstr(tem, pr[j].r);
if (p)
{
t = pr[j].l;
pr[j].l = pr[m].l;
for (i = 0; i < z; i++)
{
l = strchr(pr[i].r, t);
if (l) {
a = l - pr[i].r;
//printf("pos: %d",a);
pr[i].r[a] = pr[m].l;
}
}
}
}
}
printf("eliminate common expression\n");
for (i = 0; i < z; i++) {
printf("%c\t=", pr[i].l);
printf("%s\n", pr[i].r);
}
// duplicate production elimination

for (i = 0; i < z; i++)

41
{
for (j = i + 1; j < z; j++)
{
q = strcmp(pr[i].r, pr[j].r);
if ((pr[i].l == pr[j].l) && !q)

{
pr[i].l = '\0';
strcpy(pr[i].r, '\0');
}
}
}
printf("optimized code");
for (i = 0; i < z; i++)
{
if (pr[i].l != '\0') {
printf("%c=", pr[i].l);
printf("%s\n", pr[i].r);
} } getch();}

Output:

RESULT:
Thus, Implementation of Simple Code Optimization Techniques was executed sucessfully.

42
6. Implement back-end of the compiler for which the three address code is given as input
and the 8086 assembly language code is produced as output.

AIM:
To write a C program to implement the back end of the compiler

ALGORITHM:
1. Start the program
2. Get the three variables from statements and set the intermediate code
3. Execute the program
4. Target code for the given statement was produced
5. Stop the program

PROGRAM:
#include <stdio.h>
#include <stdlib.h>
#include<conio.h>
#include<string.h>

void main(){
char icode[10][30], str[20], opr[10];
int i=0;
printf("\nEnter the intermediate code:\n");
do{
scanf("%s",icode[i]);
}while(strcmp(icode[i++],"exit")!=0);
printf("\n target code generation");
printf("\n***********");

43
 i=0;
do{
strcpy(str,icode[i]);
switch(str[3]){
case '+':
strcpy(opr,"ADD");
break;
case '-':
strcpy(opr,"SUB");
break;
case '*':
strcpy(opr,"MUL");
break;
case '/':
strcpy(opr,"DIV");
break;
}
printf("\n\tMov %c,R%d",str[2],i);
printf("\n\tMov %s%c,R%d",opr,str[4],i);
printf("\n\tMov %R%d,%c",i,str[0]);
}while(strcmp(icode[++i],"exit")!=0);
getch();
}

44
OUTPUT:

RESULT: Thus, the program is compiled and executed successfully.

45
7. Generate Parsing table (LL or LR) – Content beyond syllabus
AIM: To generate parsing table for LL and LR

PROCEDURE:
A top-down parser that uses a one-token lookahead is called an LL(1) parser. The first L
indicates that the input is read from left to right. The second L says that it produces a left-to-right
derivation
LR parser is a bottom-up parser for context-free grammar that is very generally used by
computer programming language compiler and other associated tools. LR parser reads their
input from left to right and produces a right-most derivation

PROGRAM:
LL:
#include<stdio.h>
#define max 100
char NonTerminals[max],Terminals[max],production[max][max];
char follow[max];
int x=0,n;
void find_follow(char);
void find_first(char);

int main()
{

int i,j,k=0,length,flag,l,matrix[max][max];

printf("\nEnter the number of rules:- ");

scanf("%d",&n);

46
printf("\nEnter the rules one by one\n");
for(i=0;i<n;i++)
{
printf("%d:- ",i+1);
scanf("%s",production[i]);
flag=0;
for(l=0;l<k;l++)
{
if(NonTerminals[l]==production[i][0])
flag=1;
}
if(flag==0)
NonTerminals[k++]=production[i][0];
}
NonTerminals[k]='\0';
k=0;
printf("\n\n");
for(i=0;i<n;i++)
{
length=strlen(production[i]);
for(j=3;j<length;j++)
{
if(!(production[i][j]>=65 && production[i][j]<=90))
{
flag=0;
for(l=0;l<k;l++)
{
if(Terminals[l]==production[i][j])

47
 flag=1;
}
if(flag==0)
Terminals[k++]=production[i][j];
}

}
}
Terminals[k]='\0';

for(i=0;i<strlen(NonTerminals);i++)
{
for(j=0;j<n;j++)
{
if(NonTerminals[i]==production[j][0])
{
if(production[j][3]=='$')
{
Array_Manipulation('$');

find_follow(production[j][0]);
}
else
{
find_first(production[j][3]);

48
 for(l=0;l<strlen(Terminals);l++)
{
for(k=0;k<x;k++)
{
if(follow[k]==Terminals[l])
matrix[i][l]=j+1;
}
}
x=0;
}
}
x=0;
}
printf(" LL(1) PARSING TABLE\n\n");

for(i=0;i<strlen(Terminals);i++)
printf(" %c",Terminals[i]);
printf("\n\n");

for(i=0;i<strlen(NonTerminals);i++)
{
printf("%c ",NonTerminals[i]);
for(j=0;j<strlen(Terminals);j++)
if(matrix[i][j]==0)
printf(" ");
else
printf("%d ",matrix[i][j]);
printf("\n");

49
 }

void find_follow(char ch)

{
int i, j,length;

if(production[0][0] == ch)
{
Array_Manipulation('$');
}
for(i = 0; i < n; i++)
{
length = strlen(production[i]);
for(j = 3; j < length; j++)
{
if(production[i][j] == ch)
{
if(production[i][j + 1] != '$')
{
find_first(production[i][j + 1]);
}
if(production[i][j + 1] == '$' && ch != production[i][0])
{
find_follow(production[i][0]);
}
}

50
 }
}
}

void find_first(char ch)

{
int k;
if(!(isupper(ch)))
{
Array_Manipulation(ch);
}
for(k = 0; k <n; k++)
{
if(production[k][0] == ch)
{
if(production[k][3] == '$')
{
find_follow(production[k][0]);;
}
else if(islower(production[k][3]))
{
Array_Manipulation(production[k][3]);
}
else
{
find_first(production[k][3]);
}
}

51
 }
}

void Array_Manipulation(char ch)

{
int i;
for(i= 0;i< x;i++)
{
if(follow[i] == ch)
{
return;
}
}
follow[x++] = ch;
}

LR:
#include<stdio.h>
#include<conio.h>
#include<string.h>
#define row 100
#define col 100
#define NULL 0

struct data
{
int state_no;
int count;

52
 char items[row][col];
struct data *link2;
};

typedef struct data node;

void closure(char []);

void Goto(char [],int);
void CreateTable(int,char,char[],char[],char[]);

char Agumented[col]={'Q','-','>','.','S','$'};
int n,state=0,result=0;
char Grammar[row][col],P1[row][col],symbols[col],table[row][col],GrammarFinal[row][col];
node *start=NULL;

int main()
{
char str[30],stack[30],temp[col];
node *ptr1;

int i,j,NoOfSymbols,flag=0,k,size;

printf("\nEnter the number of rules:- ");

scanf("%d",&n);
fflush(stdin);
printf("\nEnter the Start Symbol:- ");
scanf("%c",&Agumented[4]);
fflush(stdin);

53
printf("Enter the terminal first Followed by Non terminals \n");
scanf("%s",symbols);
fflush(stdin);
printf("\nEnter the rules one by one\n");
for(i=0;i<n;i++)
{
printf("%d:- ",i+1);
scanf("%s",temp);
size=strlen(temp);

strcpy(GrammarFinal[i],temp);
GrammarFinal[i][size-1]='.';
GrammarFinal[i][size]='$';
GrammarFinal[i][size+1]='\0';

for(j=0;j<=size+1;j++)
{
if(j==3)
Grammar[i][j]='.';
if(j>3)
Grammar[i][j]=temp[j-1];
if(j<3)
Grammar[i][j]=temp[j];
if(j==strlen(temp)+1)
Grammar[i][j]='\0';
}
}

54
closure(&Agumented[0]);

ptr1=start; // GOTO Function call

while(ptr1!=NULL)
{
for(i=0;i<ptr1->count;i++)
{
Goto(ptr1->items[i],ptr1->state_no);
}
ptr1=ptr1->link2;
}

ptr1=start;
printf("\n");
while(ptr1!=NULL)
{
printf("<-------------STATE %d----------------------->\n",ptr1->state_no);
for(i=0;i<ptr1->count;i++)
{
printf("%s\n",ptr1->items[i]);
}
ptr1=ptr1->link2;
}
printf("\n PARSING TABLE \n"); // Printing Parsing Table
for(j=0;j<strlen(symbols);j++)
{
printf("%c ",symbols[j]);
}

55
 printf("\n");

for(i=0;i<=state;i++)
{
for(j=0;j<strlen(symbols);j++)
{
printf("%c",table[i][j*4]);
printf("%c",table[i][(j*4)+1]);
printf("%c ",table[i][(j*4)+2]);
}
printf("\n");
}
if(result==0)
printf("The Given Grammar is LR(0)\n");
else
printf("The Given Grammar is Not LR(0)\n");

return 0;
}

void closure(char a[])

{
int i,j,k,c1=0,n1=0,flag=0,z;
node *ptr,*ptr1=start;

56
ptr=(node *)malloc(sizeof(node));
ptr->state_no=state;
ptr->link2=NULL;
strcpy(ptr->items[c1],a);
c1++;

strcpy(P1[n1],a);
n1++;

for(k=0;k<n1;k++)
{
flag=0;
for(i=0;i<strlen(P1[k]);i++)
{
if(P1[k][i]=='.' && P1[k][i+1]!='$')
{
for(z=1;z<n1;z++)
{
if(P1[z][0]==P1[k][i+1])
{
flag=1;
break;
}
}
if(flag==0)
{
for(j=0;j<n;j++)
{

57
 if(P1[k][i+1]==Grammar[j][0])
{
strcpy(P1[n1],Grammar[j]);
n1++;
strcpy(ptr->items[c1],Grammar[j]);
c1++;
}
}
}

break;
}
}
}

ptr->count=c1;
if(start==NULL)
{
start=ptr;
}
else
{
while(ptr1->link2!=NULL)
ptr1=ptr1->link2;

ptr1->link2=ptr;
}
}

58
void Goto(char a[],int s_no)
{
char b[col],temp,buffer[3];
int i,flag=0,j,pos=0,k;
node *ptr1;

for(i=0;i<strlen(a);i++)
{
if(a[i]=='.' && a[i+1]!='$')
{
b[i]=a[i+1];
temp=a[i+1];
b[i+1]='.';
i=i+1;
}
else
{
b[i]=a[i];
}
}
b[i]='\0';

ptr1=start;
while(ptr1!=NULL)
{
if(strcmp(b,ptr1->items[0])==0)
{

59
 flag=1;

sprintf(buffer,"%d",ptr1->state_no);
CreateTable(s_no,temp,buffer,a,b);

break;
}
ptr1=ptr1->link2;
}

if(flag==0)
{
state++;

sprintf(buffer,"%d",state);
CreateTable(s_no,temp,buffer,a,b);

closure(&b[0]);
}
}

void CreateTable(int s_no,char temp,char buffer[],char a[],char b[])

{
int k,flag=0,i;

for(k=0;k<strlen(symbols);k++)
{
if(temp==symbols[k])

60
 {
flag=1;
break;
}
}
if(flag==0)
{
printf("Enter the symbols correctly \n");
printf("%s %s",temp,symbols[k]);
exit(0);
}

if(temp>=65 && temp<=90) //Goto Phase

{
table[s_no][k*4]=' ';
table[s_no][(k*4)+1]=buffer[0];
table[s_no][(k*4)+2]=buffer[1];
}
else if(strcmp(a,b)==0) //Reduce Phase
{
for(i=0;i<n;i++)
{
if(strcmp(a,GrammarFinal[i])==0)
{
sprintf(buffer,"%d",i+1);
break;
}

61
 }
for(k=0;k<strlen(symbols);k++)
{
if(a[0]=='Q' && symbols[k]=='$')
{
table[s_no][k*4]='A';
}
else if(a[0]!='Q')
{
if((symbols[k]>=97 && symbols[k]<=122)||(symbols[k]>=35 && symbols[k]<=57))
{
if(table[s_no][k*4]=='r'|| table[s_no][k*4]=='s')
result=1;
table[s_no][k*4]='r';
table[s_no][(k*4)+1]=buffer[0];
table[s_no][(k*4)+2]=buffer[1];
}
else
break;
}
}
}
else if(strcmp(a,b)!=0) //Shift Phase
{
if(table[s_no][k*4]=='r'|| table[s_no][k*4]=='s')
result=1;
table[s_no][k*4]='s';
table[s_no][(k*4)+1]=buffer[0];

62
 table[s_no][(k*4)+2]=buffer[1];
}

OUTPUT:

63
RESULT:
Thus, parsing tables for LL and LR are generated.

64
MINI PROJECT REPORT

Problem Statement and Introduction

To implement a Compiler for C++ using Lex, Yacc and C++ as the language to code the
compiler in. The input could be any valid C++ Program with Functions, Conditions and Looping
constructs. The output would be the expected output from “g++” when run on a standard Unix
shell.

Architecture of the Language

The syntax is the same as C++, for all the constructs that we are focusing on. We have made sure
to implement the semantics of the language as close to ISO C++ as possible. We have handled
all errors and border cases for every construct in our language and have added many error
checking mechanisms too.

Grammar

We used a regular Backus Normal Form Grammar to develop the entire language. Most of the
productions inspired by ISO C++ and a few constructs that we created to provide some novelty
to our project.
The grammar has been pasted below:

preprocessing-token:

#include header-name
#define literal literal

declaration-statement:
attribute declaration-specifier

function-definition:
keyword identifier (identifier-sequence) function-body

function-body:
compound-statement

token:
identifier

65
 keyword
literal
operator-token
punctuator

header-name:
< string-path >
" string-path "

identifier:

identifier-nondigit
identifier digit

statement:
labeled-statement
expression-statement
compound-statement
selection-statement
iteration-statement
jump-statement

labeled-statement
identifier : statement

compound-statement:
{ statement-seq }

statement-seq:
statement
statement-seq statement

selection-statement:
if ( condition ) statement
if ( condition ) statement else statement

condition:
expression
type-specifier-seq declarator = assignment-expression

iteration-statement:
while ( condition ) statement
for ( for-range-declaration : for-range-initializer ) statement

for-range-declaration:
attribute-specifier-seqopt type-specifier-seq declarator

66
for-range-initializer:
expression braced-init-list

jump-statement:
break ;
continue ;
return expressionopt ;
return braced-init-listopt ;

expression:
multiplicative-expression
additive-expression
relational-expression
equality-expression
logical-and-expression
logical-or-expression
conditional-expression
assignment-expression

multiplicative-expression:
pm-expression
multiplicative-expression * pm-expression
multiplicative-expression / pm-expression
multiplicative-expression % pm-expression

additive-expression:
multiplicative-expression
additive-expression + multiplicative-expression
additive-expression - multiplicative-expression

relational-expression:
shift-expression
relational-expression < shift-expression
relational-expression > shift-expression
relational-expression <= shift-expression
relational-expression >= shift-expression

equality-expression:
relational-expression
equality-expression == relational-expression
equality-expression != relational-expression

logical-and-expression:
Inclusive-or-expression
logical-and-expression && inclusive-or-expression

67
logical-or-expression:
logical-and-expression
logical-or-expression || logical-and-expression

conditional-expression:
logical-or-expression
logical-or-expression ? expression : assignment-expression

assignment-expression:
Conditional-expression
logical-or-expression assignment-operator initializer-clause
throw-expression

assignment-operator:
=
*=
/=
%=
+=
-=
>>=
<<=
&=
^=
|=

identifier-nondigit:
nondigit

nondigit:
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q

68
 r
s
t
u
v
w
x
y
z

id-expression:
identifier

Identifier-digit:
0
1
2
3
4
5
6
7
8
9

keyword:
bool
break
char
continue
double
else
false
float
for
if
int
long
return
true
void

punctuator:
{
}
[
]

69
 #
(
)
;
:
?

literal:
integer-literal
character-literal
floating-literal
string-literal
boolean-literal

integer-literal:
decimal-literal integer-suffixopt

decimal-literal:
nonzero-digit
decimal-literal digit

nonzero-digit:
1
2
3
4
5
6
7
8
9

c-char:
any member of the source character set except the single quote ', backslash \, or new-line
character
escape-sequence
universal-character-name

escape-sequence:
simple-escape-sequence

simple-escape-sequence:
\'
\"
\\
\n
\t

70
sign:
+
-

digit-sequence:
digit
digit-sequence digit

string-literal:
s-char-sequence

s-char-sequence:
s-char
s-char-sequence s-char

s-char:
any member of the source character set except the double-quote ", backslash \, or new-
line character
escape-sequence
universal-character-name

boolean-literal:
false
true

71
Design Strategies and Implementation Details

Symbol Table Generation

We are using a linked list of structures to implement our Symbol Table. It is created on the Heap
and is called to a print function just before the compilation ends. The print function outputs a
formatted symbol table to STDOUT.

A node of the symbol table has the following structure.

1. Line
2. Name
3. Scope (-1 for Global, 0 for Main and >0 for extraneous scopes)
4. Value
5. ID
6. Data Type

Which is displayed in a tabular form during the end of the program to represent the symbol table
that has been generated during the first phase.
We store the entire table in a dynamic list-esque data structure.

Abstract Syntax Tree

The syntax tree is generated entirely using Yacc. We create an Abstract Syntax Tree data
structure to store the Syntax Tree, which is essentially something that mimics the way Yacc
parses the grammar.
The treeNode has:
1. nodeType
2. string
3. value
4. dataType
5. lineNo
6. Nchildren
Every production is evaluated to the tree. So, as soon as we encounter a non-terminal, we process
the expression through the Yacc grammar to generate nodes in the AST. It contains all the meta
data as enumerated above. We basically use Dollar variables ($) in Yacc that is used to store the
various tokens and expressions that we parse along the way.

72
To print (export) the syntax tree as a text file, we essentially print all the above information to a
single line for every node and use indentation to mimic a “tree” visualization. All of this is
exported to a single file in the root directory.
The print function uses a structure that contains the follows:
1. Line Number
2. nodeType
3. string
4. value
5. dataType
Upon compilation, the tree is then printed out to a file, as a graphically accurate representation of
a tree.

Intermediate Code Generation

Intermediate Code Generation is implemented using various functions and data structures that
are used to generate and store the Intermediate Codes. We have a list of structures of type
Quadruple to store the Quadruples generated by the compiler. Several functions are used to
accomplish the required processing. We then use a print function that neatly formats the IC and
prints it onto STDOUT.

Error Handling

[TYPE HERE]

Target Code Generation

[TYPE HERE]

73
Sample Input

74
Ab
75
stract Syntax Tree Output

76
Phase 1&2 Lex Analysis

Token Generation

Lno.l
%option noyywrap

%{

int line_num = 1;

%}

%%

"/*"+([^*]|\*+[^/])*\*+\/.*\n

"//"(.)*(\n)

"\n" {fprintf(yyout, "%s %d", yytext, line_num);printf("%s %d", yytext,

line_num);line_num++;}

%%

77
int main(){

yyin = fopen("Output.cpp", "r");

yyout = fopen("output3.cpp", "w");

fprintf(yyout, " %d", line_num++);

yylex();

return 0;

Uncomment.l
%option noyywrap

%{

#include<stdio.h>

78
#include <strings.h>

%}

start \/\*

end \*\/

%%

"/*"+([^*]|\*+[^/])*\*+\/.*\n {fprintf(yyout, "");printf("\n New Comment - %s\n", yytext);}

"//"(.)*(\n) {fprintf(yyout, "");}

. {fprintf(yyout, "%s", yytext);}

%%

79
int main()

extern FILE *yyin, *yyout;

yyin = fopen("input.cpp", "r");

yyout = fopen("Output.cpp", "w");

yylex();

return 0;

Gensym.l- Convert input stream to valid datatypes

80
%option noyywrap

%{

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include "y.tab.h"

extern int yylval;

int x = 0;

int scope = 0;

int nl =1;

struct node{

int nl;

char name[100];

81
int scope;

int value;

char type[100];

struct node *next;

};

char *token;

typedef struct node node;

struct list{

node* head;

};

typedef struct list list1;

struct list* list2;

82
int exists(list1* root, char name[100], int value){

if(root == NULL || root->head == NULL){

return 0;

node *t2 = root->head;

while(t2!=NULL){

if(strcmp(t2->name, name) == 0){

t2->value = value;

return 1;

t2 = t2->next;

83
return 0;

void removespaces(char name[100]){

const char *d = name;

do{

while(*d == ' '){

++d;

}while (*name++ = *d++);

void insert(list1 *root, int nl, char name[100], int scope, int value, char type[100]){

removespaces(name);

84
int out = exists(root, name, value);

if(out == 0){

node *temp = (node*)malloc(sizeof(node));

temp->nl = nl;

temp->scope = scope;

temp->value = value;

strcpy(temp->name, name);

strcpy(temp->type, type);

temp->next = NULL;

if(root->head == NULL){

root->head = temp;

return;

85
node *t2 = root->head;

while(t2->next!=NULL){

t2 = t2->next;

t2->next = temp;

return;

void print(node *head){

node *temp = head;

printf("______________________________________\n");

printf("| Line | Name | Scope | value | type |\n");

printf("--------------------------------------\n");

86
while(temp!=NULL){

printf("| %d | %s | %d | %d | %s |\n", temp->nl, temp->name, temp->scope, temp->value,

temp->type);

temp=temp->next;

%}

datatype "int"|"float"|"char"

identifier [_a-zA-Z][_a-zA-Z0-9]*

%%

"int" { fprintf(yyout, ">KEYWORD INT\n");}

"float" {fprintf(yyout, ">KEYWORD float\n");}

"char" {fprintf(yyout, ">KEYWORD char\n");}

"while" return WHILE;

87
"do" return DO;

"if" return IF;

"for" return FOR;

"else" return ELSE;

"#include"(.)*"\n" fprintf(yyout, "> PRE_PROC_DIR %s\n", yytext);

\"[_a-zA-Z0-9$#@!%^&*]*\" fprintf(yyout, ">STRING LITERAL %s", yytext);

"(" fprintf(yyout, "> OPEN_PAR (\n");

")" fprintf(yyout, "> CLOSED_PAR )\n");

";" fprintf(yyout, "> SEMI_COLON ;\n");

"." fprintf(yyout, "> DOT_OPER .\n");

"{" {scope++; fprintf(yyout, "> OPEN_SCOPE {\n");}

"}" {scope--; fprintf(yyout, "> CLOSE_SCOPE }\n");}

"," fprintf(yyout, "> COMMA ,\n");

88
"[" fprintf(yyout, "> ARR_SUB_ST [\n");

"]" fprintf(yyout, "> ARR_SUB_END ]\n");

"\n" nl++;

[_a-zA-Z][_a-zA-Z0-9]* {fprintf(yyout, "> IDENTIFIER %s\n", yytext); insert(list2,

nl,yytext, scope, -1, "VAR");}

[_a-zA-Z][_a-zA-Z0-9]*" "*"="" "*[0-9]+"."*[0-9]* {token = strtok(yytext, "=");

fprintf(yyout, "> IDENT %s\n", token); token = strtok(NULL, "="); int val =
atoi(token);fprintf(yyout, ">LITERAL %d\n", val);insert(list2, nl,yytext, scope, val,
"VAR");}

[_a-zA-Z][_a-zA-Z0-9]*"(" {token = strtok(yytext, "("); fprintf(yyout, "> IDENT %s\n",

token); insert(list2, nl, token, scope, -1, "FUNCT");}

%%

int main(){

list2 = (struct list*)malloc(sizeof(struct list));

list2->head = NULL;

89
yyin = fopen("Output.cpp", "r");

yyout = fopen("tokens.txt", "w");

yylex();

print(list2->head);

}
Phase 3
Phase3.l
D [0-9]

NZ [1-9]

L [a-zA-Z_]

A [a-zA-Z_0-9]

WS [ \t\v\n\f]

TE [a-zA-Z_0-9!@#$%^&* \t\v\n\f]

%option yylineno

90
%{

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include "syntax_tree.tab.h"

int yywrap();

int scope = 0;

void printToken(char* type){

FILE *fp = fopen("tokens.txt", "a");

fprintf(fp," <token line=\"%d\" type=\"%s\" string=\"%s\" />\n",

yylineno,

type,

yytext);

91
fclose(fp);

static void comment(void);

%}

%%

"/*" { comment(); }

"//".* { /* consume //-comment */ }

"if" {printToken("IF"); return(IF); }

"else" {printToken("ELSE"); return(ELSE);}

"while" {printToken("WHILE"); return(WHILE);}

"return" {printToken("RETURN"); return(RETURN);}

"void" {printToken("VOID");yylval.str = strdup(yytext);

92
return(VOID);}

"int" {printToken("INT");yylval.str = strdup(yytext);

return(INT);}

"float" {printToken("FLOAT");yylval.str = strdup(yytext);

return(FLOAT);}

"char" {printToken("CHAR"); yylval.str=strdup(yytext); return(CHAR);}

"for" {printToken("FOR"); return FOR;}

"class" {printToken("CLASS"); return CLASS;}

"++" {printToken("INC_OP");return INC_OP;}

"--" {printToken("DEC_OP");return DEC_OP;}

"+" {printToken("PLUS");return PLUS;}

"-" {printToken("MINUS");return MINUS; }

"*" {printToken("STAR");return STAR; }

93
"/" {printToken("SLASH");return SLASH; }

"<" {printToken("LT");return LT; }

"<=" {printToken("LTEQ"); return LTEQ;}

">" {printToken("GT");return GT;}

">=" {printToken("GTEQ");return GTEQ;}

"==" {printToken("EQ");return EQ;}

"!=" {printToken("NEQ");return NEQ;}

"=" {printToken("ASSIGN");return ASSIGN;}

"<<" {printToken("INSERTION"); return INSERTION;}

">>" {printToken("EXTRACTION"); return EXTRACTION;}

"cin" {printToken("CIN"); return CIN;}

"cout" {printToken("COUT"); return COUT;}

("[") {printToken("LSQUAR");return LSQUAR; }

94
("]") {printToken("RSQUAR");return RSQUAR;}

("{") {printToken("LBRACE");scope++; return LBRACE;}

("}") {printToken("RBRACE");scope--; return RBRACE;}

";" {printToken("SEMI");return SEMI;}

"," {printToken("COMMA");return COMMA;}

"(" {printToken("LPAREN");return LPAREN;}

")" {printToken("RPAREN");return RPAREN; }

"endl" {printToken("ENDL"); return ENDL;}

{L}{A}* {printToken("ID");yylval.str = strdup(yytext); return ID;}

{D}+ {printToken("NUMBER");yylval.str = strdup(yytext); return NUM;}

{D}*"."{D}+ {printToken("FLOATINGPOINT");yylval.str = strdup(yytext); return FLT;}

\"{TE}*{WS}*\" {printToken("String"); yylval.str = strdup(yytext); return STR;}

{WS}+ {}

. {printToken("UNKNOWN LEXEME");printToken(yytext);}

95
%%

#include<stdio.h>

int yywrap() {

return 1;

static void comment(void)

int c;

96
while ((c = input()) != 0)

if (c == '*')

while ((c = input()) == '*')

if (c == '/')

return;

if (c == 0)

break;

printf("unterminated comment");

97
exit(-1);

Phase 4 Intermediate Code Generation

Generate three address code

Phase4.l

D [0-9]
NZ [1-9]
L [a-zA-Z_]
A [a-zA-Z_0-9]
WS [ \t\v\n\f]
TE [a-zA-Z_0-9!@#$%^&* \t\v\n\f]
%option yylineno

%{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "int_code.tab.h"
int yywrap();
int scope = 0;
void printToken(char* type){
FILE *fp = fopen("tokens.txt", "a");
fprintf(fp," <token line=\"%d\" type=\"%s\" string=\"%s\" />\n",
yylineno,
type,
yytext);

98
 fclose(fp);
}
static void comment(void);
%}
%%

"/*" { comment(); }
"//".* { /* consume //-comment */ }

"if" {printToken("IF"); return(IF); }

"else" {printToken("ELSE"); return(ELSE);}
"while" {printToken("WHILE"); return(WHILE);}
"return" {printToken("RETURN"); return(RETURN);}
"void" {printToken("VOID");yylval.str = strdup(yytext);
return(VOID);}
"int" {printToken("INT");yylval.str = strdup(yytext);
return(INT);}
"float" {printToken("FLOAT");yylval.str = strdup(yytext);
return(FLOAT);}
"char" {printToken("CHAR"); yylval.str=strdup(yytext); return(CHAR);}
"for" {printToken("FOR"); return FOR;}
"class" {printToken("CLASS"); return CLASS;}
"++" {printToken("INC_OP");return INC_OP;}
"--" {printToken("DEC_OP");return DEC_OP;}
"+" {printToken("PLUS");return PLUS;}
"-" {printToken("MINUS");return MINUS; }
"*" {printToken("STAR");return STAR; }
"/" {printToken("SLASH");return SLASH; }

99
"<" {printToken("LT");return LT; }
"<=" {printToken("LTEQ"); return LTEQ;}
">" {printToken("GT");return GT;}
">=" {printToken("GTEQ");return GTEQ;}
"==" {printToken("EQ");return EQ;}
"!=" {printToken("NEQ");return NEQ;}
"=" {printToken("ASSIGN");return ASSIGN;}
"<<" {printToken("INSERTION"); return INSERTION;}
">>" {printToken("EXTRACTION"); return EXTRACTION;}
"cin" {printToken("CIN"); return CIN;}
"cout" {printToken("COUT"); return COUT;}

("[") {printToken("LSQUAR");return LSQUAR; }

("]") {printToken("RSQUAR");return RSQUAR;}
("{") {printToken("LBRACE");scope++; return LBRACE;}
("}") {printToken("RBRACE");scope--; return RBRACE;}
";" {printToken("SEMI");return SEMI;}
"," {printToken("COMMA");return COMMA;}
"(" {printToken("LPAREN");return LPAREN;}
")" {printToken("RPAREN");return RPAREN; }
"endl" {printToken("ENDL"); return ENDL;}
{L}{A}* {printToken("ID");yylval.str = strdup(yytext);
return ID;}
{D}+ {printToken("NUMBER");yylval.str = strdup(yytext); return NUM;}
{D}*"."{D}+ {printToken("FLOATINGPOINT");yylval.str = strdup(yytext); return FLT;}
\"{TE}*{WS}*\" {printToken("String"); yylval.str = strdup(yytext); return STR;}
{WS}+ {}
. {printToken("UNKNOWN
LEXEME");printToken(yytext);}

100
%%
#include<stdio.h>

int yywrap() {
return 1;
}

static void comment(void)

{
int c;

while ((c = input()) != 0)

if (c == '*')
{
while ((c = input()) == '*')
;

if (c == '/')
return;

if (c == 0)
break;
}
printf("unterminated comment");
exit(-1);

101
}

Quadruple format (Done)

%{
// TBD DIFFERENT ENTRIES FOR LOCAL AND GLOBAL VARIABLES
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
#include "lex.yy.c"
//typedef char* string;
//#define YYSTYPE string
#define STR(VAR) (#VAR)
#define release 1
#define MAXCHILD 10
FILE *syntree;
extern void yyerror(const char *); /* prints grammar violation message */
extern int yylex(void);
extern FILE *yyin;
extern FILE *yyout;
extern int yylineno;

int iasval, itermval, iexpval;

char casval, ctermval, cexpval;
float fasval, ftermval, fexpval;
int cflag=0, iflag=0, fflag=0;

102
char* tab=" ";
char indent[100]="";
char type[200];
char* integer="INT";
char* floating="float";
char* none = "none";
char* assign = "=";
int expval=0;
int errors = 0;

struct node{
int nl;
char name[100];
char dtype[200];
int scope;
int value;
float fvalue;
char cvalue;
char type[100];
struct node *next;

};
typedef struct node node;
struct list{
node* head;
};

typedef struct list list1;

103
struct list* list2 = NULL;

int exists(list1* root, char name[100], int scope){

if(root == NULL || root->head == NULL){
return 0;
}
node *t2 = root->head;
while(t2!=NULL){
if(strcmp(t2->name, name) == 0 && t2->scope == scope){

return 1;
}
t2 = t2->next;
}
return 0;

}
node* find(list1 *root, char name[200], int scope){
if(root == NULL || root->head == NULL){
return NULL;
}
node *t2 = root->head;
while(t2!=NULL){
if(strcmp(t2->name, name)==0 && t2->scope == scope){return t2;}
t2 = t2->next;
}
t2 = root->head;

104
 while(t2!=NULL){
if(strcmp(t2->name, name)==0){
return t2;
}
t2 = t2->next;
}
return t2;

}
node* id_ex;
void insert(list1 *root, int nl, char name[100], char dtype[200], int scope, int value, float fvalue,
char cvalue, char type[100]){
int out = exists(root, name, scope);

if(out == 0){
node *temp = (node*)malloc(sizeof(node));
temp->nl = nl;
temp->scope = scope;
strcpy(temp->dtype, dtype);
if(strcmp(type, "int") == 0)

temp->value = value;
else if(strcmp(type, "float")==0)

temp->fvalue = fvalue;
else if(strcmp(type, "char")==0)

temp->cvalue = cvalue;
strcpy(temp->name, name);

105
 strcpy(temp->type, type);
temp->next = NULL;
if(root->head == NULL){
root->head = temp;
return;
}
node *t2 = root->head;
while(t2->next!=NULL){
t2 = t2->next;
}
t2->next = temp;
return;

}
else{
errors++;
printf("Error at line %d: Multiple declarations\n", nl);
}
}

void update(list1 *root, char name[100], int scope, int value, float fvalue, char cvalue){
node *t2 = root->head;
if(find(root, name, scope) == NULL){
return;
}
while(strcmp(t2->name, name)!=0){
t2 = t2->next;
}

106
 if(strcmp(t2->dtype, "int") == 0)
t2->value = value;
else if(strcmp(t2->dtype, "float")==0)
t2->fvalue = fvalue;
else if(strcmp(t2->dtype, "char")==0)
t2->cvalue = cvalue;

return;
}

void print(node *head){

// printf("1\n");
node *temp = head;
printf("____________________________________________________\n");
printf("| Line | Name | Scope | value | id_type | datatype |\n");
printf("----------------------------------------------------\n");
while(temp!=NULL){

if(strcmp(temp->dtype, "int")==0)

printf("| %d | \"%s\" | %d | %d | %s | %s |\n", temp->nl, temp->name, temp-

>scope, temp->value, temp->type, temp->dtype);
else if(strcmp(temp->dtype, "float")==0)
printf("| %d | \"%s\" | %d | %.1f | %s | %s |\n", temp->nl, temp->name, temp-
>scope, temp->fvalue, temp->type, temp->dtype);
else if(strcmp(temp->dtype, "char")==0)
printf("| %d | \"%s\" | %d | %c | %s | %s |\n", temp->nl, temp->name, temp-
>scope, temp->cvalue, temp->type, temp->dtype);
else

107
 printf("| %d | \"%s\" | %d | -- | %s | %s |\n", temp->nl, temp->name, temp-
>scope, temp->type, temp->dtype);
temp=temp->next;
}
}

struct expression_details{
int value;
char type[200];
};
typedef struct expression_details exp_det;
exp_det det1;

%}
%code requires {

}
%union{
char chr;
int integer;
float ft;
char *str;
}

%token IF ELSE WHILE RETURN VOID INT FLOAT CHAR FOR

%token INC_OP DEC_OP PLUS MINUS STAR SLASH LT LTEQ GT GTEQ EQ NEQ
ASSIGN

108
%token SEMI COMMA LPAREN RPAREN LSQUAR RSQUAR LBRACE RBRACE
LCOMMENT RCOMMENT
%token <str> ID NUM FLT
%token LETTER DIGIT
%token NONTOKEN ERROR ENDFILE
%token NL ENDL
%token STR
%token INSERTION EXTRACTION
%token CIN COUT
%token CLASS
%left PLUS MINUS
%left STAR SLASH

%nonassoc THEN
%nonassoc ELSE

%type<integer> atree program external_declaration var_declaration init_declarator_list

fun_declaration params_list compound_stmt declarator params block_item_list block_item call
factor term additive_expression simple_expression unary_expression postfix_expression
assignment_expression return_stmt while_stmt if_stmt expression statement args
expression_stmt for_stmt
%type<str> relop declaration_specifiers stream_constructs op

%start atree
%%

atree:program {}

109
program
: external_declaration {$$=$1; }
| program external_declaration { }
| class_declaration{}
| program class_declaration{}
;

external_declaration
: var_declaration {$$=$1; }
| fun_declaration {$$=$1;}
;
class_declaration
: declaration_specifiers ID LBRACE external_declaration RBRACE SEMI {insert(list2,
yylineno, $2, "class", scope, -1, 0.0, '\0', "class");}
var_declaration
: declaration_specifiers init_declarator_list SEMI
{}
| declaration_specifiers array_dec SEMI
| error SEMI{yyerrok;}
;
array_dec
: ID LSQUAR NUM RSQUAR {insert(list2, yylineno, $1, type, scope, -1, 0.0, '\0',
"ARRAY");}
| STAR ID {insert(list2, yylineno, $2, type, scope, -1, 0.0, '\0', "PTR");}

init_declarator_list
: ID {insert(list2, yylineno, $1, type, scope, -1,0.0,'\0', "IDENT");}

110
 | ID ASSIGN expression {
insert(list2, yylineno, $1, type, scope, -1,0.0,'\0', "IDENT");
update(list2, $1, scope, iexpval, fexpval, cexpval);
iflag = 0;
fflag = 0;
cflag = 0;
}
| init_declarator_list COMMA ID{ insert(list2, yylineno, $3, type, scope, -1,0.0,'\0',
"IDENT"); }

declarator
: LPAREN RPAREN {}
| LPAREN params RPAREN {}
;

fun_declaration
: declaration_specifiers ID declarator compound_stmt {insert(list2, yylineno, $2, type, scope, -
1, 0.0, '\0', "FUNCT");}
;

declaration_specifiers
: INT {$$=integer; strcpy(type, "int");}
| VOID {$$="VOID"; strcpy(type, "void");}
| FLOAT {$$="float"; strcpy(type, "float");}
| CHAR {$$="char"; strcpy(type, "char");}
| CLASS {$$="class"; strcpy(type, "class");}
;

111
params_list
: INT ID {}
| FLOAT ID {}
| params_list COMMA INT ID {}
| params_list COMMA FLOAT ID {}

params
: params_list {$$=$1;}
| VOID {}
;

compound_stmt
: LBRACE RBRACE {}
| LBRACE block_item_list RBRACE {$$ = $2;}
;

block_item_list
: block_item {$$ = $1; }
| block_item_list block_item {}
;

block_item
: var_declaration {$$=$1; }
| statement {$$=$1;}
;

112
statement
: expression_stmt {$$=$1;}
| compound_stmt {$$=$1;}
| if_stmt {$$=$1;}
| while_stmt {$$=$1;}
| return_stmt {$$=$1;}
| for_stmt {$$ = $1;}
| stream_constructs {$<str>$ = $1;}
;
stream_constructs
: cout_cascade
| cin
cout_cascade
: COUT cascade_out SEMI
cascade_out
: INSERTION op {if(errors==0) printf("%s", $2);}
| INSERTION op cascade_out {if(errors==0) printf("%s", $2);}
| INSERTION op INSERTION ENDL {if(errors==0) printf("%s\n", $2);}

cin
: CIN EXTRACTION ID SEMI {
id_ex = find(list2, $3, scope);
if(id_ex == NULL){
printf("Error in Line %d: Usage before
Declaration\n", yylineno);
errors++;
}
else{

113
 int a;
char b;
float c;
if(strcmp(id_ex->dtype, "int") == 0){

scanf("%d", &a);
id_ex->value = a;
}
if(strcmp(id_ex->dtype, "float") == 0){
scanf("%f", &c);
id_ex->fvalue = c;
}
if(strcmp(id_ex->dtype, "char")==0){
scanf("%c", &b);
id_ex->cvalue = b;
}
}
}

op
:NUM {$<str>$ = yylval.str;}
|STR {$<str>$ = yylval.str;}
|ID {
id_ex = find(list2, $1, scope);
if(id_ex == NULL){
printf("Error in Line %d: Usage before Declaration\n", yylineno);
errors++;
}

114
 else{
if(strcmp(id_ex->dtype, "int") == 0) $<str>$ = id_ex->value;
if(strcmp(id_ex->dtype, "float") == 0) $<ft>$ = id_ex->fvalue;
if(strcmp(id_ex->dtype, "char") == 0) $<str>$ = id_ex->cvalue;

expression_stmt
: SEMI {}
| expression SEMI {$$=$1;}

if_stmt
: IF LPAREN expression RPAREN statement ELSE statement { }
| IF LPAREN expression RPAREN statement %prec THEN {}
;

while_stmt
: WHILE LPAREN expression RPAREN statement {}
;

return_stmt
: RETURN SEMI {}
| RETURN expression SEMI {}
;

115
expression
: assignment_expression {$$=$1;}
| simple_expression {$$=$1;}
;
for_stmt
: FOR LPAREN assignment_expression SEMI simple_expression SEMI
unary_expression RPAREN compound_stmt

assignment_expression
: ID ASSIGN expression {

int ex = exists(list2,$1, scope);

if(ex == 0) {printf("Error in Line %d: Assignment before Declaration\n",
yylineno); errors++;}
id_ex = find(list2, $1, scope);
if(iflag == 1){
update(list2, $1, scope, $3, fexpval, cexpval);
}
if(fflag == 1){
update(list2, $1, scope, iexpval, $3, cexpval);
}
if(cflag == 1){
update(list2, $1, scope, iexpval, fexpval, $3);
}
iflag = 0;
cflag = 0;
fflag = 0;

116
 }
| unary_expression {$$=$1;} ;

unary_expression
: INC_OP ID {
id_ex = find(list2, $2, scope);
if(id_ex==NULL){
printf("Error on Lineno %d: Increment operator cannot be applied to an identifier
that's not declared\n", yylineno);
errors++;
}
else {
if(strcmp(id_ex->dtype, "int")!=0){
printf("Error on Line %d: Type Mismatch\n", yylineno);
errors++;
}
else
++id_ex->value;
}
}
| DEC_OP ID {
id_ex = find(list2, $2, scope);
if(id_ex==NULL){
printf("Error on Lineno %d: Increment operator cannot be applied to an identifier
that's not declared\n", yylineno);
errors++;}
else {
if(strcmp(id_ex->dtype, "int")!=0){

117
 printf("Error on Line %d: Type Mismatch\n", yylineno);
errors++;
}
else
--id_ex->value;
}

}
| postfix_expression {$$=$1;}
;

postfix_expression
: ID INC_OP {
id_ex = find(list2, $1, scope);
if(id_ex==NULL){
printf("Error on Lineno %d: Increment operator cannot be applied to an identifier
that's not declared\n", yylineno);
errors++;
}
else {
if(strcmp(id_ex->dtype, "int")!=0){
printf("Error on Line %d: Type Mismatch\n", yylineno);
errors++;
}
else
id_ex->value++;
}
}
| ID DEC_OP {

118
 id_ex = find(list2, $1, scope);
if(id_ex==NULL){
printf("Error on Lineno %d: Increment operator cannot be applied to an identifier
that's not declared\n", yylineno);
errors++;
}
else {
if(strcmp(id_ex->dtype, "int")!=0){
printf("Error on Line %d: Type Mismatch\n", yylineno);
errors++;
}
else
id_ex->value--;
}

}
;

simple_expression
: additive_expression {$$=$1;}
| additive_expression relop additive_expression {
if(strcmp($2, "<")==0)
$<integer>$ = $1<$3;
if(strcmp($2, "<=")==0)
$<integer>$ = $1<=$3;
if(strcmp($2, ">")==0)
$<integer>$ = $1>$3;
if(strcmp($2, ">=")==0)
$<integer>$ = $1>=$3;

119
 if(strcmp($2, "==")==0)
$<integer>$ = $1==$3;
if(strcmp($2, "!=")==0)
$<integer>$ = $1!=$3;

}
;

relop
: LT {$$ = "<";}
| LTEQ {$$ = "<=";}
| GT {$$ = ">";}
| GTEQ {$$ = ">=";}
| EQ {$$ = "==";}
| NEQ {$$ = "!=";}
;

additive_expression
: term {$$=$1;

if(iflag == 1)
iexpval = itermval;
if(fflag == 1)
fexpval = ftermval;
if(cflag == 1)
cexpval = ctermval;

120
 | additive_expression PLUS term {$$ = $1 + $3;}
| additive_expression MINUS term {$$ = $1 - $3;}
| PLUS additive_expression %prec STAR {}
| MINUS additive_expression %prec STAR {}
;

term
: factor {

if(iflag == 1)
$<integer>$ = iasval;
itermval = iasval;
if(fflag == 1)
$<ft>$ = fasval;
ftermval = fasval;
if(cflag == 1)
$<chr>$ = casval;
ctermval = casval;
}
| term STAR factor {$$ = $1*$3;}
| term SLASH factor {$$ = $1/$3;}
;

factor
: LPAREN expression RPAREN {$$=$2; }
| ID {

id_ex = find(list2, $1, scope);

121
if(id_ex == NULL){
printf("Error on %d, Assignment RHS not declared\n", yylineno);
errors++;
$$ = 0;}
else{
//$$ = $1;

if(strcmp(id_ex->dtype, "int")==0)
{
$<integer>$ = id_ex->value;
iasval = id_ex->value;
iflag = 1;
cflag = 0;
fflag = 0;
}
if(strcmp(id_ex->dtype, "float")==0){
$<ft>$ = id_ex->fvalue;

fasval = id_ex->fvalue;
iflag = 0;
fflag = 1;
cflag = 0;
}
if(strcmp(id_ex->dtype, "char")==0){
$<chr>$ = id_ex->cvalue;
casval = id_ex->cvalue;
iflag = 0;
fflag = 0;

122
 cflag = 1;
}
}}
| call {$$=$1;}
| NUM {
iasval = atoi(yylval.str); iflag = 1; cflag=0; fflag=0;
$<integer>$ = iasval;

}
|FLT{
fasval = atof(yylval.str); fflag = 1; cflag = 0; iflag = 0;
$<ft>$ = fasval;
}
|STR {}
;

call
: ID LPAREN RPAREN {}
| ID LPAREN args RPAREN {}
;

args
: expression {$$=$1;}
| expression COMMA args {}
;

%%
#include <stdio.h>

123
main(argc, argv)
int argc;
char** argv;
{
syntree = fopen("syntree.txt", "w");
FILE *fp = fopen("tokens.txt", "w");
fclose(fp);
if (argc > 1)
{
FILE *file;
file = fopen(argv[1], "r");
if (!file)
{
fprintf(stderr, "failed open");
exit(1);
}
yyin=file;
//printf("success open %s\n", argv[1]);
}
else
{
printf("no input file\n");
exit(1);
}
list2 = (struct list*)malloc(sizeof(struct list));
list2->head = NULL;

yyparse();

124
print(list2->head);
fclose(syntree);
if(errors>0){
printf("%d Errors Found\n", errors);
}
return 0;
}

void yyerror(const char *s)

{
fflush(stdout);
errors++;
fprintf(stderr, "Error: %s on line number %d\n", s, yylineno);
}

Phase 5 Intermediate Code Optimization

Phase 5.l Eliminate dead code

D [0-9]

NZ [1-9]

L [a-zA-Z_]

A [a-zA-Z_0-9]

WS [ \t\v\n\f]

TE [a-zA-Z_0-9!@#$%^&* \t\v\n\f]

%option yylineno

125
%{

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <limits.h>

#include "int_code.tab.h"

int yywrap();

int scope = 0;

void printToken(char* type){

FILE *fp = fopen("tokens.txt", "a");

fprintf(fp," <token line=\"%d\" type=\"%s\" string=\"%s\" />\n",

yylineno,

type,

yytext);

fclose(fp);

static void comment(void);

struct Stack {

int top;

unsigned capacity;

int* data;

126
};

struct Stack* createStack(unsigned capacity)

struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));

stack->capacity = capacity;

stack->top = -1;

stack->data = (int*)malloc(stack->capacity * sizeof(int));

return stack;

int isFull(struct Stack* stack)

return stack->top == stack->capacity - 1;

int isEmpty(struct Stack* stack)

return stack->top == -1;

void push(struct Stack* stack, int item)

127
 if(stack == NULL) {

stack = createStack(100);

push(stack, 0);

if (isFull(stack))

return;

stack->data[++stack->top] = item;

int pop(struct Stack* stack)

if(stack == NULL) {

stack = createStack(100);

push(stack, 0);

if (isEmpty(stack))

return -32767;

return stack->data[stack->top--];

int peek(struct Stack* stack)

if(stack == NULL) {

128
 stack = createStack(100);

push(stack, 0);

if (isEmpty(stack))

return -32767;

return stack->data[stack->top];

struct Stack* stack;

%}

%%

"/*" { comment(); }

"//".* { /* consume //-comment */ }

"if" {printToken("IF"); return(IF); }

"else" {printToken("ELSE"); return(ELSE);}

"while" {printToken("WHILE"); return(WHILE);}

"return" {printToken("RETURN"); return(RETURN);}

"break" {printToken("BREAK"); return(BREAK);}

"continue" {printToken("CONTINUE"); return(CONTINUE);}

"void" {printToken("VOID");yylval.str = strdup(yytext);

129
 return(VOID);}

"int" {printToken("INT");yylval.str = strdup(yytext);

return(INT);}

"float" {printToken("FLOAT");yylval.str = strdup(yytext);

return(FLOAT);}

"char" {printToken("CHAR"); yylval.str=strdup(yytext); return(CHAR);}

"for" {printToken("FOR"); return FOR;}

"class" {printToken("CLASS"); return CLASS;}

"#include" {printToken("PREPROCESSOR_DIRECTIVE"); return

PREPROC;}

"new" {printToken("NEW"); return NEW;}

"++" {printToken("INC_OP");return INC_OP;}

"--" {printToken("DEC_OP");return DEC_OP;}

"+" {printToken("PLUS");return PLUS;}

"-" {printToken("MINUS");return MINUS; }

"*" {printToken("STAR");return STAR; }

"/" {printToken("SLASH");return SLASH; }

"<" {printToken("LT");return LT; }

"<=" {printToken("LTEQ"); return LTEQ;}

">" {printToken("GT");return GT;}

">=" {printToken("GTEQ");return GTEQ;}

"==" {printToken("EQ");return EQ;}

"!=" {printToken("NEQ");return NEQ;}

"=" {printToken("ASSIGN");return ASSIGN;}

130
"<<" {printToken("INSERTION"); return INSERTION;}

">>" {printToken("EXTRACTION"); return EXTRACTION;}

"cin" {printToken("CIN"); return CIN;}

"cout" {printToken("COUT"); return COUT;}

("[") {printToken("LSQUAR");return LSQUAR; }

("]") {printToken("RSQUAR");return RSQUAR;}

("{") {printToken("LBRACE"); scope++; push(stack, scope); return LBRACE;}

("}") {printToken("RBRACE"); pop(stack);scope--; return RBRACE;}

";" {printToken("SEMI");return SEMI;}

"," {printToken("COMMA");return COMMA;}

"(" {printToken("LPAREN");return LPAREN;}

")" {printToken("RPAREN");return RPAREN; }

"endl" {printToken("ENDL"); return ENDL;}

{L}{A}* {printToken("ID");yylval.str = strdup(yytext); return ID;}

{D}+ {printToken("NUMBER");yylval.str = strdup(yytext); return NUM;}

{D}*"."{D}+ {printToken("FLOATINGPOINT");yylval.str = strdup(yytext); return FLT;}

\"{TE}*{WS}*\" {printToken("STRING"); yylval.str = strdup(yytext); return STR;}

{WS}+ {}

. {printToken("UNKNOWN LEXEME");printToken(yytext);}

%%

131
#include<stdio.h>

int yywrap() {

return 1;

static void comment(void)

int c;

while ((c = input()) != 0)

if (c == '*')

while ((c = input()) == '*')

if (c == '/')

return;

if (c == 0)

break;

132
 printf("unterminated comment");

exit(-1);

Int_code.y-

%{

#include <ctype.h>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <stdarg.h>

#include <limits.h>

#include "lex.yy.c"

//typedef char* string;

//#define YYSTYPE string

FILE *symtab;

#define STR(VAR) (#VAR)

#define release 1

#define MAXCHILD 10

FILE *syntree;

extern void yyerror(const char *); /* prints grammar violation message */

extern int yylex(void);

extern FILE *yyin;

extern FILE *yyout;

133
extern int yylineno;

int iasval, itermval, iexpval;

char casval, ctermval, cexpval;

float fasval, ftermval, fexpval;

int cflag=0, iflag=0, fflag=0;

char* tab=" ";

char indent[100]="";

char type[200];

char if_stmt_skip_label[10];

char* integer="INT";

char* floating="float";

char* none = "none";

char* assign = "=";

int expval=0;

int errors = 0;

/*Stack*/

FILE *icgout;

/*Data Structure to store quadruples*/

134
struct quadruple{

char statement[30];

char op[10];

char arg1[20];

char arg2[20];

char res[20];

int lineno;

struct quadruple *next;

};

typedef struct quadruple quadruple;

struct quad_list{

quadruple* head;

};

typedef struct quad_list quad_list;

quad_list* q_list1;

quadruple* create_quadruple(char* statement,char* op, char* arg1, char* arg2, char* res, int
lineno) {

quadruple* new_quadruple = (quadruple*)malloc(sizeof(quadruple));

strcpy(new_quadruple->statement,statement);

strcpy(new_quadruple->op,op);

strcpy(new_quadruple->arg1,arg1);

strcpy(new_quadruple->arg2,arg2);

135
 strcpy(new_quadruple->res,res);

new_quadruple->lineno = lineno;

//printf("Created quadruple record...\n");

new_quadruple->next=NULL;

return new_quadruple;

void insert_quadruple(quad_list * list, quadruple* q1) {

quadruple * traverse = list->head;

if(traverse==NULL) {

list->head = q1;

else {

while (traverse->next !=NULL) {

traverse = traverse->next;

traverse->next = q1;

char* get_three_add(quadruple* record) {

char *res = (char *)malloc(sizeof(char)*50);

if(strcmp(record->statement,"expression") == 0) {

sprintf(res,"%s = %s %s %s",record->res,record->arg1,record->op,record->arg2);

136
}

else if(strcmp(record->statement,"assignment") == 0){

sprintf(res,"%s = %s %s",record->res,record->op,record->arg1);

else if(strcmp(record->statement,"conditional_goto") == 0){

sprintf(res,"if %s %s %s goto %s",record->arg1,record->op,record->arg2,record->res);

else if(strcmp(record->statement,"goto") == 0){

sprintf(res,"goto %s",record->res);

else if(strcmp(record->statement,"label") == 0 ){

sprintf(res,"%s : ",record->res);

else if(strcmp(record->statement, "unary")==0){

sprintf(res, "%s = %s %s", record->res, record->arg1, record->arg2);

else if(strcmp(record->statement, "condition")==0){

sprintf(res, "%s", record->res);

else if(strcmp(record->statement, "ARR")==0){

sprintf(res, "ARR %s = %s", record->res, record->arg1);

return res;

137
}

void display_three_add(quad_list *list) {

quadruple *traverse = list->head;

while(traverse!=NULL) {

printf("%s\n", get_three_add(traverse));

fprintf(icgout, "%s\n",get_three_add(traverse));

traverse=traverse->next;

int temp_count = 0;

int label_count = 0;

char * create_temp() {

char *new_temp = (char*)malloc(sizeof(char)*10);

sprintf(new_temp,"t%d",temp_count);

temp_count+=1;

//printf("Created temporary variable : %d",temp_count);

return new_temp;

138
char * create_label() {

char *new_label=(char*)malloc(sizeof(char)*10);

sprintf(new_label,"L%d",label_count);

label_count+=1;

return new_label;

char * get_previous_temp() {

//char *new_temp = (char*)malloc(sizeof(char)*10);

//sprintf(new_temp,"t%d",temp_count-1);

quadruple * traversal = q_list1->head;

if(traversal==NULL) return "";

while(traversal->next!=NULL) {

traversal=traversal->next;

return traversal->res;

char * get_dtype(char * str) {

int i=0;

char* type = (char*)malloc(sizeof(char)*10);

if(str[0]=='\"') {

strcpy(type,"STRING");

return type;

139
}

else if(str[0]=='\'') {

strcpy(type,"CHAR");

return type;

strcpy(type,"INT");

while(str[i]!='\0' && str[i]>=0 && str[i]<=9) {

i++;

if (str[i]=='\0') {

return type;

else if (str[i]=='.') {

strcpy(type,"FLOAT");

i++;

while(str[i]!='\0' && str[i]>=0 && str[i]<=9) {

i++;

if (str[i]=='\0') {

return type;

else {

strcpy(type,"INVALID");

140
 return type;

//end of quadruples code

// Implementation of break and continue

struct construct {

char start_label[10];

char stop_label[10];

};

typedef struct construct construct;

construct current_construct;

//end

struct node{

int nl;

char name[100];

char dtype[200];

int scope;

int value;

float fvalue;

141
 char cvalue;

char rhs[200];

char type[100];

struct node *next;

};

typedef struct node node;

struct list{

node* head;

};

typedef struct list list1;

struct list* list2 = NULL;

int exists(list1* root, char name[100], int scope){

if(root == NULL || root->head == NULL){

return 0;

node *t2 = root->head;

while(t2!=NULL){

if(strcmp(t2->name, name) == 0 && t2->scope == scope){

142
 return 1;

t2 = t2->next;

t2 = root->head;

while(t2!=NULL){

if(strcmp(t2->name, name)==0){

return 1;

t2 = t2->next;

return 0;

node* find(list1 *root, char name[200], int scope){

if(root == NULL || root->head == NULL){

return NULL;

node *t2 = root->head;

while(t2!=NULL){

if(strcmp(t2->name, name)==0 && t2->scope == scope){return t2;}

t2 = t2->next;

143
 }

t2 = root->head;

while(t2!=NULL){

if(strcmp(t2->name, name)==0){

return t2;

t2 = t2->next;

return t2;

node* id_ex;

void insert(list1 *root, int nl, char name[100], char dtype[200], int scope, char rhs[200], char
type[100]){

int out = exists(root, name, scope);

if(out == 0){

node *temp = (node*)malloc(sizeof(node));

temp->nl = nl;

temp->scope = scope;

strcpy(temp->dtype, dtype);

strcpy(temp->rhs, rhs);

strcpy(temp->name, name);

strcpy(temp->type, type);

144
 temp->next = NULL;

if(root->head == NULL){

root->head = temp;

return;

node *t2 = root->head;

while(t2->next!=NULL){

t2 = t2->next;

t2->next = temp;

return;

else{

errors++;

printf("Error at line %d: Multiple declarations\n", nl);

void update(list1 *root, char name[100], int scope, char rhs[200]){

node *t2 = root->head;

if(find(root, name, scope) == NULL){

return;

145
 }

while(strcmp(t2->name, name)!=0){

t2 = t2->next;

strcpy(t2->rhs, rhs);

return;

void print(node *head){

// printf("1\n");

node *temp = head;

printf("___________________________________________________________________\n");

fprintf(symtab,
"___________________________________________________________________\n");

printf("|Line |Name |Scope |value |id_type |datatype |\n");

fprintf(symtab, "|Line |Name |Scope |value |id_type |datatype |\n");

printf("-------------------------------------------------------------------\n");

fprintf(symtab, "-------------------------------------------------------------------\n");

while(temp!=NULL){

printf("|%-10d|%-10s|%-10d|%-10s|%-10s|%-10s|\n", temp->nl, temp->name, temp->scope,

temp->rhs, temp->type, temp->dtype);

fprintf(symtab, "|%-10d|%-10s|%-10d|%-10s|%-10s|%-10s|\n", temp->nl, temp->name,

temp->scope, temp->rhs, temp->type, temp->dtype);

146
 temp=temp->next;

printf("-------------------------------------------------------------------\n");

fprintf(symtab, "-------------------------------------------------------------------\n");

void reset_scope(list1 *root, int current_scope) {

if(root == NULL || root->head == NULL){

return;

node *t2 = root->head;

while (t2!=NULL) {

if(t2->scope > current_scope) {

t2->scope=-1;

t2=t2->next;

struct expression_details{

//int value;

char type[200];

147
};

typedef struct expression_details exp_det;

exp_det det1;

%}

%code requires {

%union{

char chr;

int integer;

float ft;

char *str;

%token IF ELSE WHILE RETURN VOID INT FLOAT CHAR FOR BREAK CONTINUE

%token INC_OP DEC_OP PLUS MINUS STAR SLASH LT LTEQ GT GTEQ EQ NEQ
ASSIGN

%token SEMI COMMA LPAREN RPAREN LSQUAR RSQUAR LBRACE RBRACE

LCOMMENT RCOMMENT

%token <str> ID NUM FLT CHR

%token LETTER DIGIT

%token NONTOKEN ERROR ENDFILE

%token NL ENDL

%token STR

148
%token INSERTION EXTRACTION

%token CIN COUT

%token CLASS

%token PREPROC

%token NEW

%left PLUS MINUS

%left STAR SLASH

%nonassoc THEN

%nonassoc IF

%nonassoc LOWER_THAN_IF

%expect 2

%type<str> atree program external_declaration var_declaration init_declarator_list

fun_declaration params_list compound_stmt declarator params block_item_list block_item call
factor term additive_expression simple_expression unary_expression postfix_expression
assignment_expression return_stmt while_stmt if_stmt else_if expression statement args
expression_stmt for_stmt

%type<str> relop declaration_specifiers stream_constructs op array_init arrayindex object_dec

%start atree

%%

atree:program {display_three_add(q_list1);}

149
program

: external_declaration {$$=$1;}

| program external_declaration {}

| program PREPROC LT ID GT {printf("%s\n", $4);}

| PREPROC LT ID GT {printf("%s\n", $3);}

| class_declaration {}

| program class_declaration {}

external_declaration

: var_declaration {$$=$1; }

| fun_declaration {$$=$1;}

class_declaration

: declaration_specifiers ID LBRACE external_declaration RBRACE SEMI {insert(list2,

yylineno, $2, "class", scope, " ", "class");}

var_declaration

: declaration_specifiers init_declarator_list SEMI

{}

| declaration_specifiers array_dec SEMI {}

| object_dec {$$ = $1;}

| error SEMI{yyerrok;}

array_init

150
 : LBRACE comma_list RBRACE {$<str>$=$<str>2;}

comma_list

: NUM COMMA comma_list {$<str>$=$<str>1;strcat($<str>$,",");strcat($<str>$,$<str>3);}

| NUM {$<str>$=$<str>1;}

array_dec

: ID LSQUAR NUM RSQUAR {insert(list2, yylineno, $1, type, scope, " ", "ARRAY");}

| STAR ID {insert(list2, yylineno, $2, type, scope, " ", "PTR");}

| ID LSQUAR RSQUAR ASSIGN array_init { insert(list2, yylineno, $1, "int" , scope, $<str>5,
"ARRAY");

quadruple * new_record =
create_quadruple("ARR","",$5,"",$1, yylineno);

insert_quadruple(q_list1,new_record); }

init_declarator_list

: ID { id_ex = find(list2, $1, scope+1);

if(id_ex !=NULL){

printf("Error on line %d, multiple definitions\n", yylineno);

else

insert(list2, yylineno, $1, type, scope, " ", "IDENT");}

| ID ASSIGN expression {

id_ex = find(list2, $1, scope+1);

151
 if(id_ex !=NULL){

printf("Error on line %d, multiple

definitions\n", yylineno);

else{

char arg1[10];

sprintf(arg1,"%s",$3);

quadruple * new_record =
create_quadruple("assignment","",arg1,"",$1, yylineno);

insert_quadruple(q_list1,new_record);

insert(list2, yylineno, $1, type, scope, " ", "IDENT");

update(list2, $1, scope, $3);

iflag = 0;

fflag = 0;

cflag = 0;

| init_declarator_list COMMA ID { id_ex = find(list2, $3, scope+1);

if(id_ex !=NULL){

printf("Error on line %d,

multiple definitions\n", yylineno);

else

insert(list2, yylineno, $3, type,

scope, " ", "IDENT");

152
 }

| init_declarator_list COMMA ID ASSIGN expression {

id_ex = find(list2, $3, scope+1);

if(id_ex !=NULL){

printf("Error on line %d, multiple

definitions\n", yylineno);

else{

char arg1[10];

sprintf(arg1,"%s",$5);

quadruple * new_record =
create_quadruple("assignment","",arg1,"",$3, yylineno);

insert_quadruple(q_list1,new_record);

insert(list2, yylineno, $3, type, scope, " ", "IDENT");

update(list2, $3, scope, $5);

iflag = 0;

fflag = 0;

cflag = 0;

object_dec

153
 : ID ID ASSIGN NEW ID LPAREN RPAREN {id_ex = find(list2, $1, scope+1);

if(id_ex == NULL){

printf("Error
in Line %d, %s is not a data type\n", yylineno, $1);

else if(strcmp(id_ex-
>dtype, "class")!=0){

printf("Error
in line %d, %s is not a defined type\n", yylineno, $1);

else if(strcmp($1,
$5)!=0){

id_ex =
find(list2, $5, scope+1);

if(id_ex ==
NULL){

printf("Error in line %d, Unknown identifier\n", yylineno);

else
if(strcmp(id_ex->dtype, "class")!=0){

printf("Error in line %d, identifier is not a class type\n", yylineno);

154
 else if(find(list2, $2,
scope+1)!=NULL){

printf("Error
in line %d, multiple definitions not allowed\n");

else{

insert(list2,
yylineno, $2, $1, scope, " ", "object");

declarator

: LPAREN RPAREN {}

| LPAREN params RPAREN {}

fun_declaration

: declaration_specifiers ID declarator compound_stmt {insert(list2, yylineno, $2, type, scope, "

", "FUNCT");}

declaration_specifiers

: INT {$$=integer; strcpy(type, "int");}

| VOID {$$="VOID"; strcpy(type, "void");}

| FLOAT {$$="float"; strcpy(type, "float");}

| CHAR {$$="char"; strcpy(type, "char");}

155
 | CLASS {$$="class"; strcpy(type, "class");}

params_list

: INT ID {}

| FLOAT ID {}

| params_list COMMA INT ID {}

| params_list COMMA FLOAT ID {}

params

: params_list {$$=$1;}

| VOID {}

compound_stmt

: LBRACE RBRACE {$$ = "$";}

| LBRACE block_item_list RBRACE {$$ = $2; reset_scope(list2,scope);}

block_item_list

: block_item {$$ = $1; }

156
 | block_item_list block_item {$$ = $2;}

block_item

: var_declaration {$$=$1; }

| statement {$$=$1;}

statement

: expression_stmt {$$=$1;}

| compound_stmt {$$=$1;}

| if_stmt {$$=$1;}

| while_stmt {$$=$1;}

| return_stmt {$$=$1;}

| for_stmt {$$ = $1;}

| stream_constructs {$$ = $1;}

| break_stmt {}

| continue_stmt {}

break_stmt

: BREAK {

if (strcmp(current_construct.stop_label,"") !=0) {

157
 quadruple* new_record;

new_record = create_quadruple("goto","","","",current_construct.stop_label, yylineno);

insert_quadruple(q_list1,new_record);

} else {

errors++;

printf("Error in Line %d : Wrong Usage of statement \"break\"...\n", yylineno);

continue_stmt

: CONTINUE {

if (strcmp(current_construct.start_label,"") !=0) {

quadruple* new_record;

new_record = create_quadruple("goto","","","",current_construct.start_label, yylineno);

insert_quadruple(q_list1,new_record);

} else {

errors++;

printf("Error in Line %d : Wrong Usage of statement \"continue\"...\n", yylineno);

stream_constructs

: cout_cascade {}

158
 | cin {}

cout_cascade

: COUT cascade_out SEMI

cascade_out

: INSERTION op {if(errors==0) printf("%s", $2);}

| INSERTION op cascade_out {if(errors==0) printf("%s", $2);}

| INSERTION op INSERTION ENDL {if(errors==0) printf("%s\n", $2);}

cin

: CIN EXTRACTION ID SEMI {

id_ex = find(list2, $3, scope);

if(id_ex == NULL){

printf("Error in Line %d : Usage before

Declaration\n", yylineno);

errors++;

else{

int a;

char b;

float c;

if(strcmp(id_ex->dtype, "int") == 0){

scanf("%d", &a);

id_ex->value = a;

159
 }

if(strcmp(id_ex->dtype, "float") == 0){

scanf("%f", &c);

id_ex->fvalue = c;

if(strcmp(id_ex->dtype, "char")==0){

scanf("%c", &b);

id_ex->cvalue = b;

op

:NUM {$<str>$ = yylval.str;}

|STR {$<str>$ = yylval.str;}

|ID {

id_ex = find(list2, $1, scope);

if(id_ex == NULL){

printf("Error in Line %d : Usage before Declaration\n", yylineno);

errors++;

else{

if(strcmp(id_ex->dtype, "int") == 0) $<integer>$ = id_ex->value;

160
 if(strcmp(id_ex->dtype, "float") == 0) $<ft>$ = id_ex->fvalue;

if(strcmp(id_ex->dtype, "char") == 0) $<chr>$ = id_ex->cvalue;

expression_stmt

: SEMI {}

| expression SEMI {$$=$1;}

if_stmt

:IF LPAREN expression RPAREN {

quadruple* new_record;

//Insert Condition

char statement_type[20],arg1[10],arg2[10],arg3[10],temp[10],true_label[10],false_label[10];

sprintf(statement_type,"conditional_goto");

strcpy(arg1,$3);

strcpy(true_label,create_label());

161
 new_record = create_quadruple(statement_type,arg1,"","",true_label, yylineno);

insert_quadruple(q_list1,new_record);

sprintf(statement_type,"goto");

strcpy(false_label,create_label());

new_record = create_quadruple(statement_type,"","","",false_label, yylineno);

insert_quadruple(q_list1,new_record);

new_record = create_quadruple("label","","","",true_label, yylineno);

insert_quadruple(q_list1,new_record);

$<str>$=false_label;

} statement {

quadruple* new_record;

strcpy(if_stmt_skip_label,create_label());

new_record = create_quadruple("goto","","","",if_stmt_skip_label, yylineno);

insert_quadruple(q_list1,new_record);

new_record = create_quadruple("label","","","",$<str>5, yylineno);

insert_quadruple(q_list1,new_record);

} else_if {

quadruple* new_record;

new_record = create_quadruple("label","","","",if_stmt_skip_label, yylineno);

insert_quadruple(q_list1,new_record);

162
else_if :

ELSE IF LPAREN expression RPAREN {

quadruple* new_record;

//Insert Condition

char statement_type[20],arg1[10],arg2[10],arg3[10],temp[10],true_label[10],false_label[10];

sprintf(statement_type,"conditional_goto");

strcpy(arg1,$<str>4);

strcpy(true_label,create_label());

new_record = create_quadruple(statement_type,arg1,"","",true_label, yylineno);

insert_quadruple(q_list1,new_record);

sprintf(statement_type,"goto");

strcpy(false_label,create_label());

new_record = create_quadruple(statement_type,"","","",false_label, yylineno);

insert_quadruple(q_list1,new_record);

new_record = create_quadruple("label","","","",true_label, yylineno);

insert_quadruple(q_list1,new_record);

$<str>$=false_label;

} statement {

quadruple* new_record;

new_record = create_quadruple("goto","","","",if_stmt_skip_label, yylineno);

insert_quadruple(q_list1,new_record);

163
 new_record = create_quadruple("label","","","",$<str>6, yylineno);

insert_quadruple(q_list1,new_record);

} else_if {}

| ELSE else_body %prec LOWER_THAN_IF {

//printf("else\n");

| {}

else_body

: expression_stmt {$<str>$=$1;}

| compound_stmt {$<str>$=$1;}

| while_stmt {$<str>$=$1;}

| return_stmt {$<str>$=$1;}

| for_stmt {$<str>$ = $1;}

| stream_constructs {$<str>$ = $1;}

| break_stmt {}

| continue_stmt {}

while_stmt

: WHILE {

quadruple* new_record;

164
 char while_label[10];

strcpy(while_label,create_label());

new_record = create_quadruple("label","","","",while_label, yylineno);

insert_quadruple(q_list1,new_record);

strcpy(current_construct.start_label,while_label);

$<str>$=while_label;} LPAREN expression RPAREN

quadruple* new_record;

char statement_type[20],arg1[10],arg2[10],arg3[10],temp[10],true_label[10],false_label[10];

sprintf(statement_type,"conditional_goto");

strcpy(arg1,$4);

strcpy(true_label,create_label());

new_record = create_quadruple(statement_type,arg1,"","",true_label, yylineno);

insert_quadruple(q_list1,new_record);

sprintf(statement_type,"goto");

strcpy(false_label,create_label());

new_record = create_quadruple(statement_type,"","","",false_label, yylineno);

insert_quadruple(q_list1,new_record);

strcpy(current_construct.stop_label,false_label);

new_record = create_quadruple("label","","","",true_label, yylineno);

insert_quadruple(q_list1,new_record);

$<str>$=false_label;

} statement {

165
 quadruple* new_record = create_quadruple("goto","","","",$<str>2, yylineno);

insert_quadruple(q_list1,new_record);

new_record = create_quadruple("label","","","",$<str>6, yylineno);

insert_quadruple(q_list1,new_record);

strcpy(current_construct.start_label,"");

strcpy(current_construct.stop_label,"");

return_stmt

: RETURN SEMI {}

| RETURN expression SEMI {}

expression

: assignment_expression {$$=$1;}

| simple_expression {$$=$1; }

for_stmt

: FOR {scope++;} LPAREN for_initialiser SEMI {

quadruple* new_record;

char for_label[10];

166
 strcpy(for_label,create_label());

new_record = create_quadruple("label","","","",for_label, yylineno);

insert_quadruple(q_list1,new_record);

strcpy(current_construct.start_label,for_label);

$<str>$=for_label;

simple_expression SEMI for_update RPAREN {

quadruple* new_record;

char break_label[10],body_label[10];

strcpy(body_label,create_label());

strcpy(break_label,create_label());

new_record = create_quadruple("conditional_goto",$<str>7,"","",body_label, yylineno);

insert_quadruple(q_list1,new_record);

new_record = create_quadruple("goto","","","",break_label, yylineno);

insert_quadruple(q_list1,new_record);

new_record = create_quadruple("label","","","",body_label, yylineno);

insert_quadruple(q_list1,new_record);

strcpy(current_construct.stop_label,break_label);

$<str>$=break_label;

scope--;

} statement {

char update_stmt[20],iterable[20],operator[5],update_value[20],for_label[10];

strcpy(update_stmt,$<str>9);

167
 strcpy(iterable,strtok(update_stmt, " "));

strcpy(operator,strtok(NULL," "));

strcpy(update_value,strtok(NULL," "));

id_ex = find(list2, iterable, scope+1);

update(list2, id_ex->name,scope+1,update_stmt);

quadruple* new_record;

new_record = create_quadruple("expression",operator,iterable,update_value,iterable,
yylineno);

insert_quadruple(q_list1,new_record);

strcpy(for_label,$<str>6);

new_record = create_quadruple("goto","","","",for_label, yylineno);

insert_quadruple(q_list1,new_record);

char break_label[10];

strcpy(break_label,$<str>11);

new_record = create_quadruple("label","","","",break_label, yylineno);

insert_quadruple(q_list1,new_record);

strcpy(current_construct.start_label,"");

strcpy(current_construct.stop_label,"");

for_initialiser

: assignment_expression {}

| declaration_specifiers ID ASSIGN expression {

char arg1[10];

168
 sprintf(arg1,"%s",$4);

quadruple * new_record =
create_quadruple("assignment","",arg1,"",$2, yylineno);

insert_quadruple(q_list1,new_record);

insert(list2, yylineno, $2, type, scope, " ", "IDENT");

update(list2, $2, scope, $4);

iflag = 0;

fflag = 0;

cflag = 0;

for_update

: INC_OP ID {

id_ex = find(list2, $<str>2, scope);

if(id_ex==NULL){

printf("Error on Lineno %d : Increment operator cannot be applied to an identifier

that's not declared\n", yylineno);

errors++;

else {

char increement[20];

strcpy(increement,id_ex->name);

strcat(increement," + 1");

$<str>$ = increement;

169
 }

| DEC_OP ID {

id_ex = find(list2, $<str>2, scope);

if(id_ex==NULL){

printf("Error on Lineno %d : Increment operator cannot be applied to an identifier

that's not declared\n", yylineno);

errors++;

else {

char decreement[20];

strcpy(decreement,id_ex->name);

strcat(decreement," - 1");

$<str>$ = decreement;

| ID INC_OP {

id_ex = find(list2, $<str>2, scope);

if(id_ex==NULL){

printf("Error on Lineno %d : Increment operator cannot be applied to an identifier

that's not declared\n", yylineno);

errors++;

170
 else {

char increement[20];

strcpy(increement,id_ex->name);

strcat(increement," + 1");

$<str>$ = increement;

| ID DEC_OP {

id_ex = find(list2, $<str>2, scope);

if(id_ex==NULL){

printf("Error on Lineno %d : Increment operator cannot be applied to an identifier

that's not declared\n", yylineno);

errors++;

else {

char decreement[20];

strcpy(decreement,id_ex->name);

strcat(decreement," - 1");

$<str>$ = decreement;

171
assignment_expression

: ID ASSIGN expression {

char arg1[10],previous_temp[10];

strcpy(previous_temp,get_previous_temp());

sprintf(arg1,"%s",$3);

quadruple * new_record =
create_quadruple("assignment","",arg1,"",$1, yylineno);

insert_quadruple(q_list1,new_record);

int ex = exists(list2,$1, scope);

if(ex == 0) {printf("Error in Line %d : Assignment before Declaration\n",

yylineno); errors++;}

id_ex = find(list2, $1, scope);

update(list2, $1, scope, $3);

iflag = 0;

cflag = 0;

fflag = 0;

| arrayindex ASSIGN expression{

char arg1[10], previous_temp[10];

strcpy(previous_temp,get_previous_temp());

sprintf(arg1,"%s",$3);

172
 quadruple * new_record =
create_quadruple("assignment","",arg1,"",$1, yylineno);

insert_quadruple(q_list1,new_record);

char id[200];

strcpy(id, "");

int tempcount = 0;

char lhs[200];

strcpy(lhs, $1);

while(lhs[tempcount]!='['){

id[tempcount] = lhs[tempcount];

tempcount++;

id[tempcount] = '\0';

int ex = exists(list2,id, scope);

if(ex == 0) {printf("Error in Line %d : Assignment before

Declaration\n", yylineno); errors++;}

id_ex = find(list2, id, scope);

update(list2, id, scope, $3);

iflag = 0;

cflag = 0;

fflag = 0;

173
 | unary_expression {$$=$1;} ;

unary_expression

: INC_OP ID {

id_ex = find(list2, $2, scope);

if(id_ex==NULL){

printf("Error on Lineno %d : Increment operator cannot be applied to an identifier

that's not declared\n", yylineno);

errors++;

else {

if(strcmp(id_ex->dtype, "int")!=0){

printf("Error on Line %d : Type Mismatch\n", yylineno);

errors++;

else{

quadruple* new_record;

char statement_type[20],arg1[10],arg2[10],arg3[10],temp[10];

sprintf(statement_type,"expression");

//strcpy(temp,create_temp());

new_record =
create_quadruple(statement_type,"+",$<str>2,"1",$<str>2, yylineno);

insert_quadruple(q_list1,new_record);

174
 //char te[20];

//strcpy(te, "++");

//strcat(te, $2);

//insert(list2, yylineno, temp,"TEMP", scope, te, "TEMP");

char increement[20];

strcpy(increement,id_ex->name);

strcat(increement,"+1");

update(list2, id_ex->name,scope,increement);

$<str>$ = id_ex->rhs;

| DEC_OP ID {

id_ex = find(list2, $2, scope);

if(id_ex==NULL){

printf("Error on Lineno %d : Increment operator cannot be applied to an identifier

that's not declared\n", yylineno);

errors++;}

else {

if(strcmp(id_ex->dtype, "int")!=0){

printf("Error on Line %d : Type Mismatch\n", yylineno);

errors++;

175
 else{

quadruple* new_record;

char statement_type[20],arg1[10],arg2[10],arg3[10],temp[10];

sprintf(statement_type,"expression");

//strcpy(temp,create_temp());

new_record = create_quadruple(statement_type,"-
",$<str>2,"1",$<str>2, yylineno);

insert_quadruple(q_list1,new_record);

char te[20];

strcpy(te, "--");

strcat(te, $2);

//insert(list2, yylineno, temp,"TEMP", scope, te, "TEMP");

char decreement[20];

strcpy(decreement,id_ex->name);

strcat(decreement,"+1");

update(list2, id_ex->name,scope,decreement);

$<str>$ = id_ex->rhs;

| postfix_expression {$$=$1;}

176
 ;

postfix_expression

: ID INC_OP {

id_ex = find(list2, $1, scope);

if(id_ex==NULL){

printf("Error on Lineno %d : Increment operator cannot be applied to an identifier

that's not declared\n", yylineno);

errors++;

else {

if(strcmp(id_ex->dtype, "int")!=0){

printf("Error on Line %d : Type Mismatch\n", yylineno);

errors++;

else{

quadruple* new_record;

char statement_type[20],arg1[10],arg2[10],arg3[10],temp[10];

sprintf(statement_type,"expression");

//strcpy(temp,create_temp());

new_record =
create_quadruple(statement_type,"+",$<str>1,"1",$<str>1, yylineno);

insert_quadruple(q_list1,new_record);

177
 strcat($1, "++");

char increement[20];

strcpy(increement,id_ex->name);

strcat(increement,"+1");

//insert(list2, yylineno, temp,"TEMP", scope, $1, "TEMP");

$<str>$ = id_ex->rhs;

update(list2, id_ex->name,scope,increement);

| ID DEC_OP {

id_ex = find(list2, $1, scope);

if(id_ex==NULL){

printf("Error on Lineno %d : Increment operator cannot be applied to an identifier

that's not declared\n", yylineno);

errors++;

else {

if(strcmp(id_ex->dtype, "int")!=0){

printf("Error on Line %d : Type Mismatch\n", yylineno);

errors++;

else{

178
 quadruple* new_record;

char statement_type[20],arg1[10],arg2[10],arg3[10],temp[10];

sprintf(statement_type,"expression");

//strcpy(temp,create_temp());

new_record = create_quadruple(statement_type,"-
",$<str>1,"1",$<str>1, yylineno);

insert_quadruple(q_list1,new_record);

strcat($1, "--");

char decreement[20];

strcpy(decreement,id_ex->name);

strcat(decreement,"+1");

//insert(list2, yylineno, temp,"TEMP", scope, $1, "TEMP");

$<str>$ = id_ex->rhs;

update(list2, id_ex->name, scope,decreement);

179
simple_expression

: additive_expression {$$=$1;}

| additive_expression relop additive_expression {

strcat($1, $2);

strcat($1, $3);

$$ = $1;

relop

: LT {$$ = "<";}

| LTEQ {$$ = "<=";}

| GT {$$ = ">";}

| GTEQ {$$ = ">=";}

| EQ {$$ = "==";}

| NEQ {$$ = "!=";}

additive_expression

: term {$$=$1;

| additive_expression PLUS additive_expression {

180
 quadruple* new_record;

char statement_type[20],arg1[10],arg2[10],arg3[10],temp[10];

sprintf(statement_type,"expression");

strcpy(temp,create_temp());

new_record = create_quadruple(statement_type,"+",$1,$3,temp, yylineno);

insert_quadruple(q_list1,new_record);

strcat($1, "+");

strcat($1, $3);

insert(list2, yylineno, temp,"TEMP", scope, $1, "TEMP");

$$ = temp;

| additive_expression MINUS additive_expression{

quadruple* new_record;

char statement_type[20],arg1[10],arg2[10],arg3[10],temp[10];

sprintf(statement_type,"expression");

strcpy(temp,create_temp());

new_record = create_quadruple(statement_type,"-",$1,$3,temp, yylineno);

insert_quadruple(q_list1,new_record);

strcat($1, "-");

181
 strcat($1, $3);

insert(list2, yylineno, temp,"TEMP", scope, $1, "TEMP");

$$ = temp;

| PLUS additive_expression %prec STAR {$$ = $2;}

| MINUS additive_expression %prec STAR {char temp[20];strcpy(temp,"-

");strcat(temp,$2);$$ = temp;}

term

: factor {

$$ = $1;

| arrayindex {$$ = $1;}

| term STAR term {

quadruple* new_record;

char statement_type[20],arg1[10],arg2[10],arg3[10],temp[10];

sprintf(statement_type,"expression");

strcpy(temp,create_temp());

new_record = create_quadruple(statement_type,"*",$1,$3,temp, yylineno);

insert_quadruple(q_list1,new_record);

182
 strcat($1, "*");

strcat($1, $3);

insert(list2, yylineno, temp,"TEMP", scope, $1, "TEMP");

$$ = temp;

| term SLASH term {

quadruple* new_record;

char statement_type[20],arg1[10],arg2[10],arg3[10],temp[10];

sprintf(statement_type,"expression");

strcpy(temp,create_temp());

new_record = create_quadruple(statement_type,"/",$1,$3,temp, yylineno);

insert_quadruple(q_list1,new_record);

strcat($1, "/");

strcat($1, $3);

insert(list2, yylineno, temp,"TEMP", scope, $1, "TEMP");

$$ = temp;

arrayindex

: ID LSQUAR NUM RSQUAR {

183
 char lhs[200];

strcpy(lhs, "");

strcat(lhs, $1);

strcat(lhs, "[");

strcat(lhs, $3);

strcat(lhs, "]");

id_ex = find(list2, $1, scope);

if(id_ex == NULL){

printf("Error on %d, Assignment RHS not

declared\n", yylineno);

errors++;

$$ = "$";

else{

$$ = lhs;

strcpy(det1.type, id_ex->dtype);

| ID LSQUAR ID RSQUAR {

char lhs[200];

strcpy(lhs, "");

strcat(lhs, $1);

strcat(lhs, "[");

strcat(lhs, $3);

184
 strcat(lhs, "]");

id_ex = find(list2, $3, scope);

if(id_ex == NULL){

printf("Error on %d, Usage before declaration\n",

yylineno);

errors++;

$$ = "$";

else{

id_ex = find(list2, $1, scope);

if(id_ex == NULL){

printf("Error on %d, Assignment RHS not

declared\n", yylineno);

errors++;

$$ = "$";

else{

$$ = lhs;

strcpy(det1.type, id_ex->dtype);

185
factor

: LPAREN expression RPAREN {$$=$2; }

| ID {

if(yylineno == 1){

$$ = $1;

else{

id_ex = find(list2, $1, scope);

if(id_ex == NULL){

printf("Error on %d, Assignment RHS not declared\n", yylineno);

errors++;

$$ = "$";}

else{

$$ = $1;

strcpy(det1.type,id_ex->dtype);

}}}

| call {

$$=$1;

| NUM {

$$ = yylval.str;

strcpy(det1.type,"int");

186
 |FLT{

$$ = yylval.str;

strcpy(det1.type,"float");

|STR {$$ = yylval.str;strcpy(det1.type,"string");}

call

: ID LPAREN RPAREN {}

| ID LPAREN args RPAREN {}

args

: expression {$$=$1;}

| expression COMMA args {}

%%

#include <stdio.h>

int

main(argc, argv)

int argc;

187
char** argv;

//syntree = fopen("syntree.txt", "w");

FILE *fp = fopen("tokens.txt", "w");

icgout = fopen("icg.txt", "w");

symtab = fopen("symtab.txt", "w");

fclose(fp);

if (argc > 1)

FILE *file;

file = fopen(argv[1], "r");

if (!file)

fprintf(stderr, "failed open");

exit(1);

yyin=file;

//printf("success open %s\n", argv[1]);

else

printf("no input file\n");

exit(1);

188
}

list2 = (struct list*)malloc(sizeof(struct list));

list2->head = NULL;

q_list1 = (quad_list*)malloc(sizeof(quad_list));

q_list1->head = NULL;

yyparse();

print(list2->head);

// fclose(syntree);

if(errors>0){

printf("%d Errors Found\n", errors);

} else {

//display_three_add(q_list1);

fclose(icgout);

fclose(symtab);

return 0;

void yyerror(const char *s)

fflush(stdout);

errors++;

189
 fprintf(stderr, "Error: %s on line number %d\n", s, yylineno);

Assembly.s

.text

MOV R0,=c

MOV R1,[R0]

MOV R2,#10

CMP R1,R2

BLT L0

B L1

L0 :

MOV R3,=a

MOV R4,[R3]

MOV R5,#50

STR R5, [R3]

B L2

L1 :

L2 :

MOV R6,=b

MOV R7,[R6]

MOV R8,#14

STR R8, [R6]

MOV R9,=a

190
MOV R10,[R9]

MOV R11,#48

STR R11, [R9]

MOV R12,=c

MOV R0,[R12]

MOV R1,#10

CMP R0,R1

BLT L3

B L4

L3 :

MOV R2,=a

MOV R3,[R2]

MOV R4,#7

STR R4, [R2]

B L5

L4 :

MOV R5,=c

MOV R6,[R5]

MOV R7,#10

CMP R6,R7

BGT L6

B L7

L6 :

191
MOV R8,=a

MOV R9,[R8]

MOV R10,#66

STR R10, [R8]

B L5

L7 :

MOV R11,=c

MOV R12,[R11]

MOV R0,#10

CMP R12,R0

BGT L8

B L9

L8 :

MOV R1,=a

MOV R2,[R1]

MOV R3,#66

STR R3, [R1]

B L5

L9 :

L5 :

MOV R4,=c

MOV R5,[R4]

MOV R6,#43

192
STR R6, [R4]

MOV R7,=c

MOV R8,[R7]

MOV R9,#t15

STR R9, [R7]

MOV R10,=p

MOV R11,[R10]

MOV R12,#9.7

STR R12, [R10]

MOV R0,=p

MOV R1,[R0]

MOV R2,#200

STR R2, [R0]

MOV R3,=p

MOV R4,[R3]

MOV R5,#5

CMP R4,R5

BLT L10

B L11

L10 :

MOV R6,=a

MOV R7,[R6]

MOV R8,#10

193
STR R8, [R6]

B L12

L11 :

L12 :

L13 :

MOV R9,=i

MOV R10,[R9]

MOV R11,#10

CMP R10,R11

BLT L14

B L15

L14 :

MOV R12,=a

MOV R0,[R12]

MOV R1,=b

MOV R2,[R1]

CMP R0,R2

BLT L16

B L17

L16 :

B L13

B L18

L17 :

194
L18 :

MOV R3,=a

MOV R4,[R3]

MOV R5,=b

MOV R6,[R5]

CMP R4,R6

BGT L19

B L20

L19 :

B L15

B L21

L20 :

L21 :

MOV R7,=i

MOV R8,[R7]

MOV R9,#1

MOV R10,=i

MOV R11,[R10]

ADD R11,R8,R9

STR R11, [R10]

B L13

L15 :

MOV R12,=a

195
MOV R0,[R12]

MOV R1,#200

STR R1, [R12]

SWI 0x011

.DATA

p: .WORD 0

arr: .WORD 1 2 3

a: .WORD 17

b: .WORD 22

c: .WORD 39

i: .WORD 0

Output

196
197
Results

Our Compiler has been able to compile and generate code for the Sample Input files pretty
accurately. It can detect a plethora of errors and satisfactorily compile and produce optimal code.
We are confident that by the end of the semester, we will be able to build a reputable compiler
for C++.

Possible Shortcoming

The compiler we built is a mini-compiler and doesn’t entirely mimic or compile all C++ code.
We haven’t implemented Object Oriented Programming or STLs that make up the majority of
C++. And the functions we have generated have been optimized specifically for the current
language and grammar that has been elaborated on in this document. The generated code may be
a bit buffed up compared to a highly optimized version of the same, generated by an Official
C++ Compiler.

Conclusions

We can conclude that a satisfactorily accurate compiler can be build using Lex and Yacc for a
number of different languages spreading across multiple genres. We can conclude that the
various phases of a standard compiler can be built and implemented using these tools and by
following all regulations, a standard compiler can be built for almost any language.

Enhancements

We have included one construct of our own and plan to add a few more techniques we have
learned during the duration of this course that may not be present in the standard C++ compiler.

198