Compiler Design [31707] | Manvi Savani

Practical 1
Implementation of Finite Automata and String Validation
 Code:
#include <stdio.h>
#define max 100
void main() {
char str[max],f='a';
int i;
printf("enter the string to be checked: ");
scanf("%s",str);
for(i=0;str[i]!='\1';i++) {
switch(f) {
case 'a': if(str[i]=='1') f='b';
else if(str[i]=='0') f='a';
break;
case 'b': if(str[i]=='1') f='b';
else if(str[i]=='0') f='c';
break;
case 'c': if(str[i]=='1') f='b';
else if(str[i]=='0') f='a';
break;
}
}
if(f=='c')
printf("\n String is accepted \n", f);
else printf("\n String is not accepted \n", f);
return 0;
}

190760107055 1
 Compiler Design [31707] | Manvi Savani

 Output:

190760107055 2
 Compiler Design [31707] | Manvi Savani

Practical 2
Introduction to Lex Tool.
 What is LAX?
o It is a tool or software which automatically generates a lexical analyzer (finite
Automata). It takes as its input a LEX source program and produces lexical
Analyzer as its output. Lexical Analyzer will convert the input string entered by
the user into tokens as its output.
o LEX is a program generator designed for lexical processing of character
input/output stream. Anything from simple text search program that looks for
pattern in its input-output file to a C compiler that transforms a program into
optimized code.
o In program with structure input-output two tasks occurs over and over. It can
divide the input-output into meaningful units and then discovering the
relationships among the units for C program (the units are variable names,
constants, and strings). This division into units (called tokens) is known as lexical
analyzer or LEXING. LEX helps by taking a set of descriptions of possible tokens
n producing a routine called a lexical analyzer or LEXER or Scanner.

 The function of LAX

o Firstly lexical analyzer creates a program lex.1 in the Lex language. Then Lex
compiler runs the lex.1 program and produces a C program [Link].c.
o Finally C compiler runs the [Link].c program and produces an object program
[Link].
o [Link] is lexical analyzer that transforms an input stream into a sequence of tokens.

 LAX Source Program

o It is a language used for specifying or representing Lexical Analyzer.
o A Lex program is separated into three sections by %% delimiters. The formal of
Lex source is as follows:

190760107055 3
 Compiler Design [31707] | Manvi Savani

{ definitions }   
%%  
{ rules }   
%%   
{ user subroutines }  
o There are two parts of the LEX source program −
 Auxiliary Definitions
 Translation Rules

 Auxiliary Definition:
o It denotes the regular expression of the form.
o Distinct Names [D1=R1\D2=R2\Dn=Rn][D1=R1\D2=R2\Dn=Rn] Regular
Expressions
o Where
Distinct Names (Di)→ Shortcut name of Regular Expression
Regular Expression (Ri)→ Notation to represent a collection of input symbols.
o Example
o Auxiliary Definition for Identifiers −

o Auxiliary Definition for Signed Numbers

integer=digit digit*
sign = + | -
signedinteger = sign integer

190760107055 4
 Compiler Design [31707] | Manvi Savani

o Auxiliary Definition for Decimal Numbers

decimal = signedinteger . integer | [Link]
o Auxiliary Definition for Exponential Numbers
Exponential – No = (decimal | signedinteger) E signedinteger
o Auxiliary Definition for Real Numbers
Real-No. = decimal | Exponential – No

 Translation Rules:
o It is a set of rules or actions which tells Lexical Analyzer what it has to do or
what it has to return to parser on encountering the token.
o It consists of statements of the form −

o Where
Pi → Pattern or Regular Expression consisting of input alphabets and Auxiliary
definition names.
Actioni → It is a piece of code that gets executed whenever a token is
Recognized. Each Actioni specifies a set of statements to be executed whenever
each regular expression or pattern Pi matches with the input string.
o Example
o Translation Rules for "Keywords"

o We can see that if Lexical Analyzer is given the input "begin", it will recognize
the token "begin" and Lexical Analyzer will return 1 as integer code to the parser.
o Translation Rules for "Identifiers"
letter (letter + digit)* {Install ( );return 6}

190760107055 5
 Compiler Design [31707] | Manvi Savani

o If Lexical Analyzer is given the token which is an "identifier", then the Action
taken by the Lexical Analyzer is to install or store the name in the symbol table &
return value 6 as integer code to the parser.

 Example:
/*lex program to count number of words*/
%{
#include<stdio.h>
#include<string.h>
int i = 0;
%}
/* Rules Section*/
%%
([a-zA-Z0-9])* {i++;} /* Rule for counting
number of words*/
"\n" {printf("%d\n", i); i = 0;}
%%
int yywrap(void){}
int main()
{
// The function that starts the analysis
   yylex();  
    return 0;
}

190760107055 6
 Compiler Design [31707] | Manvi Savani

Practical 3
Implement following Programs Using Lex
a. Generate Histogram of words
 Code:
%{
#include<stdio.h>
#include<string.h>
int i = 0;
%}
%%
([a-zA-Z0-9])* {i++;}
"\n" {printf("%d\n", i); i = 0;}
%%
int yywrap(void) {}
int main() {
yylex();
return 0;
}

 Output:

190760107055 7
 Compiler Design [31707] | Manvi Savani

b. Ceasor Cypher
 Code:
%%
[a-z] {char ch = yytext[0];
ch += 3;
if (ch> 'z') ch -= ('z'+1- 'a');
printf ("%c" ,ch );
}
[A-Z] { char ch = yytext[0] ;
ch += 3;
if (ch> 'Z') ch -= ('Z'+1- 'A');
printf("%c",ch);
}
%%

 Output:

190760107055 8
 Compiler Design [31707] | Manvi Savani

c. Extract single and multiline comments from C Program

 Code:
%{
#include<stdio.h>
%}
%%
\/\/(.*) {};
\/\*(.*\n)*.*\*\/ {};
%%
int yywrap() {
return 1;
}
int main() {
yyin=fopen("input6.c","r");
yyout=fopen("out.c","w");
yylex();
return 0;
}

 input6.c file:

190760107055 9
 Compiler Design [31707] | Manvi Savani

 Output:

Practical 4
Implement following Programs Using Lex.
a. Convert Roman to Decimal
 Code:
WS [ \t]+
%%
int total=0;
I total += 1;
IV total += 4;
V total += 5;
IX total += 9;
X total += 10;
XL total += 40;
L total += 50;
XC total += 90;
C total += 100;
CD total += 400;
D total += 500;
CM total += 900;
M total += 1000;
{WS} |
\n return total;
%%
int main (void) {
int first;
first = yylex ();

190760107055 10
 Compiler Design [31707] | Manvi Savani

printf ("%d \n", first);

return 0;
}

 Output:

b. Check weather given statement is compound or simple

 Code:
%{
#include<stdio.h>
int flag=0;
%}
%%
and |
or |
but |
because |
if |
then |
nevertheless { flag=1; }
. ;
\n { return 0; }
%%
int main() {
printf("Enter the sentence:\n");
yylex();
if(flag==0)
printf("Simple sentence\n");
else
printf("compound sentence\n");
}

190760107055 11
 Compiler Design [31707] | Manvi Savani

int yywrap( ) {
return 1;
}

 Output:

c. Extract html tags from .html file

 Code:
%{
#include<stdio.h>
%}
%%
\<[^>]*\> fprintf(yyout,"%s\n",yytext);
.|\n;
%%
int yywrap() {
return 1;
}
int main() {
yyin=fopen("[Link]","r");

190760107055 12
 Compiler Design [31707] | Manvi Savani

yyout=fopen("[Link]","w");
yylex();
return 0;
}

 [Link] file:
<html>
<head></head>
<body>
<h1> SSASIT </h1>
<h2> CD </h2>
</body>
</html>

 Output:

190760107055 13
 Compiler Design [31707] | Manvi Savani

190760107055 14
 Compiler Design [31707] | Manvi Savani

Practical 5
Implementation of Recursive Descent Parser without backtracking
Input: The string to be parsed.
Output: Whether string parsed successfully or not. Explanation:
Students have to implement the recursive procedure for RDP for a typical
grammar. The production no. are displayed as they are used to derive the
string.
 Code:
#include<stdio.h>
#include<string.h>
#include<ctype.h>
char input[10];
int i,error;
void E();
void T();
void Eprime();
void Tprime();
void F();
main() {
i=0;
error=0;
printf("Enter an arithmetic expression : ");
gets(input);
E();
if(strlen(input)==i&&error==0)
printf("\nAccepted..!!!\n");
else
printf("\nRejected..!!!\n");
}
void E() {
T();
Eprime();
}
void Eprime() {
if(input[i]=='+') {
i++;
T();
Eprime();
}
}

190760107055 15
 Compiler Design [31707] | Manvi Savani

void T() {
F();
Tprime();
}
void Tprime() {
if(input[i]=='*') {
i++;
F();
Tprime();
}
}
void F() {
if(isalnum(input[i]))
i++;
else if(input[i]=='(') {
i++;
E();
if(input[i]==')')
i++;
else
error=1;
}
else
error=1;
}

 Grammar:
E -> TE'
E' -> +TE' | ε
T -> FT'
T' -> *FT' | ε
F -> (E) | a

190760107055 16
 Compiler Design [31707] | Manvi Savani

 Output:

190760107055 17
 Compiler Design [31707] | Manvi Savani

Practical 6
Finding “First” set
Input: The string consists of grammar symbols.
Output: The First set for a given string.
Explanation:
The student has to assume a typical grammar. The program when run will
ask for the string to be entered. The program will find the First set of the
given string.
 Code:
#include<stdio.h>
#include<ctype.h>
#include<string.h>
void findfirst(char, int, int);
int count, n = 0;
char calc_first[10][100];
char production[10][10];
char f[10], first[10];
int k;
char ck;
int e;
int main(int argc, char **argv) {
int jm = 0;
int km = 0;
int i, choice;
char c, ch;
count = 8;
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");
int kay;
char done[count];
int ptr = -1;
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++) {

190760107055 18
 Compiler Design [31707] | Manvi Savani

c = production[k][0];
point2 = 0;
xxx = 0;
for(kay = 0; kay <= ptr; kay++)
if(c == done[kay])
xxx = 1;
if (xxx == 1)
continue;
findfirst(c, 0, 0);
ptr += 1;
done[ptr] = c;
printf("\n First(%c) = { ", c);
calc_first[point1][point2++] = c;
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");
}
void findfirst(char c, int q1, int q2) {
int j;
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)) {
findfirst(production[q1][q2], q1, (q2+1));
}
else

190760107055 19
 Compiler Design [31707] | Manvi Savani

first[n++] = '#';
}
else if(!isupper(production[j][2])) {
first[n++] = production[j][2];
}
else {
findfirst(production[j][2], j, 3);
}
}
}
}

 Output:

190760107055 20
 Compiler Design [31707] | Manvi Savani

Practical 7
Generate 3-tuple intermediate code for given infix expression.
 Code:
#include<stdio.h>
#include<conio.h>
#include<string.h>
int i=1,j=0,no=0,tmpch=90;
char str[100],left[15],right[15];
void findopr();
void explore();
void fleft(int);
void fright(int);
struct exp{
int pos;
char op;
}
k[15];
void main(){
printf("\t\tINTERMEDIATE CODE GENERATION\n\n");
printf("Enter the Expression :");
scanf("%s",str);
printf("The intermediate code:\n");
findopr();
explore();
}
void findopr(){
for(i=0;str[i]!='\0';i++)
if(str[i]==':'){
k[j].pos=i;
k[j++].op=':';
}
for(i=0;str[i]!='\0';i++)
if(str[i]=='/'){
k[j].pos=i;
k[j++].op='/';
}
for(i=0;str[i]!='\0';i++)
if(str[i]=='*'){
k[j].pos=i;
k[j++].op='*';
}
for(i=0;str[i]!='\0';i++)
if(str[i]=='+'){
k[j].pos=i;
k[j++].op='+';

190760107055 21
 Compiler Design [31707] | Manvi Savani

}
for(i=0;str[i]!='\0';i++)
if(str[i]=='-'){
k[j].pos=i;
k[j++].op='-';
}
}
void explore(){
i=1;
while(k[i].op!='\0'){
fleft(k[i].pos);
fright(k[i].pos);
str[k[i].pos]=tmpch--;
printf("\t%c := %s%c%s\t\t",str[k[i].pos],left,k[i].op,right);
printf("\n");
i++;
}
fright(-1);
if(no==0){
fleft(strlen(str));
printf("\t%s := %s",right,left);
getch();
exit(0);
}
printf("\t%s := %c",right,str[k[--i].pos]);
getch();
}
void fleft(int x){
int w=0,flag=0;
x--;
while(x!= -1 &&str[x]!= '+' &&str[x]!='*'&&str[x]!='='&&str[x]!='\0'&&str[x]!
='-'&&str[x]!='/'&&str[x]!=':'){
if(str[x]!='$'&& flag==0){
left[w++]=str[x];
left[w]='\0';
str[x]='$';
flag=1;
}
x--;
}
}
void fright(int x){
int w=0,flag=0;
x++;
while(x!= -1 && str[x]!= '+'&&str[x]!='*'&&str[x]!='\0'&&str[x]!='='&&str[x]!
=':'&&str[x]!='-'&&str[x]!='/'){

190760107055 22
 Compiler Design [31707] | Manvi Savani

if(str[x]!='$'&& flag==0){
right[w++]=str[x];
right[w]='\0';
str[x]='$';
flag=1;
}
x++;
}
}

 Output:

190760107055 23
 Compiler Design [31707] | Manvi Savani

Practical 8
Extract Predecessor and Successor from given Control Flow Graph.
 Code:
#include<stdio.h>
#include<stdlib.h>
typedef struct _tnode{
int value;
struct _tnode *parent;
struct _tnode *left;
struct _tnode *right;
} tnode;
typedef tnode Tree;
tnode * newTNode(int X){
tnode * temp;
temp = (tnode *)malloc(sizeof(tnode));
temp->value = X;
temp->left = temp->right = temp->parent = NULL;
return temp;
}
tnode * FindMin(Tree * T){
if(T!=NULL)
while(T->left!=NULL)
T = T->left;
return T;
}
tnode * FindMax(Tree * T){
if(T!=NULL)
while(T->right!=NULL)
T = T->right;
return T;
}
tnode * Find(int X, Tree * T){
while(T!=NULL){
if(X > T->value)
T = T->right;
else if( X < T->value)
T = T->left;
else
break;
}
return T;
}
Tree * Insert(int X, Tree * T){
if(T == NULL)
return newTNode(X);

190760107055 24
 Compiler Design [31707] | Manvi Savani

else{
if(X > T->value){
T->right = Insert(X, T->right);
T->right->parent = T;
}
else if(X < T->value){
T->left = Insert(X, T->left);
T->left->parent = T;
}
}
return T;
}
void printInOrder(Tree *T){
if(T!=NULL){
printInOrder(T->left);
printf(" %d ",T->value);
printInOrder(T->right);
}
}
tnode * Successor(tnode * N, Tree * T){
tnode * succ = NULL;
if(N->right!=NULL)
succ = FindMin(N->right);
else{
succ = N->parent;
while(succ!=NULL && succ->right == N){
N = succ;
succ = N->parent;
}
}
return succ;
}
tnode * Predecessor(tnode * N, Tree *T){
tnode * predec = NULL;
if(N->left!=NULL){
predec = FindMax(N->left);
}
else{
predec = N->parent;
while(predec!=NULL && predec->left == N){
N = predec;
predec = N->parent;
}
}
return predec;
}

190760107055 25
 Compiler Design [31707] | Manvi Savani

int main(){
Tree * T = NULL;
tnode *temp, *found;
int arr[8];
printf("Enter 5 integers: ");
for(int i = 0; i < 8; ++i) {
scanf("%d", &arr[i]);
}
int i = 0;
for(i=0; i<8;i++)
T = Insert(arr[i],T);
printf("Tree: ");
printInOrder(T);
printf("\n");
for(i=0; i<8;i++) {
found = Find(arr[i],T);
printf("%d's Succesor is ",found->value);
temp = Successor(found,T);
if(temp!=NULL)
printf("%d ", temp->value);
else
printf("none ");
printf("and Predecessor is ");
temp = Predecessor(found,T);
if(temp!=NULL)
printf("%d\n", temp->value);
else
printf("none\n");
}
return 0;
}

 Output:

190760107055 26
 Compiler Design [31707] | Manvi Savani

Practical 9
Introduction to YACC and generate Calculator Program.
 Code:
%{
#include<stdio.h>
#include "[Link].h"
extern int yylval;
%}
%%
[0-9]+ {
yylval=atoi(yytext);
return NUMBER;
}
[\t] ;
[\n] return 0;
. return yytext[0];
%%
int yywrap(){
return 1;
}

 Output:

190760107055 27
 Compiler Design [31707] | Manvi Savani

Practical 10
Finding “Follow” set
Input: The string consists of grammar symbols.
Output: The Follow set for a given string.
Explanation:
The student has to assume a typical grammar. The program when run will
ask for the string to be entered. The program will find the Follow set of the
given string.
 Code:
#include<stdio.h>
#include<ctype.h>
#include<string.h>
void followfirst(char, int, int);
void follow(char c);
void findfirst(char, int, int);
int count, n = 0;
char calc_first[10][100];
char calc_follow[10][100];
int m = 0;
char production[10][10];
char f[10], first[10];
int k;
char ck;
int e;
int main(int argc, char **argv) {
int jm = 0;
int km = 0;
int i, choice;
char c, ch;
count = 8;
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");
int kay;
char done[count];
int ptr = -1;
for(k = 0; k < count; k++) {
for(kay = 0; kay < 100; kay++) {
calc_first[k][kay] = '!';

190760107055 28
 Compiler Design [31707] | Manvi Savani

}
}
int point1 = 0, point2, xxx;
for(k = 0; k < count; k++) {
c = production[k][0];
point2 = 0;
xxx = 0;
for(kay = 0; kay <= ptr; kay++)
if(c == done[kay])
xxx = 1;
if (xxx == 1)
continue;
findfirst(c, 0, 0);
ptr += 1;
done[ptr] = c;
calc_first[point1][point2++] = c;
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) {
calc_first[point1][point2++] = first[i];
}
}
jm = n;
point1++;
}
printf("\n");
char donee[count];
ptr = -1;
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;
for(kay = 0; kay <= ptr; kay++)

190760107055 29
 Compiler Design [31707] | Manvi Savani

if(ck == donee[kay])
xxx = 1;
if (xxx == 1)
continue;
land += 1;
follow(ck);
ptr += 1;
donee[ptr] = ck;
printf(" Follow(%c) = { ", ck);
calc_follow[point1][point2++] = ck;
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) {
int i, j;
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') {
followfirst(production[i][j+1], i, (j+2));
}
if(production[i][j+1]=='\0' && c!=production[i][0]) {
follow(production[i][0]);
}
}
}
}
}

190760107055 30
 Compiler Design [31707] | Manvi Savani

void findfirst(char c, int q1, int q2) {

int j;
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)) {
findfirst(production[q1][q2], q1, (q2+1));
}
else
first[n++] = '#';
}
else if(!isupper(production[j][2])) {
first[n++] = production[j][2];
}
else {
findfirst(production[j][2], j, 3);
}
}
}
}
void followfirst(char c, int c1, int c2) {
int k;
if(!(isupper(c)))
f[m++] = c;
else {
int i = 0, j = 1;
for(i = 0; i < count; i++) {
if(calc_first[i][0] == c)
break;
}
while(calc_first[i][j] != '!') {
while(calc_first[i][j] != '#') {
f[m++] = calc_first[i][j];
}
else {
if(production[c1][c2] == '\0') {
follow(production[c1][0]);
}
else {
followfirst(production[c1][c2], c1, c2+1);
}

190760107055 31
 Compiler Design [31707] | Manvi Savani

}
j++;
}
}
}

 Output:

190760107055 32
 Compiler Design [31707] | Manvi Savani

Practical 11
Implement a C program for constructing LL (1) parsing.
 Code:
#include<stdio.h>
#include<string.h>
#define TSIZE 128
int table[100][TSIZE];
char terminal[TSIZE];
char nonterminal[26];
struct product {
char str[100];
int len;
} pro[20];
int no_pro;
char first[26][TSIZE];
char follow[26][TSIZE];
char first_rhs[100][TSIZE];
int isNT(char c) {
return c >= 'A' && c <= 'Z';
}
void readFromFile() {
FILE* fptr;
fptr = fopen("[Link]", "r");
char buffer[255];
int i;
int j;
while (fgets(buffer, sizeof(buffer), fptr)) {
printf("%s", buffer);
j = 0;
nonterminal[buffer[0] - 'A'] = 1;
for (i = 0; i < strlen(buffer) - 1; ++i) {
if (buffer[i] == '|') {
++no_pro;
pro[no_pro - 1].str[j] = '\0';
pro[no_pro - 1].len = j;
pro[no_pro].str[0] = pro[no_pro - 1].str[0];
pro[no_pro].str[1] = pro[no_pro - 1].str[1];
pro[no_pro].str[2] = pro[no_pro - 1].str[2];
j = 3;
}
else {
pro[no_pro].str[j] = buffer[i];
++j;
if (!isNT(buffer[i]) && buffer[i] != '-' && buffer[i] != '>') {
terminal[buffer[i]] = 1;

190760107055 33
 Compiler Design [31707] | Manvi Savani

}
}
}
pro[no_pro].len = j;
++no_pro;
}
}
void add_FIRST_A_to_FOLLOW_B(char A, char B) {
int i;
for (i = 0; i < TSIZE; ++i) {
if (i != '^')
follow[B - 'A'][i] = follow[B - 'A'][i] || first[A - 'A'][i];
}
}
void add_FOLLOW_A_to_FOLLOW_B(char A, char B) {
int i;
for (i = 0; i < TSIZE; ++i) {
if (i != '^')
follow[B - 'A'][i] = follow[B - 'A'][i] || follow[A - 'A'][i];
}
}
void FOLLOW() {
int t = 0;
int i, j, k, x;
while (t++ < no_pro) {
for (k = 0; k < 26; ++k) {
if (!nonterminal[k])
continue;
char nt = k + 'A';
for (i = 0; i < no_pro; ++i) {
for (j = 3; j < pro[i].len; ++j) {
if (nt == pro[i].str[j]) {
for (x = j + 1; x < pro[i].len; ++x) {
char sc = pro[i].str[x];
if (isNT(sc)) {
add_FIRST_A_to_FOLLOW_B(sc, nt);
if (first[sc - 'A']['^'])
continue;
}
else {
follow[nt - 'A'][sc] = 1;
}
break;
}
if (x == pro[i].len)
add_FOLLOW_A_to_FOLLOW_B(pro[i].str[0], nt);

190760107055 34
 Compiler Design [31707] | Manvi Savani

}
}
}
}
}
}
void add_FIRST_A_to_FIRST_B(char A, char B) {
int i;
for (i = 0; i < TSIZE; ++i) {
if (i != '^') {
first[B - 'A'][i] = first[A - 'A'][i] || first[B - 'A'][i];
}
}
}
void FIRST() {
int i, j;
int t = 0;
while (t < no_pro) {
for (i = 0; i < no_pro; ++i) {
for (j = 3; j < pro[i].len; ++j) {
char sc = pro[i].str[j];
if (isNT(sc)) {
add_FIRST_A_to_FIRST_B(sc, pro[i].str[0]);
if (first[sc - 'A']['^'])
continue;
}
else {
first[pro[i].str[0] - 'A'][sc] = 1;
}
break;
}
if (j == pro[i].len)
first[pro[i].str[0] - 'A']['^'] = 1;
}
++t;
}
}
void add_FIRST_A_to_FIRST_RHS__B(char A, int B) {
int i;
for (i = 0; i < TSIZE; ++i) {
if (i != '^')
first_rhs[B][i] = first[A - 'A'][i] || first_rhs[B][i];
}
}
void FIRST_RHS() {
int i, j;

190760107055 35
 Compiler Design [31707] | Manvi Savani

int t = 0;
while (t < no_pro) {
for (i = 0; i < no_pro; ++i) {
for (j = 3; j < pro[i].len; ++j) {
char sc = pro[i].str[j];
if (isNT(sc)) {
add_FIRST_A_to_FIRST_RHS__B(sc, i);
if (first[sc - 'A']['^'])
continue;
}
else {
first_rhs[i][sc] = 1;
}
break;
}
if (j == pro[i].len)
first_rhs[i]['^'] = 1;
}
++t;
}
}
int main() {
readFromFile();
follow[pro[0].str[0] - 'A']['$'] = 1;
FIRST();
FOLLOW();
FIRST_RHS();
int i, j, k;
printf("\n");
for (i = 0; i < no_pro; ++i) {
if (i == 0 || (pro[i - 1].str[0] != pro[i].str[0])) {
char c = pro[i].str[0];
printf("FIRST OF %c: ", c);
for (j = 0; j < TSIZE; ++j) {
if (first[c - 'A'][j]) {
printf("%c ", j);
}
}
printf("\n");
}
}
printf("\n");
for (i = 0; i < no_pro; ++i) {
if (i == 0 || (pro[i - 1].str[0] != pro[i].str[0])) {
char c = pro[i].str[0];
printf("FOLLOW OF %c: ", c);

190760107055 36
 Compiler Design [31707] | Manvi Savani

for (j = 0; j < TSIZE; ++j) {

if (follow[c - 'A'][j]) {
printf("%c ", j);
}
}
printf("\n");
}
}
printf("\n");
for (i = 0; i < no_pro; ++i) {
printf("FIRST OF %s: ", pro[i].str);
for (j = 0; j < TSIZE; ++j) {
if (first_rhs[i][j]) {
printf("%c ", j);
}
}
printf("\n");
}
terminal['$'] = 1;
terminal['^'] = 0;
printf("\n");
printf("\n\t**************** LL(1) PARSING TABLE *******************\n");
printf("\t--------------------------------------------------------\n");
printf("%-10s", "");
for (i = 0; i < TSIZE; ++i) {
if (terminal[i]) printf("%-10c", i);
}
printf("\n");
int p = 0;
for (i = 0; i < no_pro; ++i) {
if (i != 0 && (pro[i].str[0] != pro[i - 1].str[0]))
p = p + 1;
for (j = 0; j < TSIZE; ++j) {
if (first_rhs[i][j] && j != '^') {
table[p][j] = i + 1;
}
else if (first_rhs[i]['^']) {
for (k = 0; k < TSIZE; ++k) {
if (follow[pro[i].str[0] - 'A'][k]) {
table[p][k] = i + 1;
}
}
}
}
}
k = 0;

190760107055 37
 Compiler Design [31707] | Manvi Savani

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

if (i == 0 || (pro[i - 1].str[0] != pro[i].str[0])) {
printf("%-10c", pro[i].str[0]);
for (j = 0; j < TSIZE; ++j) {
if (table[k][j]) {
printf("%-10s", pro[table[k][j] - 1].str);
}
else if (terminal[j]) {
printf("%-10s", "");
}
}
++k;
printf("\n");
}
}
}

190760107055 38
 Compiler Design [31707] | Manvi Savani

 Output:

190760107055 39
 Compiler Design [31707] | Manvi Savani

Practical 12
Implement a C program to implement LALR parsing.
 Code:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void push(char *,int *,char);
char stacktop(char *);
void isproduct(char,char);
int ister(char);
int isnter(char);
int isstate(char);
void error();
void isreduce(char,char);
char pop(char *,int *);
void printt(char *,int *,char [],int);
void rep(char [],int);
struct action{
char row[6][5];
};
const struct action A[12]={
{"sf","emp","emp","se","emp","emp"},
{"emp","sg","emp","emp","emp","acc"},
{"emp","rc","sh","emp","rc","rc"},
{"emp","re","re","emp","re","re"},
{"sf","emp","emp","se","emp","emp"},
{"emp","rg","rg","emp","rg","rg"},
{"sf","emp","emp","se","emp","emp"},
{"sf","emp","emp","se","emp","emp"},
{"emp","sg","emp","emp","sl","emp"},
{"emp","rb","sh","emp","rb","rb"},
{"emp","rb","rd","emp","rd","rd"},
{"emp","rf","rf","emp","rf","rf"}
};
struct gotol{
char r[3][4];
};
const struct gotol G[12]={
{"b","c","d"},
{"emp","emp","emp"},
{"emp","emp","emp"},
{"emp","emp","emp"},
{"i","c","d"},
{"emp","emp","emp"},
{"emp","j","d"},

190760107055 40
 Compiler Design [31707] | Manvi Savani

{"emp","emp","k"},
{"emp","emp","emp"},
{"emp","emp","emp"},
};
char ter[6]={'i','+','*',')','(','$'};
char nter[3]={'E','T','F'};
char states[12]={'a','b','c','d','e','f','g','h','m','j','k','l'};
char stack[100];
int top=-1;
char temp[10];
struct grammar{
char left;
char right[5];
};
const struct grammar rl[6]={
{'E',"e+T"},
{'E',"T"},
{'T',"T*F"},
{'T',"F"},
{'F',"(E)"},
{'F',"i"},
};
void main(){
char inp[80],x,p,dl[80],y,bl='a';
int i=0,j,k,l,n,m,c,len;
printf(" Enter the input :");
scanf("%s",inp);
len=strlen(inp);
inp[len]='$';
inp[len+1]='\0';
push(stack,&top,bl);
printf("\n stack \t\t\t input");
printt(stack,&top,inp,i);
do{
x=inp[i];
p=stacktop(stack);
isproduct(x,p);
if(strcmp(temp,"emp")==0)
error();
if(strcmp(temp,"acc")==0)
break;
else{
if(temp[0]=='s'){
push(stack,&top,inp[i]);
push(stack,&top,temp[1]);
i++;

190760107055 41
 Compiler Design [31707] | Manvi Savani

}
else{
if(temp[0]=='r'){
j=isstate(temp[1]);
strcpy(temp,rl[j-2].right);
dl[0]=rl[j-2].left;
dl[1]='\0';
n=strlen(temp);
for(k=0;k<2*n;k++)
pop(stack,&top);
for(m=0;dl[m]!='\0';m++)
push(stack,&top,dl[m]);
l=top;
y=stack[l-1];
isreduce(y,dl[0]);
for(m=0;temp[m]!='\0';m++)
push(stack,&top,temp[m]);
}
}
}
printt(stack,&top,inp,i);
}
while(inp[i]!='\0');
if(strcmp(temp,"acc")==0)
printf(" \n accept the input ");
else
printf(" \n do not accept the input ");
}
void push(char *s,int *sp,char item){
if(*sp==100)
printf(" stack is full ");
else{
*sp=*sp+1;
s[*sp]=item;
}
}
char stacktop(char *s){
char i;
i=s[top];
return i;
}
void isproduct(char x,char p){
int k,l;
k=ister(x);
l=isstate(p);
strcpy(temp,A[l-1].row[k-1]);

190760107055 42
 Compiler Design [31707] | Manvi Savani

}
int ister(char x){
int i;
for(i=0;i<6;i++)
if(x==ter[i])
return i+1;
return 0;
}
int isnter(char x){
int i;
for(i=0;i<3;i++)
if(x==nter[i])
return i+1;
return 0;
}
int isstate(char p){
int i;
for(i=0;i<12;i++)
if(p==states[i])
return i+1;
return 0;
}
void error(){
printf(" error in the input ");
exit(0);
}
void isreduce(char x,char p){
int k,l;
k=isstate(x);
l=isnter(p);
strcpy(temp,G[k-1].r[l-1]);
}
char pop(char *s,int *sp){
char item;
if(*sp==-1)
printf(" stack is empty ");
else{
item=s[*sp];
*sp=*sp-1;
}
return item;
}
void printt(char *t,int *p,char inp[],int i){
int r;
printf("\n");
for(r=0;r<=*p;r++)

190760107055 43
 Compiler Design [31707] | Manvi Savani

rep(t,r);
printf("\t\t\t");
for(r=i;inp[r]!='\0';r++)
printf("%c",inp[r]);
}
void rep(char t[],int r){
char c;
c=t[r];
switch(c){
case 'a': printf("0");
break;
case 'b': printf("1");
break;
case 'c': printf("2");
break;
case 'd': printf("3");
break;
case 'e': printf("4");
break;
case 'f': printf("5");
break;
case 'g': printf("6");
break;
case 'h': printf("7");
break;
case 'm': printf("8");
break;
case 'j': printf("9");
break;
case 'k': printf("10");
break;
case 'l': printf("11");
break;
default :printf("%c",t[r]);
break;
}
}

190760107055 44
 Compiler Design [31707] | Manvi Savani

 Output:

190760107055 45
 Compiler Design [31707] | Manvi Savani

Practical 13
Implement a C program to implement operator precedence parsing.
 Code:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char *input;
int i=0;
char lasthandle[6],stack[50],handles[][5]={")E(","E*E","E+E","i","E^E"};
int top=0,l;
char prec[9][9]={
/*input*/
/*stack + - * / ^ i ( ) $ */
/* + */ '>', '>','<','<','<','<','<','>','>',
/* - */ '>', '>','<','<','<','<','<','>','>',
/* * */ '>', '>','>','>','<','<','<','>','>',
/* / */ '>', '>','>','>','<','<','<','>','>',
/* ^ */ '>', '>','>','>','<','<','<','>','>',
/* i */ '>', '>','>','>','>','e','e','>','>',
/* ( */ '<', '<','<','<','<','<','<','>','e',
/* ) */ '>', '>','>','>','>','e','e','>','>',
/* $ */ '<', '<','<','<','<','<','<','<','>',
};
int getindex(char c) {
switch(c) {
case '+':return 0;
case '-':return 1;
case '*':return 2;
case '/':return 3;
case '^':return 4;
case 'i':return 5;
case '(':return 6;
case ')':return 7;
case '$':return 8;
}
}
int shift() {
stack[++top]=*(input+i++);
stack[top+1]='\0';
}

190760107055 46
 Compiler Design [31707] | Manvi Savani

int reduce() {
int i,len,found,t;
for(i=0;i<5;i++)//selecting handles {
len=strlen(handles[i]);
if(stack[top]==handles[i][0]&&top+1>=len) {
found=1;
for(t=0;t<len;t++) {
if(stack[top-t]!=handles[i][t]) {
found=0;
break;
}
}
if(found==1) {
stack[top-t+1]='E';
top=top-t+1;
strcpy(lasthandle,handles[i]);
stack[top+1]='\0';
return 1;
}
}
}
return 0;
}
void dispstack() {
int j;
for(j=0;j<=top;j++)
printf("%c",stack[j]);
}
void dispinput() {
int j;
for(j=i;j<l;j++)
printf("%c",*(input+j));
}
void main() {
int j;
input=(char*)malloc(50*sizeof(char));
printf("\nEnter the string\n");
scanf("%s",input);
input=strcat(input,"$");
l=strlen(input);
strcpy(stack,"$");
printf("\nSTACK\tINPUT\tACTION");
while(i<=l) {
shift();
printf("\n");
dispstack();

190760107055 47
 Compiler Design [31707] | Manvi Savani

printf("\t");
dispinput();
printf("\tShift");
if(prec[getindex(stack[top])][getindex(input[i])]=='>') {
while(reduce()) {
printf("\n");
dispstack();
printf("\t");
dispinput();
printf("\tReduced: E->%s",lasthandle);
}
}
}
if(strcmp(stack,"$E$")==0)
printf("\nAccepted;");
else
printf("\nNot Accepted;");
}

190760107055 48
 Compiler Design [31707] | Manvi Savani

 Output:

190760107055 49