Compiler Design lab

1. AIM: Write a C program to identify different types of Tokens in a given Program

SOURCE CODE:

#include <stdbool.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
bool isValidDelimiter(char ch) {
if (ch == ' ' || ch == '+' || ch == '-' || ch == '*' ||
ch == '/' || ch == ',' || ch == ';' || ch == '>' ||
ch == '<' || ch == '=' || ch == '(' || ch == ')' ||
ch == '[' || ch == ']' || ch == '{' || ch == '}')
return (true);
return (false);
}
bool isValidOperator(char ch){
if (ch == '+' || ch == '-' || ch == '*' ||
ch == '/' || ch == '>' || ch == '<' ||
ch == '=')
return (true);
return (false);
}
// Returns 'true' if the string is a VALID IDENTIFIER.
bool isvalidIdentifier(char* str){
if (str[0] == '0' || str[0] == '1' || str[0] == '2' ||
str[0] == '3' || str[0] == '4' || str[0] == '5' ||
str[0] == '6' || str[0] == '7' || str[0] == '8' ||
str[0] == '9' || isValidDelimiter(str[0]) == true)
return (false);
return (true);
}
bool isValidKeyword(char* str) {
if (!strcmp(str, "if") || !strcmp(str, "else") || !strcmp(str, "while") || !strcmp(str,
"do") || !strcmp(str, "break") || !strcmp(str, "continue") || !strcmp(str, "int")
|| !strcmp(str, "double") || !strcmp(str, "float") || !strcmp(str, "return") || !
strcmp(str, "char") || !strcmp(str, "case") || !strcmp(str, "char")

Dept. of CSE Page 1

Compiler Design lab

|| !strcmp(str, "sizeof") || !strcmp(str, "long") || !strcmp(str, "short") || !

strcmp(str, "typedef") || !strcmp(str, "switch") || !strcmp(str, "unsigned")
|| !strcmp(str, "void") || !strcmp(str, "static") || !strcmp(str, "struct") || !
strcmp(str, "goto"))
return (true);
return (false);
}
bool isValidInteger(char* str) {
int i, len = strlen(str);
if (len == 0)
return (false);
for (i = 0; i < len; i++) {
if (str[i] != '0' && str[i] != '1' && str[i] != '2'&& str[i] != '3' && str[i] != '4' &&
str[i] != '5'
&& str[i] != '6' && str[i] != '7' && str[i] != '8' && str[i] != '9' || (str[i] == '-' && i
> 0))
return (false);
}
return (true);
}
bool isRealNumber(char* str) {
int i, len = strlen(str);
bool hasDecimal = false;
if (len == 0)
return (false);
for (i = 0; i < len; i++) {
if (str[i] != '0' && str[i] != '1' && str[i] != '2' && str[i] != '3' && str[i] != '4' &&
str[i] != '5' && str[i] != '6' && str[i] != '7' && str[i] != '8'
&& str[i] != '9' && str[i] != '.' || (str[i] == '-' && i > 0))
return (false);
if (str[i] == '.')
hasDecimal = true;
}
return (hasDecimal);
}
char* subString(char* str, int left, int right) {
int i;

Dept. of CSE Page 2

Compiler Design lab

char* subStr = (char*)malloc( sizeof(char) * (right - left + 2));

for (i = left; i <= right; i++)
subStr[i - left] = str[i];
subStr[right - left + 1] = '\0';
return (subStr);
}
void detectTokens(char* str) {
int left = 0, right = 0;
int length = strlen(str);
while (right <= length && left <= right) {
if (isValidDelimiter(str[right]) == false)
right++;
if (isValidDelimiter(str[right]) == true && left == right) {
if (isValidOperator(str[right]) == true)
printf("Valid operator : '%c'", str[right]);
right++;
left = right;
} else if (isValidDelimiter(str[right]) == true && left != right || (right == length
&& left != right)) {
char* subStr = subString(str, left, right - 1);
if (isValidKeyword(subStr) == true)
printf("Valid keyword : '%s' ", subStr);
else if (isValidInteger(subStr) == true)
printf("Valid Integer : '%s' ", subStr);
else if (isRealNumber(subStr) == true)
printf("Real Number : '%s' ", subStr);
else if (isvalidIdentifier(subStr) == true
&& isValidDelimiter(str[right - 1]) == false)
printf("Valid Identifier : '%s' ", subStr);
else if (isvalidIdentifier(subStr) == false
&& isValidDelimiter(str[right - 1]) == false)
printf("Invalid Identifier : ' ", subStr);
left = right;
}
}
return;
}

Dept. of CSE Page 3

Compiler Design lab

int main(){
char str[100] = "float x = a + 1b; ";
printf("The Program is : '%s'
", str);
printf("All Tokens are :
");
detectTokens(str);
return (0);
}

Output:
The Program is : 'float x = a + 1b; '
All Tokens are :
Valid keyword : 'float'
Valid Identifier : 'x'
Valid operator : '='
Valid Identifier : 'a'
Valid operator : '+'
Invalid Identifier : '1b'

2. AIM: Write a Lex Program to implement a Lexical Analyzer using Lex tool

SOURCE CODE:
lexp.l
%{
int COMMENT=0;
Dept. of CSE Page 4
Compiler Design lab

%}
identifier [a-zA-Z][a-zA-Z0-9]*
%%
#.* {printf ("\n %s is a Preprocessor Directive",yytext);}
int |
float |
main |
if |
else |
printf |
scanf |
for |
char |
getch |
while {printf("\n %s is a Keyword",yytext);}
"/*" {COMMENT=1;}
"*/" {COMMENT=0;}
{identifier}\( {if(!COMMENT) printf("\n Function:\t %s",yytext);}
\{ {if(!COMMENT) printf("\n Block Begins");
\} {if(!COMMENT) printf("\n Block Ends");}
{identifier}(\[[0-9]*\])? {if(!COMMENT) printf("\n %s is an Identifier",yytext);}
\".*\" {if(!COMMENT) printf("\n %s is a String",yytext);}
[0-9]+ {if(!COMMENT) printf("\n %s is a Number",yytext);}
\)(\;)? {if(!COMMENT) printf("\t");ECHO;printf("\n");}
\( ECHO;
= {if(!COMMENT) printf("\n%s is an Assmt oprtr",yytext);}
\<= |
\>= |
\< |
== {if(!COMMENT) printf("\n %s is a Rel. Operator",yytext);}
.|\n
%%
int main(int argc, char **argv)
{
if(argc>1)
{
FILE *file;

Dept. of CSE Page 5

Compiler Design lab

file=fopen(argv[1],"r");
if(!file)
{
printf("\n Could not open the file: %s",argv[1]);
exit(0);
}
yyin=file;
}
yylex();
printf("\n\n");
return 0;
}
int yywrap()
{
return 0;
}

Output:
test.c
#include<stdio.h>
main()
{
int fact=1,n;
for(int i=1;i<=n;i++)
{ fact=fact*i; }
printf("Factorial Value of N is", fact);
getch();
}
$ lex lexp.l
$ cc lex.yy.c
$ ./a.out test.c
#include<stdio.h> is a Preprocessor Directive
Function: main( )
Block Begins
int is a Keyword
fact is an Identifier
= is an Assignment Operator

Dept. of CSE Page 6

Compiler Design lab

1 is a Number
n is an Identifier
Function: for(
int is a Keyword
i is an Identifier
= is an Assignment Operator
1 is a Number
i is an Identifier
<= is a Relational Operator
n is an Identifier
i is an Identifier
);
Block Begins
fact is an Identifier
= is an Assignment Operator
fact is an Identifier
i is an Identifier
Block Ends
Function: printf(
"Factorial Value of N is" is a String
fact is an Identifier );
Function: getch( );
Block Ends

3. AIM: Write a C program to Simulate Lexical Analyzer to validating a given input

String.
SOURCE CODE:
#include<string.h>
#include<ctype.h>
#include<stdio.h>

Dept. of CSE Page 7

Compiler Design lab

void keyword(char str[10])

{
if(strcmp("for",str)==0||strcmp("while",str)==0||strcmp("do",str)==0||
strcmp("int",str )==0||strcmp("float",str)==0||strcmp("char",str)==0||
strcmp("double",str)==0||strcmp("static",str)==0||strcmp("switch",str)==0||
strcmp("case",str)==0)
printf("\n%s is a keyword",str);
else
printf("\n%s is an identifier",str);
}
int main()
{
FILE *f1,*f2,*f3;
char c,str[10],st1[10];
int num[100],lineno=0,tokenvalue=0,i=0,j=0,k=0;
printf("\nEnter the c Program: ");/*gets(st1);*/
f1=fopen("input","w");
while((c=getchar())!=EOF)
putc(c,f1);
fclose(f1);
f1=fopen("input","r");
f2=fopen("identifier","w");
f3=fopen("specialchar","w");
while((c=getc(f1))!=EOF)
{
if(isdigit(c))
{
tokenvalue=c-'0';
c=getc(f1);
while(isdigit(c))
{
tokenvalue*=10+c-'0';
c=getc(f1);
}
num[i++]=tokenvalue;
ungetc(c,f1);
}

Dept. of CSE Page 8

Compiler Design lab

else if(isalpha(c))
{
putc(c,f2);
c=getc(f1);
while(isdigit(c)||isalpha(c)||c=='_'||c=='$')
{
putc(c,f2);
c=getc(f1);
}
putc(' ',f2);
ungetc(c,f1);
}
else if(c==' '||c=='\t')
printf(" ");
else if(c=='\n')
lineno++;
else
putc(c,f3);
}
fclose(f2);
fclose(f3);
fclose(f1);
printf("\nThe no's in the program are");
for(j=0; j<i; j++)
printf("%d",num[j]);
printf("\n");
f2=fopen("identifier","r");
k=0;
printf("The keywords and identifiersare:");
while((c=getc(f2))!=EOF)
{
if(c!=' ')
str[k++]=c;
else
{
str[k]='\0';
keyword(str);

Dept. of CSE Page 9

Compiler Design lab

k=0;
}
}
fclose(f2);
f3=fopen("specialchar","r");
printf("\nSpecial characters are");
while((c=getc(f3))!=EOF)
printf("%c",c);
printf("\n");
fclose(f3);
printf("Total no. of lines are:%d",lineno);
return 0;
}

Output:

Enter the c Program: a+b*c

The no's in the program are

The keywords and identifiers are:
a is an identifier
b is an identifier
c is an identifier
Special characters are+*
Total no. of lines are:1

4. AIM: Write a C program to implement the Brute force technique of Top down
Parsing

SOURCE CODE:

#include<stdio.h>

Dept. of CSE Page 10

Compiler Design lab

#include<conio.h>

#include<iostream.h>

void main()

int a[30];

clrscr();

int min=10000,temp=0,i,lev,n,noofc,z;

printf("please enter how many number");

cin>>n;

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

a[i]=0;

cout<<"enter value of root";

cin>>a[0];

for(i=1;i<=n/2;i++)

cout<<"please enter no of child of parent with value"<<a[i-1]<<":";

cin>>noofc;

for(int j=1;j<=noofc;j++)

{z=(i)*2+j-2;

cout<<"please enter value of child";

cin>>a[z];

Dept. of CSE Page 11

Compiler Design lab

for(i=n-1;i>=n/2;i--)

temp=0;

for(int j=i+1;j>=1;j=j/2)

temp=temp+a[j-1];

if(temp<min)

min=temp;

cout<<"temp min is"<<temp<<"\n";

cout<<"min is"<<min;

getch();

5. AIM: Write a C program to implement a Recursive Descent Parser

SOURCE CODE:
#include<stdio.h>
#include<conio.h>
#include<string.h>
char str[20];

Dept. of CSE Page 12

Compiler Design lab

int flag=1;
int i=0;
void main()
{
int S();
clrscr();
printf("enter input string");
gets(str);
S();
if(flag==1&&str[i]=='\0')
printf("\n given string %s is completly parsed",str);
else
printf("sorry not parsed");
getch();
}

int S()
{
int A();
if(str[i]=='a')
{
i++;
A();
if(str[i]=='d')
{
i++;
return 0;
}
else
{
flag=0;
return 0;
}
}
}

int A()

Dept. of CSE Page 13

Compiler Design lab

{
if(str[i]=='a')
{
i++;
if(str[i]=='b')
{
i++;
return 0;
}
else
{
A();
return 0;
}
}
else
{
return 0;
}
}
Output:
Enter input string :aaabd

Given string ‘aaabd’ is complety parsed

6. AIM: Write C program to compute the First and Follow Sets for the given
Grammar.
SOURCE CODE:
a) Computation of FIRST(x):
#include<stdio.h>
#include<string.h>

Dept. of CSE Page 14

Compiler Design lab

char res[10] = {" "},first[10];

int l=0,count=0,j,term=0;
FILE *fp1;
main()
{
FILE *fp;
int i=0,k=0,n,a[10],set,tem[10]={0},t;
char ch,s;
printf("ENTER THE PRODUCTIONS .. \n");
fp = fopen("input.txt","w");
while(( ch = getchar() )!= EOF)
putc(ch,fp);
fclose(fp);
fp = fopen("input.txt","r");
/* calculation of production starting variables */
while(!(feof(fp)))
{
ch = fgetc(fp); if(feof(fp)) break; first[l++] = ch;
count++;
a[i++] = count;
while(ch!='\n') { count++; ch=fgetc(fp); }
count++;
}
rewind(fp);
n=l;
clrscr();
j=0; l=0;
while(!(feof(fp)))
{ ch = fgetc(fp); if(feof(fp)) break;
while(ch != '\n' )
{
ch =fgetc(fp);
(count==1) /* it comes the string after > or | */
Dept. of CSE Page 15
Compiler Design lab

if( ((ch >= 'a')&& ( ch <= 'z')) || ch == '+' || ch== '-' ||

ch=='*'||ch=='/'||ch=='^'||ch==')'||ch=='('||(ch=='^')||
(ch=='#'))
{
if(term!=1 || ch!='#')
unione(ch,j++);
if( (term==1) && (ch=='#') )
term=2;
/* term=1 represents it is a subproduction,
term=2 means that sub-production has nullvalue*/
count=0;
}
else
{
tem[++k] = ftell(fp); set=1; } /* if a non-terminal occurs */
}
if( ch == '>' || ch == '|')
{
count =1; }
if(set==1) /* its a non-terminal production */
{
for(i=0;i<n;i++)
{
fseek(fp,a[i]-1,0); s= fgetc(fp);
if(s==ch) { term=1; break; }
}
count=0;
set=0;
}
}/* while loop for ch!='\n' */
if(tem[k]!=0) /* for retrieving previous production */
{ t = tem[k]-1; tem[k--]= 0;
fseek(fp,t,0);
Dept. of CSE Page 16
Compiler Design lab

if(term==2) count=1;
fgetc(fp); ch=fgetc(fp);
if( ( k==0 && term==2) && ( ch=='\n' || ch=='|'))
unione('#',j++);
fseek(fp,t,0);
}
else
j=print();
}
getch();
}u
nione(char ch,int j) /* for removing duplicates */
{
int i;
for(i=0;i<j;i++)
if(res[i]==ch)
return;
res[++j] = ch;
}p
rint() /* for the printing */
{
static int k=0;
if(k==0)
{
fp1 = fopen("output.txt","w"); k=1; }
printf(" First[%c] ==",first[l]); fputc(first[l++],fp1);
for(j=0;res[j]!='\0';j++)
{
printf("%c",res[j]);
fputc(res[j],fp1); }
printf("\n");
for(j=0;res[j]!='\0';j++)
res[j]=' ';
Dept. of CSE Page 17
Compiler Design lab

count=0; /* it indicates the start of another production

*/
term=0;
fputc('\n',fp1);
return(0);
}

Input:
Enter the no of productions 2
Enter the productions
E -> AA
A->+
Output:
FIRST(E) = {+}
FIRST(A) = {+}

b) Computation of Follow(x):

#include<stdio.h>
#include<conio.h>
Dept. of CSE Page 18
Compiler Design lab

#include<string.h>
int n,m=0,p,j=0,i=0;
char a[10][10],followresult[10];
void follow(char c);
void first(char c);
void first(char c);
void addtoresult(char c);
int main()
{
int i;
int choice;
char c,ch;
clrscr();
printf("enter number of productions");
scanf("%d",&n);
printf("enter %d productions\n",n);
for(i=0;i<n;i++)
scanf("%s%c",a[i],&ch);
//gets(a[i]);
do
{
m=0;
printf("find follow of....");
scanf("%c",&c);
follow(c);
printf("follow (%c)={",c);
for(i=0;i<m;i++)
printf("%c",followresult[i]);
printf("}\n");
printf("%d%c",&choice,&ch);
}while(choice==1);
}
void follow(char c)
{
if(a[0][0]==c)
addtoresult('$');
for(i=0;i<n;i++)

Dept. of CSE Page 19

Compiler Design lab

{
for(j=2;j<strlen(a[i]);j++)
{
if(a[i][j]==c)
{
if(a[i][j+1]!='\0')first(a[j][j+1]);
if(a[i][j+1]=='\0'&&c!=a[i][0])
follow(a[i][0]);
}
}
}
getch();
}

void first(char c)
{
int k;
if(!(isupper(c)))
//f(m++)=c;
addtoresult(c);
for(k=0;k<n;k+1)
{
if(a[k][2]=='$')
follow(a[i][0]);
else if(islower(a[k][2]))
//if [m++]=a[k][2];
addtoresult(a[k][2]);
else first(a[k][2]);
}
}
void addtoresult(char c)
{
int i;
for(i=0;i<=m;i++)
if(followresult[i]==c)
return;
followresult[m++]=c;

Dept. of CSE Page 20

Compiler Design lab

output:
enter number of prductions:2
enter 2 productions
S->CC
C->d
Find follw of --- :s
Follow(s)={$}
Do you want to continue(press 1 to continue):1
Find follow of ----:c
Follow(c)={$}
Do you want to continue (press 1 to continue):0

7. AIM: Write a C program for eliminating the left recursion and left factoring of
a given grammar
SOURCE CODE:
left recursion:

Dept. of CSE Page 21

Compiler Design lab

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define SIZE 20

int main()
{
char pro[SIZE], alpha[SIZE], beta[SIZE];
int nont_terminal,i,j, index=3;

printf("Enter the Production as E->E|A: ");

scanf("%s", pro);

nont_terminal=pro[0];
if(nont_terminal==pro[index]) //Checking if the Grammar is LEFT RECURSIVE
{
//Getting Alpha
for(i=++index,j=0;pro[i]!='|';i++,j++){
alpha[j]=pro[i];
//Checking if there is NO Vertical Bar (|)
if(pro[i+1]==0){
printf("This Grammar CAN'T BE REDUCED.\n");
exit(0); //Exit the Program
}
}
alpha[j]='\0'; //String Ending NULL Character

if(pro[++i]!=0) //Checking if there is Character after Vertical Bar (|)

{
//Getting Beta
for(j=i,i=0;pro[j]!='\0';i++,j++){
beta[i]=pro[j];
}
beta[i]='\0'; //String Ending NULL character

//Showing Output without LEFT RECURSION

Dept. of CSE Page 22

Compiler Design lab

printf("\nGrammar Without Left Recursion: \n\n");

printf(" %c->%s%c'\n", nont_terminal,beta,nont_terminal);
printf(" %c'->%s%c'|#\n", nont_terminal,alpha,nont_terminal);
}
else
printf("This Grammar CAN'T be REDUCED.\n");
}
else
printf("\n This Grammar is not LEFT RECURSIVE.\n");
}

output:

left factoring:

#include<stdio.h>
#include<string.h>

Dept. of CSE Page 23

Compiler Design lab

int main()
{
char
gram[20],part1[20],part2[20],modifiedGram[20],newGram[20],tempGram[20];
int i,j=0,k=0,l=0,pos;
printf("Enter Production : A->");
gets(gram);
for(i=0;gram[i]!='|';i++,j++)
part1[j]=gram[i];
part1[j]='\0';
for(j=++i,i=0;gram[j]!='\0';j++,i++)
part2[i]=gram[j];
part2[i]='\0';
for(i=0;i<strlen(part1)||i<strlen(part2);i++){
if(part1[i]==part2[i]){
modifiedGram[k]=part1[i];
k++;
pos=i+1;
}
}
for(i=pos,j=0;part1[i]!='\0';i++,j++){
newGram[j]=part1[i];
}
newGram[j++]='|';
for(i=pos;part2[i]!='\0';i++,j++){
newGram[j]=part2[i];
}
modifiedGram[k]='X';
modifiedGram[++k]='\0';
newGram[j]='\0';
printf("\nGrammar Without Left Factoring : : \n");
printf(" A->%s",modifiedGram);
printf("\n X->%s\n",newGram);
}
output:

Dept. of CSE Page 24

Compiler Design lab

8. AIM: Write a C program to check the validity of input string using Predictive
Parser.

Dept. of CSE Page 25

Compiler Design lab

SOURCE CODE:
#include<stdio.h>
#include<iostream.h>
#include<ctype.h>
#include<string.h>
#include<conio.h>
struct stru1
{
char non_ter[1],pro[25];
}cfg[25];
int n,st=-1,j,i,t=-1,m;
int v,c,p=1;
char str[20],stack[20],ch,tmp[10];
void match(int k);
void matchl(int k);
void main()
{
clrscr();
cprintf("Enter the number of productions:\n\r");
cscanf("%d",&n);
cprintf("\n\r");
cprintf("Enter the productions on LEFT and RIGHT sides:\n\r");

for(i=0;i<n;i++)
{
cscanf("%s",cfg[i].non_ter);
cprintf("\n\r");
cprintf("->\n\r");
cscanf("%s",cfg[i].pro);
cprintf("\n\r");
}
cprintf("Enter the input string:\n\r");
cscanf("%s",str);
cprintf("\n\r");
i=0;
do
{

Dept. of CSE Page 26

Compiler Design lab

ch=str[i];
stack[++st]=ch;
tmp[0]=ch;
match(1);
i++;
}while(str[i]!='\0');
c=st;
v=st;
cputs(stack);
cprintf("\n\r");
while(st!=0)
{
v=--st;
t=-1;
p=0;
while(v<=c)
{
tmp[++t]=stack[v++];
p++;
}
matchl(p);
}
cfg[0].non_ter[1]='\0';
if(strcmp(stack,cfg[0].non_ter)==0)
cprintf("String is present in Grammar G\n\r");
else
cprintf("String is not present in Grammar G\n\r");
}

void match(int k)
{
for(j=0;j<n;j++)
{
if(strlen(cfg[j].pro)==k)
{
if(strcmp(tmp,cfg[j].pro)==0)
{

Dept. of CSE Page 27

Compiler Design lab

stack[st]=cfg[j].non_ter[0];
break;
}
}
}
}
void matchl(int k)
{
int x=1,y;
y=k-1;
for(j=0;j<n;j++)
{
if(strlen(cfg[j].pro)==k)
{
if(strcmp(tmp,cfg[j].pro)==0)
{
k=c-k+1;
stack[k]=cfg[j].non_ter[0];
do
{
stack[k+x]='\0';
tmp[t--]='\0';
c--;
x++;
}while(x<=y);
tmp[t]='\0';
cputs(stack);
cprintf("\n\r");
break;
}
}
}
}

9. AIM: Write a C program for implementation of LR parsing algorithm to accept a

given input string.

Dept. of CSE Page 28

Compiler Design lab

SOURCE CODE:

#include

#include

char stack[30];

int top=-1;

void push(char c)

top++;

stack[top]=c;

char pop()

char c;

if(top!=-1)

c=stack[top];

top--;

return c;

Dept. of CSE Page 29

Compiler Design lab

return'x';

void printstat()

int i;

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

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

printf("%c",stack[i]);

void main()

int i,j,k,l;

char s1[20],s2[20],ch1,ch2,ch3;

clrscr();

printf("\n\n\t\t LR PARSING");

printf("\n\t\t ENTER THE EXPRESSION");

scanf("%s",s1);

l=strlen(s1);

j=0;

Dept. of CSE Page 30

Compiler Design lab

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

for(i=0;i<l;i++)< span="">

if(s1[i]=='i' && s1[i+1]=='d')

s1[i]=' ';

s1[i+1]='E';

printstat(); printf("id");

push('E');

printstat();

else if(s1[i]=='+'||s1[i]=='-'||s1[i]=='*' ||s1[i]=='/' ||s1[i]=='d')

push(s1[i]);

printstat();

printstat();

Dept. of CSE Page 31

Compiler Design lab

l=strlen(s2);

while(l)

ch1=pop();

if(ch1=='x')

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

break;

if(ch1=='+'||ch1=='/'||ch1=='*'||ch1=='-')

ch3=pop();

if(ch3!='E')

printf("errror");

exit();

else

Dept. of CSE Page 32

Compiler Design lab

push('E');

printstat();

ch2=ch1;

getch();

} </l;i++)<>
OUTPUT:

LR PARSING

ENTER THE EXPRESSION

id+id*id-id

$id

$E

$E+

$E+id

$E+E

$E+E*

Dept. of CSE Page 33

Compiler Design lab

$E+E*id

$E+E*E

$E+E*E-

$E+E*E-id

$E+E*E-E

$E+E*E-E

$E+E*E

$E

10. AIM: Write a C program for implementation of a Shift Reduce Parser using
Stack Data Structure to accept a given input string of a given grammar.

SOURCE CODE:
Dept. of CSE Page 34
Compiler Design lab

#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);
Dept. of CSE Page 35
Compiler Design lab

}
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);
}

Dept. of CSE Page 36

Compiler Design lab

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
Dept. of CSE Page 37
Compiler Design lab

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

11. AIM: Simulate the calculator using LEX and YACC tool.
SOURCE CODE:
Step1: A Yacc source program has three parts as follows:

Dept. of CSE Page 38

Compiler Design lab

Declarations %% translation rules %% supporting C routines

Step2: Declarations Section: This section contains entries that:

i. Include standard I/O header file.

ii. Define global variables.

iii. Define the list rule as the place to start processing.

iv. Define the tokens used by the parser. v. Define the operators and their
precedence.

Step3: Rules Section: The rules section defines the rules that parse the input
stream. Each rule of a grammar production and the associated semantic action.

Step4: Programs Section: The programs section contains the following

subroutines. Because these subroutines are included in this file, it is not necessary
to use the yacc library when processing this file.

Step5: Main- The required main program that calls the yyparse subroutine to
start the program.

Step6: yyerror(s) -This error-handling subroutine only prints a syntax error

message.

Step7: yywrap -The wrap-up subroutine that returns a value of 1 when the end of
input occurs. The calc.lex file contains include statements for standard input and
output, as programmar file information if we use the -d flag with the yacc
command. The y.tab.h file contains definitions for the tokens that the parser
program uses.
Dept. of CSE Page 39
Compiler Design lab

Step8: calc.lex contains the rules to generate these tokens from the input stream.

PROGRAM CODE:

//Implementation of calculator using LEX and YACC

LEX PART:

%{

#include<stdio.h>

#include "y.tab.h"

extern int yylval;

%}

%%

[0-9]+ {

yylval=atoi(yytext);

return NUMBER;

[\t] ;

[\n] return 0;

Dept. of CSE Page 40

Compiler Design lab

. return yytext[0];

%%

int yywrap()

return 1;

YACC PART:

%{

#include<stdio.h>

int flag=0;

%}

%token NUMBER

%left '+' '-'

%left '*' '/' '%'

%left '(' ')'

%%

ArithmeticExpression: E{

printf("\nResult=%d\n",$$);

Dept. of CSE Page 41

Compiler Design lab

return 0;

};

E:E'+'E {$$=$1+$3;}

|E'-'E {$$=$1-$3;}

|E'*'E {$$=$1*$3;}

|E'/'E {$$=$1/$3;}

|E'%'E {$$=$1%$3;}

|'('E')' {$$=$2;}

| NUMBER {$$=$1;}

%%

void main()

printf("\nEnter Any Arithmetic Expression which can have operations Addition,

Subtraction, Multiplication, Divison, Modulus and Round brackets:\n");

yyparse();

if(flag==0)

printf("\nEntered arithmetic expression is Valid\n\n");

Dept. of CSE Page 42

Compiler Design lab

void yyerror()

printf("\nEntered arithmetic expression is Invalid\n\n");

flag=1;

OUTPUT:

Dept. of CSE Page 43