Wednesday 8 May 2013
PRINCIPLES OF COMPILER DESIGN LAB MANUAL
EX. NO: 1 CONSTRUCTION OF NFA
AIM:
To construct NFA for the given regular expression.
ALGORITHM:
1. Get the regular expression.
2. Mark the initial state with a line and final state with double circle.
3. Mark the intermediate states with a single circle and a line connecting previous state and current state with an arrow towards the current state.
4. Display the input above the arrow for every transition.
5. Initial state must have no incoming states and final state should not have any outgoing states.
6. The input is, A REGULAR EXPRESSION ‘r’ OVER AN ALPHABET ‘E’.
7. The output is, AN NFA ‘N’ ACCEPTING L(r).
8. Parse ‘r’ into the sub expressions.
9. Using the rules construct NFA for each of the basic symbols in ‘r’.
PROGRAM:
#include<stdio.h>
#include<conio.h>
#include<dos.h>
#include<graphics.h>
#include<math.h>
void a(int,int);
void b(int,int);
void p();
void main()
{
int ch;
int gd=DETECT,gm;
initgraph(&gd,&gm,"E:\\TC\\BGI\\");
clrscr();
while(ch!=6)
{
printf("Menu \n 1. Empty Input \n 2. a \n 3. a|b \n 4. ab\n 5. (a|b)^* \n 6.Exit \n Enter the exp ");
scanf("%d",&ch);
switch(ch)
{
case 1:
a(150,150);
circle(210,150,15);
outtextxy(180,135,"e");
outtextxy(125,147,">");
line(115,150,140,150);
getch();
cleardevice();
break;
case 2:
a(150,150);
circle(210,150,15);
line(115,150,140,150);
outtextxy(125,147,">");
outtextxy(180,135,"a");
getch();
cleardevice();
break;
case 3:
circle(245,200,15);
p();
getch();
cleardevice();
break;
case 4:
a(150,150);
b(275,150);
line(220,150,265,150);
circle(335,150,15);
outtextxy(175,140,"a");
outtextxy(300,140,"b");
outtextxy(235,140,"e");
outtextxy(125,147,">");
line(110,150,140,150);
line(315,150,310,145);
line(245,150,240,145);
line(245,150,240,155);
getch();
cleardevice();
break;
case 5:
p();
circle(300,200,10);
circle(300,200,15);
circle(65,200,10);
line(25,200,55,200);
line(255,200,285,200);
outtextxy(65,200,"I");
outtextxy(35,197,">");
outtextxy(300,200,"F");
arc(185,215,180,0,120);
outtextxy(185,332,">");
outtextxy(265,185,"e");
outtextxy(200,123,"<");
arc(200,190,-0,-175,65);
outtextxy(265,196,">");
outtextxy(85,185,"e");
outtextxy(185,110,"e");
outtextxy(185,320,"e");
getch();
cleardevice();
break;
case 6:
exit(0);
}
}
getch();
closegraph();
}
void a(int x,int y)
{
int ch;
circle(x,y,10);
circle(x+60,y,10);
line(x+10,y,x+50,y);
outtextxy(x,y,"2");
outtextxy(x+60,y,"3");
line(185,y,180,y-5);
line(185,y,180,y+5);
}
void b(int x,int y)
{ int ch;
circle(x,y,10);
circle(x+60,y,10);
line(x+10,y,x+50,y);
outtextxy(x,y,"4");
outtextxy(x+60,y,"5");
line(185,y,180,y-5);
line(185,y,180,y+5); }
void p()
{ a(150,150);
b(150,250);
circle(125,200,10);
outtextxy(120,170,"e");
outtextxy(85,197,">");
outtextxy(120,220,"e");
outtextxy(240,170,"e");
outtextxy(240,220,"e");
outtextxy(180,135,"a");
outtextxy(180,260,"b");
outtextxy(85,197,"<");
line(75,200,115,200);
line(125,190,140,155);
line(125,210,145,240);
circle(245,200,10);
line(220,155,240,185);
line(240,215,220,250);
outtextxy(125,200,"1");
outtextxy(245,200,"6");
}
OUTPUT:
Menu
1. E
2. a + b
3. a.b
4. a
5. (a/b)*
Enter the option 2
RESULT:
Thus the program for Constructing NFA for the given regular expression is executed successfully.
EX.NO:2 CONSTRUCTION OF MINIMIZED DFA
AIM:
To construct DFA for the given regular expression.
ALGORITHM:
1. Start the process.
2. Get the regular expression.
3. Mark the initial state Π of the set of states with accepting states and non accepting states.
4. Apply the procedure to Π to partition construct a new partition Π new.
5. If Π new= Π, let Π final= Π and continue with step 4 otherwise repeat step 2 with Π := Π new.
6. When the final partition Π has been constructed, pick a representative for each group..
7. Start state and accepting state of the minimized DFA are the group containing the start state and accepting states of the original DFA.
8. Stop the process.
PROGRAM:
#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<process.h>
void main()
{
int t,i=0,j=0;
char ch[10],l[10],r[10];
clrscr();
printf("\n REGULAR EXPRESSION TO DFA\n");
printf("\nEnter the regular expression : ");
scanf("%s",ch);
t=strlen(ch);
while(i<=t)
{
if(ch[i]=='a'||ch[i]=='b')
{
l[j]=ch[i];
j++;
}
else if(ch[i]=='*')
{
r[j-1]=ch[i-1];
l[j-1]='\0';
j--;
}
else if(ch[i]=='+')
{
r[j]=ch[i-1];
}
i++;
}
printf("\n TRANSITION TABLE FOR DFA\n");
printf("\nSTATES \t a \tb\n");
for(i=0; i<=j; i++)
{
if(r[i]=='a')
{
if(l[i]=='a')
printf("\n %d\t %d,%d",i,i,i+1);
else if(l[i]=='b')
printf("\n %d\t%d, %d",i,i,i+1);
else
printf("\n %d\t %d",i,i);
}
else if(r[i]=='b')
{
if(l[i]=='b')
printf("\n %d\t\t%d, %d",i,i,i+1);
else if(l[i]=='a')
printf("\n %d\t %d\t%d",i,i+1,i);
else
printf("\n %d\t\t%d",i,i);
}
else
{
if(l[i]=='a')
printf("\n %d\t %d",i,i+1);
else if(l[i]=='b')
printf("\n %d\t\t%d",i,i+1);
else
printf("\n %d\t - \t - ",i);
}
}
getch();
}
OUTPUT:
REGULAR EXPRESSION TO DFA
Enter the regular expression : ab*b+
TRANSITION TABLE FOR DFA
STATES a b
0 1
1 1, 2
2 2
RESULT:
Thus the program for Constructing DFA for the given regular expression is executed successfully
EX.NO:3 IMPLEMENTATION OF LEXICAL ANALYSER USING LEXTOOL
AIM:
To write a C program to implement lexical analysis using LEX tool.
ALGORITHM:
1. Start the program.
2. Lex program consists of three parts.
a. Declaration %%
b. Translation rules %%
c. Auxilary procedure.
3. The declaration section includes declaration of variables, maintest, constants and regular definitions.
4. Translation rule of lex program are statements of the form
a. P1 {action}
b. P2 {action}
c. …
d. …
e. Pn {action}
5. Write a program in the vi editor and save it with .l extension.
6. Compile the lex program with lex compiler to produce output file as lex.yy.c. eg $ lex filename.l
$ cc lex.yy.c -ll
7. Compile that file with C compiler and verify the output.
PROGRAM:
%{
%}
identifier[a-zA-Z][a-zA-Z0-9]*
%%
#.* printf("\n%s is PREPROCESSOR DIRECTIVE\n", yytext);
int |
float |
double |
char |
for |
if printf("%s is a keyword\n",yytext);
{identifier}\( printf("\n\n FUNCTION CALL\n %s",yytext);
\{
printf("BLOCK BEGINS\n");
\}
printf("BLOCK ENDS\n");
{identifier}(\[[0-9]*\])? printf("%s is identifier\n",yytext);
= printf("%s is a ASSIGNMENT OPERATOR\n",yytext);
[0-9]+ printf("%s is NUMBER\n",yytext);
\< |
\> |
\== |
\>= |
\<= printf("%s is a RELATIONAL OPERATOR\n",yytext);
\( { ECHO(;printf("\n");}
\) { ECHO); printf("\n");}
\+ |
\- |
\* printf("%s is a ARITHMETIC OPERATOR \n");
\++ printf("%s is a INCREMENTAL OPERATOR\n");
\; { ECHO; printf("\n");}
%%
main()
{
yylex();
}
int yywrap()
{
return 1;
}
"sam1.l" 42L, 753C written
OUTPUT:
[localhost@server ~]$ lex sam1.l
[localhost @server ~]$ cc lex.yy.c -ll
[localhost @server ~]$. /a. out
a
a is identifier
#
# is PREPROCESSOR DIRECTIVE
include
include is identifier
<
< is a RELATIONAL OPERATOR
stdio
stdio is identifier
RESULT:
Thus the lexical analyser is implemented using lex tool.
EX.NO:4 IMPLEMENTATION OF SYMBOL TABLE
AIM:
To implement symbol table using C Language.
ALGORITHM:
1. Open the file pointer for the input file.
2. Read each string and separate the token.
3. For identifiers use ‘id’,’k’ for keywords and‘s’ for symbols.
4. Write each string in the above form to an output file.
5. For each identifier read make an entry in symbol table.
6. For each symbol mention its type, value, relocatable location and size.
7. If there is an assignment expression updates the table.
PROGRAM:
#include<conio.h>
#inclde<string.h>
#include<ctype.h>
#include<process.h>
struct identifier
{
char name[10],type[10],value[10];
int size;
};
void main()
{
FILE *f;
struct identifier id[10];
char ch, str[19],num[2]=”0”;
int nid=0,k,flag=0,lastdata,I,oper1=0.idflag=0,,s[10]={1,2,4,8},loc=1000,operand1,operand2,des;
char key[10][10]={“char”,”int”,”float”,”double”};
char iden[10][10],operation;
clrscr();
f=fopen(“lexical.txt”,”r”);
if(f==NULL)
exit(0);
ch=fgetc(f);
while(ch!=’{‘)
ch=fgetc(f);
while(ch=EOF)
{
switch(ch)
{
case ‘{‘:
printf(“\n OB”);
break;
case’}’:
printf(“\n CB”);
break;
case’,’:
printf(“\n PM1”);
break;
case’;’:
printf(“\n PM2”);
break;
case’:’:
printf(“\n PM3”);
break;
case’”’:
printf(“\n PM4”);
break;
case’ ’:
printf(“ ”);
break;
case’(’:
printf(“\n OPA”);
break;
case’)’:
printf(“\n CPA”);
break;
case’+’:
printf(“\nOP1”);
break;
case’-’:
printf(“\nOP2”);
break;
case’*’:
printf(“\nOP3”);
break;
case’/’:
printf(“\nOP4”);
break;
case’>’:
printf(“\nOP5”);
break;
case’<’:
printf(“\nOP6”);
break;
case’!’:
printf(“\nOP7”);
break;
case’&’:
printf(“\nOP8”);
break;
case’=’:
printf(“\nOP9”);
break;
case ‘1’:
case ‘2’:
case ‘3’:
case ‘4’:
case ‘5’:
case ‘6’:
case ‘7’:
case ‘8’:
case ‘9’:
case ‘0’:
printf(“%c”,ch);
break;
default:
if(isalpha(ch))
{
if(idflag!=1)
{
k=0;
while(ch=’’)&& &&(ch!=’;’) (ch!=’,’) &&(ch!=’=’) &&(ch!=’+’) &&(ch!=’=’) &&(ch!=’-’) &&(ch!=’*’) &&(ch!=’/’))
{
str[k++]=ch;
ch=fgetc(f);
flag=1;
idflag=1;
}
Str[k++]=ch;
ch=fgetc(f);
flag=1;
idflag=1;
}
str[k]=’\0’;
if(strcmp(str,”char”)==0)
{
lastdata=0;
printf(“\n key1”);
}
else if(strcmp(str,”int”)==0)
{
lastdata=1;
printf(“\n key2”);
}
else if(strcmp(str,”float”)==0)
{
lastdata=1;
printf(“\n key3”);
}
else if(strcmp(str,”double”)==0)
{
lastdata=3;
printf(“\n key4”);
}
else
{
idflag=0;
for(i=0;i<nid;i++)
{
if(strcmp(str,iden[i])==0)
break;
}
if(i==nid+1)
printf(“Found invalid identifier”);
else
{
printf(“%s”,id[i].name);
if(ch==’;’)
{
strcpy(str,id[i].value);
operand2=0;
for(j=0;j<strlen(str);j++)
{
operand2=opearnd2*10+(str[j]-48);
}
if(operation==’+’)
operand1=operand1+operand2;
if(operation==’-’)
operand1=operand1-operand2;
if(operation==’*’)
operand1=operand1*operand2;
if(operation==’/’)
operand1=operand1/operand2;
j=0;
while(operand>0)
{
str[j]=(opearnd1%10)+48;
opearnd1=operand1/10;
j++;
}
str[j]=’\0’;
strrev(str);
strcpy(id[des].value,str);
}
if(ch==’+’||ch==’-‘||ch==’/’||ch==’*’)
{
operation=ch;
if(oper1==0)
{
strcpy(str,id[i].value);
operand1=0;
for(j=o;j<strlen(str);j++)
{
operand1=opearnd1*10+(str[j]-48);
}
oper1=1;
}
}
if(ch==’=’)
{
ch=fget(f);
if(isdigit(ch))
{
k=0;
printf(“OP9”);
while((ch!=’;’)&&(ch!=’,’)&&(ch!=’ ‘))
{
flag=1;
str[k++]=ch;
ch=fgetc(f);
}
str[k]=’\0’;
strcpy(id[i].value,str);
printf(“%s”,id[i].value);
}
else
{
des=I;
}}}}}
else
{
flag=1;
k=0;
while((ch!=’;’)&&(ch!=’,’)&&(ch!=’=’))
{
str[k++]=ch;
ch=fgetc(f);
flag=1;
}
str[k]=’\0’;
strcpy(iden[nid],str);
strcpy(str,”id”);
strcat(str,num);
num[0]++;
strcpy(id[nid].name,str);
id[nid].size=s[lastdata];
printf(“%s”,str);
if(ch==’;’)
{
idflag=0;
lastdata=4;
}
k=0;
if(ch==’=’)
{
printf(“OP9”);
ch=fgetc(f);
if(isdigit(ch))
{
while((ch!=’;’)&&(ch!=’,’)&&(ch!=’ ‘))
{
Str[k++]=ch;
ch=fgetc(f);
}
str[k]=’\0’;
printf(“%s”,str);
strcpy(id[nid].value,str);
}
}
nid++;
}
}
break;
}
if(flag!=1)
ch=fgetc(f);
flag=0;
}
printf(“\n \t SYMBOL TABLE \n\n NAME TYPE SIZE LOC VALUE \n”);
for(i=0;i<nid;i++)
{
printf(“%s\t%s\t%d”,iden[i],id[i].type,id[i].size);
printf(“\t%d”,loc);
loc=loc+id[i].size;
printf(“\t%s\n”,id[i].value);
}
}
OUTPUT:
Lexical.txt:
Main()
{
Float x,y,z;
X=10;y=5;z=x-y;
}
OB
key3 id0 PM1 id1 PM1 id2 PM2
id0 OP9 10 PM2
id1 OP9 5 PM2
id2 id0 OP2 id1 PM2
CB
SYMBOL TABLE
NAME TYPE SIZE LOC VALUE
x float 4 1000 10
y float 4 1004 5
z float 4 1008 5
RESULT:
Thus the symbol table program was executed and verified successfully.
EX.NO:5 CONSTRUCTION OF OPERATOR PRECEDENCE PARSE TABLE
AIM:
To implement the construction of operator precedence parse table using C Language.
ALGORITHM:
1. Start the process.
2. Get the regular expression.
3. Get the no of terminals including $.
4. For identifier ‘i’ and operators ‘+’,’*’ are used.
5. Enter the terminals in row and column wise for each entry.
6. For each identifier read make an entry in operator precedence parse table.
7. For each symbol mention its type, value, relocatable location and size.
8. Finally update the symbols in priority basis to the table.
PROGRAM:
#include<stdio.h>
#include<conio.h>
void main( )
{
int i,j,n,ib=0,top=0,num[10],k,r,t,l,x,y,z,g=0,li;
char tab[10][10],s[10],stack[20],inter[10],prod[10][10];
clrscr( );
printf(“\n Enter the input expression:\n”);
scanf(“%s”,s);
printf(“\n Enter the number of terminals INC $:\n”);
scanf(“%d”,&n);
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
tab[i][j]=’ ‘;
printf({“\n Give The entries in first row and column corresponding to terminal:\n”);
num[0]=’\0’;
for(i=1;i<=n;i++)
{
scanf(“%s”,&tab[0][i]);
num[i]=tab[0][i];
tab[i][0]=tab[0][i];
}
printf(“\n Enter the precedence table row wise:\n”);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf(“%s”,&tab[i][j]);
}
}
for(i=0;i<=n;i++)
{
for(j=0;j<=n;j++)
{
printf(“%c\t”,tab[i][j]);
}
printf(“\n\n”);
}
stack[top]= ‘$’;
l=strlen(s);
s[l]=’$’;
s[l+1]=’\0’;
printf(“\nStack \t Input buffer \t Popped Elements:\n”);
printf(“$\t%s\n”,s);
for(i=0;i<=l;i++)
{
for(k=1;k<=n;k++)
{
if(stack[top]= =num[k])
x=k;
if(s[i] = =num[k])
y=k;
}
if(tab[x][y]= = ‘=’ || tab[x][y] = = ‘<’)
{
stack[top+1]=s[i];
top++;
ib++;
}
else if(tab[x][y]= = ‘>’)
{
inter[g]=stack[top];
g++;
stack[top]=s[i];
ib++;
}
for(r=0;r<=top;r++)
printf(“%c”,stack[r]);
printf(“\t”);
for(t=ib;t<=l;t++)
printf(“%c”,s[t]);
printf(“\t\t”);
if(tab[x][y] = = ‘>’)
{
printf(“%c”, inter[g-1]);
}
printf(“\n”);
}
top--;
while(stack[top]!=’$’)
{
inter[g]=stack[top];
g++;
top--;
for(r=0;r<=top;r++)
printf(“%c”,stack[r]);
printf(“\t\t\t”);
printf(“%c”,inter[g-1]);
printf(“\n”);
}
getch( );}
OUTPUT:
Enter the input expression:
i+i*i
Enter the number of terminals including $:
4
Give the entries in first row and column corresponding to terminal:
i
+
*
$
Enter the precedence table row wise:
-
>
>
>
<
>
<
>
<
>
>
>
<
<
<
-
Operator Precedence Table:
i + * $
i - > > >
+ < > < >
* < > > >
$ < < < -
STACK INPUT BUFFER POPPED ELEMENTS:
$ i+i*i$
$i +i*i$
$+ i*i$ i
$+i *i$
$+* i$ i
$+*i $
$+* i
$+ *
$ +
RESULT:
Thus the operator precedence parse table program was executed and verified successfully.
EX. NO: 6 SYNTAX ANALYSIS USING YACC
AIM:
To implement simple desk calculator using Yacc tool.
ALGORITHM:
1. Start the program.
2. Yacc program consists of three parts namely
a. Declarations
%%
b. Transition Rule
%%
c. Supporting C – routines.
3. Declaration part consists of two sections, first section contains only include statements and the second statements contains declaration of the grammar tokens.
4. Each rule in set of transition rules consists of grammar production and semantic action. The set of productions are of the form
a. <left side>: <alt 1> {semantic action 1}
1. | <alt 2> {semantic action 2}
2. …..
3. | <alt n> {semantic action n}
4. ;
5. In the third part, error recovery routines are added.
6. The program is typed using vi editor, and saved with .y extension.
7. It is first compiled with the yacc compiler to produce the C code for C compiler (yacc samp.y).
8. After that compile that program with C compiler (cc y.tab.c – ly standard output file of yacc compiler).
9. See the output using ./a. out.
10. Stop the program.
PROGRAM:
%{
#include<ctype.h>
#include<stdio.h>
#define YYSTYPE double
%}
%token NUMBER
%left '+' '-'
%left '*' '/'
%right '^'
%right UMINUS
%%
lines : lines expr '\n' {printf("%lf",$2);}
| lines '\n'
|
;
expr : expr '+' expr {$$=$1+$3;}
| expr '-' expr {$$=$1-$3;}
| expr '*' expr {$$=$1*$3;}
| expr '/' expr {if($3!=0) {$$=$1/$3;}
else yyerror("divident should be a positive no.\n");
}
| expr '^' expr { int i,sum=1;
for(i=1;i<=$3;i++)
{sum *= $1;}
$$=sum;
}
| '(' expr ')' {$$=$2;}
| '-' expr %prec UMINUS {$$= $2;}
| NUMBER
;
%%
yylex()
{
int c;
while((c=getchar())==' ');
if((c=='.')||(isdigit(c)))
{
ungetc(c,stdin);
scanf("%lf",&yylva l);
return NUMBER;
}
return c;
}
OUTPUT:
[localhost@server ~]$ yacc samp.y
[localhost@server ~]$ cc y.tab.c -ly
[localhost@server ~./a.out
9
9.000000
6+3
9.000000
25-12
13.000000
RESULT:
Thus a calculator is implemented using YACC tool.
EX.NO:7 IMPLEMENTATION OF SHIFT REDUCE PARSING ALGORITHM
AIM:
To write a C program to implement the shift reduce parsing.
ALGORITHM:
1. Start the program.
2. Get the input string from the user.
3. Push $ onto top of the stack.
4. Set ip to point to the first input symbol.
5. If there is any production which can be used to reduce the input symbol reduce the string otherwise push it to the top of the stack.
6. Set ip to point to next input symbol.
7. Repeat the above steps until the top of the stack contains the $ and the starting symbol. If so, then the string is valid, otherwise the string is invalid, return an error message.
8. Stop the program.
PROGRAM:
#include<stdio.h>
#include<string.h>
int shift(int,int);
int reduce(int,int);
struct pro
{
char l,r[10];
}ip,pr[10],st;
void main()
{
int n=0,i=0,j=0,l=0,s=0,k=0;
clrscr();
printf("enter the no of production");
scanf("%d",&n);
printf("enter the production");
for(i=0;i<n;i++)
{
pr[i].l=getche();
printf("-->");
scanf("%s",pr[i].r);
}
printf("enter the input");
scanf("%s",ip.r);
printf("\tstack\t\tinput\t\taction");
printf("\n$\t\t%s$",ip.r);
k=l=strlen(ip.r);
for(j=0;j<k;j++)
{
if(l!=0)
{
s=shift(s,l);
l=strlen(ip.r);
}
s=reduce(s,n);
}
if(l==0&&(strlen(st.r)==1)&&(st.r[0]==pr[0].l))
{
printf("\t\taccepted");
getch();
exit();
}
else if(l==0&&(strlen(st.r)>=2)||(st.r[0]!=pr[0].l))
{printf("\t\terror");
exit();
getch();
}
}
int shift(int s, int l)
{
int i;
st.r[s]=ip.r[0];
s++;
l--;
for(i=0;i<l+1;i++)
{
if(ip.r[i+1]!='\0')
ip.r[i]=ip.r[i+1];
else if(ip.r[i+1]=='\0')
ip.r[i]='\0';
}
printf("\t\tshift\n\t$%s\t\t%s$",st.r,ip.r);
return(s);
}
int reduce(int s, int n)
{
int a,b,c,i;
char ch;
for(i=0;i<n;i++)
{
c=strlen(pr[i].r);
ch=st.r[s-1];
if((pr[i].r[0]==ch)&&islower(ch))
{
st.r[s-1]=pr[i].l;
printf("\t\treduce\n\t$%s\t\t%s$",st.r,ip.r);
}}
for(i=0;i<n;i++)
{
a=strlen(st.r);
b=strlen(pr[i].r);
if(a==b&&(strcmp(st.r,pr[i].r)==0))
{
st.r[s-a]=pr[i].l;
for(c=0;c<s;c++)
st.r[c+1]='\0';
s=(s-a)+1;
printf("\t\treduce\n\t$%s\t\t%s$",st.r,ip.r);
}}
return(s);
}
OUTPUT:
enter the no of production3
enter the productionE-->E+E
E-->E*E
E-->i
enter the input i+i*i
stack input action
$ i+i*i$ shift
$i +i*i$ reduce
$E +i*i$ shift
$E+ i*i$ shift
$E+i *i$ reduce
$E+E *i$ reduce
$E *i$ shift
$E* i$ shift
$E*i $ reduce
$E*E $ reduce
$E $ accepted
RESULT:
Thus the Shift Reduce Parsing Algorithm was implemented and verified successfully.
EX.NO:8 CONSTRUCTION OF LR PARSING TABLE
AIM:
To write a C program to implement simple LR Parsing algorithm.
ALGORITHM:
• Input: An input string w and an LR parsing table with functions action and goto for a grammar G.
• Output: If w is in L(G), a bottom – up parse for w; otherwise an error indication.
• Method: Initially, the parser has s0 on its stack, s0 is the initial state, and w$ in the input buffer. The parser then executes the program until accept or error action is encountered.
set ip to point to the first symbol of w$;
repeat forever begin
let s be the state on the top of the stack and
a the symbol pointed to by ip;
if action [s, a] = shift s then begin
push a then s on the top of the stack;
advance ip to the next input symbol
end
else if action [s, a] = reduce A then begin
pop 2*|| symbols off the stack;
let s be the state now on top of the stack;
push A then goto [s, A] on top of the stack;
output the production A
end
else if action [s, a] = accept then
return
else error()
end
PROGRAM:
#include <iostream.h>
#include <conio.h>
#include <string.h>
#define MPd 20 /* Max no of Productions */
#define Mt 20 /* Max no of terminal symbols */
#define MNt 10 /* Max no of Nonterminal symbols */
#define MSt 30 /* Max no of States */
class LR0Item
{
public:
char Item[MPd][30];
int NIt;
int Goto[MNt + Mt];
LR0Item ();
void Add (char []);
int operator == (LR0Item);
};
void LR0Item::LR0Item ()
{
for (int i=0; i<Mt+MNt; i++)
Goto [i] = -1;
}
void LR0Item::Add (char s[])
{
for (int i=0; i<NIt; i++)
{
if (strcmp (Item[i], s) == 0)
return;
if (strcmp (Item[i], s) > 0)
{
for (int j=NIt; j>i; j--)
strcpy (Item[j], Item[j - 1]);
strcpy (Item[i], s);
NIt++;
return;
} }
strcpy (Item[NIt++], s);
}
int LR0Item::operator == (LR0Item S1)
{
if (NIt != S1.NIt) return 0;
for (int i=0; i<NIt; i++)
{
if (strcmp (Item[i], S1.Item[i]) != 0)
return 0;
}
return 1;
}
int NSt, NPd;
char Ter[Mt], NTer[MNt];
char Prd[MPd][20];
char AxnTbl[MSt][Mt][5], GotoTbl[MSt][MNt][5];
char Follow[MNt][Mt];
LR0Item Set[MSt];
inline int IsCap (char c)
{
if (c >= 'A' && c <= 'Z') return 1;
return 0;
}
void ToString (char c[], int i)
{
if (i < 10)
{
c[0] = (char)(i + '0');
c[1] = '\0';
}
else
{
c[0] = (char)((i / 10) + '0');
c[1] = (char)((i % 10) + '0');
c[2] = '\0';
}}
void Adds (char s1[], char s2[])
{
for (int i=0; s2[i] != '\0'; i++)
{
for (int j=0; s1[j] != '\0'; j++)
if (s1[j] == s2[i]) break;
if (s1[j] == '\0')
{
s1[j++] = s2[i];
s1[j] = '\0';
} }}
void Add (char s1[], char c)
{
char s[2];
s[0] = c;
s[1] = '\0';
Adds (s1, s);
}
int GetTer (char c)
{
for (int i=0; Ter[i] != '\0' && Ter[i] != c; i++);
if (Ter[i] == '\0') return -1;
return i;
}
int GetNTer (char c)
{
for (int i=0; NTer[i] != '\0' && NTer[i] != c; i++);
if (NTer[i] == '\0') return -1;
return i;
}
void Closure (LR0Item *It)
{
char s[MNt] = "";
char s1[30];
int i, j, k;
for (j=0; j<It -> NIt; j++)
{
for (i=3; It -> Item[j][i] !='\0'; i++)
if (It -> Item[j][i] == '.')
Add (s, It -> Item[j][i + 1]);
}
for (i = 0; s[i] != '\0'; i++)
{
for (j=0; j<NPd; j++)
if (Prd[j][0] == s[i])
{
for (k=0; k<3; k++)
s1[k] = Prd[j][k];
s1[3] = '.';
if (GetNTer (Prd[j][3]) != -1)
Add (s, Prd[j][3]);
for (k=3; Prd[j][k] != '\0'; k++)
s1[k + 1] = Prd[j][k];
s1[k+1] = '\0';
It -> Add (s1);
} }}
void ConstColl ()
{
char s[20], Sym[MNt + Mt], c;
strcpy (Sym, NTer);
strcat (Sym, Ter);
for (int i=0; i<3; i++)
s[i] = Prd[0][i];
s[3] = '.';
s[4] = Prd[0][3];
s[5] = '\0';
Set[0].NIt = 0;
Set[0].Add (s);
Closure (&Set[0]);
NSt = 1;
for (i=0; i<NSt; i++)
{
for (int j=0; j<Sym[j] != '\0'; j++)
{
Set[NSt].NIt = 0;
for (int k=0; k<Set[i].NIt; k++)
{
for (int l=0; Set[i].Item[k][l] != '.'; l++)
s[l] = Set[i].Item[k][l];
if (Set[i].Item[k][l + 1] == Sym[j])
{
s[l] = Set[i].Item[k][l + 1];
s[++l] = '.';
l++;
for (;Set[i].Item[k][l] != '\0'; l++)
s[l] = Set[i].Item[k][l];
s[l] = '\0';
Set[NSt].Add (s);
} }
if (Set[NSt].NIt > 0)
{
Closure (&Set[NSt]);
int Fnd = -1;
for (k=0; k<NSt; k++)
if (Set[k] == Set[NSt])
Fnd = k;
if (Fnd == -1)
Fnd = NSt++;
int n1 = GetNTer (Sym[j]);
int n2 = GetTer (Sym[j]);
if (n1 != -1)
Set[i].Goto[n1] = Fnd;
else if (n2 != -1)
Set[i].Goto[MNt + n2] = Fnd;
} } }}
void Init ()
{
for (int i=0; i<MSt; i++)
{
for (int j=0; j<MNt; j++)
AxnTbl[i][j][0] = '\0';
for (j=0; j<Mt; j++)
GotoTbl[i][j][0] = '\0';
}
for (i=0; i<MNt; i++)
Follow[i][0] = '\0';
}
void FindFollow ()
{
int n1;
Add (Ter, '$');
strcpy (Follow[0], "$");
for (int Cnt=0; NTer[Cnt] != '\0'; Cnt++)
{
for (int i=0; i<NPd; i++)
{
int n1;
for (int j=3; Prd[i][j] != '\0'; j++)
{
if ((n1 = GetNTer (Prd[i][j])) != -1)
Add (Follow[n1], Prd[i][j+1]);
}
if ((n1 = GetNTer (Prd[i][j - 1])) != -1)
Adds (Follow[n1], Follow[GetNTer (Prd[i][0])]);
} }
for (int i=0; NTer[i] != '\0'; i++)
{
char s[30] ="";
for (int j=0; Follow[i][j] != '\0'; j++)
if (GetTer (Follow[i][j]) != -1)
Add (s, Follow[i][j]);
strcpy (Follow[i], s);
}}
void ConstTable ()
{
char s[30], s1[5], s2[5];
int n;
for (int i=0; i<NSt; i++)
{
for (int j=0; j<Set[i].NIt; j++)
{
for (int k=0; Set[i].Item[j][k] != '.'; k++);
k++;
if (Set[i].Item[j][k] == '\0')
{
strcpy (s, Set[i].Item[j]);
s[strlen (Set[i].Item[j]) - 1] = '\0';
for (int l=0; l<NPd; l++)
{
if (strcmp (s, Prd[l]) == 0)
{
if (l == 0)
{
strcpy (AxnTbl[i][GetTer ('$')], "acc");
break;
}
n = GetNTer (s[0]);
for (int m=0; Follow[n][m] != '\0'; m++)
{
strcpy (s1, "r");
ToString (s2, l);
strcat (s1, s2);
strcpy (AxnTbl[i][GetTer (Follow[n][m])], s1);
} } } }
else if ((n = GetTer (Set[i].Item[j][k])) != -1)
{
strcpy (s1, "s");
ToString (s2, Set[i].Goto[MNt + n]);
strcat (s1, s2);
strcpy (AxnTbl[i][n], s1);
}
else if ((n = GetNTer (Set[i].Item[j][k])) != -1)
{
ToString (GotoTbl[i][n], Set[i].Goto[n]);
} } }}
void Prints (char s[])
{
cout << s;
for (int i = strlen(s); i<5; i++) cout << " ";
}
void main ()
{
clrscr ();
char s[30];
cout << "Enter the augmented grammar productions followed by \"end\"\n";
while (1)
{
cout << "(" << NPd << ") ";
cin >> s;
if (!strcmp (s, "end")) break;
Add (NTer, s[0]);
strcpy (Prd[NPd], s);
Add (NTer, Prd[NPd][0]);
for (int i=3; Prd[NPd][i] != '\0'; i++)
if (!IsCap (Prd[NPd][i]))
Add (Ter, Prd[NPd][i]);
NPd++;
}
Init ();
ConstColl ();
FindFollow ();
ConstTable ();
clrscr ();
cout << "\t\tSLR Parsing Table\n";
cout << "\n\t Action";
for (int i=0; Ter[i] != '\0'; i++) cout << " ";
cout << "Goto\n\n\t";
for (i=0; Ter[i] != '\0'; i++) cout << Ter[i] << " ";
cout << "\t";
for (i=1; NTer[i] != '\0'; i++) cout << NTer[i] << " ";
cout << "\n";
for (i=0; i<NSt; i++)
{
cout << "\n" << i << "\t";
for (int j=0; Ter[j] != '\0'; j++)
Prints (AxnTbl[i][j]);
cout << "\t";
for (j=1; NTer[j] != '\0'; j++)
Prints (GotoTbl[i][j]);
}
getch ();
}
OUTPUT:
Enter the augmented grammar productions followed by "end"
(0) P->E
(1) E->E+T
(2) E->T
(3) T->T*F
(4) T->F
(5) F->(E)
(6) F->i
(7) end
SLR Parsing Table
____________________
Action Goto
+ * ( ) i $ E T F
0 s4 s5 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s4 s5 8 2 3
5 r6 r6 r6 r6
6 s4 s5 9 3
7 s4 s5 10
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
RESULT:
Thus the program for Constructing LR Parsing Table for the given grammar is executed successfully
EX.NO:9 IMPLEMENTATION OF INTERMEDIATE CODE GENERATION
AIM:
To write a C program to implement the intermediate code for the given set of input expressions.
ALGORITHM:
1. Start the program.
2. Get the input expression from the user.
3. Check the expressions for its validation.
4. If it is invalid return the error message.
5. Otherwise, for each computation store the result in the three – address statement (store it in temporary variable say t1, t2, etc.,) .
6. Assign the final temporary value to the variable in which the result has to be stored.
7. Stop the program.
PROGRAM:
#include<stdio.h>
#include<ctype.h>
#include<stdlib.h>
#include<conio.h>
#include<string.h>
void small();
void dove(int );
int p[5]={0,1,2,3,4},c=1,i,k,l,m,pi;
char sw[5]={'=','-','+','/','*'},j[20],a[5],b[5],ch[2];
void main()
{
clrscr();
printf("Enter the expression:");
scanf("%s",j);
printf("\n\n\tThe Intermediate code is:\n");
small();
}
void dove(int i)
{
a[0]='\0';b[0]='\0';
I f(!isdigit(j[i+2]) && !isdigit(j[i-2]))
{
a[0]=j[i-1];
b[0]=j[i+1];
}
if(isdigit(j[i+2]))
{
a[0]=j[i-1];
b[0]='t';
b[1]=j[i+2];
}
if(isdigit(j[i-2]))
{ b[0]=j[i+1];
a[0]='t';
a[1]=j[i-2];
b[1]='\0'; }
if(isdigit(j[i+2]) && isdigit(j[i-2]))
{ a[0]='t';
b[0]='t';
a[1]=j[i-2];
b[1]=j[i+2];
itoa(c,ch,10);
j[i+2]=j[i-2]=ch[0]; }
if(j[i]=='*')
printf("\tt%d=%s*%s\n",c,a,b);
if(j[i]=='/')
printf("\tt%d=%s/%s\n",c,a,b);
if(j[i]=='+')
printf("\tt%d=%s+%s\n",c,a,b);
if(j[i]=='-')
printf("\tt%d=%s-%s\n",c,a,b);
if(j[i]=='=')
printf("\t%c=t%d",j[i-1],--c);
itoa(c,ch,10);
j[i]=ch[0];
c++;
small();
}
void small()
{ pi=0;l=0;
for(i=0;i<strlen(j);i++)
{ for(m=0;m<5;m++)
if(j[i]==sw[m])
if(pi<=p[m])
{
pi=p[m];
l=1;
k=i;
} }
if(l==1)
dove(k);
else
{
getch();
exit (0);
} }
OUTPUT:
Enter the expression:
a=b+c*d-e/f
The Intermediate code is:
t1=c*d
t2=e/f
t3=b+t1
t4=t1-t2
a=t4
RESULT:
Thus the front end of a compiler is implemented by generating 3 address codes as input for the regular expression
EX.NO:10 IMPLEMENTATION OF CODE OPTIMIZATION TECHNIQUES
AIM:
To write a C program to implement the code generation algorithm.
ALGORITHM:
The code generation algorithm takes as input a sequence of three – address statements constituting a basic block. For each three – address statement of the form x := y op z we perform the following actions:
1. Invoke a function getreg to determine the location L where the result of the computation y op z should be stored. L will usually be a register, but it could also be a memory location. We shall describe getreg shortly.
2. Consult the address descriptor for y to determine y, (one of) the current location(s) of y. prefer the register for y if the value of y is currently both in memory and a register. If the value of y is not already in L, generate the instruction MOV y, L to place a copy of y in L.
3. Generate the instruction OP z, L where z is a current location of z. Again, prefer a register to a memory location if z is in both. Update the address descriptor of x to indicate that x is in location L. If L is a register, update its descriptor to indicate that it contains the value of x, and remove x from all other register descriptors.
4. If the current values of y and/or z have no next users, are not live on exit from the block, and are in register descriptor to indicate that, after execution of x := y op z, those registers no longer will contain y and/or z, respectively.
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("left\t");
op[i].l=getche();
printf("right:\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);
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++)
{
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:
enter no of values 5
left aright: 9
left bright: c+d
left eright: c+d
left fright: b+e
left rright: f
intermediate Code
a=9
b=c+d
e=c+d
f=b+e
r=f
after dead code elimination
b =c+d
e =c+d
f =b+e
r =f
eliminate common expression
b =c+d
b =c+d
f =b+b
r =f
optimized codeb=c+d
f=b+b
r=f
RESULT:
Thus the above program is compiled and executed successfully and output is verified.
EX.NO:11 CONVERSION OF INFIX TO POSTFIX EXPRESSION
AIM:
To write a C program to implement the postfix expression for the given infix expression
ALGORITHM:
1. Scan the input from left to right.
2. Initialise an empty stack.
3. If the scannned character is an operand, add it to the Postfix string. If the scanned character is an operator and if the stack is empty Push the character tostack.
If the scanned character is an Operand and the stack is not empty, compare the precedence of the character with the element on top of the stack(topStack).
If topStack has higher precedence over the scanned character Popthe stack else Push the scanned character to stack. Repeat this step as long as stack is not empty and topStack has precedence over the character.
Repeat this step till all the characters are scanned.
4. (After all characters are scanned, we have to add any character that the stackmay have to the Postfix string.) If stack is not empty add topStack to Postfix stringand Pop the stack. Repeat this step as long as stack is not empty.
5. Return the Postfix string.
PROGRAM:
#include<stdio.h>
#include<conio.h>
#include<string.h>
int pp=0, sp= -1, ip=0, i;
char post[80], stack[80],in[80],oper[6][2]= {‘^’,’3’,’*’,’2’,’/’,’2’,’+’,’1’,’-‘,’1’};
void main( )
{
clrscr( );
printf(“\n\n\t ENTER THE EXPRESSION:”);
scanf(“%s”, in);
strcat(in, ‘#’);
while(in[ip]!= ‘#’)
{
if(in[ip]= = ’(‘ )
stack[++sp] = in[ip++];
else if(in[ip] = = ‘)’ )
{
for(; stack[sp]!= ‘(‘ ; sp--)
post[pp++] = stack[sp];
sp--;
ip++;
}
else if(operation(in[ip]) = = 0)
post[pp++] = in[ip++];
else if(operation(in[ip])>operation(stack[sp]))
stack[++sp] = in[ip++];
else
post[pp++] = stack[sp--];
}
post[pp] = stack[++sp] =’\0’
strrev(stack);
strcat(post,stack);
printf(“\n\n\n\t Infix: %s\n\n\t Postfix: %s\n\n”, in, post);
getch( );
}
int operation(char ch)
{
for(i=0;i<5;i++)
if(ch = = oper[i][0])
return(48+oper[i][1]);
return(0);
}
OUTPUT:
ENTER THE EXPRESSION: a+b*c
Infix a+b*c#
Postfix abc*+
RESULT:
Thus the infix to postfix expression is converted & executed successfully and output is verified.
EX.NO:12 IMPLEMENTATION OF QUADRAPLES
AIM:
To write a C program to derive quadraples for the given expression
ALGORITHM:
1. Read the given input from right to left
2. Basically quadruples are the record structure with four fields called op,arg1,arg2, and result.
3. Unary operators does not use arg2.Conditional & unconditional jump put target label in result.
4. Partition the input into symbols,operators,keywords and identifiers as given in the input.
5. If so,the temporary names must be entered into the symbol table as they are created
6. Finally,the quadruples for the given input is generated.
PROGRAM:
#include<stdio.h>
#include<conio.h>
#include<ctype.h>
char stack[25];
int top=0;
char postfixexp[25];
void quadruples( )
{
char qstack[25];
int top=0,i=0,t=1;
char ch;
while((ch=postfixexp[i])!=’\0’)
{
if(isalpha(ch))
{
top++;
qstack[top]=ch;
}
else
{
if(ch = =’~‘)
{
if(isalpha(qstack[top]))
printf(“\n%c \t%c \tt%d”,ch,qstack[top],t);
qstack[top]=t;
}
else
{
printf(“\n%c”,ch);
if(isalpha(qstack[top]))
printf(“\t%c”, qstack[top]);
else
printf(“\tt%d”,qstack[top]);
if(isalpha(qstack[top-1]))
printf(“\t%c”,qstack[top-1]);
else
printf(“\tt%d”,qstack[top-1);
printf(“\tt%d”,t);
top--;
qstack[top]=t;
}
t++;
}
i++;
}
}
void main( )
{
clrscr( );
printf(“ENTER THE EXPRESSION IN POSTFIX FORM:”);
scanf(“%s”,postfixexp);
quadruples( );
getch( );
}
OUTPUT:
ENTER THE EXPERESSION IN POSTFIX FORM: ab+cd+*
+ b a t1
+ d c t2
* t2 t1 t3
RESULT:
Thus the implementation of quadraples is compiled and executed successfully and output is verified.
EX.NO:13 IMPLEMENTATION OF TRIPLES
AIM:
To write a C program to derive triples for the given expression
ALGORITHM:
1. Start the Program
2. Read the input expression from right to left.
3. Avoid entering temporary names into the symbol table,refer to a temporary value by the position of the statement that computes it.
4. Then the Three address statements can be represented by records with only three fields :op,arg1,arg2.
5. (ie.)The statement is encoded in the triple representation by placing the input in the specified colums.
6. Same as quadruples except that result that occupies extra one column.
7. Finally the given statements is printed as a triple representation form.
PROGRAM:
#include<stdio.h>
#include<conio.h>
#include<ctype.h>
char stack[25];
int top=0;
char postfixexp[25];
void triples( )
{
char qstack[25];
int top=0,i=0,t=0;
char ch;
while((ch=postfixexp[i])!=’\0’)
{
if(isalnum(ch))
{
top++;
qstack[top]=ch;
}
else
{
if(ch = =’-‘)
{
if(isalpha(qstack[top]))
printf(“\n%d \t%c \t%c”,t,ch,qstack[top]);
else
printf(“\n%d \t%c \t(%d)”,t,ch,qstack[top]);
}
else
{
printf(“\n%d \t%c”,t,ch);
if(isalpha(qstack[top-1]))
printf(“\t%c”, qstack[top-1]);
else
printf(“\t(%d)”,qstack[top-1]);
if(isalpha(qstack[top]))
printf(“\t%c”,qstack[top]);
else
printf(“\t(%d)”,qstack[top);
top--;
qstack[top]=t;
}
t++;
}
i++;
}
}
void main( )
{
clrscr( );
printf(“ENTER THE EXPRESSION IN POSTFIX FORM:”);
scanf(“%s”,postdixexp);
triples( );
getch( );
}
OUTPUT:
ENTER THE EXPRESSION IN POSTFIX FORM: ab+cd+*
0 + a b
1 + c d
2 * (0) (1)
RESULT:
Thus the implementation of triples is compiled and executed successfully and output is verified.
.
EX.NO:14 GENERATION OF TOKENS FOR GIVEN LEXEME
AIM:
To write a C program to generate tokens for the given expression
ALGORITHM:
1. Start the Program
2. Read the input from right to left
3. First identify the characters individually,that it has a collective meaning.
4. Tokens nothing but a string of descriptors
5. After giving the expression it display the tokens whether it is keyword,operators,identifiers or any other special symbols in the symbol table.
PROGRAM:
#include<stdio.h>
#include<string.h>
void main()
{
char input[30];
int len,i=0,j=0,k,b=0,c=0,m=0;
printf("\n enter the expression:");
scanf("%s",input);
printf("%s\n",input);
len=strlen(input);
i=0;
while(i<len)
{
if(isalpha(input[i]))
{
m=i;
i++;
while(isalpha(input[i]))
i++;
c=i;
for(k=m;k<c;k++)
printf("%c",input[k]);
printf("\t identifier\n");
}
else if(isdigit(input[i]))
{
m=i;
while(isdigit(input[i]))
i++;
b=I;
for(k=m;k<b;k++)
printf("%c",input[k]);
printf("\t constant\n");
}
else
{
printf("%c\t operator\n",input[i]);
i++;
}
}
}
OUTPUT:
Enter the expression: sum=rate + var
sum=rate + var
sum identifier
= operator
rate identifier
+ operator
var identifier
RESULT:
Thus the tokens generated for the given statements successfully and output is verified.
EX.NO:15 PARSING THE STRING
AIM:
To write a C program to find whether the string is parsing or not.
ALGORITHM:
1. Start the Program
2. Read the input from right to left
3. Then collect the information about the tokens as per the input.
4. Then perform type checking and other type of semantic analysis.
5. From that generate the intermediate representation then it will be parsed.
6. If it s not generated means then the string will not be not parsed.
PROGRAM:
#include<stdio.h>
char ip[20];
int i = 0;
void main()
{
printf("\n enter the string");
scanf("%s",ip);
e();
if(ip[i]=='$')
printf("\n the string is parsed");
if(ip[i]!='$')
printf("\n the string is not properly terminated");
getch();
}
e()
{
t();
eprime();
}
eprime()
{
if(ip[i]=='+')
{
i++;
t();
eprime();
}
}
t()
{
f();
tprime();
}
tprime()
{
if(ip[i]=='*')
{
i++;
f();
tprime();
}
}
f()
{
if(isalpha(ip[i]))
i++;
else if(ip[i]=='(')
{
i++;
e();
if(ip[i]==')')
i++;
else
error();
}
else
error();
}
error()
{
printf("\n string cannot be parsed successfully\n");
getch();
}
OUTPUT:
Enter the string
a+b*c$
the string is parsed
Enter the string
a+b*c
the string is not properly terminated
Enter the string
a+*b*c$
string cannot be parsed successfully
RESULT:
Thus the parsing program is compiled and executed successfully and output is verified.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment