Lab File
Compiler Design Lab
(BCS -652)
Submitted by
[Student’s Name]
[Roll No.]
Department of Computer Science & Engineering
B. S. A. College of Engineering &
Technology Mathura (U.P.) -
281004
List of Experiments
Serial Date
Experiment
No.
1 INSTALLATION OF SOFTWARES : DEV CPP, FLEX, BISON.
2 WRITE A LEX PROGRAM TO CHEAK WETHER INPUT
STRING CONTAINS NUMBER.
3 WRITE A PROGRAM TO CHECK INPUT
IDENTEFIER IS VALID OR NOT.
4 WRITE A LEX PROGRAM TO COUNT NUMBER OF WORDS
CHARACTER , NUMBER OF LINES AND SPACES
5 IMPLEMENT LEXICAL ANALYSER USING LEX TOOL
6 WRITE YACC PROGRAM TO RECOGNIZE A VALID ARITHMETIC
EXPRESSION THAT USES OPERATOR +,-, * AND /.
7 WRITE YACC PROGRAM TO RECOGNIZE A VALID VARIABLE
WHICH STARTS WITH A LETTER FOLLOWED BY ANY NUMBER OF
LETTERS OR DIGITS.
8 WRITE A YACC PROGRAM TO IMPLEMENT GRAMMER FOR
A SIMPLE CALCULATOR.
9 WRITE A PROGRAM TO DESIGN LALR BOTTOM UP PARSER.
10 WRITE A PROGRAM TO CONVERT NFA INTO DFA.
11 WRITE A PROGRAM FOR IMPLEMENTATION OF SHIFT
REDUCE PARSING ALGORITHM
PROGRAM NO:-1
Softwares Installation
Gnuwin provides Win32-versions of GNU tools or tools with a similar open source licence.
1) Dev c++(with gcc compiler)
install DevC++ at “C:\[Link]”
2) Flex([Link]
install flex at “C:\GnuWin32”
3) Bison([Link]
install flex at “C:\GnuWin32”
4) Open Environment Variables.
Add “C:\GnuWin32\bin;C:\Dev-Cpp\TDM-GCC-64\bin” to path
Compiling and running LEX program
flex filename.l
gcc [Link].c
[Link]
Compiling and running Yacc program
flex filename.l
bison -dy filename.y
gcc [Link].c [Link].c
[Link]
Flex (Fast Lexical Analyzer Generator)
Flex (Fast Lexical Analyzer Generator), or simply Flex, is a tool for generating lexical analyzers scanners or lexers. Written by Vern
Paxson in C, circa 1987,
Flex is designed to produce lexical analyzers that is faster than the original Lex program.
It is often used along with Berkeley Yacc or GNU Bison parser generators. Both Flex and Bison are more flexible, and produce faster
code, than their ancestors Lex and Yacc.
Flex (fast lexical analyzer) and Yacc (yet another compiler-compiler/Bison) generate scanners and parsers respectively to create compilers.
Flex converts input characters into tokens defined by regular expressions, while Yacc parses these tokens based on grammar rules to
produce C code, which is then compiled into an executable.
Role of Flex in Compiler Design
Flex takes a specification file (with extension .l) containing regular expressions and actions, and automatically generates a C program that
performs lexical analysis.
Flex generates a function called yylex()
yylex() reads the input stream character by character
It identifies tokens based on the given rules
These tokens are then passed to the parser
Given image describes how the Flex is used:
How Flex Works (Workflow)
1. A lexical specification file lex.l is written using Flex syntax.
2. The Flex compiler converts lex.l into a C file named [Link].c.
3. The C compiler compiles [Link].c into an executable (usually [Link]).
4. The executable reads input characters and produces a stream of tokens.
Parser (Yacc - parser.y)
Defines the grammar. yacc -d creates [Link].h to share token definitions (%token) with Flex.
Key Concepts
yylval : Variable used to pass token values from Flex to Yacc.
yytext : String containing the matched text.
yylex(): Function generated by Flex that returns the next token.
yyparse() : Function generated by Yacc to start [Link] Resolution: If two patterns match the same string, the longest
match wins; otherwise, the first listed rule [Link] Recursion: In Yacc, prefer left-recursive rules (e.g., list: list ',' item) over right-
recursive rules to prevent stack overflow. Windows: Install through MinGW or GnuWin32.
PROGRAM N0:02
OBJECT: WRITE A LEX PROGRAM TO CHEAK WETHER INPUT STRING
CONTAINS NUMBER
%{
#include <stdio.h>
%}
%%
[0-9]+ { printf("entered value contains\ninteger: %s\n", yytext); }
. { ;}
%%
main( ){
printf("enter alphanumeric\n");
yylex();
}
int yywrap(){
return 1;
}
PROGRAM N0:03
OBJECT:WRITE A PROGRAM TO CHEAK INPUT IDENTEFIER IS VALID
OR NOT.
%{
#include<stdio.h>
%}
%%
([_]?[a-zA-Z][_]?[a-zA-Z0-9]*)* {printf("\n %s is valid identifier",yytext);}
.* { printf("\n\t%s is invalid Identifier",yytext);}
%%
int main()
{
printf("enter identifier\n");
yylex();
}
int yywrap()
{
return 1;
}
PROGRAM NO:04
Object:WRITE A LEX PROGRAM TO COUNT NUMBER OF CHARACTER,
WORDS, LINES AND NUMBER OF SPACES.
%{
#include<stdio.h>
int sc=0,wc=0,lc=0,cc=0;
%}
%%
[\n] { lc++; }
[ \t] { sc++; }
[^\t\n ]+ { wc++; cc+=yyleng;}
%%
main(){
printf("Enter the input\n");
yylex();
printf("The number of lines=%d\n",lc);
printf("The number of spaces=%d\n",sc);
printf("The number of words=j%d\n",wc);
printf("The number of characters are=%d\n",cc);
}
int yywrap( )
{
return 1;
}
PROGRAM NO:05
Object: IMPLEMENT LEXICAL ANALYSER USING LEX TOOL.
%{
int COMMENT=0;
%}
identifier [a-zA-Z][a-zA-Z0-9]*
%%
#.* {printf("\n%s is preprocessor directive",yytext);}
int |
float |
char |
double |
while |
for |
struct |
do |
if |
break |
continue |
void |
switch |
return |
else |
goto {printf("\n\t%s is a keyword",yytext);}
"/*" {COMMENT=1;}{printf("\n\t %s is COMMENT",yytext);}
{identifier}\( {if(!COMMENT)printf("\nFUNCTION \n\t%s",yytext);}
\{ {if(!COMMENT)printf("\n BLOCK BEGINS");}
\} {if(!COMMENT)printf("BLOCK ENDS ");}
{identifier}(\[[0-9]*\])? {if(!COMMENT) printf("\n %s IDENTIFIER",yytext);}
\".*\" {if(!COMMENT)printf("\n\t %s is STRING",yytext);}
[0-9]+ {if(!COMMENT) printf("\n %s is INTEGER NUMBER ",yytext);}
[0-9]*\.[0-9]+ {if(!COMMENT) printf("\n %s is FLOAT NUMBER ",yytext);}
\)(\:)? {if(!COMMENT)printf("\n\t");ECHO;printf("\n");}
\( ECHO;
= {if(!COMMENT)printf("\n\t %s is ASSIGNMENT OPERATOR",yytext);}
\<= |
\>= |
\< |
== |
\> {if(!COMMENT) printf("\n\t%s is RELATIONAL OPERATOR",yytext);}
%%
int main(int argc, char **argv)
{
FILE *file;
file=fopen("var.c","r");
if(!file)
{
printf("could not open the file");
exit(0);
}
yyin=file;
yylex();
printf("\n");
return 0;
}
int yywrap()
{
return 1;
}
var.c
int main()
{
int a=23;
int b=6.7;
printf("%d,%f",a,b);
return 0;
}
PROGRAM NO:06
Object: WRITE YACC PROGRAM TO RECOGNIZE A VALID ARITHMETIC
EXPRESSION THAT USES OPERATOR +,-, * AND /.
CREATE bas.l FILE-
%{
#include "[Link].h"
%}
%%
[a-zA-Z] { return ALPHA; }
[0-9]+ { return NUM; }
[\t\n]+ ;
. { return yytext[0]; }
%%
CREATE bas.y FILE-
%{
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
int yylex();
int yyerror();
%}
%token NUM ALPHA
%left '+' '-'
%left '*' '/ '
%left '(' ')'
%%
expr:'+'expr
|'-'expr
|expr'+'expr
|expr'-'expr
|expr'*'expr
|expr'/'expr
|'('expr')'
|NUM
|ALPHA
;
%%
int main( )
{
printf("enter an arithmetic expression\n"); yyparse();
printf("arithmetic expression is valid\n"); return 0;
}
int yyerror( )
{
printf("\n arithmetic expression is invalid"); exit(0);
}
yywrap()
{
return 1;
}
PROGRAM NO:07
Object: WRITE YACC PROGRAM TO RECOGNIZE A VALID VARIABLE WHICH
STARTS WITH A LETTER FOLLOWED BY ANY NUMBER OF LETTERS OR DIGITS
CREATE bas.l FILE-
%{
#include "[Link].h"
%}
%%
[a-zA-Z][a-zA-Z0-9]* { return VARIABLE; }
[ \t\n]+ ;
. { return yytext[0];}
%%
CREATE bas.y FILE-
%{
#include <stdio.h>
#include
<stdlib.h> #include
<string.h> int
yyerror();
int yylex();
%}
%token VARIABLE
%%
E:
VARIABLE {printf("Valid variable\n");}
;
%%
int main() {
printf("Enter a variable name:
"); yyparse();
return 0;
}
int yyerror() {
printf("invalid variable\n");
exit(0);
}
yywrap()
{
return 1;
}
PROGRAM NO:08
Object: WRITE A YACC PROGRAM TO IMPLEMENT GRAMMER FOR A SIMPLE
CALCULATOR
CREATE bas.l FILE-
%{
#include<stdio.h>
#include"[Link].h"
extern int yylval;
%}
%%
[0-9]+ { yylval=atoi(yytext); return NUM;}
[\t\n ] ;
. return yytext[0];
%%
CREATE bas.y FILE-
%{
#include<stdio.h >
#include<stdlib.h>
#include<ctype.h>
int yylex();
int yyerror();
%}
%token NUM
%left '+' '-'
%left '*' '/'
%%
expr: e { printf("Result:%d\n",$$); return 0; }
;
e:e'+'e {$$=$1+$3;}
| e'-'e {$$=$1-$3;}
| e'*'e {$$=$1*$3;}
| e'/'e {$$=$1/$3;}
| '('e')' {$$=$2;}
| NUM {$$=$1;}
;
%%
int main(){
printf("\n Enter the Arithmetic Expression:\n"); yyparse();
printf("\nValid Expression\n");
}
int yyerror()
{
printf("\n Invalid Expression\n"); exit(0);
}
int yywrap( )
{
return 1;
}
PROGRAM NO:09
Object : Write a program to Design LALR Bottom up Parser. LALR PARSER E-
>E+T E->T
T->T*F T-
>F F->(E) F-
>i
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>
void push(char *,int *,char);
char stacktop(char *);
void isproduct(char,char);
int ister(char);
int isnter(char);
int isstate(char);
void error();
void isreduce(char,char);
char pop(char *,int *);
void printt(char *,int *,char [],int);
void rep(char [],int);
struct action
{
char row[6][5];
};
const struct action A[12]={
{"sf","emp","emp","se","emp","emp"},
{"emp","sg","emp","emp","emp","acc"},
{"emp","rc","sh","emp","rc","rc"},
{"emp","re","re","emp","re","re"},
{"sf","emp","emp","se","emp","emp"},
{"emp","rg","rg","emp","rg","rg"},
{"sf","emp","emp","se","emp","emp"},
{"sf","emp","emp","se","emp","emp"},
{"emp","sg","emp","emp","sl","emp"},
{"emp","rb","sh","emp","rb","rb"},
{"emp","rb","rd","emp","rd","rd"},
{"emp","rf","rf","emp","rf","rf"}
};
struct gotol
{
char r[3][4];
};
const struct gotol G[12]={
{"b","c","d"},
{"emp","emp","emp"},
{"emp","emp","emp"},
{"emp","emp","emp"},
{"i","c","d"},
{"emp","emp","emp"},
{"emp","j","d"},
{"emp","emp","k"},
{"emp","emp","emp"},
{"emp","emp","emp"},
};
char ter[6]={'i','+','*',')','(','$'};
char nter[3]={'E','T','F'};
char states[12]={'a','b','c','d','e','f','g','h','m','j','k','l'};
char stack[100];
int top=-1; char temp[10];
struct grammar
{
char left; char right[5];
};
const struct grammar rl[6]={
{'E',"E+T"},
{'E',"T"},
{'T',"T*F"},
{'T',"F"},
{'F',"(E)"},
{'F',"i"},
};
void main()
{
char inp[80],x,p,dl[80],y,bl='a';
int i=0,j,k,l,n,m,c,len;
//clrscr();
printf(" Enter the input :");
scanf("%s",inp);
len=strlen(inp);
inp[len]='$';
inp[len+1]='\0';
push(stack,&top,bl); printf("\
n stack \t\t\t input");
printt(stack,&top,inp,i);
do
{
x=inp[i];
p=stacktop(stack);
isproduct(x,p);
if(strcmp(temp,"emp")==0)
error();
if(strcmp(temp,"acc")==0)
break;
else
{
if(temp[0]=='s')
{
push(stack,&top,inp[i]);
push(stack,&top,temp[1]); i+
+;
}
else
{
if(temp[0]=='r')
{
j=isstate(temp[1]);
strcpy(temp,rl[j-2].right);
dl[0]=rl[j-2].left;
dl[1]='\0';
n=strlen(temp);
for(k=0;k<2*n;k++)
pop(stack,&top);
for(m=0;dl[m]!='\0';m++)
push(stack,&top,dl[m]);
l=top;
y=stack[l-1];
isreduce(y,dl[0]);
for(m=0;temp[m]!='\0';m++)
push(stack,&top,temp[m]);
}
}
}
printt(stack,&top,inp,i);
}while(inp[i]!='\0');
if(strcmp(temp,"acc")==0)
printf(" \n accept the input ");
else
printf(" \n do not accept the input ");
getch();
}
void push(char *s,int *sp,char item)
{
if(*sp==100)
printf(" stack is full ");
else
{
*sp=*sp+1;
s[*sp]=item;
}
}
char stacktop(char *s)
{
char i; i=s[top];
return i;
}
void isproduct(char x,char p)
{
int k,l;
k=ister(x);
l=isstate(p);
strcpy(temp,A[l-1].row[k-1]);
}
int ister(char x)
{
int i;
for(i=0;i<6;i++)
if(x==ter[i])
return i+1;
return 0;
}
int isnter(char x)
{
int i; for(i=0;i<3;i+
+) if(x==nter[i])
return i+1; return 0;
}
int isstate(char p)
{
int i;
for(i=0;i<12;i++)
if(p==states[i])
return i+1;
return 0;
}
void error()
{
printf(" error in the input ");
exit(0);
}
void isreduce(char x,char p)
{
int k,l;
k=isstate(x);
l=isnter(p);
strcpy(temp,G[k-1].r[l-1]);
}
char pop(char *s,int *sp)
{
char item;
if(*sp==-1)
printf(" stack is empty ");
else
{
item=s[*sp];
*sp=*sp-1;
}
return item;
}
void printt(char *t,int *p,char inp[],int i)
{
int r;
printf("\n");
for(r=0;r<=*p;r++)
rep(t,r); printf("\t\
t\t");
for(r=i;inp[r]!='\0';r++)
printf("%c",inp[r]);
}
void rep(char t[],int r)
{
char c;
c=t[r];
switch(c)
{
case 'a': printf("0"); break;
case 'b': printf("1"); break;
case 'c': printf("2"); break;
case 'd': printf("3"); break;
case 'e': printf("4"); break;
case 'f': printf("5"); break;
case 'g': printf("6"); break;
case 'h': printf("7"); break;
case 'm': printf("8"); break;
case 'j': printf("9"); break;
case 'k': printf("10"); break;
case 'l': printf("11"); break;
default :printf("%c",t[r]); break;
}
}
PROGRAM NO:10
Object : Write a program to convert NFA to DFA
Create Nfa_ip.txt file
1,2 1
-1 2
-1 -1#
0
2
Create C program
#include<stdio.h>
int Fa[10][10][10],states[2]
[10],row=0,col=0,sr=0,sc=0,th=0, in,stat,new_state[10]
[10],max_inp=-1,no_stat;
FILE *fp;
int search(int search_var)
{
int i;
for(i=0;i<no_stat;i++)
if(search_var == states[1][i])
return 1;
return 0;
}
int sort(int *arr,int count)
{
int temp,i,j;
for(i=0;i<count-1;i++)
{
for(j=i+1;j<count;j++)
{
if(arr[i]>=arr[j])
{
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}
return 0;
}
int checkcon(int *arr,int *count) //for doing this {4,1}={1,2,1}=={1,2}
{
int i,temp,j,k,c,t,m;
for(i=0;i<*count;i++)
{
if(arr[i]>row)
{
temp =arr[i];
c=0;
t=0;
while(new_state[arr[i]][t]!=-1)
{t++;
c++;
}
//right shift from ith postion (c-2) th
time for(k=0;k<=c-2;k++)
{
for(j=9;j>=i+1+k;j--)
{
arr[j]=arr[j-1];
}
}
t=0;
for(j=i;j<c;j++)
{
arr[j]=new_state[temp][t];
t++;
}
}
}
c=0;
for(i=0;arr[i]!=-1;i++)
c++;
*count=c;
return 0;
}
int remove_duplicate(int *arr,int *count)
{
int i,j=0;
for(i=1;i<*count;i++)
{
if(arr[i]!=arr[j])
{
j++;
arr[j]=arr[i];
}
}
*count=j+1;
return 0;
}
int check(int i ,int j,int c,int *name)///for checking is this a new state?
{
int t,l,f; for(l=0;l<=stat;l+
+)
{
t=0; f=0;
while(Fa[i][j][t]!=-1)
{
if(Fa[i][j][t]==new_state[l][t])
t++;
else
{f
=1;
break;
}
}
if((t==c)&&!f)
{
*name=l;
return 1;
}
}
return 0;
}
int trans(int i ,int j,int t,int c,int *count,int *arr)//transition o/p for particular i/p on states
{
int k=0,co,temp;
*count=0; for(k=0;k<c;k+
+)
{
temp=Fa[i][j][k];
co=0;
while(Fa[temp][t][co]!=-1)
{
arr[*count]=Fa[temp][t][co++]; (*count)
++;
}
}
return 0;
}
int nfa2dfa(int start,int end)
{
int j,t,c,i,k,count,arr[10],name,l;
for(i=start;i<=end;i++)
{
for(j=0;j<=max_inp;j++)
{
c=0;t=0;
while(Fa[i][j][t]>=0)
{t
++;
c++;
}
if(c>1)
{
if(check(i,j,c,&name)==0)
{
for(k=0;k<c;k++)
{
new_state[stat][k]=Fa[i][j][k];
for(l=0;states[1][l]!=-1;l++)
if(new_state[stat][k] == states[1][l]&& !search(stat)) states[1][no_stat+
+]=stat;
}
for(t=0;t<=max_inp;t++)
{
count=0;
for(k=0;k<10;k++)
arr[k]=-1;
trans(i,j,t,c,&count,arr);
checkcon(arr,&count);
sort(arr,count);
remove_duplicate(arr,&count);
for(k=0;k<count;k++) Fa[stat][t]
[k]=arr[k];
}
Fa[i][j][0]=stat++;
for(t=1;t<c;t++)
Fa[i][j][t]=-1;
}
else
{
Fa[i][j][0]=name
; for(t=1;t<c;t++)
Fa[i][j][t]=-1;
}
}
}
}
return 0;
}
int main()
{
int i,j,k,flag=0,start,end;
char c,ch;
fp=fopen("Nfa_ip.txt","r+");
for(i=0;i<2;i++)
for(j=0;j<10;j++)
states[i][j]=-1;
for(i=0;i<10;i++)
for(j=0;j<10;j++)
new_state[i][j]=-1;
for(i=0;i<10;i++)
for(j=0;j<10;j++)
for(k=0;k<10;k++)
Fa[i][j][k]=-1;
while(fscanf(fp,"%d",&in)!=EOF)
{
fscanf(fp,"%c",&c);
if(flag)
{
states[sr][sc++]=in;
if(c=='\n')
{
sr++;
sc=0;
}
}
else if(c=='#')
{
flag=1; Fa[row][col]
[th]=in;
}
else if(!flag)
{
Fa[row][col][th]=in;
if(c==',')
{
th++;
}
else if(c=='\n')
{
if(max_inp<col)
max_inp=col;
col=0;
row++;
th=0;
}
else if(c!=',')
{
col++;
th=0;
}
}
}
no_stat=0;
i=0;
while(states[1][i++]!=-1)
no_stat++;
stat=row+1;
start=0;end=row;
while(1)
{
nfa2dfa(start,end);
start=end+1;
end=row;
if(start>end)
break;
}
printf("\n\nDFA IS : \n\n\n");
for(i=0;i<=max_inp;i++)
printf("\t%d",i);
printf("\n");
printf(" \n");
for(i=0;i<stat;i++)
{
printf("%d-> |",i);
for(j=0;j<=max_inp;j++)
{
printf("%2d ",Fa[i][j][0]);
}
printf("\n");
}
printf("\n\n");
printf("Total Number Of State Is : %d \n\
n",stat); printf("Final States Are : ");
for(i=0;states[1][i]!=-1;i++)
printf("%d ",states[1][i]);
printf("\n\n");
getch();
return 0;
}
PROGRAM NO:11
OBJECT:To write a C program to implement the shift-reduce parsing algorithm
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char ip_sym[15],stack[15]; int ip_ptr=0,st_ptr=0,len,i; char temp[2],temp2[2];
char act[15];
void check();
void main()
{
//clrscr();
printf("\n\n\t Shift Reduce Parser\n"); printf("\n\t***** ****** ******");
printf("\n Grammar\n\n");
printf("E->E+E\nE->E/E\n"); printf("E->E*E\nE->a/b");
printf("\n Enter the Input Symbol:\t"); gets(ip_sym);
printf("\n\n\t Stack Implementation Table"); printf("\n Stack\t\t Input Symbol\t\t Action");
printf("\n $\t\t %s$\t\t\t --",ip_sym);
strcpy(act,"shift");
temp[0]=ip_sym[ip_ptr];
temp[1]='\0';
strcat(act,temp);
len=strlen(ip_sym);
for(i=0;i<=len-1;i++)
{
stack[st_ptr]=ip_sym[ip_ptr]; stack[st_ptr+1]='\
0'; ip_sym[ip_ptr]=' '; ip_ptr++; printf("\n$%s\t\
t%s$\t\t\t%s",stack,ip_sym,act);
strcpy(act,"shift");
temp[0]=ip_sym[ip_ptr];
temp[1]='\0';
strcat(act,temp);
check();
st_ptr++;
}
st_ptr++; check();
getch();
}
void check()
{
int flag=0;
temp2[0]=stack[st_ptr];
temp[1]='\0';
if((!strcmpi(temp2,"a"))||(!strcmpi(temp2,"b")))
{
stack[st_ptr]='E'; if(!
strcmpi(temp2,"a"))
printf("\n$%s\t\t%s$\t\t\tE->a",stack,ip_sym);
else
printf("\n$%s\t\t%s$\t\t\tE->a",stack,ip_sym);
flag=1;
}
if((!strcmpi(temp2,"+"))||(strcmpi(temp2,"*"))||(!strcmpi(temp2,"/")))
{
flag=1;
}
if((!strcmpi(stack,"E+E"))||(!strcmpi(stack,"E/E"))||(!strcmpi(stack,"E*E")))
{
strcpy(stack,"E");
st_ptr=0; if(!
strcmpi(stack,"E+E"))
printf("\n$%s\t\t%s$\t\t\tE->E+E",stack,ip_sym);
else
if(!strcmpi(stack,"E/E")) printf("\n$%s\t\t\t%s$\t\
tE->E/E",stack,ip_sym); else
printf("\n$%s\t\t%s$\t\t\tE->E*E",stack,ip_sym);
flag=1;
}
if(!strcmpi(stack,"E")&&ip_ptr==len)
{
printf("\n$%s\t\t%s$\t\t\tAccept",ip_sym);
//getch();
exit(0);
}
if(flag==0)
{
printf("\n %s \t\t\t %s \t\t Reject",stack,ip_sym);
}
return;
}