LAB MANUAL

ON

COMPILER DESIGN
ACADEMIC YEAR 2022-23
III B.Tech.–II SEMESTER (R20)

DEPARTMENT OF COMPUTER SCIENCE

V S M COLLEGE OF ENGINEERING
RAMCHANDRAPURAM
E.G DISTRICT
533255
 R-20 Syllabus for CSE, JNTUK w. e. f. 2020 – 21

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY KAKINADA

KAKINADA – 533 003, Andhra Pradesh, India

DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

L T P C
III Year – II Semester
0 0 3 1.5
COMPILER DESIGN LAB

Course Objectives:
To enlighten the student with knowledge base in compiler design and its applications

Course Outcomes: The end of the course student will be able to

x Design simple lexical analyzers
x Determine predictive parsing table for a CFG
x Apply Lex and Yacc tools
x Examine LR parser and generating SLR Parsing table
x Relate Intermediate code generation for subset C language

List of Experiments:
1. Write a C program to identify different types of Tokens in a given Program.
2. Write a Lex Program to implement a Lexical Analyzer using Lex tool.
3. Write a C program to Simulate Lexical Analyzer to validating a given input String.
4. Write a C program to implement the Brute force technique of Top down Parsing.
5. Write a C program to implement a Recursive Descent Parser.
6. Write C program to compute the First and Follow Sets for the given Grammar.
7. Write a C program for eliminating the left recursion and left factoring of a given grammar
8. Write a C program to check the validity of input string using Predictive Parser.
9. Write a C program for implementation of LR parsing algorithm to accept a given input string.
10. 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.
11. Simulate the calculator using LEX and YACC tool.
12. Generate YACC specification for a few syntactic categories.
13. Write a C program for generating the three address code of a given expression/statement.
14. Write a C program for implementation of a Code Generation Algorithm of a given
expression/statement.

Text Books & Reference Books :

1. Compilers: Principles, Techniques and Tools, Second Edition, Alfred V. Aho, Monica S. Lam,
Ravi Sethi, Jeffry D. Ullman, Pearson Publishers, 2007.
2. John R Levine, Tony Mason, Doug Brown, "Lex and Yacc", Orielly, 2nd Edition, 2009.
1. Write a C program to identify different types of Tokens in a given
Program.

#include <stdbool.h>

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

// Returns 'true' if the character is a DELIMITER.

bool isDelimiter(char ch)

if (ch == ' ' || ch == '+' || ch == '-' || ch == '*' ||

ch == '/' || ch == ',' || ch == '>' ||

ch == '<' || ch == '=' || ch == '(' || ch == ')' ||

ch == '[' || ch == ']' || ch == '{' || ch == '}')

return (true);

return (false);

// Returns 'true' if the character is an OPERATOR.

bool isOperator(char ch)

{
 if (ch == '+' || ch == '-' || ch == '*' ||

ch == '/' || ch == '>' || ch == '<' ||

ch == '=')

return (true);

return (false);

// Returns 'true' if the string is a VALID IDENTIFIER.

bool validIdentifier(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' || isDelimiter(str[0]) == true)

return (false);

return (true);

// Returns 'true' if the string is a KEYWORD.

bool isKeyword(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")

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

// Returns 'true' if the string is an INTEGER.

bool isInteger(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);

// Returns 'true' if the string is a REAL NUMBER.

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

// Extracts the SUBSTRING.

char* subString(char* str, int left, int right)

int i;

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

// Parsing the input STRING.

void parse(char* str)

int left = 0, right = 0;

int len = strlen(str);

printf(" lenrth of string:%d\n",len);

while (right <= len && left <= right)

if (isDelimiter(str[right]) == false)

right++;

if (isDelimiter(str[right]) == true && left == right)

if (isOperator(str[right]) == true)

printf("'%c' IS AN OPERATOR\n", str[right]);

right++;

left = right;

else if (isDelimiter(str[right]) == true && left != right

|| (right == len && left != right))

char* subStr = subString(str, left, right - 1);

if (isKeyword(subStr) == true)

printf("'%s' IS A KEYWORD\n", subStr);

 else if (isInteger(subStr) == true)

printf("'%s' IS AN INTEGER\n", subStr);

else if (isRealNumber(subStr) == true)

printf("'%s' IS A REAL NUMBER\n", subStr);

else if (validIdentifier(subStr) == true

&& isDelimiter(str[right - 1]) == false)

printf("'%s' IS A VALID IDENTIFIER\n", subStr);

else if (validIdentifier(subStr) == false

&& isDelimiter(str[right - 1]) == false)

printf("'%s' IS NOT A VALID IDENTIFIER\n", subStr);

left = right;

return;

// DRIVER FUNCTION

int main()

{
 // maximum length of string is 100 here

char str[100] = "int a = b + 1c : ";

parse(str); // calling the parse function

return (0);

Output:

lenrth of string:17

'int' IS A KEYWORD

'a' IS A VALID IDENTIFIER

'=' IS AN OPERATOR

'b' IS A VALID IDENTIFIER

'+' IS AN OPERATOR

'1c' IS NOT A VALID IDENTIFIER

':' IS A VALID IDENTIFIER

2. write a Lex program to implement a lexical analyzer using Lex Tool

INPUT:1 (lex.l save file)

%{

/* program to recognize a c program */

int COMMENT=0;

int cnt=0;
%}

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

%%

#.* { printf("\n%s is a PREPROCESSOR DIRECTIVE",yytext);}

int |

float |

char |

double |

while |

for |

do |

if |

break |

continue |

void |

switch |

case |

long |

struct |

const |

typedef |

return |

else |
goto {printf("\n\t%s is a KEYWORD",yytext);}

"/*" {COMMENT = 1;}

"*/" {COMMENT = 0; cnt++;}

{identifier}\( {if(!COMMENT)printf("\n\nFUNCTION\n\t%s",yytext);}

\{ {if(!COMMENT) printf("\n BLOCK BEGINS");}

\} {if(!COMMENT) printf("\n BLOCK ENDS");}

{identifier}(\[[0-9]*\])? {if(!COMMENT) printf("\n %s IDENTIFIER",yytext);}

\".*\" {if(!COMMENT) printf("\n\t%s is a STRING",yytext);}

[0-9]+ {if(!COMMENT) printf("\n\t%s is a NUMBER",yytext);}

\)(\;)? {if(!COMMENT) printf("\n\t");ECHO;printf("\n");}

\( ECHO;

= {if(!COMMENT)printf("\n\t%s is an ASSIGNMENT OPERATOR",yytext);}

\<= |

\>= |

\< |

== |

\> {if(!COMMENT) printf("\n\t%s is a RELATIONAL OPERATOR",yytext);}

%%

int main(int argc,char **argv)

if (argc > 1)

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

if(!file)

printf("could not open %s \n",argv[1]);

exit(0);

yyin = file;

yylex();

printf("\n\n Total No.Of comments are %d",cnt);

return 0;

int yywrap()

return 1;

INPUT:2 (LEX2.c save file)

#include<stdio.h>

main()

int a,b;

}
output:

C:\Users\USCEFI HYD\OneDrive\Desktop\Anuradha>flex lex.l

C:\Users\USCEFI HYD\OneDrive\Desktop\Anuradha>gcc lex.yy.c

C:\Users\USCEFI HYD\OneDrive\Desktop\Anuradha>a.exe lex2.c

#include<stdio.h> is a PREPROCESSOR DIRECTIVE

FUNCTION

main(

BLOCK BEGINS

int is a KEYWORD

a IDENTIFIER,

b IDENTIFIER;

BLOCK ENDS
Total No.Of comments are 0

C:\Users\USCEFI HYD\OneDrive\Desktop\Anuradha>

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

String.

#include<stdio.h>

#include<conio.h>

#include<string.h>

void main()

char s[5];

clrscr();

printf("\n Enter any operator:");

gets(s);

switch(s[0])

case'>': if(s[1]=='=')

printf("\n Greater than or equal");

else

printf("\n Greater than");

break;

case'<': if(s[1]=='=')
printf("\n Less than or equal");

else

printf("\nLess than");

break;

case'=': if(s[1]=='=')

printf("\nEqual to");

else

printf("\nAssignment");

break;

case'!': if(s[1]=='=')

printf("\nNot Equal");

else

printf("\n Bit Not");

break;

case'&': if(s[1]=='&')

printf("\nLogical AND");

else

printf("\n Bitwise AND");

break;

case'|': if(s[1]=='|')

printf("\nLogical OR");

10

else
printf("\nBitwise OR");

break;

case'+': printf("\n Addition");

break;

case'-': printf("\nSubstraction");

break;

case'*': printf("\nMultiplication");

break;

case'/': printf("\nDivision");

break;

case'%': printf("Modulus");

break;

default: printf("\n Not a operator");

getch();

OUTPUT:

Enter any operator:*

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

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

static const char alphabet[] =

"abcdefghijklmnopqrstuvwxyz"
"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
"0123456789";

static const int alphabetSize = sizeof(alphabet) - 1;

void bruteImpl(char* str, int index, int maxDepth)

{
for (int i = 0; i < alphabetSize; ++i)
{
str[index] = alphabet[i];

if (index == maxDepth - 1) printf("%s\n", str);

else bruteImpl(str, index + 1, maxDepth);
}
}

void bruteSequential(int maxLen)

{
char* buf = malloc(maxLen + 1);

for (int i = 1; i <= maxLen; ++i)

{
memset(buf, 0, maxLen + 1);
bruteImpl(buf, 0, i);
}

free(buf);
}

int main(void)
{
 bruteSequential(3);
return 0;
}

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

#include<stdio.h>

#include<string.h>

int E(),Edash(),T(),Tdash(),F();

char *ip;

char string[50];

int main()

printf("Enter the string\n");

scanf("%s",string);

ip=string;

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

if(E() &&ip=="\0"){

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

printf("\n String is successfully parsed\n");

else{

printf("\n--------------------------------\n");
printf("Error in parsing String\n");

int E()

printf("%s\tE->TE' \n",ip);

if(T())

if(Edash())

return 1;

else

return 0;

else

return 0;

intEdash()

if(*ip=='+')

printf("%s\tE'->+TE' \n",ip);
ip++;

if(T())

if(Edash())

return 1;

else

return 0;

else

return 0;

else

printf("%s\tE'->^ \n",ip);

return 1;

int T()

printf("%s\tT->FT' \n",ip);

if(F())
{

if(Tdash())

return 1;

else

return 0;

else

return 0;

intTdash()

if(*ip=='*')

printf("%s\tT'->*FT' \n",ip);

ip++;

if(F())

if(Tdash())

return 1;
}

else

return 0;

else

return 0;

else

printf("%s\tT'->^ \n",ip);

return 1;

int F()

if(*ip=='(')

printf("%s\tF->(E) \n",ip);

ip++;

if(E())

if(*ip==')')

{
ip++;

return 0;

else

return 0;

else

return 0;

else if(*ip=='i')

ip++;

printf("%s\tF->id \n",ip);

return 1;

else

return 0;

Output
Enter the string

Input Action
--------------------------------
E->TE'
T->FT'

--------------------------------
Error in parsing String

6. Write C program to compute the First and Follow Sets for the given
Grammar

// C program to calculate the First and

// Follow sets of a given grammar

#include<stdio.h>

#include<ctype.h>

#include<string.h>

// Functions to calculate Follow

voidfollowfirst(char, int, int);

void follow(char c);

// Function to calculate First

voidfindfirst(char, int, int);

int count, n = 0;

// Stores the final result

// of the First Sets

charcalc_first[10][100];

// Stores the final result

// of the Follow Sets

charcalc_follow[10][100];

int m = 0;

// Stores the production rules

char production[10][10];

char f[10], first[10];

int k;

charck;

int e;

int main(intargc, char **argv)

intjm = 0;

int km = 0;
inti, choice;

char c, ch;

count = 8;

// The Input grammar

strcpy(production[0], "E=TR");

strcpy(production[1], "R=+TR");

strcpy(production[2], "R=#");

strcpy(production[3], "T=FY");

strcpy(production[4], "Y=*FY");

strcpy(production[5], "Y=#");

strcpy(production[6], "F=(E)");

strcpy(production[7], "F=i");

intkay;

char done[count];

intptr = -1;

// Initializing the calc_first array

for(k = 0; k < count; k++) {

for(kay = 0; kay< 100; kay++) {

calc_first[k][kay] = '!';

}
}

int point1 = 0, point2, xxx;

for(k = 0; k < count; k++)

c = production[k][0];

point2 = 0;

xxx = 0;

// Checking if First of c has

// already been calculated

for(kay = 0; kay<= ptr; kay++)

if(c == done[kay])

xxx = 1;

if (xxx == 1)

continue;

// Function call

findfirst(c, 0, 0);

ptr += 1;

// Adding c to the calculated list

done[ptr] = c;

printf("\n First(%c) = { ", c);

calc_first[point1][point2++] = c;

// Printing the First Sets of the grammar

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

int lark = 0, chk = 0;

for(lark = 0; lark < point2; lark++) {

if (first[i] == calc_first[point1][lark])

chk = 1;

break;

if(chk == 0)

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

calc_first[point1][point2++] = first[i];

printf("}\n");
 jm = n;

point1++;

printf("\n");

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

chardonee[count];

ptr = -1;

// Initializing the calc_follow array

for(k = 0; k < count; k++) {

for(kay = 0; kay< 100; kay++) {

calc_follow[k][kay] = '!';

point1 = 0;

int land = 0;

for(e = 0; e < count; e++)

ck = production[e][0];

point2 = 0;

xxx = 0;

// Checking if Follow of ck
// has already been calculated

for(kay = 0; kay<= ptr; kay++)

if(ck == donee[kay])

xxx = 1;

if (xxx == 1)

continue;

land += 1;

// Function call

follow(ck);

ptr += 1;

// Addingck to the calculated list

donee[ptr] = ck;

printf(" Follow(%c) = { ", ck);

calc_follow[point1][point2++] = ck;

// Printing the Follow Sets of the grammar

for(i = 0 + km; i< m; i++) {

int lark = 0, chk = 0;

for(lark = 0; lark < point2; lark++)

{
 if (f[i] == calc_follow[point1][lark])

chk = 1;

break;

if(chk == 0)

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

calc_follow[point1][point2++] = f[i];

printf(" }\n\n");

km = m;

point1++;

void follow(char c)

inti, j;

// Adding "$" to the follow

// set of the start symbol

if(production[0][0] == c) {

f[m++] = '$';

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

for(j = 2;j < 10; j++)

if(production[i][j] == c)

if(production[i][j+1] != '\0')

// Calculate the first of the next

// Non-Terminal in the production

followfirst(production[i][j+1], i, (j+2));

if(production[i][j+1]=='\0' && c!=production[i][0])

// Calculate the follow of the Non-Terminal

// in the L.H.S. of the production

follow(production[i][0]);

}
 }

voidfindfirst(char c, int q1, int q2)

int j;

// The case where we

// encounter a Terminal

if(!(isupper(c))) {

first[n++] = c;

for(j = 0; j < count; j++)

if(production[j][0] == c)

if(production[j][2] == '#')

if(production[q1][q2] == '\0')

first[n++] = '#';

else if(production[q1][q2] != '\0'

 && (q1 != 0 || q2 != 0))

// Recursion to calculate First of New

// Non-Terminal we encounter after epsilon

findfirst(production[q1][q2], q1, (q2+1));

else

first[n++] = '#';

else if(!isupper(production[j][2]))

first[n++] = production[j][2];

else

// Recursion to calculate First of

// New Non-Terminal we encounter

// at the beginning

findfirst(production[j][2], j, 3);

}
voidfollowfirst(char c, int c1, int c2)

int k;

// The case where we encounter

// a Terminal

if(!(isupper(c)))

f[m++] = c;

else

inti = 0, j = 1;

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

if(calc_first[i][0] == c)

break;

//Including the First set of the

// Non-Terminal in the Follow of

// the original query

while(calc_first[i][j] != '!')

{
 if(calc_first[i][j] != '#')

f[m++] = calc_first[i][j];

else

if(production[c1][c2] == '\0')

// Case where we reach the

// end of a production

follow(production[c1][0]);

else

// Recursion to the next symbol

// in case we encounter a "#"

followfirst(production[c1][c2], c1, c2+1);

j++;

}
Output :
First(E)= { (, i, }
First(R)= { +, #, }
First(T)= { (, i, }
First(Y)= { *, #, }
First(F)= { (, i, }

-----------------------------------------------

Follow(E) = { $, ), }
Follow(R) = { $, ), }
Follow(T) = { +, $, ), }
Follow(Y) = { +, $, ), }
Follow(F) = { *, +, $, ), }

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

#include<stdio.h>
#include<string.h>
int main()
{
char
gram[20],part1[20],part2[20],modifiedGram[20],newGram[20],tempGram[20];
inti,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);
}
8.

#include<stdio.h>
#include<ctype.h>
#include<string.h>
#include<stdlib.h>
#define SIZE 128
#define NONE -1
#define EOS '\0'
#define NUM 257
#define KEYWORD 258
#define ID 259
#define DONE 260
#define MAX 999
char lexemes[MAX];
char buffer[SIZE];
intlastchar=-1;
intlastentry=0;
inttokenval=DONE;
intlineno=1;
intlookahead;
struct entry
{
char *lexptr;
int token;
}
symtable[100];
struct entry
keywords[]=
{"if",KEYWORD,"else",KEYWORD,"for",KEYWORD,"int",KEYWORD,"float"
,KEYWORD,

"double",KEYWORD,"char",KEYWORD,"struct",KEYWORD,"return",KEYWO
RD,0,0
};
voidError_Message(char *m)
{
fprintf(stderr,"line %d, %s \n",lineno,m);
exit(1);
}
intlook_up(char s[ ])
{
int k;
for(k=lastentry; k>0; k--)
if(strcmp(symtable[k].lexptr,s)==0)
return k;
return 0;
}
int insert(char s[ ],inttok)
{
intlen;
len=strlen(s);
if(lastentry+1>=MAX)
Error_Message("Symbpl table is full");
if(lastchar+len+1>=MAX)
Error_Message("Lexemes array is full");
lastentry=lastentry+1;
symtable[lastentry].token=tok;
symtable[lastentry].lexptr=&lexemes[lastchar+1];
lastchar=lastchar+len+1;
strcpy(symtable[lastentry].lexptr,s);
returnlastentry;
}
/*void Initialize()
{
struct entry *ptr;
for(ptr=keywords;ptr->token;ptr+1)
insert(ptr->lexptr,ptr->token);
}*/
intlexer()
{
int t;
intval,i=0;
while(1)
{
t=getchar();
if(t==' '||t=='\t');
else if(t=='\n')
lineno=lineno+1;
else if(isdigit(t))
{
ungetc(t,stdin);
scanf("%d",&tokenval);
return NUM;
}
else if(isalpha(t))
{
while(isalnum(t))
{
buffer[i]=t;
t=getchar();
i=i+1;
if(i>=SIZE)
Error_Message("Compiler error");
}
buffer[i]=EOS;
if(t!=EOF)
ungetc(t,stdin);
val=look_up(buffer);
if(val==0)
val=insert(buffer,ID);
tokenval=val;
returnsymtable[val].token;
}
else if(t==EOF)
return DONE;
else
{
tokenval=NONE;
return t;
}
}
}
void Match(int t)
{
if(lookahead==t)
lookahead=lexer();
else
Error_Message("Syntax error");
}
void display(intt,inttval)
{
if(t=='+'||t=='-'||t=='*'||t=='/')
printf("\nArithmetic Operator: %c",t);
else if(t==NUM)
printf("\n Number: %d",tval);
else if(t==ID)
printf("\n Identifier: %s",symtable[tval].lexptr);
else
printf("\n Token %d tokenval %d",t,tokenval);
}
void F()
{
//void E();
switch(lookahead)
{
case '(' :
Match('(');
E();
Match(')');
break;
case NUM :
display(NUM,tokenval);
Match(NUM);
break;
case ID :
display(ID,tokenval);
Match(ID);
break;
default :
Error_Message("Syntax error");
}
}
void T()
{
int t;
F();
while(1)
{
switch(lookahead)
{
case '*' :
t=lookahead;
Match(lookahead);
F();
display(t,NONE);
continue;
case '/' :
t=lookahead;
Match(lookahead);
display(t,NONE);
continue;
default :
return;
}
}
}
void E()
{
int t;
T();
while(1)
{
switch(lookahead)
{
case '+' :
t=lookahead;
Match(lookahead);
T();
display(t,NONE);
continue;
case '-' :
t=lookahead;
Match(lookahead);
T();
display(t,NONE);
continue;
default :
return;
}
}
}
void parser()
{
lookahead=lexer();
while(lookahead!=DONE)
{
E();
Match(';');
}
}
int main()
{
charans[10];
printf("\n Program for recursive descent parsing ");
printf("\n Enter the expression ");
printf("And place ; at the end\n");
printf("Press Ctrl-Z to terminate\n");
parser();
return 0;
}
SAMPLE OUTPUT:

Program for recursive descent parsing

Enter the expression And place ; at the end
Press Ctrl-Z to terminate
a*b+c;

Identifier: a
Identifier: b
Arithmetic Operator: *
Identifier: c
Arithmetic Operator: +
5*7;

Number: 5
Number: 7
Arithmetic Operator: *
*2;
line 5, Syntax error
9. Write a C program for implementation of LR parsing algorithm to accept a
given input string

ALGORITHM:
1. Get the input expression and store it in the input buffer.
2. Read the data from the input buffer one at the time and convert in to
corresponding Non Terminal using production rules available.
3. Perform push & pop operation for LR parsing table construction.
4. Display the result with conversion of corresponding input symbols to
production and production reduction to start symbol. No operation
performed on the operator.

PROGRAM:

#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;

return'x';

voidprintstat()

inti;

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

for(i=0;i<=top;i++)
printf("%c",stack[i]);

void main()

inti,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;

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

for(i=0;i<l;i++)< span="" style="box-sizing: border-box;">

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

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

push('E');

printstat();

ch2=ch1;

getch();

} </l;i++)<>
Output

OUTPUT:

LR PARSING

ENTER THE EXPRESSION

id+id*id-id

$id

$E

$E+

$E+id

$E+E

$E+E*

$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. 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.

// Including Libraries

#include <bits/stdc++.h>

using namespace std;

// Global Variables

int z = 0, i = 0, j = 0, c = 0;

// Modify array size to increase

// length of string to be parsed

char a[16], ac[20], stk[15], act[10];

// This Function will check whether

// the stack contain a production rule

// which is to be Reduce.

// Rules can be E->2E2 , E->3E3 , E->4

void check()
{

// Copying string to be printed as action

strcpy(ac,"REDUCE TO E -> ");

// c=length of input string

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

// checking for producing rule E->4

if(stk[z] == '4')

printf("%s4", ac);

stk[z] = 'E';

stk[z + 1] = '\0';

//printing action

printf("\n$%s\t%s$\t", stk, a);

for(z = 0; z < c - 2; z++)

// checking for another production

if(stk[z] == '2' &&stk[z + 1] == 'E' &&

 stk[z + 2] == '2')

printf("%s2E2", ac);

stk[z] = 'E';

stk[z + 1] = '\0';

stk[z + 2] = '\0';

printf("\n$%s\t%s$\t", stk, a);

i = i - 2;

for(z = 0; z < c - 2; z++)

//checking for E->3E3

if(stk[z] == '3' &&stk[z + 1] == 'E' &&

stk[z + 2] == '3')

printf("%s3E3", ac);

stk[z]='E';

stk[z + 1]='\0';

stk[z + 2]='\0';

printf("\n$%s\t%s$\t", stk, a);

 i = i - 2;

return ; // return to main

// Driver Function

int main()

printf("GRAMMAR is -\nE->2E2 \nE->3E3 \nE->4\n");

// a is input string

strcpy(a,"32423");

// strlen(a) will return the length of a to c

c=strlen(a);

// "SHIFT" is copied to act to be printed

strcpy(act,"SHIFT");

// This will print Labels (column name)

printf("\nstack \t input \t action");

// This will print the initial

// values of stack and input

printf("\n$\t%s$\t", a);

// This will Run upto length of input string

for(i = 0; j < c; i++, j++)

// Printing action

printf("%s", act);

// Pushing into stack

stk[i] = a[j];

stk[i + 1] = '\0';

// Moving the pointer

a[j]=' ';

// Printing action

printf("\n$%s\t%s$\t", stk, a);

// Call check function ..which will

// check the stack whether its contain

// any production or not

 check();

// Rechecking last time if contain

// any valid production then it will

// replace otherwise invalid

check();

// if top of the stack is E(starting symbol)

// then it will accept the input

if(stk[0] == 'E' &&stk[1] == '\0')

printf("Accept\n");

else //else reject

printf("Reject\n");

Output
GRAMMAR is -
E->2E2
E->3E3
E->4

stack input action

$ 32423$ SHIFT
$3 2423$ SHIFT
$32 423$ SHIFT
$324 23$ REDUCE TO E -> 4
$32E 23$ SHIFT
$32E2 3$ REDUCE TO E -> 2E2
$3E 3$ SHIFT
$3E3 $ REDUCE TO E -> 3E3
$E $ Accept

11. Simulate the calculator using LEX and YACC tool.

ALGORITHM:

Step1: A Yacc source program has three parts as follows:

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.

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"

externintyylval;

%}

%%

[0-9]+ {

yylval=atoi(yytext);

return NUMBER;

[\t] ;

[\n] return 0;

. returnyytext[0];

%%

intyywrap()

return 1;

YACC PART:

%{

#include<stdio.h>
 int flag=0;

%}

%token NUMBER

%left '+' '-'

%left '*' '/' '%'

%left '(' ')'

%%

ArithmeticExpression: E{

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

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

voidyyerror()

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

flag=1;

Output:
12. . Generate YACC specification for a few syntactic categories.

%{
/* This LEX program returns the tokens for the expression */
#include “y.tab.h”
%}

%%
“=” {printf(“\n Operator is EQUAL”);}
“+” {printf(“\n Operator is PLUS”);}
“-“ {printf(“\n Operator is MINUS”);}
“/” {printf(“\n Operator is DIVISION”);}
“*” {printf(“\n Operator is MULTIPLICATION”);}

[a-z A-Z]*[0-9]* {
printf(“\n Identifier is %s”,yytext);
return ID;
}
return yytext[0];
\n return 0;
%%

intyywrap()
{
return 1;
}

Program Name : arith_id.y

%{
#include
/* This YYAC program is for recognizing the Expression */
%}
%%
statement: A’=’E
|E{
printf(“\n Valid arithmetic expression”);
$$ = $1;
};

E: E’+’ID
| E’-’ID
| E’*’ID
| E’/’ID
| ID
;
%%
extern FILE *yyin;
main()
{
do
{
yyparse();
}while(!feof(yyin));
}

yyerror(char*s)
{
}

Output:

[root@localhost]# lex arith_id.1

[root@localhost]# yacc –d arith_id.y
[root@localhost]# gcclex.yy.cy.tab.c
[root@localhost]# ./a.out
x=a+b;

Identifier is x
Operator is EQUAL
Identifier is a
Operator is PLUS
Identifier is b

b) Program to recognise a valid variable which starts with a letter

followed by any number of letters or digits.
Program name: variable_test.l

%{
/* This LEX program returns the tokens for the Expression */
#include "y.tab.h"
%}
%%
"int " {return INT;}
"float" {return FLOAT;}
"double" {return DOUBLE;}
[a-zA-Z]*[0-9]*{
printf("\nIdentifier is %s",yytext);
return ID;
}
return yytext[0];
\n return 0;
intyywrap()
{
return 1;
}

Program name: variable_test.y

%{
#include
/* This YACC program is for recognising the Expression*/
%}
%token ID INT FLOAT DOUBLE
%%
D;T L
;
L:L,ID
|ID
;
T:INT
|FLOAT
|DOUBLE
;
%%
extern FILE *yyin;
main()
{
do
{
yyparse();
}while(!feof(yyin));
}
yyerror(char*s)
{
}

Output:

[root@localhost]# lexvariable_test.I
[root@localhost]# yacc –d variable_test.y
[root@localhost]# gcclex.yy.cy.tab.c
[root@localhost]# ./a.out
inta,b;

Identifier is a
Identifier is b[root@localhost]

13. Write a C program for generating the three address code of a given
expression/statement.

ALGORITHM:

Step1: Begin the program

Step2 : The expression is read from the file using a file pointer
Step3 : Each string is read and the total no. of strings in the file is calculated.
Step4: Each string is compared with an operator; if any operator is seen then the
previous string and next string are concatenated and stored in a first temporary
value and the three address code expression is printed
Step5 : Suppose if another operand is seen then the first temporary value is
concatenated to the next string using the operator and the expression is printed.
Step6 : The final temporary value is replaced to the left operand value.
Step7 : End the program.

PROGRAM: //program for three address code generation

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

struct three
{
char data[10],temp[7];
}s[30];
voidmain()
{
char d1[7],d2[7]="t";
int i=0,j=1,len=0;
FILE *f1,*f2;
clrscr();
f1=fopen("sum.txt","r");
f2=fopen("out.txt","w");
while(fscanf(f1,"%s",s[len].data)!=EOF)
len++;
itoa(j,d1,7);
strcat(d2,d1);
strcpy(s[j].temp,d2);
strcpy(d1,"");
strcpy(d2,"t");
if(!strcmp(s[3].data,"+"))
{
fprintf(f2,"%s=%s+%s",s[j].temp,s[i+2].data,s[i+4].data);
j++;
}
else if(!strcmp(s[3].data,"-"))
{
fprintf(f2,"%s=%s-%s",s[j].temp,s[i+2].data,s[i+4].data);
j++;
}
for(i=4;i<len-2;i+=2)
{
itoa(j,d1,7);
strcat(d2,d1);
strcpy(s[j].temp,d2);
if(!strcmp(s[i+1].data,"+"))
fprintf(f2,"\n%s=%s+%s",s[j].temp,s[j-1].temp,s[i+2].data);
else if(!strcmp(s[i+1].data,"-"))
fprintf(f2,"\n%s=%s-%s",s[j].temp,s[j-1].temp,s[i+2].data);
strcpy(d1,"");
strcpy(d2,"t");
j++;
}
fprintf(f2,"\n%s=%s",s[0].data,s[j-1].temp);
fclose(f1);
fclose(f2);
getch();

Input: sum.txt

out = in1 + in2 + in3 - in4

Output : out.txt

t1=in1+in2
t2=t1+in3
t3=t2-in4
out=t3