COMPILER DESIGN LAB FILE

SUBMITTED BY:- SUBMITTED TO :-

TUSHAR GUPTA DR GEETANJALI
181217
 INDEX

Serial Experiment Date

No.

1 Infix to Postfix 22/01/21

2 Integer to Number 29/01/21

3 Token Counter 29/01/21

4 English to Pig Latin 02/02/21

5 LA Implementation 05/02/21

6 Symbol Table Implementation 16/02/21

7 Leftmost Derivation 23/02/21

8 Predictive Parsing Algorithm 12/03/21

Code 1: INFIX TO POSTFIX

#include<bits/stdc++.h>

using namespace std;

int prec(char c)

if(c == '^')

return 3;

else if(c == '*' || c == '/')

return 2;

else if(c == '+' || c == '-')

return 1;

else

return -1;

void infitopost(string s)

std::stack<char> st;

st.push('N');

int l = s.length();

string ns;

for(int i = 0; i < l; i++)

if((s[i] >= 'a' && s[i] <= 'z') ||

(s[i] >= 'A' && s[i] <= 'Z'))

ns+=s[i];

else if(s[i] == '(')

 st.push('(');

else if(s[i] == ')')

while(st.top() != 'N' && st.top() != '(')

char c = st.top();

st.pop();

ns += c;

if(st.top() == '(')

char c = st.top();

st.pop();

else{

while(st.top() != 'N' && prec(s[i]) <=

prec(st.top()))

char c = st.top();

st.pop();

ns += c;

st.push(s[i]);

}
 while(st.top() != 'N')

char c = st.top();

st.pop();

ns += c;

cout << ns << endl;

int main()

string exp;

cout<<"Enter the expression:-\n";

cin>>exp;

infitopost(exp);

return 0;

}
Code 2:-Integer to Number
#include<iostream>

using namespace std;

int main()

int n;

cout<<"Enter the no of max length 3:-\n";

cin>>n;

int x;

int d=100;

for(int i=0;i<3;i++)

x=n/d%10;

d=d/10;

if(x==1)
{

cout<<"ONE";

else if(x==2)

cout<<"TWO";

else if(x==3)

cout<<"THREE";

else if(x==4)

cout<<"FOUR";

else if(x==5)

cout<<"FIVE";

else if(x==6)

cout<<"SIX";

else if(x==7)

{
 cout<<"SEVEN";

else if(x==8)

cout<<"EIGHT";

else if(x==9)

cout<<"NINE";

else if(x==10)

cout<<"TEN";

else

cout<<"Nothing";

cout<<" ";

}
CODE 3:-TOKEN COUNTER
#include<stdbool.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int cnt=0;
bool isDelimiter(char ch)
{
if (ch == ' ' || ch == '+' || ch == '-' || ch == '*' ||
ch == '/' || ch == ',' || ch == ';' || ch == '>' ||
ch == '<' || ch == '=' || ch == '(' || ch == ')' ||
ch == '[' || ch == ']' || ch == '{' || ch == '}')
return (true);
return (false);
}
bool isOperator(char ch)
{
if (ch == '+' || ch == '-' || ch == '*' ||
ch == '/' || ch == '>' || ch == '<' ||
ch == '='||ch==';')
return (true);
return (false);
}
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);
}
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);
}
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);
}

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;
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 parse(char* str)
{
int left = 0, right = 0;
int len = strlen(str);

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]);
cnt++;}

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

cnt++;
left = right;
}
}
return;
}
int main()
{

char str[100] = "int a =3; int b=7; int c= a+b; ";

parse(str);
printf("Total tokens %d",cnt);
return (0);
}

CODE 4:-ENGLISH TO PIGLATIN

#include <bits/stdc++.h>

using namespace std;

bool isVowel(char c)

return (c == 'A' || c == 'E' || c == 'I' ||

c == 'O' || c == 'U' || c == 'a' ||

 c == 'e' || c == 'i' || c == 'o' ||

c == 'u');

string pigLatin(string s)

int len = s.length();

int index = -1;

for (int i = 0; i < len; i++) {

if (isVowel(s[i])) {

index = i;

break;

if (index == -1)

return "-1";

return s.substr(index) + s.substr(0, index) + "ay";

int main()

string str = pigLatin("canada");

if (str == "-1")

cout << "No vowels found. Pig Latin not possible";

else

cout << str;

}

CODE 5:- LA IMPLEMENTATION

#include<stdio.h>
int op(char s)
{
if(s=='+'||s=='-'||s=='*'||s=='/'||s==';')
return 1;
else
return 0;
}
void main()
{
char s[100];
char var[100][1];
char id[100][3];
int t;
printf("Enter the expression or string:- ");
scanf("%s",&s);
int I=0,J=0;
int cnt=0,flag=0,i,j,k,c=0;
for(i=0;s[i]!='\0';i++)
{
if(op(s[i])==1&&cnt==0)
{
flag=1;
break;
}
 else if(op(s[i])==1)
{
continue;
}
else
{
t=1;
for(k=0;k<cnt;k++)
{
if(var[k][0]==s[i])
{
t=0;
break;
}
}
if(t==1)
{
cnt++;
var[I][0]=s[i];
id[I][0]='I';
id[I][1]='D';
id[I][2]=(cnt+'0');
I++;
}
}
}

if(flag==1)
printf("!!!!Invalid expression!!!!");
else
{
printf("Variable count is : %d\n",cnt);
for(i=0;i<cnt;i++)
{
printf("%c\t%c%c%c\n",var[i][0],id[i][0],id[i][1],id[i][2]);
}
}
}
Code 6:- Implementation of Symbol Table
#include<stdio.h>
#include<ctype.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
void main()
{
int i=0,j=0,x=0,n;
void *p,*add[5];
char ch,srch,b[15],d[15],c;
printf("Expression terminated by $:");
while((c=getchar())!='$')
{
b[i]=c;
i++;
}
n=i-1;
printf("Given Expression:");
i=0;
while(i<=n)
{
printf("%c",b[i]);
i++;
}
printf("\n Symbol Table\n");
printf("Symbol \t addr \t type");
while(j<=n)
{
c=b[j];
if(isalpha(toascii(c)))
{
p=malloc(c);
add[x]=p;
d[x]=c;
printf("\n%c \t %d \t identifier\n",c,p);
x++;
j++;
}
else
{
ch=c;
if(ch=='+'||ch=='-'||ch=='*'||ch=='=')
{
p=malloc(ch);
add[x]=p;
d[x]=ch;
printf("\n %c \t %d \t operator\n",ch,p);
x++;
j++;
}}}}
Code 7:- Implementation of Left Most Derivation
#include <iostream>
using namespace std;
int main()
{
cout<<"Given CFG: E ---> (E + E) / (E - E)/ (E * E)/ (E / E)/ (E)/ (id)"<<endl;
cout<<"Given String: id + id * id"<<endl;
cout<<"Generating Left Most Derivation of given CFG"<<endl;

string s1, s2, s3, s4, id;

s1 = "E"; s2 = "E"; s3 = "E"; id = "id";
string s = s1 + "*" + s2;
for(int i = 0; i < 1; i++)
{
cout<< s <<endl;
s1 = s1 + "+" +s1;
s4 = s1 + "*" +s2;
}
cout<< s4 <<endl;
s4 = id + "+" + s1;
string s5;
s5 = id + "+" + id + "*" + s3;
cout<<s5<<endl;
string s6;
s6 = id + "+" + "id" + "*" + id;
cout<<s6<<endl;
}
Code 8:- Implementation of Predictive Parsing Algorithm

#include<iostream>

#include<string>

#include<deque>

using namespace std;

int n,n1,n2;

int getPosition(string arr[], string q, int size)

for(int i=0;i<size;i++)

if(q == arr[i])

return i;

}
 return -1;

int main()

string prods[10],first[10],follow[10],nonterms[10],terms[10];

string pp_table[20][20] = {};

cout<<"Enter the number of productions : ";

cin>>n;

cin.ignore();

cout<<"Enter the productions"<<endl;

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

getline(cin,prods[i]);

cout<<"Enter first for "<<prods[i].substr(3)<<" : ";

getline(cin,first[i]);

cout<<"Enter the number of Terminals : ";

cin>>n2;

cin.ignore();

cout<<"Enter the Terminals"<<endl;

for(int i=0;i<n2;i++)

cin>>terms[i];

terms[n2] = "$";
n2++;

cout<<"Enter the number of Non-Terminals : ";

cin>>n1;

cin.ignore();

for(int i=0;i<n1;i++)

cout<<"Enter Non-Terminal : ";

getline(cin,nonterms[i]);

cout<<"Enter follow of "<<nonterms[i]<<" : ";

getline(cin,follow[i]);

cout<<endl;

cout<<"Grammar"<<endl;

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

cout<<prods[i]<<endl;

for(int j=0;j<n;j++)

int row = getPosition(nonterms,prods[j].substr(0,1),n1);

if(prods[j].at(3)!='#')
 {

for(int i=0;i<first[j].length();i++)

int col = getPosition(terms,first[j].substr(i,1),n2);

pp_table[row][col] = prods[j];

else

for(int i=0;i<follow[row].length();i++)

int col = getPosition(terms,follow[row].substr(i,1),n2);

pp_table[row][col] = prods[j];

//Display Table

for(int j=0;j<n2;j++)

cout<<"\t"<<terms[j];

cout<<endl;

for(int i=0;i<n1;i++)

cout<<nonterms[i]<<"\t";

//Display Table

for(int j=0;j<n2;j++)
 {

cout<<pp_table[i][j]<<"\t";

cout<<endl;

//Parsing String

char c;

do{

string ip;

deque<string> pp_stack;

pp_stack.push_front("$");

pp_stack.push_front(prods[0].substr(0,1));

cout<<"Enter the string to be parsed : ";

getline(cin,ip);

ip.push_back('$');

cout<<"Stack\tInput\tAction"<<endl;

while(true)

for(int i=0;i<pp_stack.size();i++)

cout<<pp_stack[i];

cout<<"\t"<<ip<<"\t";

int row1 = getPosition(nonterms,pp_stack.front(),n1);

int row2 = getPosition(terms,pp_stack.front(),n2);

int column = getPosition(terms,ip.substr(0,1),n2);

if(row1 != -1 && column != -1)

{

string p = pp_table[row1][column];

if(p.empty())

cout<<endl<<"String cannot be Parsed."<<endl;

break;

pp_stack.pop_front();

if(p[3] != '#')

for(int x=p.size()-1;x>2;x--)

pp_stack.push_front(p.substr(x,1));

cout<<p;

else

if(ip.substr(0,1) == pp_stack.front())

if(pp_stack.front() == "$")

cout<<endl<<"String Parsed."<<endl;

break;
 }

cout<<"Match "<<ip[0];

pp_stack.pop_front();

ip = ip.substr(1);

else

cout<<endl<<"String cannot be Parsed."<<endl;

break;

cout<<endl;

cout<<"Continue?(Y/N) ";

cin>>c;

cin.ignore();

}while(c=='y' || c=='Y');

return 0;