CHANDIGARH COLLEGE OF ENGINEERING

AND TECHNOLOGY
(DEGREE WING)
Government Institute under Chandigarh (UT) Administration, Affiliated to
Panjab University, Chandigarh
Sector-26, Chandigarh. PIN-160019

Semester: 6th
Compiler Design (Practical)
Subject Code: CS 654

Submitted By: Submitted To:

Lalit Kumar Dr. Gulshan Goyal
CO20328 Professor
(CSE Department)
Page 1 of 136
Compiler design Practical (CS-654) C020328

ACKNOWLEDGEMENT

Perseverance, inspiration and motivation have played a great role in the success of any venture.
It would be incomplete to submit this practical file without acknowledging the people behind
this endeavour and without whose support I wouldn't have able to achieve this. I would like to
thank Dr. Gulshan Goyal for giving me an opportunity to work on such a fabulous project and
for their guidance and support in completing my project. Secondly, I would like to thank my
parents for their constant support which helped me finish my practical in limited time. It gives
me immense pleasure to express my gratitude to everyone who shared with me their precious
time and effort during the practical period

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 2
Compiler design Practical (CS-654) C020328

Index

Sr. No. Name of Experiment Page no.

1. Program to design 3 types of DFA: prefix, suffix, 4-13

substring based on userinput.

2. Program to convert NFA to DFA. 14-24

3. Program to recognize single line andmultiline 25-31

comment from given code.

4. Program to implement lexical analyzer. 32-38

5. Program to implement bottom-up parser. 39-56

a) Shift reduce parser
b) Operator precendence parser
6. Program to implement SLR Parser. 57-70

7. Program to implement CLR Parser. 71-85

8. Program to implement LR Parser. 86-95

9. Program to implement Top Down Parser(LL(1)). 96-103

10. Program to convert infix to postfix 104-117

expression and then generate 3 addresscode and its
syntax tree.
11. (a) Program to implement minimum 5 118-124
optimizations.
11(b). Program to implement code generation. 125-128

12. A software program designed to compute the Leading 129-136

and Trailing sets of Non-Terminals.

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 3
Compiler design Practical (CS-654) C020328

Practical - 1
1.1. Aim
Write a program to generate a DFA and to show string processing corresponding to the DFA
generated.

1.2. Input

The various input parameters by the user include:

• Selecting the type of DFA:
• Suffix (ending with a particular substring)
• Prefix (starting with a particular substring)
• Specific Substring (containing a specific substring)
• A particular substring of length 3 corresponding to the type of DFA.
• A string of any length to check its acceptance by DFA
1.3. Output
The output, corresponding to the input parameters will be:
• A transition table representing the DFA
• Result for the string acceptance by the DFA, the string either gets
• Accepted
• Rejected or
• The user may enter an invalid substring
1.4. Algorithm
1. Start
2. Declare:
• 2.1. String[] states, to store the states, start_state = q0, end_state = q3
• 2.2. Hashmap(part of Java‟s collection) for transition mapping
3. Select the type of DFA to be constructed from and store the value in some variable(say x):
• 3.1. SUFFIX
• 3.2. PREFIX
• 3.3. SPECIFIC SUBSTRING
4. Enter any substring of length three and put it in a variable (say input).
5. If (x is equal to suffix):
▪ 5.1.1. Set no of states (n) = 4
▪ 5.1.2. Set flag_a = -1
▪ 5.1.3. Set flag_b = -1

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 4
Compiler design Practical (CS-654) C020328

▪ 5.1.4. for i, 0 to n-1 times:

• 5.1.4.1. if (input[i]=`a`
• 5.1.4.1.1. define the transition hashmaps and set tag_b=i
• 5.1.4.2. else
• 5.1.4.2.1. define the transition hashmaps and set tag_a=i
▪ 5.1.5. if (input = „aab‟ or „bba‟):
• 5.1.5.1. if (aab)
• 5.1.5.1.1. set tag_a=1 and define transition hashmaps
• 5.1.5.2. else if (bba)
• 5.1.5.2.1. set tag_b=1 and define transition hashmaps
▪ 5.1.6. Go to 5 5.2. If (x is equal to prefix):
▪ 5.2.1. Set no of states (n) = 5
▪ 5.2.2. Set dead_state = q4
▪ 5.2.3. For i, 0 to n-1 times
▪ 5.2.3.1. Define the transition hashmaps.
▪ 5.2.4. Go to
▪ 5 5.3. If(x is equal to specific substring):
▪ 5.3.1. Set no of states (n) = 4
▪ 5.3.2. Set flag_a = -1
▪ 5.3.3. Set flag_b = -1
▪ 5.3.4. for i, 0 to n-1 times:
• 5.3.4.1. if(input[i]=‟a‟
• 5.3.4.1.1. define the transition hashmaps and set tag_b=i
• 5.3.4.2. else
• 5.3.4.2.1. define the transition hashmaps and set tag_a=i
▪ 5.3.5. Go to 5
6. Function to print the transition table:
▪ 6.1. Pass the string[] states as parameter; for i, n-1 times
▪ 6.1.1. if state[i]=start_state
• 6.1.1.1. print(“--> q0 “ and corresponding transition on a and b)
▪ 6.1.2. else if state[i]=end_state
• 6.1.2.1. print(“ * q3” and corresponding transition on a and b)
▪ 6.1.3. else if state[i] = dead_state
• 6.1.3.1.print(“ #d dead_state” and corresponding transition on a and
b)
▪ 6.1.4. else
• 6.1.4.1.print (“ state[i]” and corresponding transition on a and b)
7. Function for string processing:
▪ 7.1. Input the string
▪ 7.2. Set process=start_state
▪ 7.3. for i, 0 to length of input string
▪ 7.3.1. if(input[i]=‟a‟
• 7.3.1.1. process=transition_a
• 7.3.1.2.print(process)
▪ 7.3.2. else
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 5
Compiler design Practical (CS-654) C020328

• 7.3.2.1. process=transition_b
• 7.3.2.2.print(process)
▪ 7.4. If (transition from last character of input string maps to final_state)
▪ 7.4.1. print(“string accepted”)
▪ 7.5. else
▪ 7.5.1. print(“string rejected”)
1. Stop.

1.5. Flowchart

1.6. Source Code:

#include <iostream>
#include<cstring>
using namespace std;
int dfa[10][10];
int col1,col2;//col1 for transitions of a nd col2 for transitions of b
int states,length;//states calculates total no. of states
int flaga,statea,flagb,stateb;
char alpha1,alpha2;//input alphabets
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 6
Compiler design Practical (CS-654) C020328

char str[20];//string to be processed

void print_table()
{
cout << "\n---TRANSITION TABLE---\n\n";
cout << " |\t" <<alpha1 << "\t" << alpha2<<"\n";
cout << "_______|____________________\n";
//initial state
cout << "->q0 |\t" ;
cout << "q"<<dfa[0][0]<<"\t"<<"q"<<dfa[0][1]<<"\n";
//rest states
for(int i=1;i<length; i++)
{
cout << " q"<<i<< " |\t" ;
cout << "q"<<dfa[i][0]<<"\t"<<"q"<<dfa[i][1]<<"\n";
}
//final state
cout << " *q"<<length<< " |\t" ;
cout << "q"<<dfa[length][0]<<"\t"<< "q"<< dfa[length][1]<<"\n";
//dead state(prefix)
if(states==length+2)
{
cout << " q"<<states-1<< " |\t";
cout << "q"<< dfa[length+1][0]<<"\t"<< "q"<< dfa[length+1][1]<<"\n";
}
}
void string_process()
{
cout<<"\n\n---STRING PROCESSING---\n\n";
cout<<"Enter the string to be processed: ";
cin>>str;
int lenstr,curr_state=0;
lenstr=strlen(str);
for(int i=0;i<lenstr;i++)
{
if(str[i]==alpha1)
{
cout<< "q" << curr_state << "-" <<str[i] << "->";
curr_state = dfa[curr_state][0];
}
else
{
cout << "q" << curr_state << "-" <<str[i] << "->";
curr_state = dfa[curr_state][1];
}
}
if(curr_state==length)//final state
{
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 7
Compiler design Practical (CS-654) C020328

cout << "*q" << curr_state;

cout << "\n\nSTRING ACCEPTED\n\n";
}
else
{
cout << "q" << curr_state;
cout << "\n\nSTRING REJECTED\n\n";
}
}
int main()
{
int choice,i,j;
do{
cout<<"\n\n---------------------------------"<<endl;
cout<<"PROGRAM TO IMPLEMENT DFA\n"<<endl;
cout<<"Types of DFA: "<<endl;
cout<<"1 Prefix "<<endl;
cout<<"2 Suffix "<<endl;
cout<<"3 Substring"<<endl;
cout<<"4 Exit menu"<<endl;
cout<<"Enter your choice for which you want to design the DFA: ";
cin>>choice;
cout<<endl<<"Enter the alphabets over which you want to design the DFA: ";
cin>>alpha1>>alpha2;
cout<<"\n";
switch(choice)
{
case 1:
cout<<"---DFA for PREFIX---"<<endl;
char prefix[10];
cout<<"Enter the prefix string over alphabet {"<<alpha1<<","<<alpha2<<"}: ";
cin>>prefix;
length=strlen(prefix);
states=length+2;
for(i=0; i<length; i++)
{
col1=(prefix[i]==alpha1)? 0: 1;
col2=(col1==0)? 1 : 0;
dfa[i][col1] = i+1;//next state
dfa[i][col2] = length+1;//dead state
}
dfa[length][0] = length;//final state
dfa[length][1] = length;//final state
dfa[length+1][0] = length+1;//dead state
dfa[length+1][1] = length+1;//dead state
print_table();
string_process();
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 8
Compiler design Practical (CS-654) C020328

break;
case 2:
cout<<"---DFA for SUFFIX---"<<endl;
char suffix[10];
cout<<"Enter the suffix string over alphabet {"<<alpha1<<","<<alpha2<<"}: ";
cin>>suffix;
length=strlen(suffix);
states=length+1;
for(i=0; i<length; i++)
{
col1= (suffix[i]==alpha1)? 0: 1;
dfa[i][col1] = i+1;//next state
col2 = (col1==0)? 1 : 0;//for second alphabet
//flag shows missed one time atleast
//state set as per the iteration going nd is repeated further
if(col2 == 0 && flaga==0)
{
dfa[i][col2] = i;
flaga = 1;
statea = i;
}
else if(col2 == 0 && flaga==1)
{
dfa[i][col2] = statea;
}
if(col2== 1 && flagb==0)
{
dfa[i][col2] = i;
flagb = 1;
stateb = i;
}
else if(col2 == 1 && flagb==1)
{
dfa[i][col2] = stateb;
}
}
if(flaga)
dfa[length][0] = statea;
else //case of aaa
dfa[length][0] = length;
if(flagb)
dfa[length][1] = stateb;
else//case of bbb
dfa[length][1] = length;
//handling exceptional cases for final states
if(suffix[0]==alpha1 && suffix[1]==alpha1 && suffix[2]==alpha2)//aab
dfa[3][0]=1;
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 9
Compiler design Practical (CS-654) C020328

if(suffix[0]==alpha1 && suffix[1]==alpha2 && suffix[2]==alpha1)//aba

dfa[3][1]=2;
if(suffix[0]==alpha2 && suffix[1]==alpha1 && suffix[2]==alpha2)//bab
dfa[3][0]=2;
if(suffix[0]==alpha2 && suffix[1]==alpha2 && suffix[2]==alpha1)//bba
dfa[3][1]=1;
print_table();
string_process();
flaga=0, flagb=0;
statea=0,stateb=0;
break;
case 3:
cout<<"---DFA for SUBSTRING---"<<endl;
char substring[10];
cout<<"Enter the substring string over alphabet {"<<alpha1<<","<<alpha2<<"}: ";
cin>>substring;
length=strlen(substring);
states=length+1;
for(i=0; i<length; i++)
{
col1= (substring[i]==alpha1)? 0: 1;
dfa[i][col1] = i+1;//next state
col2 = (col1==0)? 1 : 0;//for second alphabet
//flag shows missed one time atleast
//state set as per the iteration going nd is repeated further
if(col2 == 0 && flaga==0)
{
dfa[i][col2] = i;
flaga = 1;
statea = i;
}
else if(col2 == 0 && flaga==1)
{
dfa[i][col2] = statea;
}
if(col2== 1 && flagb==0)
{
dfa[i][col2] = i;
flagb = 1;
stateb = i;
}
else if(col2 == 1 && flagb==1)
{
dfa[i][col2] = stateb;
}
}
//for final states self loops
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 10
Compiler design Practical (CS-654) C020328

dfa[length][0]=length;
dfa[length][1]=length;
print_table();
string_process();
flaga=0, flagb=0;
statea=0,stateb=0;
break;
case 4:
break;
default:
cout<<"Select a valid option !";
}
}while(choice!=4);
return 0;
}

1.7. Output:

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 11
Compiler design Practical (CS-654) C020328

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 12
Compiler design Practical (CS-654) C020328

1.8. Frequently Asked Questions (FAQs):

Q1: What is a DFA?

Ans: A DFA can be represented by a 5-tuple (Q, ∑, δ, q0, F) where
Q is a finite set of states.
∑ is a finite set of symbols called the alphabet.
δ is the transition function where δ: Q × ∑ → Q
q0 is the initial state from where any input is processed (q0 ∈ Q).
F is a set of final state/states of Q (F ⊆ Q).

Q2: What is a regular expression?

Ans: These are mathematical expressions used to describe regular languages. In compiler
design regular expressions are used for description of tokens.

Q3: Write the regular expression for strings containing “abb” prefix over alphabet {a,
b}.
Ans: abb(a+b)*

Q4.What is a Dead State in DFA?

Ans: It is a rejecting state. Once the machine reaches dead state, there is no way to reach to
any final state.

Q5: What do you mean by acceptability of a string?

Ans: A string w is accepted by a DFA (Q, Σ, q0, Δ, F), if and only if *(

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 13
Compiler design Practical (CS-654) C020328

Practical-2
2.1. Aim
To write a program to convert NFA to DFA.

2.2. Input

Following is the input which is asked from the user that includes the details for designing the
NFA -
• Initial State of NFA
• Final State of NFA
• No. of transitions and states of NFA
• Initial state, final state & corresponding alphabet for that every transition state of NFA

2.3. Expected Output

• Transition table for the NFA

• Transition table for the DFA

2.4. Method
The method of converting NFA to its equivalent DFA is discussed below. In NFA, when a
specific input is given to the current state, the machine goes to multiple states. It can have zero,
one or more than one move on a given input symbol. On the other hand, in DFA, when a
specific input is given to the current state, the machine goes to only one state. DFA has only
one move on a given input symbol.
As we know that M = (Q, ∑, δ, q0, F) is an NFA which accepts the language L(M). So there
should be equivalent DFA denoted by M' = (Q', ∑', q0', δ', F') such that L(M) = L(M').
• The main objective of the program is to generate the transition table for a DFA for user
input designed NFA. For this purpose, the user is initially asked to enter the initial state,
final State of NFA, no. of transitions and states of NFA. Then the user enters the initial
state, final state & corresponding alphabet for that every transition state for which the NFA
has to be generated.
• Functions such as bootstrapDFA(), createDFA(), initDFA(), initNFA(),
showTableNFA(NFA), showTableDFA(DFA), addTransition() and inputTransition() are
used to implement the conversion process from NFA to DFA.
• Here showTableNFA(NFA) and showTableDFA(DFA) are used to display the transition
table of NFA and DFA respectively.
• Then the transition table of NFA is shown on the basis of the user input.
• Thereafter, the NFA is successfully converted into DFA and transition table of DFA is
displayed.
2.5. Algorithm

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 14
Compiler design Practical (CS-654) C020328

1. BEGIN
2. Declare
a. struct Transition {
i. unsigned int input_state;
i. unsigned int output_states;
ii. int symbol;
iii. };
This structure is for storing information for designing NFA.
b. final[10] – For storing the final states of NFA.
c. total_states[1] – For storing the total no. of states of NFA.
d. final_count[1] – For storing the total no. of final states of NFA.
e. struct FA {
unsigned int starting_state;
unsigned int final_states;
vector<struct Transition> transition_table;
};
This structure is for storing information for generating DFA.
3. Execute the function initNFA().
4. Enter the initial state, total no. of states, total no. of final states of NFA, final state, no.
of transitions.
5. Then the user enters the initial state, final state & corresponding alphabet for that every
transition state for which the NFA has to be generated.
6. Execute showTableNFA(NFA) – It displays the transition table of NFA.
a. Perform switch(check){
1. case 'a':
a. tab[ctr][0]=setToString((*j).output_states);
b. break;
2. case 'b':
a. tab[ctr][1]=setToString((*j).output_states);
b. break;
b. Perform bool check_final(int index)to check whether the state index present in
the set of final states or not.
c. Set check = false.
d. Initialize k .
e. while(final[k] && !check){
if(index == final[k]) then set check = true and increment k
Else return check;
}
f. if(check_final(k)) then mark the initial state of the DFA by ->q0
g. Else mark final state by DFA by *qn.
7. Display the transition table of NFA.
8. Execute createDFA() which implements the transition table of DFA table.
9. Perform initDFA() to find out the combination of States for each possible input
alphabet.
a. Set DFA.final_states = 0.
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 15
Compiler design Practical (CS-654) C020328

b. Then add the transitions for NFA's starting state to DFA.

c. Then addTransition( ) checks if transition with same input state and symbol
exists.
d. Final_state of DFA will be all states with contain F (final states of NFA).
10. Each time a new DFA state is generated under the input alphabet columns, goto step 7
again, otherwise go to step 9.
11. The states which contain any of the final states of the NFA are the final states of the
equivalent DFA.
12. Perform bootstrapDFA() to find moves from marked states stored in the queue on input
symbol a and b using transition function of NFA and update the transition table of
DFA.
13. END.

2.6. Flowchart

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 16
Compiler design Practical (CS-654) C020328

q0, w) ∈ F. That is a string is accepted by a DFA if and only if the DFA starting at the initial
state ends in an accepting state after processing the string.

2.7. Source Code:

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
char str[100000];
int nstates[1000][100], temp[100];
int ntable[1000][100];
void print1(int k, int n)
{
int i, f=0, in=-1;
printf("\t[");
for(i=0;i<n;i++)
{
if(nstates[k][i])
{
f++;
if(in==-1)
in=i;
}
}
if(f==1)
{
printf("q%d",in);
}
else if(f>1)
{
printf("q%d", in);
for(i=in+1;i<n;i++)
{
if(nstates[k][i])
{
printf("q%d", i);
}
}
}
printf("]\t");
}
int main()
{
int n, ip, i, j, initial, noFinal, q, in, k, fin, numOftrans, f, no, l;
//variables
char choice;
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 17
Compiler design Practical (CS-654) C020328

printf("Enter number of states:"); /*print message and scan the input*/

scanf("%d", &n);
printf("Enter the number of input symbols:");
scanf("%d", &ip);
int table[n][ip][n+1];
char symbols[ip];
printf("Enter the input symbols:");
for(i=0;i<ip;i++)
{
fflush(stdin);
scanf("%c", &symbols[i]);
fflush(stdin);
}
printf("Input the transition table:\n");
for(i=0;i<n;i++)
{
for(j=0;j<ip;j++)
{
printf("\nEnter the number of transitions for delta(q%d,%c):", i,symbols[j]);
scanf("%d", &numOftrans);
while(numOftrans>n||numOftrans<0)
{
printf("Invalid input\nEnter correct value:");
scanf("%d", &numOftrans);
}
for(k=0;k<numOftrans;k++)
{
printf("Enter %d transition of delta(q%d, %c): q", k+1,
i,symbols[j]);
scanf("%d", &table[i][j][k]);
}
table[i][j][k] = -1;
}
}
printf("\nEnter the initial state: q");
scanf("%d", &initial);
printf("Enter the number of final state:");
scanf("%d", &noFinal);
int final[noFinal];
printf("Enter the final states:");
for(i=0;i<noFinal;i++)
{
printf("q");
scanf("%d", &final[i]);
}
printf("\n\n-- -- -- -- -- -- -- -- -- -- -- TRANSITION TABLE-- -- -- -- -- -- -- -- -- -- -- -- -- ");
printf("\n\n\t states |");
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 18
Compiler design Practical (CS-654) C020328

for(i=0;i<ip;i++)
{
printf("\t %c |\t", symbols[i]);
}
printf("\n\t|-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -|\n");
for(i=0;i<n;i++)
{
if(i==initial)
{
printf("\t q%d", i);
}
else
{
printf("\t q%d", i);
}
for(j=0;j<noFinal;j++)
{
if(final[j]==i)
{
break;
}
}
if(j<noFinal)
{
printf("**\t");
}
else
{
printf( " ");
}
for(j=0;j<ip;j++)
{
printf("|\t{");
if(table[i][j][0]!=-1)
{
printf("q%d", table[i][j][0]);
for(k=1;table[i][j][k]!=-1;k++)
{
printf("q%d", table[i][j][k]);
}
}
printf("}\t");
}
printf("\t|\n\t|-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -|\n");
printf("\n");
}
printf("HELLO");
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 19
Compiler design Practical (CS-654) C020328

nstates[0][initial] = 1;
no = 1;
for(i=0;i<no;i++)
{
for(j=0;j<ip;j++)
{
for(k=0;k<n;k++)
{
temp[k] =0;
}
for(k=0;k<n;k++)
{
if(nstates[i][k])
{
for(l=0;table[k][j][l]!=-1;l++)
{
temp[table[k][j][l]] = 1;
}
}
}
for(k=0;k<no;k++)
{
f=1;
for(l=0;l<n;l++)
{
if(temp[l]!=nstates[k][l])
{
f=0;
break;
}
}
if(f) break;
}
ntable[i][j] = k;
if(k>=no)
{
for(l=0;l<n;l++)
{
nstates[k][l] = temp[l];
}
no++;
}
}
}
printf("\n\n-- -- -- -- -- -- -- -- -- -- -- TRANSITION TABLE-- -- -- -- -- -- -- -- -- -- -- -- -- ");
printf("\n\n\t states |");
for(i=0;i<ip;i++)
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 20
Compiler design Practical (CS-654) C020328

{
printf("\t %c |\t", symbols[i]);
}
printf("\n\t|-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -|\n");
for(i=0;i<no;i++)
{
if(i==0)
{
printf(" ");
print1(0,n);
}
else
{
printf(" ");
print1(i,n);
}
f=0;
for(j=0;j<noFinal;j++)
{
for(k=0;k<n;k++)
{
if(nstates[i][k] && k==final[j])
{
f=1;
break;
}
}
if(f) break;
}
if(f)
{
printf("**");
}
printf("|");
for(j=0;j<ip;j++)
{
print1(ntable[i][j], n);
printf(" ");
}
printf("\n\t|-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -|");
printf("\n");
}
return 0;
}

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 21
Compiler design Practical (CS-654) C020328

2.8. Output

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 22
Compiler design Practical (CS-654) C020328

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 23
Compiler design Practical (CS-654) C020328

2.9. Discussion
Thus for any initial state, final state & corresponding alphabet for that every transition state the
user has entered, the NFA and its conversion into equivalent DFA can be successfully
implemented.

2.10. Frequently Asked Questions

1. What does Subset Construction method refers to?
Ans. The conversion of a non-deterministic automata into a deterministic one is a process we
call subset construction or power set construction.

2. What does the production of form non-terminal -> ε is called?

Ans. The production of form non-terminal ->ε is call null production.

3. What is used to form an NFA from a regular expression?

Ans. Thompson Construction method is used to turn a regular expression in an NFA by
fragmenting the given regular expression through the operations performed on the input
alphabets.

4. Predict the number of transitions required to automate the following language using
only 3 states:
L= {w | w ends with 00}
Ans. 3

5. The finite automata is called NFA when there exists____________ for a specific input
from current state to next state. Fill in the blank.
Ans. Multiple paths

6. Under which of the operations, NFA is closed?

Ans: NFA is said to be closed under the following operations:
a) Union
b) Intersection
c) Concatenation
d) Kleene Closure

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 24
Compiler design Practical (CS-654) C020328

Practical - 3
3.1. Aim

Write a program to identify and count the single line and multiline comments in a program
taken either as input using file handling or given by the user.

3.2. Input

The inputs to the code are as follows:

1. The code from text file
2. The code in console mode

3.3. Expected Output

The program must output:

1. Table of all comments
2. Number of single-line comments
3. Number of multi-line comments

3.4. Method

The purpose of this program to accept an input code and print every multi-line and single-line
comments in the source code, as well as the total number of both types of comments. Program
comments are explanatory statements that one can include in the code. These comments help
anyone reading the source code. All programming languages allow for some form of
comments. In this program I have implemented this code for single line and multi-line
comments in C++ language.
As known , in C++ single line comment is written as // (double slash) and multi-line comment
as (/* …*/) , so this program find s the count of these only. The code can be given in two ways
either in user input form or from a text file. The program then scans the entire code for
comments. It does so by looking for the first forward slash (/), and if it finds another slash (/)
immediately after it, it counts it as a single-line remark and adds one to its count. It marks it as
a multi-line comment and increases its count by one if an asterisk (*) is discovered after a slash
(/) and then after some characters, if and only if an asterisk (*) followed by a slash (/) is found.
The output of the program is a table including all of the comments, as well as the kind of each
sort of remark and their count.

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 25
Compiler design Practical (CS-654) C020328

3.5. Algorithm

1. Start
2. Main menu opens to choose from three options.
a. Enter the code on console
b. Using notepad
c. Exit
3. If invalid option is entered go to 2
4. If option selected = c, then Exit
5. If option selected = a, then go to 7
6. If option selected = b, then go to 8
7. User input of code on console as string and go to 10
8. Open the text file mentioned in code
9. Read the contents of opened file line by line and store it in a string.
10. Convert string into char array.
11. Finding the length of the input and assign it in variable len.
12. Initialise single=0 and multi=0.
13. Scan the code i.e. is in the char array.
14. If the input character = /
II. Check next character
III. If next character=/, then go to 14.iii. else go to 14.v.
IV. Print single line comment.
V. Increment single.
VI. If current character=*, then go to 14.vi. else go to 15.
VII. Print multi line comment.
VIII. Increment multi.
15. Repeat step 14 until the entire input array is scanned.
16. Output the table showing type of comment and the corresponding comment.
17. Print the count of single and multi-line comments in the code.
18. End

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 26
Compiler design Practical (CS-654) C020328

3.6. Flowchart

3.7 Source Code:

#include<iostream>
#include<stdlib.h>
#include<fstream>
#include<string.h>
#include<ctype.h>
#include<iomanip>

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 27
Compiler design Practical (CS-654) C020328

using namespace std;

int num=0, len=0;
char inp[400];
int main()
{
start:
num=0;
len=0;
char check[30];
string input, line,str;
int choice,i,j=0,x=0;
int single=0, multi=0;
ifstream fin;
cout<<"Choose the way you want to enter the code:"<<endl;
cout<<"1. Enter the code on output screen"<<endl;;
cout<<"2. Using notepad file"<<endl;
cout<<"3. Exit"<<endl;
cout<<"Enter your option: ";
cin>>choice;
switch(choice)
{
case 1:
{
cout<<"Enter input:\n";
do
{
getline(cin,line);
input += line;
input += '\n';
}while(line != "end");
len= input.length();
for(int p=0;p<len;p++)
inp[p]=input[p];
break;
}
case 2:
{
fin.open("notepad.txt");
if(!fin.is_open()){
cout<<"\nError while opening the file\n";
exit(0);
}
getline(fin, str);
while (fin){
input += str;
getline(fin, str);
}
len = input.length();
for(int p=0;p<len;p++)
inp[p]=input[p];
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 28
Compiler design Practical (CS-654) C020328

break; }
case 3:
{
exit(0);
break; }
default:
cout<<"Enter valid option";
}
cout<<"\nS.No. |\tType of Comment\t\t|\tComment\n";
cout<<"________|_______________________________|_________________________";
while(x!=len)
{
if(inp[x]=='/')
{
x++;
if(inp[x]=='/')
{
x++;
i=0;
while(inp[x]!='\n')
{
check[i]=inp[x];
x++;
i++;
}
cout<<"\n "<<++num<<"\t|\t"<<"Single line Comment"<<"\t|\t";
single++;
for(int q=0; q<i; q++)
cout<<check[q];
}
if(inp[x]=='*')
{
cout<<"\n "<<++num<<"\t|\t"<<"Multi line Comment"<<"\t|\t";
multi++;
x++;
i=0;
while(inp[x]!='*')
{
if(inp[x]=='\n')
{
x++;
continue;
}
cout<<inp[x];
i++;
x++;
}
}
}
x++;
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 29
Compiler design Practical (CS-654) C020328

}
cout<<"\n\n";
cout<<"Number of Single line Comments: "<<single<<endl;
cout<<"Number of Multi line Comments: "<<multi<<endl<<endl<<endl;
fin.close();
goto start;
return 0;
}

3.8. Output

Using code console:

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 30
Compiler design Practical (CS-654) C020328

Using text file:

3.9. FAQS

Q1. How single line and multi-line comments are distinguished?

Ans. Single line comments starts with double slashes (//) and does not need any closing symbol,
whereas multi-line comments begin with a slash and star (/*) and it is necessary to close it with
a star and slash (*/).

Q2. How compiler treats comment lines.

Ans. The compiler treats a comment as a single white-space character.

Q3. Give an example of multi-line comment.

Ans: /* C++ comments
can also span multiple lines*/

Q4. Is it necessary to have comments for proper execution of the code?

Ans. Comments are not necessary but highly preferable.

Q5. What is a single line comment?

Ans. Comments are portions of the code ignored by the compiler which allow the user to make
simple notes in the relevant areas of the source code. Comments come either in block form or
as single lines.

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 31
Compiler design Practical (CS-654) C020328

Practical - 4
4.1. Aim
Write a program to construct a lexical analyser which scans the input code and produces the
lexemes and tokens as an output.

4.2. Input
In this program the user will type the required program and store it with .cpp extension. The
program will take the use the source code file to perform lexical analysis on it.

4.3. Expected Output

The program should identify all the tokens present in the source code and output their
respective types in the form of a table.

4.4. Method
In this experiment, a program is designed in C++ language that takes an input code and outputs.
In this practical, a lexical analyser has been implemented using C++. The primary task of the
lexical analyser is to convert the given input code into a stream of tokens. A token is nothing
but a small unit of the program which is basically made of series of characters. The tokens can
be keywords, identifiers, constant, operators, header files or punctuation symbols. The lexical
analyser does its work by scanning the whole program and splitting the whole program into
corresponding tokens. In this program, the user either inputs the code which has to be converted
into tokens via a text file or through the console. The program then scans the entire code and
stores it into a string array and then it scans character by character and matches it with the
initially specified operators, keywords or header files. Scanning the entire code, the given
program generates lexemes and classifies them into tokens. The defined token categories used
in the program are identifier, keyword, header files, operators, punctuation symbols and
constant. In C++, there are thirty four keywords.

4.5. Algorithm

2. Begin.
3. Select input method
1. Using string
2. Using file handling
4. Split string into tokens using delimiters
5. Select i token
th

1. If (token == constant), then store “constant”

2. Else If (token == string), then store “string”
3. Else if (token == operator), then store “operator”
4. Else if (token == keyword), then store “Keyword”
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 32
Compiler design Practical (CS-654) C020328

5. Else store “Identifier”

6. Print token[i] && token type.
7. End
4.6. Flowchart

4.7. Source Code:

#include<iostream>
#include<stdlib.h>
#include<fstream>
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 33
Compiler design Practical (CS-654) C020328

#include<string.h>
#include<ctype.h>
#include<iomanip>
using namespace std;
int num=0, len=0;
char inp[400];
void keyword(char check[60]){
char valid_keyword[34][12] =
{"string","auto","break","case","char","const","continue","default",
"do","double","else","enum","extern","float","for","goto",
"if","elif","int","long","register","return","short","signed",
"sizeof","static","struct","switch","typedef","union",
"unsigned","void","while","main"};
int i, key = 0;
for(i=0;i<34;i++){
if(strcmp(valid_keyword[i], check) == 0){
key=1;
break;
}
else
key=0;
}
if(key==1)
cout<<"\n "<<++num<<"\t|\t"<<check<<"\t\t|\t"<<"Keyword";
if(key==0)
cout<<"\n "<<++num<<"\t|\t"<<check<<"\t\t|\t"<<"Identifier";
}
int main()
{
start:
num=0;
len=0;
char check[30], operators[] = "+-*/%=";
string input, line,str;
int choice,i,j=0,x=0;
ifstream fin;
cout<<"Choose the way you want to enter the code:"<<endl;
cout<<"1. Enter the code on output screen"<<endl;;
cout<<"2. Using notepad file"<<endl;
cout<<"3. Exit"<<endl;
cout<<"Enter your option: ";
cin>>choice;
switch(choice)
{
case 1:
{
cout<<"Enter input:\n";
do
{
getline(cin,line);
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 34
Compiler design Practical (CS-654) C020328

input += line;
}while(line != " ");
len= input.length();
for(int p=0;p<len;p++)
inp[p]=input[p];
break;
}
case 2:
{
fin.open("code.txt");
if(!fin.is_open()){
cout<<"\nError while opening the file\n";
exit(0);
}
getline(fin, str);
while (fin){
input += str;
getline(fin, str);
}
len = input.length();
for(int p=0;p<len;p++)
inp[p]=input[p];
break; }
case 3:
{
exit(0);
break; }
default:
cout<<"Enter valid option";
}
cout<<"\nS.No. |\tLexeme\t\t|\tToken\n";
cout<<"________|_______________________|_________________________";
while(x!=len){
for(i = 0; i < 6; ++i){
if(inp[x] == operators[i])
cout<<"\n "<<++num<<"\t|\t"<<inp[x]<<"\t\t|\t"<<"Operator";
}
if(inp[x]==';')
cout<<"\n "<<++num<<"\t|\t"<<inp[x]<<"\t\t|\t"<<"Punctuation Marks";
if(inp[x]=='#'){
cout<<"\n "<<++num<<"\t| ";
while(inp[x]!='>'){
cout<<inp[x];
x++;
}
cout<<inp[x]<<"\t|\t"<<"Header file";
}
if(isdigit(inp[x])){
cout<<"\n "<<++num<<"\t|\t";
while(isdigit(inp[x])){
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 35
Compiler design Practical (CS-654) C020328

cout<<inp[x];
x++;
}
cout<<inp[x]<<"\t\t|\t"<<"Constant";
}
if(isalnum(inp[x]) || inp[x]=='_'){
check[j++] = inp[x];
}
if((inp[x]==' ' || inp[x]=='\n') && (j!=0)){
check[j] = '\0';
j=0;
keyword(check);
}
x++;
}
cout<<"\n\n";
fin.close();
goto start;
return 0;
}

4.8. Output:

Figure 4.2 code taking input from console

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 36
Compiler design Practical (CS-654) C020328

Figure 4.3 code taking input from a file

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 37
Compiler design Practical (CS-654) C020328

4.9. Discussion

This experiment teaches us how to design a lexical analyser for some hypothetical language
which tokenizes the input code given to it. The input can be a code through console window
or a file. Also various tokens for the hypothetical language are mentioned in the code of the
analyser. The program breaks each input line and matches it against the listed token, which
are: keywords, tokens, strings, constants, header files, separator. The output is a table
consisting of the lexeme and its token category.

4.10. Frequently Asked Questions

1. What is the output of lexical analysis phase?

Ans. Stream of tokens.

2. What is a token?
Ans. It is a sequence of characters that can be treated as a unit in the grammar of the
programming languages.

3. What does instance of token known as?

Ans. Lexeme.

4. The output of lexical analysis phase is further fed to which phase of compiler?
Ans. Syntax and semantic analyzer.

5. What are keywords?

Ans. Keywords are the tokens whose definition is known to the compiler.

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 38
Compiler design Practical (CS-654) C020328

Practical - 5
5.1. Aim
Write a program to implement bottom-up parsing using:

A) shift-reduce parser
B) Operator precedence parser

5.2. Shift reduce parser

5.2.1. Input
• Set of production rules
• String to be parsed

5.2.2. Expected Output

• Stack Implementation table for Bottom-up Parsing.
• Determine whether the string is parsed or not

5.2.3. Method
Basically, a program is designed which can demonstrate the process of bottom-up parsing.
Bottom-up parsing starts from the leaf nodes of a tree and works in upward direction till it
reaches the root node.
Here, we start from a sentence and then apply production rules in reverse manner in order
to reach the start symbol. The input to the code will be a grammar and input string which
has to be parsed. The output will be the stack implementation of parsing of the input string.
For every step, the table consists of the current stack, current input and the action performed
correspondingly. And then the final step will determine as to whether or not the string is
accepted by the grammar or not and the same is displayed.

5.2.4. Algorithm
1. Start
2. Store the production rules of grammar in a construct.
3. Enter the input string to be checked.
4. Calculate its length and store first element in stack.
5. Do steps 6-12 until the length of stack !=1 && stacktop == input length.
6. Print the current stack elements and current input string.
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 39
Compiler design Practical (CS-654) C020328

7. According to the action print Reduced or Shifted.

8. If reduce is possible then go to 9 else go to 5.
9. Pop the first element from stack.
10. Compare with each production rule and if matched go to 11 else go to 5.
11. Pop Matched part from stack.
12. Push LHS of that rule in stack.
13. If length(stack) == 1 then go to 14 else go to 15.
14. Print string can be parsed.
15. End

5.2.5. Flowchart

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 40
Compiler design Practical (CS-654) C020328

5.2.6. Source Code:

#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
struct grammer{
char p[20];
char prod[20];
}g[10];
int main()
{
int i,stpos,j,k,l,m,o,p,f,r;
int np,tspos,cr;
cout<<"\n--------------------------------BOTTOM UP PARSING---------------------------------";
cout<<"\nEnter total no. of productions in your grammer: ";
cin>>np;
char sc,ts[10];
cout<<"\nEnter the set of productions:\n";
for(i=0;i<np;i++)
{
cin>>ts;
strncpy(g[i].p,ts,1);
strcpy(g[i].prod,&ts[3]);
}
char ip[10];
cout<<"\nEnter input string:";
cin>>ip;
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 41
Compiler design Practical (CS-654) C020328

int lip=strlen(ip);
char stack[10];
stpos=0;
i=0;
//moving input
sc=ip[i];
stack[stpos]=sc;
i++;stpos++;
cout<<"\n\n|Stack|\t|Input|\t|Action|";
do
{
r=1;
while(r!=0)
{
cout<<"\n";
for(p=0;p<stpos;p++)
{
cout<<stack[p];
}
cout<<"\t";
for(p=i;p<lip;p++)
{
cout<<ip[p];
}
if(r==2)
{
cout<<"\tReduced";
}
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 42
Compiler design Practical (CS-654) C020328

else
{
cout<<"\tShifted";
}
r=0;
//try reducing
for(k=0;k<stpos;k++)
{
f=0;
for(l=0;l<10;l++)
{
ts[l]='\0';
}
tspos=0;
for(l=k;l<stpos;l++) //removing first char
{
ts[tspos]=stack[l];
tspos++;
}
//now compare each possibility with production
for(m=0;m<np;m++)
{
cr = strcmp(ts,g[m].prod);
//if cr is zero then match is found
if(cr==0)
{
for(l=k;l<10;l++) //removing matched part from stack
{
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 43
Compiler design Practical (CS-654) C020328

stack[l]='\0';
stpos--;
}
stpos=k;
//concatenate the string
strcat(stack,g[m].p);
stpos++;
r=2;
}
}
}
}
//moving input
sc=ip[i];
stack[stpos]=sc;
i++;stpos++;
}while(strlen(stack)!=1 && stpos!=lip);
if(strlen(stack)==1)
{
cout<<"\n \nString Accepted";
}
else
cout<<"\n \nString Rejected";
return 0;
}

5.2.7. Output:
1. Accepting a String:
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 44
Compiler design Practical (CS-654) C020328

2. Rejecting a string

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 45
Compiler design Practical (CS-654) C020328

5.2.8. Discussion
In this program a bottom-up parser is designed in which takes a grammar’s production rules
as input and a corresponding string that we want to parse through the parser. As an output,
a table is generated which displays all the steps involved in the process of parsing like the
current stack elements, remaining input and the action being performed. After the complete
parsing, it displays whether the string can be accepted or not based on the stack size.

5.2.9. Frequently Asked Questions (FAQs):

Q1. What is Shift reduce parsing?
Answer- Shift reduce parsing is a process of reducing a string to the start symbol of a
grammar. Shift reduce parsing uses a stack to hold the grammar and an input tape to hold the
string.

Q2. What is handle?

Answer- A handle of a string is a substring that matches the right side of a production, and
whose reduction to the nonterminal on the left side of the production represents one step
along the reverse of a rightmost derivation.

Q3. A grammar that produces more than one parse tree for some sentence is called?
Answer – Ambiguous grammar has more than one parse tree.

Q4. How can shift reduce parsing be implemented?

Answer- Shift reduce parsing can be implemented using a stack data structure and an input
buffer to store the input string.

Q5. Which derivation is used in Bottom-up parsing?

Answer- RMD: Right Most derivation In Reverse Order.

5.3. Operator Precedence Parser

5.3.1. Input:

1. String to check accepted or not

2. Grammar

5.3.2. Expected Output:

1. Generate handle pruning.

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 46
Compiler design Practical (CS-654) C020328

2. Stack implementation

5.3.3. Method:
5.3.3.1. Bottom-up Parsing.
This parser compresses the non-terminals where it starts and moves backward to the starting
symbol of the parse tree using grammar productions to draw the input string's parse tree.
• In this technique, parsing starts from the leaf node of the parse tree to the start
symbol of the parse tree in a bottom-up manner.
• Bottom-up parsing attempts to construct a parse tree by reducing input string and
using Right Most Derivation.
• Bottom-up parsing starts with the input symbol and constructs the parse tree up
to the start symbol using a production rule to reduce the string to get the starting
symbol.

5.3.3.2. Operator Precedence Parsing

Operator precedence parsing is a type of Shift Reduce Parsing. In operator precedence parsing,
an operator grammar and an input string are fed as input to the operator precedence parser,
which may generate a parse tree. Note that a parse tree will only be generated if the input string
gets accepted.

In operator, precedence parsing, the shift and reduce operations are done based on the priority
between the symbol at the top of the stack and the current input symbol.
Note:
• Shift operation- This operation involves moving the current symbol from the input
buffer onto the stack.
• Reduce operation- When the parser knows the right hand of the handle is at the top of
the stack, the reduce operation applies the applicable production rules, i.e., pops out
the RHS of the production rule from the stack and pushes the LHS of the production
rule onto the stack.
The operator precedence parser performs the operator precedence parsing using operator
grammar.

5.3.4. Algorithm
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 47
Compiler design Practical (CS-654) C020328

Here's the algorithm for the given code:

1. Take a stack, put the $ symbol into it, and put the input string into the input buffer with
the $ symbol at its end.
2. Check whether the given grammar is operator grammar or not. If not, convert it to
operator grammar.
3. Draw the operator precedence relation table.
4. From the operator precedence relations discussed above, we will draw a table
containing the precedence relations of all the terminals present in our grammar.
5. Parse the input string.
6. Let “a” be the symbol at the top of the stack, and “b” be the current input symbol.
7. If a ⋖ b or a ≐ b, perform the shift operation by pushing “b” onto the stack.
8. Else if a ⋗ b, perform the reduce operation by popping the symbols out from the stack
until the top of the stack symbol has lower precedence than the current input symbol.
9. Repeat step 4. If the stack and the input buffer contain only the $ symbol, then accept
the string; else, call an error-handling routine.
10. If the string is accepted, generate the parse tree.
5.3.5. Source code
#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()
{

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 48
Compiler design Practical (CS-654) C020328

string prods[10],leads[10],trails[10],nonterms[10],terms[10];
char op_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 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 Leads of "<<nonterms[i]<<" : ";
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 49
Compiler design Practical (CS-654) C020328

getline(cin,leads[i]);
cout<<"Enter Trails of "<<nonterms[i]<<" : ";
getline(cin,trails[i]);
}
cout<<"Enter the Rules (exit to stop)"<<endl;

string rule = "";

while(rule != "exit")
{
getline(cin,rule);
if(rule[0] == '1')
{
int row = getPosition(terms,rule.substr(2,1),n2);
int column = getPosition(terms,rule.substr(4,1),n2);
op_table[row][column] = '=';
}
if(rule[0] == '2')
{
int ntp = getPosition(nonterms,rule.substr(4,1),n1);
int row = getPosition(terms,rule.substr(2,1),n2);
for(int j=0;j<leads[ntp].size();j++)
{
int col = getPosition(terms,leads[ntp].substr(j,1),n2);
op_table[row][col] = '<';
}
}
if(rule[0] == '3')
{
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 50
Compiler design Practical (CS-654) C020328

int col = getPosition(terms,rule.substr(4,1),n2);

int ntp = getPosition(nonterms,rule.substr(2,1),n1);
for(int j=0;j<trails[ntp].size();j++)
{
int row = getPosition(terms,trails[ntp].substr(j,1),n2);
op_table[row][col] = '>';
}
}
}
for(int j=0;j<leads[0].size();j++)
{
int col = getPosition(terms,leads[0].substr(j,1),n2);
op_table[n2-1][col] = '<';
}
for(int j=0;j<trails[0].size();j++)
{
int row = getPosition(terms,trails[0].substr(j,1),n2);
op_table[row][n2-1] = '>';
}
cout<<endl;
cout<<"Grammar"<<endl;
for(int i=0;i<n;i++)
{
cout<<prods[i]<<endl;
}
//Display Table
for(int j=0;j<n2;j++)
cout<<"\t"<<terms[j];
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 51
Compiler design Practical (CS-654) C020328

cout<<endl;
for(int i=0;i<n2;i++)
{
cout<<terms[i]<<"\t";
for(int j=0;j<n2;j++)
{
cout<<op_table[i][j]<<"\t";
}
cout<<endl;
}
//Parsing String
char c;
do{
string ip;
deque<string> op_stack;
op_stack.push_back("$");
cout<<"Enter the string to be parsed : ";
getline(cin,ip);
ip.push_back('$');
cout<<"Stack\ti/p Buffer\tRelation\tAction"<<endl;
while(true)
{
for(int i=0;i<op_stack.size();i++)
cout<<op_stack[i];
cout<<"\t";
cout<<ip<<"\t";
int row = getPosition(terms,op_stack.back(),n2);
int column = getPosition(terms,ip.substr(0,1),n2);
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 52
Compiler design Practical (CS-654) C020328

if(op_table[row][column] == '<')
{
op_stack.push_back("<");
op_stack.push_back(ip.substr(0,1));
ip = ip.substr(1);
cout<<"\t"<<"<\t\tPush";
}
else if(op_table[row][column] == '=')
{
op_stack.push_back("=");
op_stack.push_back(ip.substr(0,1));
ip = ip.substr(1);
cout<<"\t"<<"=\t\tPush";
}
else if(op_table[row][column] == '>')
{
string last;
do
{
op_stack.pop_back();
last = op_stack.back();
op_stack.pop_back();
}while(last != "<");
cout<<"\t"<<">\t\tPop";
}
else
{
if(ip[0] == '$' && op_stack.back() == "$")
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 53
Compiler design Practical (CS-654) C020328

{
cout<<"\t\t\tAccept\nString Parsed."<<endl;
break;
}
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;
}

5.3.6. Output

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 54
Compiler design Practical (CS-654) C020328

Figure: Taking input from user

Figure: Output for user

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 55
Compiler design Practical (CS-654) C020328

5.3.7. Frequently Asked Questions (FAQs):

Q1. What is operator precedence parsing?

Ans: Operator precedence parsing is a type of shift-reduce parsing. In operator precedence
parsing, an operator grammar and an input string are fed as input to the operator precedence
parser, which may generate a parse tree.

Q2. What are the three operator precedence relations?

Ans: The three operator precedence relations are ⋗ , ⋖ and ≐.

Q3. How is the parsing precedence relation define?

Ans: A directed edge that connects the earlier event to the subsequent one represents each
precedence relation. For every pair of non-terminals in the operator precedence parsing,
precedence relations are defined. No production has two adjacent non-terminals, and no
production has operator precedence parsers on its right side.

Q4. Which binary operators have same precedence in parsing?

Ans: There are three operator precedence relations. The relation a < b means that a has lower
precedence than b. Similarly, a > b means that a has higher precedence than b. And the
relations a = b, here a "has equal precedence as" b. So, = have the same precedence in parsing

Q5. What are the precedence of operators?

Ans: The "tightness" with which an operator binds two phrases depends on its precedence. The
priority given to each operator in an expression is known as the "precedence of the operators. "For
instance, the addition operator ("+") has a lower precedence than the multiplication operator ("*").
Logical not has the highest precedence.

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 56
Compiler design Practical (CS-654) C020328

Practical – 6
6.1. Aim

Write a program to SLR parser.

6.2. Input

• Set of non-terminals
• Set of terminals
• Set of production rules

6.3. Expected Output

• Item sets generated

• Table representing Shift and Accept actions
• Table representing Reduce actions

6.4. Method

This practical aims at constructing an SLR parser. Simple LR parser is one of the three types
of bottom-up parsers. The first L in LR refers to scanning the tokens from left to right and R
defines the use of rightmost derivation in reverse. In this practical, I constructed an SLR
parser using C++ programming language. For this we first need to find the canonical item
sets for the entered context-free grammar.

Next in SLR parsing table has two parts i.e. one is ACTION and other is GoTO An Action
table that gives a grammar rule to apply, given the current state and the current terminal
symbol in the input stream; a Goto table that prescribes to which new state it should move.
After that decision is taken which action mong SHIFT REDUCE and ACCEPT has to be

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 57
Compiler design Practical (CS-654) C020328

taken based upon the canonical item sets formed. The program outputs the parsing table with
the corresponding actions taken.

6.5. Algorithm

1. Begin

2. Call get_prods function to get user input of set of terminals, non-terminals and

production rules.

3. Create augmented grammar using add_dots function.

4. Initialise the goto_table

5. Calculate closure for the first itemset I0.

6. Print I0.

7. Compute goto on I0 and generate subsequent itemsets.

8. Compute first and follow.

9. Create Shift table using goto_table.

10. Find production rules which can be reduced.

11. Compute reduce table by computing follow of all terminals in left hand side of

productions in 10.

12. Print Reduce table.

13. End

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 58
Compiler design Practical (CS-654) C020328

6.6. Flowchart

6.7. Source Code:

#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
using namespace std;
char terminals[100]={};int no_t;
char non_terminals[100]={};int no_nt;
char goto_table[100][100];
char reduce[20][20];
char follow[20][20];char fo_co[20][20];
char first[20][20];
struct state{
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 59
Compiler design Practical (CS-654) C020328

int prod_count;
char prod[100][100]={{}};
};
void add_dots(struct state *I)//augumented grammar
{
for(int i=0;i<I->prod_count;i++){
for (int j=99;j>3;j--)
I->prod[i][j] = I->prod[i][j-1];
I->prod[i][3]='.';
}
}
void augument(struct state *S,struct state *I){
if(I->prod[0][0]=='S')
strcpy(S->prod[0],"Z->.S");
else{
strcpy(S->prod[0],"S->.");
S->prod[0][4]=I->prod[0][0];}
S->prod_count++;
}
void get_prods(struct state *I)//user input
{
cout<<"SLR PARSING TABLE"<<endl;
cout<<endl<<"Directions: \n 1. Terminals must be single lettered. \n 2. Each production rule must
contain only 1 rule.\n 3. The format of the prodcution rule is: S->ABc"<<endl;
cout<<endl<<"Enter total no. of productions: ";
cin>>I->prod_count;
cout<<endl<<"Enter no. of non terminals: ";
cin>>no_nt;
cout<<endl<<"Enter non terminals: ";
for(int i=0;i<no_nt;i++)
cin>>non_terminals[i];
cout<<endl<<"Enter no. of terminals: ";
cin>>no_t;
cout<<endl<<"Enter terminals: ";
for(int i=0;i<no_t;i++)
cin>>terminals[i];
cout<<endl<<"Enter the production rules: ";
for(int i=0;i<I->prod_count;i++){
cin>>I->prod[i];
cout<<endl;
}
}
bool is_non_terminal(char a){
if (a >= 'A' && a <= 'Z')
return true;
else
return false;
}
bool in_state(struct state *I,char *a){
for(int i=0;i<I->prod_count;i++){
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 60
Compiler design Practical (CS-654) C020328

if(!strcmp(I->prod[i],a))
return true;
}
return false;
}
char char_after_dot(char a[100]){
char b;
for(int i=0;i<strlen(a);i++)
if(a[i]=='.'){
b=a[i+1];
return b;}
}
char* move_dot(char b[100],int len){
char a[100]={};
strcpy(a,b);
for(int i=0;i<len;i++){
if(a[i]=='.'){
swap(a[i],a[i+1]);
break;
}
}
return &a[0];
}
bool same_state(struct state *I0,struct state *I){
if (I0->prod_count != I->prod_count)
return false;
for (int i=0; i<I0->prod_count; i++)
{
int flag = 0;
for (int j=0; j<I->prod_count; j++)
if (strcmp(I0->prod[i], I->prod[j]) == 0)
flag = 1;
if (flag == 0)
return false;
}
return true;
}
void closure(struct state *I,struct state *I0){
char a={};
for(int i=0;i<I0->prod_count;i++){
a=char_after_dot(I0->prod[i]);
if(is_non_terminal(a)){
for(int j=0;j<I->prod_count;j++){
if(I->prod[j][0]==a){
if(!in_state(I0,I->prod[j])){
strcpy(I0->prod[I0->prod_count],I->prod[j]);
I0->prod_count++;
}
}
}
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 61
Compiler design Practical (CS-654) C020328

}
}
}
void goto_state(struct state *I,struct state *S,char a){
int time=1;
for(int i=0;i<I->prod_count;i++){
if(char_after_dot(I->prod[i])==a){
if(time==1){
time++;
}
strcpy(S->prod[S->prod_count],move_dot(I->prod[i],strlen(I->prod[i])));
S->prod_count++;
}
}
}
void print_prods(struct state *I){
for(int i=0;i<I->prod_count;i++)
printf("%s\n",I->prod[i]);
cout<<endl;
}
bool in_array(char a[20],char b){
for(int i=0;i<strlen(a);i++)
if(a[i]==b)
return true;
return false;
}
char* chars_after_dots(struct state *I){
char a[20]={};
for(int i=0;i<I->prod_count;i++){
if(!in_array(a,char_after_dot(I->prod[i]))){
a[strlen(a)]=char_after_dot(I->prod[i]);
}
}
return &a[0];
}
void cleanup_prods(struct state * I){
char a[100]={};
for(int i=0;i<I->prod_count;i++)
strcpy(I->prod[i],a);
I->prod_count=0;
}
int return_index(char a){
for(int i=0;i<no_t;i++)
if(terminals[i]==a)
return i;
for(int i=0;i<no_nt;i++)
if(non_terminals[i]==a)
return no_t+i;
}
void print_shift_table(int state_count){
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 62
Compiler design Practical (CS-654) C020328

cout<<endl<<"SHIFT ACTIONS"<<endl<<endl;
cout<<"\t";
for(int i=0;i<no_t;i++)
cout<<terminals[i]<<"\t";
for(int i=0;i<no_nt;i++)
cout<<non_terminals[i]<<"\t";
cout<<endl;
for(int i=0;i<state_count;i++){
int arr[no_nt+no_t]={-1};
for(int j=0;j<state_count;j++){
if(goto_table[i][j]!='~'){
arr[return_index(goto_table[i][j])]= j;
}
}
cout<<"I"<<i<<"\t";
for(int j=0;j<no_nt+no_t;j++){
if(i==1&&j==no_t-1)
cout<<"ACC"<<"\t";
if(arr[j]==-1||arr[j]==0)
cout<<"\t";
else{
if(j<no_t)
cout<<"S"<<arr[j]<<"\t";
else
cout<<arr[j]<<"\t";
}
}
cout<<"\n";
}
}
int get_index(char c,char *a){
for(int i=0;i<strlen(a);i++)
if(a[i]==c)
return i;
}
void add_dot_at_end(struct state* I){
for(int i=0;i<I->prod_count;i++){
strcat(I->prod[i],".");
}
}
void add_to_first(int n,char b){
for(int i=0;i<strlen(first[n]);i++)
if(first[n][i]==b)
return;
first[n][strlen(first[n])]=b;
}
void add_to_first(int m,int n){
for(int i=0;i<strlen(first[n]);i++){
int flag=0;
for(int j=0;j<strlen(first[m]);j++){
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 63
Compiler design Practical (CS-654) C020328

if(first[n][i]==first[m][j])
flag=1;
}
if(flag==0)
add_to_first(m,first[n][i]);
}
}
void add_to_follow(int n,char b){
for(int i=0;i<strlen(follow[n]);i++)
if(follow[n][i]==b)
return;
follow[n][strlen(follow[n])]=b;
}
void add_to_follow(int m,int n){
for(int i=0;i<strlen(follow[n]);i++){
int flag=0;
for(int j=0;j<strlen(follow[m]);j++){
if(follow[n][i]==follow[m][j])
flag=1;
}
if(flag==0)
add_to_follow(m,follow[n][i]);
}
}
void add_to_follow_first(int m,int n){
for(int i=0;i<strlen(first[n]);i++){
int flag=0;
for(int j=0;j<strlen(follow[m]);j++){
if(first[n][i]==follow[m][j])
flag=1;
}
if(flag==0)
add_to_follow(m,first[n][i]);
}
}
void find_first(struct state *I){
for(int i=0;i<no_nt;i++){
for(int j=0;j<I->prod_count;j++){
if(I->prod[j][0]==non_terminals[i]){
if(!is_non_terminal(I->prod[j][3])){
add_to_first(i,I->prod[j][3]);
}
}
}
}
}
void find_follow(struct state *I){
for(int i=0;i<no_nt;i++){
for(int j=0;j<I->prod_count;j++){
for(int k=3;k<strlen(I->prod[j]);k++){
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 64
Compiler design Practical (CS-654) C020328

if(I->prod[j][k]==non_terminals[i]){
if(I->prod[j][k+1]!='\0'){
if(!is_non_terminal(I->prod[j][k+1])){
add_to_follow(i,I->prod[j][k+1]);
}
}
}
}
}
}
}
int get_index(int *arr,int n){
for(int i=0;i<no_t;i++){
if(arr[i]==n)
return i;
}
return -1;
}
void print_reduce_table(int state_count,int *no_re,struct state *temp1){
cout<<"REDUCE ACTIONS"<<endl<<endl;
cout<<"\t";
int arr[temp1->prod_count][no_t]={-1};
for(int i=0;i<no_t;i++){
cout<<terminals[i]<<"\t";
}
cout<<endl;
for(int i=0;i<temp1->prod_count;i++){
int n=no_re[i];
for(int j=0;j<strlen(follow[return_index(temp1->prod[i][0])-no_t]);j++){
for(int k=0;k<no_t;k++){
if(follow[return_index(temp1->prod[i][0])-no_t][j]==terminals[k])
arr[i][k]=i+1;
}
}
cout<<"I"<<n<<"\t";
for(int j=0;j<no_t;j++){
if(arr[i][j]!=-1&&arr[i][j]!=0&&arr[i][j]<state_count)
cout<<"R"<<arr[i][j]<<"\t";
else
cout<<"\t";
}
cout<<endl;
}
}
int main(){
struct state init;
struct state temp;struct state temp1;
int state_count=1;
get_prods(&init);
temp=init;
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 65
Compiler design Practical (CS-654) C020328

temp1=temp;
add_dots(&init);
for(int i=0;i<100;i++)
for(int j=0;j<100;j++)
goto_table[i][j]='~';
struct state I[50];
augument(&I[0],&init);
closure(&init,&I[0]);
cout<<"\nI0:\n";
print_prods(&I[0]);
char characters[20]={};
for(int i=0;i<state_count;i++){
char characters[20]={};
for(int z=0;z<I[i].prod_count;z++)
if(!in_array(characters,char_after_dot(I[i].prod[z])))
characters[strlen(characters)]=char_after_dot(I[i].prod[z]);
for(int j=0;j<strlen(characters);j++){
goto_state(&I[i],&I[state_count],characters[j]);
closure(&init,&I[state_count]);
int flag=0;
for(int k=0;k<state_count-1;k++){
if(same_state(&I[k],&I[state_count])){
cleanup_prods(&I[state_count]);flag=1;
cout<<"I"<<i<<" on reading the symbol "<<characters[j]<<" goes to I"<<k<<".\n";
goto_table[i][k]=characters[j];;
break;
}
}
if(flag==0){
state_count++;
cout<<"I"<<i<<" on reading the symbol "<<characters[j]<<" goes to I"<<state_count-1<<":\n";
goto_table[i][state_count-1]=characters[j];
print_prods(&I[state_count-1]);
}
}
}
int no_re[temp.prod_count]={-1};
terminals[no_t]='$';no_t++;
add_dot_at_end(&temp1);
for(int i=0;i<state_count;i++){
for(int j=0;j<I[i].prod_count;j++)
for(int k=0;k<temp1.prod_count;k++)
if(in_state(&I[i],temp1.prod[k]))
no_re[k]=i;
}
find_first(&temp);
for(int l=0;l<no_nt;l++){
for(int i=0;i<temp.prod_count;i++){
if(is_non_terminal(temp.prod[i][3])){
add_to_first(return_index(temp.prod[i][0])-
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 66
Compiler design Practical (CS-654) C020328

no_t,return_index(temp.prod[i][3])-no_t);
}
}}
find_follow(&temp);
add_to_follow(0,'$');
for(int l=0;l<no_nt;l++){
for(int i=0;i<temp.prod_count;i++){
for(int k=3;k<strlen(temp.prod[i]);k++){
if(temp.prod[i][k]==non_terminals[l]){
if(is_non_terminal(temp.prod[i][k+1])){
add_to_follow_first(l,return_index(temp.prod[i][k+1])-no_t);}
if(temp.prod[i][k+1]=='\0')
add_to_follow(l,return_index(temp.prod[i][0])-no_t);
}
}
}
}
print_shift_table(state_count);
cout<<endl<<endl;
print_reduce_table(state_count,&no_re[0],&temp1);
cout<<"The above two tables combined generate the SLR Parsing Table \n";
cout<<"*For error entries->cells where both shift and reduce actions are present";
}

6.8. Output:

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 67
Compiler design Practical (CS-654) C020328

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 68
Compiler design Practical (CS-654) C020328

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 69
Compiler design Practical (CS-654) C020328

6.9. Discussion

In this program we learnt one of the form of bottom up parsers. This is known as simple LR
parser. After learning the way of constructing SLR parser we implemented it in C++
programming language. For this we first need to find the canonical item sets for the entered
context free grammar. Next in SLR parsing table has two parts ie.e one is ACTION and other
is GoTO An Action table that gives a grammar rule to apply, given the current state and the
current terminal symbol in the input stream; a Goto table that prescribes to which new state it
should move. After that decision is taken which action mong SHIFT REDUCE and ACCEPT
has to be taken based upon the canonical itemsets formed. And finally the program outputs
the parsing table with the corresponding actions taken.

Frequently Asked Questions (FAQs):

Q1. Write three types of LR parsers?
Answer- SLR parser , CLR parser and LALR parser

Q2. Which string derivation is used in SLR parser?

Answer- RMD

Q3. What is an augmented grammar?

Answer Augmented grammar is the grammar having the augmented production rule, which
is of the form S’-> S. Where S is the start symbol of original grammar G. Ambiguous
grammar has more than one parse tree.

Q4. What SHIFT/REDUCE conflict?

Answer- When reduce actions are added to ACTION table, it can happen that the same cell is
fit with reduce action and a shift action. This situation is known as SHIFT/REDUCE conflict.

Q5. Is SLR grammar ambiguous?

Answer- Every SLR grammar is unambiguous but there are many unambiguous grammars
that are not SLR

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 70
Compiler design Practical (CS-654) C020328

Practical – 7
7.1. Aim

Write a program to CLR parser.

7.2. Input

• Set of non-terminals
• Set of terminals
• Set of production rules

7.3. Expected Output

• The augmented grammar of the original grammar with all the canonical collection of
LR(1) items and then the CLR parsing table.

7.4. Method

This program implements a CLR parser. CLR stand for canonical LR parser. It is also called
LR(1) parser. A CLR parser is similar to LR(0) parser, the only difference being that items of
an itemset contains a follow as well. CLR parser generates more number of states as compared
to SLR parser. CLR parser works in the following way :
a) Make augmented grammar
b) Create itemsets
c) Generate CLR parsing table
In our program, production rules(such that only one rule is present), terminals and non-
terminals are set of inputs given by user. Output is the parsing table with SHIFT, REDUCE,
ERROR and ACCEPT actions, and it shows the stack implementation with the result that
whether string is accepted by parser or not.

7.5. Algorithm

1. User enters the production rules of the grammar.

2. Firstly, calculate the FIRST and FOLLOW of all non-terminals.

3. The next step is to write the augmented grammar of the given grammar.

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 71
Compiler design Practical (CS-654) C020328

4. Now find the collection of LR(1) items using the closure and the goto.

5. To find the first item set find the closure of the first production rule of the augmented
grammar.

6. Repeat until all the itemset are reduced.

7. Check the dot symbol in each production rule and apply goto to the next symbol after it.

8. There is also a look ahead symbol which have to be taken cared of after the comma.

9. The rules which are derived from any other rule, there look ahead symbol depends on the
previous rule

and is calculated with the help of FIRST(c,terminal) where c can be a terminal or a non terminal
in the rule

A.Bc,terminal.

10. Now another itemset will be formed from this closure.

11. If the itemset formed has the dot after all the symbols ,then that itemset is reduced. Else
follow the same

steps to find another itemset.

12. Now construct a table with the following details-

• Itemset number which is in the Stack

• Action which consists of all the terminals,and

• Goto which consists of all the non-terminals.

13. Now construct the CLR parsing table which consists of the shift and the reduce operations.

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 72
Compiler design Practical (CS-654) C020328

6.6. Flowchart

7.7. Source Code:

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

char prod[100][100], term[100], non_term[100], action[100][100][100];

int term_len, non_term_len, first[100][100], follow[100][100], hash1[100], no_of_prod, hash2[100],
canonical[100][20][10][10], can_len, go_to[100][100], clr;

void calc_first(int k)
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 73
Compiler design Practical (CS-654) C020328

{
int j, flag = 0, len, l, m, i;
if (hash1[k])
return;
hash1[k] = 1;
for (i = 0; i < no_of_prod; i++)
{
if (prod[i][0] == non_term[k])
{
flag = 0;
len = strlen(prod[i]);
for (j = 3; j < len; j++)
{
if (!flag)
{
if (prod[i][j] >= 'A' && prod[i][j] <= 'Z')
{
for (l = 0; l < non_term_len; l++)
{
if (non_term[l] == prod[i][j])
break;
}
flag = 1;
if (hash1[l])
{
for (m = 0; m < term_len; m++)
{
if (first[l][m])
{
first[k][m] = 1;
if (term[m] == '^')
flag = 0;
}
}
}
else
{
calc_first(l);
for (m = 0; m < term_len; m++)
{
if (first[l][m])
{
first[k][m] = 1;
if (term[m] == '^')
flag = 0;
}
}
}
}
else if (prod[i][j] != '|')
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 74
Compiler design Practical (CS-654) C020328

{
for (l = 0; l < term_len; l++)
{
if (term[l] == prod[i][j])
break;
}
first[k][l] = 1;
flag = 1;
}
}
else
{
if (prod[i][j] == '|')
flag = 0;
}
}
}
}
}
void print(int in)
{
int i, j, len, k, l, prnt;
printf("I%d:\n", in);
for (i = 0; i < 10; i++)
{
prnt = 0;
for (k = 0; k < term_len; k++)
{
if (canonical[in][no_of_prod - 1][i][k])
{
if (!prnt)
{
len = strlen(prod[no_of_prod - 1]);
for (j = 0; j <= len; j++)
{
if (j == i)
printf(".");
printf("%c", prod[no_of_prod - 1][j]);
}
printf(",%c", term[k]);
prnt = 1;
}
else
printf("|%c", term[k]);
}
}
if (prnt)
puts("");
}
for (l = 0; l < no_of_prod - 1; l++)
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 75
Compiler design Practical (CS-654) C020328

{
for (i = 0; i < 10; i++)
{
prnt = 0;
for (k = 0; k < term_len; k++)
{
if (canonical[in][l][i][k])
{
if (!prnt)
{
len = strlen(prod[l]);
for (j = 0; j <= len; j++)
{
if (j == i)
printf(".");
printf("%c", prod[l][j]);
}
printf(",%c", term[k]);
prnt = 1;
}
else
printf("|%c", term[k]);
}
}
if (prnt)
puts("");
}
}
}
void Frst(char *str, int *arr)
{
int j, flag = 0, len, l, m, i, k;
len = strlen(str);
for (j = 0; j < len; j++)
{
if (!flag)
{
if (str[j] >= 'A' && str[j] <= 'Z')
{
for (l = 0; l < non_term_len; l++)
{
if (non_term[l] == str[j])
break;
}
flag = 1;
for (m = 0; m < term_len; m++)
{
if (first[l][m])
{
arr[m] = 1;
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 76
Compiler design Practical (CS-654) C020328

if (term[m] == '^')
flag = 0;
}
}
}
else if (str[j] != '|')
{
for (l = 0; l < term_len; l++)
{
if (term[l] == str[j])
break;
}
arr[l] = 1;
flag = 1;
}
}
else
break;
}
}
void closure(int arr[][10][10])
{
int i, j, flag = 1, k, l, m, arr1[10], n;
char c, str[100];
while (flag)
{
flag = 0;
for (i = 0; i < no_of_prod; i++)
{
for (k = 0; k < 10; k++)
{
for (n = 0; n < 10; n++)
{
if (arr[i][k][n])
{
c = prod[i][k];
for (j = 0; j < no_of_prod; j++)
{
if (prod[j][0] == c)
{
for (m = 0; m < 10; m++)
arr1[m] = 0;
for (m = k + 1; prod[i][m] != '\0'; m++)
{
str[m - k - 1] = prod[i][m];
}
str[m - k - 1] = term[n];
str[m - k] = '\0';
Frst(str, arr1);
for (m = 0; m < term_len; m++)
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 77
Compiler design Practical (CS-654) C020328

{
if (arr1[m] && !arr[j][3][m])
{
flag = 1;
arr[j][3][m] = 1;
}
}
}
}
}
}
}
}
}
}
int Goto(int in, int sym, int nt)
{
int j, ans = 0, arr[100][10][10] = {0}, flg = 0, k, l, len, i, m;
char c;
for (i = 0; i < no_of_prod; i++)
{
for (j = 0; j < 10; j++)
{
for (k = 0; k < term_len; k++)
{
if (canonical[in][i][j][k])
{
if (nt)
{
if (prod[i][j] == non_term[sym])
{
arr[i][j + 1][k] = 1;
flg = 1;
}
}
else if (prod[i][j] == term[sym])
{
arr[i][j + 1][k] = 1;
flg = 1;
}
}
}
}
}
if (!flg)
return 0;
closure(arr);
for (j = 0; j < can_len; j++)
{
flg = 0;
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 78
Compiler design Practical (CS-654) C020328

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

{
for (l = 0; l < 10; l++)
{
for (i = 0; i < term_len; i++)
{
if (canonical[j][k][l][i] != arr[k][l][i])
{
flg = 1;
break;
}
}
if (flg)
break;
}
if (flg)
break;
}
if (!flg)
{
ans = j;
break;
}
}
if (flg)
{
for (j = 0; j < no_of_prod; j++)
{
for (l = 0; l < 10; l++)
{
for (i = 0; i < term_len; i++)
canonical[can_len][j][l][i] = arr[j][l][i];
}
}
ans = can_len;
can_len++;
}
if (nt)
go_to[in][sym] = ans;
else
{
if (action[in][sym][0] == '\0')
sprintf(action[in][sym], "s%d\0", ans);
else
{
sscanf(action[in][sym], "s%d", &k);
if (k != ans)
{
clr = 0;
len = strlen(action[in][sym]);
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 79
Compiler design Practical (CS-654) C020328

sprintf(action[in][sym] + len, ",s%d", ans);

}
}
}
if (flg)
{
for (i = 0; i < no_of_prod; i++)
{
len = strlen(prod[i]);
for (j = 0; j < 10; j++)
{
for (l = 0; l < term_len; l++)
{
if (arr[i][j][l] && j == len)
{
if (i == no_of_prod - 1)
sprintf(action[can_len - 1][term_len - 1], "acc\0");
else
{
if (action[can_len - 1][l][0] == '\0')
sprintf(action[can_len - 1][l], "r%d\0", i + 1);
else
{
sscanf(action[can_len - 1][l], "r%d", &k);
if (k != i + 1)
{
clr = 0;
len = strlen(action[can_len - 1][l]);
sprintf(action[can_len - 1][l] + len, "r%d\0", i + 1);
}
}
}
}
}
}
}
}
return flg;
}
int main()
{
int i, j, len, k, a, b, t, flag;
char c, temp[100];
clr = 1;
can_len = 0;
term_len = non_term_len = 0;
printf("Enter the number of productions: ");
scanf("%d", &no_of_prod);
printf("Enter the production rules in the form (A->string) (^ for null)\n");
for (i = 0; i < no_of_prod; i++)
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 80
Compiler design Practical (CS-654) C020328

{
scanf("%s", &prod[i]);
len = strlen(prod[i]);
for (j = 0; j < len; j++)
{
if (prod[i][j] >= 'A' && prod[i][j] <= 'Z')
{
for (k = 0; k < non_term_len; k++)
{
if (non_term[k] == prod[i][j])
break;
}
if (k == non_term_len)
{
non_term[non_term_len] = prod[i][j];
non_term_len++;
}
}
else if (prod[i][j] != '-' && prod[i][j] != '>' && prod[i][j] != '|')
{
for (k = 0; k < term_len; k++)
{
if (term[k] == prod[i][j])
break;
}
if (k == term_len)
{
term[term_len] = prod[i][j];
term_len++;
}
}
}
}
printf("\nNon terminals are:\n");
printf("%c", non_term[0]);
for (i = 1; i < non_term_len; i++)
{
printf(",%c", non_term[i]);
}
puts("");
printf("\nTerminals are:\n");
printf("%c", term[0]);
for (i = 1; i < term_len; i++)
{
printf(",%c", term[i]);
}
puts("");
printf("\nFirst\n");
for (i = 0; i < non_term_len; i++)
{
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 81
Compiler design Practical (CS-654) C020328

calc_first(i);
printf("%c = { ", non_term[i]);
for (j = 0; j < term_len; j++)
{
if (first[i][j])
break;
}
if (j < term_len)
{
printf("%c", term[j]);
j++;
for (; j < term_len; j++)
{
if (first[i][j])
printf(" ,%c", term[j]);
}
}
printf(" }\n");
}
term[term_len] = '$';
term_len++;
for (i = 0; i < 100; i++)
{
for (j = 0; j < 100; j++)
{
sprintf(action[i][j], "\0");
go_to[i][j] = -1;
}
}
sprintf(prod[no_of_prod], "X->%c\0", prod[0][0]); // Added new initial symbol...
no_of_prod++;
puts("\nCanonical LR(1) collection of sets for grammar");
canonical[0][no_of_prod - 1][3][term_len - 1] = 1;
closure(canonical[0]);
can_len++;
puts("");
print(0);
flag = 1;
while (flag)
{
flag = 0;
for (i = 0; i < can_len; i++)
{
for (j = 0; j < non_term_len; j++)
{
if (Goto(i, j, 1))
{
printf("\nGOTO(I%d, %c) ", i, non_term[j]);
print(can_len - 1);
flag = 1;
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 82
Compiler design Practical (CS-654) C020328

}
}
for (j = 0; j < term_len - 1; j++)
{
if (Goto(i, j, 0))
{
printf("\nGOTO(I%d, %c) ", i, term[j]);
print(can_len - 1);
flag = 1;
}
}
}
}
if (clr)
{
printf("\nCLR Parsing Table\n\n");
printf("State\t|\t\tAction");
for (i = 0; i < term_len - 2; i++)
printf("\t");
printf("|\tGoTo\n");
printf("------------------------------------------------\n\t|");
for (i = 0; i < term_len; i++)
{
printf("%c\t", term[i]);
}
printf("|");
for (i = 0; i < non_term_len; i++)
{
printf("%c\t", non_term[i]);
}
puts("\n------------------------------------------------");
for (i = 0; i < can_len; i++)
{
printf("%d\t|", i);
for (j = 0; j < term_len; j++)
{
printf("%s\t", action[i][j]);
}
printf("|");
for (j = 0; j < non_term_len; j++)
{
if (go_to[i][j] != -1)
printf("%d", go_to[i][j]);
printf("\t");
}
puts("");
}
puts("\nThe Grammar is CLR(1)");
}
else
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 83
Compiler design Practical (CS-654) C020328

{
puts("\nThe Grammar is not CLR(1)");
}
return 0;
}

7.8. Output:

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 84
Compiler design Practical (CS-654) C020328

Frequently Asked Questions (FAQs):

Q1. How many Look-ahead symbols are used by CLR Parser?
Answer- It is an LR(k) parser for k=1, i.e. with a single lookahead terminal.

Q2. What are the different components of CLR parsing table?

Answer- The CLR parsing table consists of two parts the Action table and the Goto table.
The Action table contains all terminals of the grammar and the symbol $. The Goto table
contains all the non-terminals of the grammar.

Q3. What is the function of GOTO?

Answer- The GOTO function measures the transitions from one state to another and it is
calculated for each of LR(1) items in each state.

Q4. Which is the most powerful parser among SLR, CLR and LALR?
Answer- CLR parser.

Q5. Define validity

Answer- The notion of validity changes. An item [A → β1 • β2, a] is valid for a viable prefix
α β1 if there is a rightmost derivation that yields α A a w which in one step yields α β1β2 a w.

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 85
Compiler design Practical (CS-654) C020328

Practical – 8
8.1. Aim

Write a program to implement LALR parser.

8.2. Input

Production rules of the grammar

8.3. Expected Output

The augmented grammar of the original grammar with all the canonical collection of LALR
(1) items and then the LALR parsing table.

8.4. Method

This program implements a LALR parser. LALR stand for lookahead LR parser. A LALR
parser is similar to CLR parser, we use the canonical collection of CLR parser, the only
difference being that if two states differ only in lookahead, then these two states are combined
together in LALR parser.
In our program, set of production rules(such that only one rule is present) is the input, Output
is the parsing table with SHIFT, REDUCE, ERROR and ACCEPT actions, and it shows the
stack implementation with the result that whether string is accepted by parser or not.

8.5. Algorithm

1. User enters the production rules of the grammar.

2. Firstly, calculate the FIRST and FOLLOW of all non-terminals.

3. The next step is to write the augmented grammar of the given grammar.

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 86
Compiler design Practical (CS-654) C020328

4. Now find the collection of LR(1) items using the closure and the goto.

5. To find the first item set find the closure of the first production rule of the augmented
grammar.

6. Repeat until all the itemset are reduced.

7. Check the dot symbol in each production rule and apply goto to the next symbol after it.

8. There is also a look ahead symbol which have to be taken cared of after the comma.

9. The rules which are derived from any other rule, there look ahead symbol depends on the
previous rule

and is calculated with the help of FIRST(c,terminal) where c can be a terminal or a non terminal
in the rule

A.Bc,terminal.

10. Now find the closure of the next symbol after the dot.

11. Now another itemset will be formed from this closure.

12. If the itemset formed has the dot after all the symbols ,then that itemset is reduced. Else
follow the same

steps to find another itemset.

13. Now the itemsets which are common on the LHS side but different on the RHS side, make
them a single

itemset.

14. After performing the previous step, LR(1) items are converted into LALR(1) items.

15. Now construct the LALR parsing table which consists of the shift and the reduce operations.
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 87
Compiler design Practical (CS-654) C020328

8.6. Flowchart

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 88
Compiler design Practical (CS-654) C020328

8.7. Source Code:

/*LALR PARSER
E->E+T
E->T
T->T*F
T->F
F->(E)
F->i */
#include <stdio.h>
#include <conio.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"},
{"emp", "emp", "k"},
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 89
Compiler design Practical (CS-654) C020328

{"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"},
};
int 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 string :");
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++;
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 90
Compiler design Practical (CS-654) C020328

}
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 Input string is accepted\n ");
printf(" \n Grammar is LALR(1)\n ");
}
else
printf(" \n do not accept the input ");
getch();
}
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)
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 91
Compiler design Practical (CS-654) C020328

{
int k, l;
k = ister(x);
l = isstate(p);
strcpy(temp, A[l - 1].row[k - 1]);
}
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;
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 92
Compiler design Practical (CS-654) C020328

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++)
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;
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 93
Compiler design Practical (CS-654) C020328

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

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 94
Compiler design Practical (CS-654) C020328

8.8. Output:

8.9. Frequently Asked Questions (FAQs):

Q1. What is LALR parser?
Answer- LALR parser or look ahead LR parser is a simplified version of a canonical LR
parser, to parse a text according to a set of production rules specified by a formal grammar for
a computer language.

Q2. How LALR parser is different from CLR parser?

Answer- For LALR parsing we use the canonical collection of CLR parser, the only difference
being that if two states differ only in lookahead, then these two states are combined together in
LALR parser.

Q3. What is the similarity between LR, LALR and SLR?

Answer They use the same algorithm but have different parsing tables.

Q4. What are the two functions used in creating canonical collection of items in LR
parsers?
Answer- GOTO() and CLOSURE().

Q5. Elaborate ERROR action of parser

Answer- This action is taken when parser is unable to decide what it should do. It can neither
shift, reduce nor accept.

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 95
Compiler design Practical (CS-654) C020328

Practical – 9
9.1. Aim
Write a program to implement top-down parser (LL(1)).

9.2. Input
Production rules of the grammar
String

9.3. Expected Output

1. Bottom-up Parsing table

2. String is parsed or not

9.4. Method
Bottom-up parsing begins at a tree's leaf nodes and moves up the tree until it reaches the root
node. Here, we begin with a sentence and use production rules backwards to get to the start
symbol.
LR(1) – LR Parser:
o Works on complete set of LR(1) Grammar
o Generates large table and large number of states
o Slow construction

9.5. Algorithm

1.Begin
2.Store the production rules of grammar.
3.Input the string to be parsed.
4.Calculate its length and store first element in stack.
5.Do steps 6-12 while the length of stack !=1 && stacktop == input
length.
6. Print the current stack elements and current input string.
7. According to the action print Reduced or Shifted.
8. If reduce is possible then goto 9 else goto 5
9. Pop first element from stack.
10. Compare with each production rule and if matched goto 11 else goto 5
11. Pop matched part from stack.
12. Push LHS of that rule in stack.
13. If length(stack) == 1 then goto 14 else goto 15
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 96
Compiler design Practical (CS-654) C020328

14. Print string can be parsed.

15. End.

9.6. Flowchart

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 97
Compiler design Practical (CS-654) C020328

9.7. Source Code:

#include <iostream>
#include <conio.h>
#include <string.h>
using namespace std;
char a[10];
int top = -1, i;
void error(void);
void push(char[]);
void pop(void);
char TOS(void);
void display(void);
void display1(char *, int);
char *stack();

int main()

char ip[20];
char r[20], st, an;
int ir, ic, j = 0, k;
char t[5][6][10] = {"$", "$", "TH", "$", "TH", "$",

"+TH", "$", "e", "e", "$", "e",

"$", "$", "FU", "$", "FU", "$",

"e", "*FU", "e", "e", "$", "e",

"$", "$", "(E)", "$", "i", "$"};

cout << "--------------- To implement a Top-Down Parser---------------\n";

cout << "Grammar : \n";
cout << "E -> TH\n";
cout << "H -> +TH | e\n";
cout << "T -> FU\n";
cout << "U -> *FT | e\n";
cout << "F -> w | (E)\n";
cout << "\nDirections of use: Append the input string with $";
cout << "\nInput the string that you want to parse: ";
cin >> ip;
cout << "\nStack\tInput\tOutput\n";
cout << "=====\t=====\t=====\n";
push("$E");
display();
cout << "\t" << ip << "\n";
for (j = 0; ip[j] != '\0';)
{
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 98
Compiler design Practical (CS-654) C020328

if (TOS() == an)

pop();
display();
display1(ip, j + 1);
cout << "\tPOP\n";
j++;
}

an = ip[j];

st = TOS();

if (st == 'E')
ir = 0;
else if (st == 'H')
ir = 1;
else if (st == 'T')
ir = 2;
else if (st == 'U')
ir = 3;
else if (st == 'F')
ir = 4;
else
{

error();
break;
}

if (an == '+')
ic = 0;
else if (an == '*')
ic = 1;
else if (an == '(')
ic = 2;
else if (an == ')')
ic = 3;
else if ((an >= 'a' && an <= 'z') || (an >= 'A' && an <= 'Z'))
{
ic = 4;
an = 'i';
}
else if (an == '$')
ic = 5;

strcpy(r, strrev(t[ir][ic]));
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 99
Compiler design Practical (CS-654) C020328

strrev(t[ir][ic]);
pop();

push(r);
if (TOS() == 'e')
{

pop();
display();
display1(ip, j);

cout << "\t" << st << "->e\n";

}

else
{

display();
display1(ip, j);
cout << "\t" << st << "->" << t[ir][ic] << "\n";
}

if (TOS() == '$' && an == '$')

break;
if (TOS() == '$')
{

error();
break;
}
}

k = strcmp(stack(), "$"); // if(k==0 && i==strlen(ip))

if (k == 0 && ip[j] == '$')

cout << "\n \nThe inputted string is ACCEPTED!!";
else
cout << "\n \nThe inputted string is REJECTED!";
return 0;
}
void error()
{
cout << "Syntax Error";
}

void push(char k[]) // Pushes The Set Of Characters on to the Stack

for (i = 0; k[i] != '\0'; i++)

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 100
Compiler design Practical (CS-654) C020328

if (top < 9)
a[++top] = k[i];
}
}

char TOS() // Returns TOP of the Stack

return a[top];
}

void pop() // Pops 1 element from the Stack

if (top >= 0)
a[top--] = '\0';
}

void display() // Displays Elements Of Stack

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

cout << a[i];
}

void display1(char p[], int m)

// Displays The Present Input String
{

int l;
cout << "\t";
for (l = m; p[l] != '\0'; l++)
cout << p[l];
}

char *stack()
{
return a;
}

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 101
Compiler design Practical (CS-654) C020328

9.8. Output:

Figure 9.2 Implementation of a top down parser

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 102
Compiler design Practical (CS-654) C020328

9.9. Frequently Asked Questions (FAQs):

Q1. What is a top-down parser?

Answer- A top-down parser is a parsing technique that begins with the most general syntactic
category of the input and uses a recursive approach to generate the input by applying production
rules. The parser endeavors to create a parse tree of the input by comparing it with a grammar
in a top-to-bottom fashion.

Q2. What is LL parsing?

Answer- LL parsing is a variety of top-down parsing that examines the input from left to right
and produces a leftmost derivation of the input. It is denoted as LL since it scans the input from
left to right and generates a leftmost derivation of the input.

Q3. What is backtracking in parsing?

Answer. In parsing, backtracking is employed to address ambiguity in the grammar. If a parser

is faced with multiple options for production rules, it may initially attempt one of them and
then go back and try a different rule if the first one doesn't succeed in producing the input. The
parser continues to try different rules until it identifies one that generates the input correctly.

Q4. What is the difference between top-down and bottom-up parsing?

Answer- Top-down parsing starts with the broadest syntactic category and applies production
rules repeatedly to generate the input, while bottom-up parsing begins with the input tokens
and seeks to reach the highest-level syntactic category via reduction rules. Typically, top-down
parsing is utilized for LL grammars, whereas bottom-up parsing is more suitable for LR
grammars.

Q5. Elaborate ERROR action of parser

Answer- When a parser cannot determine its next step and is faced with uncertainty, it may
take a particular course of action. In such a scenario, the parser cannot shift, reduce or accept.

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 103
Compiler design Practical (CS-654) C020328

Practical – 10
10.1. Aim

Write a program to implement intermediate code Generator using postfix, three address code and
its syntax tree.

10.2. Input

Infix expression

10.3. Expected Output

1. Postfix expression
2. 3 address code
3. Syntax tree

10.4. Method

A sort of intermediate code called three address code is simple to create and may be quickly
translated into machine code. To represent an expression, it uses a maximum of three addresses
and one operator, and the value computed at each instruction is saved in a temporary variable
created by the compiler. The order of three address codes' operations is determined by the
compiler.
A syntax tree's nodes can all be executed as data that has numerous fields. One field of the
operator node identifies the operator, and the remaining field contains a pointer to the operands'
nodes. The operator is often referred to as the node's label. The nodes of the syntax tree for
expressions with binary operators are created using the following functions. A pointer to the
most recent node formed is the result of each function.

10.5. Algorithm
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 104
Compiler design Practical (CS-654) C020328

1. Define a function to check if a character is an operator or not.

2. Define a function to check the precedence of an operator.
3. Define a function to convert an infix expression to postfix expression.
1. Create an empty stack to store operators.
2. Traverse the infix expression from left to right.
1. If the current character is an operand, add it to
the output string.
2. If the current character is an
opening parenthesis, push it
onto thestack.
3. If the current character is a
closing parenthesis, pop
operators from thestack and add
them to the output string until an
opening parenthesis is found.
Discard the opening parenthesis.
4. If the current character is an operator:
1. While there are operators on top of
the stack with higher or equal
precedence, pop them from the stack
and add them to theoutput string.
2. Push the current operator onto the stack.
3. Pop any remaining operators from the stack and add them to the
output string.

4. Return the postfix expression.

4. Define a function to generate three-address code from a postfix
expression.
1. Create an empty stack to store operands.

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 105
Compiler design Practical (CS-654) C020328

2. Traverse the postfix expression from left to right.

1. If the current character is an operand, push it
onto the stack.
2. If the current character is an operator:
1. Pop the top two operands from the stack.
2. Generate a new temporary variable name.
3. Add a new instruction to the
three-address code with the
operator and the two operands
as arguments, and the new
temporary variable name as the
destination.
4. Push the new temporary variable onto the stack.
3. The top of the stack should contain the final result of the
expression.
4. Return the three-address code.
5. Define a function to generate a syntax tree from a postfix expression.
1. Create an empty stack to store nodes.
2. Traverse the postfix expression from left to right.
1. If the current character is an operand, create
a new leaf node with theoperand as its label,
and push it onto the stack.
2. If the current character is an operator:
1. Pop the top two nodes from the stack.
2. Create a new internal node with the
operator as its label, and the two
popped nodes as its children.
3. Push the new internal node onto the stack.
3. The top of the stack should contain the root of the syntax tree.

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 106
Compiler design Practical (CS-654) C020328

4. Return the syntax tree.

6. Take the input infix expression from the user.
7. Call the functions to convert the infix expression to postfix
expression, generate three- address code, and generate the
syntax tree.
8. Print the postfix expression, three-address code, and syntax tree.

10.6. Flowchart

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 107
Compiler design Practical (CS-654) C020328

3-Address code generation

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 108
Compiler design Practical (CS-654) C020328

Syntax tree Generation

10.7. Source Code:

#include <bits/stdc++.h>
using namespace std;

int i = 1, j = 0, no = 0, tmpch = 90;

char str[100];
int p[5] = {0, 1, 2, 3, 4}, c = 1, kp, l, pi;
char sw[5] = {'=', '-', '+', '/', '*'}, expr[20], a[5], b[5], ch[2];
void scan();
void threeAddressCode(int i);
void intermediateCode();

struct Node
{
char data;
Node *left;

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 109
Compiler design Practical (CS-654) C020328

Node *right;
Node(char data) : data(data), left(NULL), right(NULL) {}
};

bool isOperator(char c)
{
if (c == '+' || c == '-' || c == '*' || c == '/')
return true;
return false;
}

struct exp
{
int pos;
char op;
} k[15];

struct Stack
{
int top;
unsigned capacity;
int *array;
};

struct Stack *createStack(unsigned capacity)

{
struct Stack *stack = (struct Stack *)malloc(sizeof(struct Stack));

if (!stack)
return NULL;

stack->top = -1;
stack->capacity = capacity;
stack->array = (int *)malloc(stack->capacity * sizeof(int));
return stack;
}
int isEmpty(struct Stack *stack)
{
return stack->top == -1;
}
char peek(struct Stack *stack)
{
return stack->array[stack->top];
}
char pop(struct Stack *stack)
{
if (!isEmpty(stack))
return stack->array[stack->top--];
return '$';
}
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 110
Compiler design Practical (CS-654) C020328

void push(struct Stack *stack, char op)

{
stack->array[++stack->top] = op;
}

int isOperand(char ch)

{
return (ch >= 'a' && ch <= 'z') ||
(ch >= 'A' && ch <= 'Z');
}

int Prec(char ch)

{
switch (ch)
{
case '+':
case '-':
return 1;

case '*':
case '/':
return 2;

case '^':
return 3;

case '=':
return 4;
}
return -1;
}

Node *buildSyntaxTree(string expression)

{
stack<Node *> nodes;
stack<char> operators;

for (int i = 0; i < expression.length(); i++)

{
char c = expression[i];
cout << c << endl;
if (isOperator(c))
{
while (!operators.empty() && Prec(operators.top()) >= Prec(c))
{
Node *node = new Node(operators.top());
operators.pop();
node->right = nodes.top();
nodes.pop();
node->left = nodes.top();
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 111
Compiler design Practical (CS-654) C020328

nodes.pop();
nodes.push(node);
}
operators.push(c);
}
else if (c == '(')
{
operators.push(c);
}
else if (c == ')')
{
while (operators.top() != '(')
{
Node *node = new Node(operators.top());
operators.pop();
node->right = nodes.top();
nodes.pop();
node->left = nodes.top();
nodes.pop();
nodes.push(node);
}
operators.pop();
}
else if (isalpha(c))
{
Node *node = new Node(c);
nodes.push(node);
}
}

while (!operators.empty())
{
Node *node = new Node(operators.top());
operators.pop();
node->right = nodes.top();
nodes.pop();
node->left = nodes.top();
nodes.pop();
nodes.push(node);
}
Node *node = new Node(str[0]);
node->left = new Node(str[1]);
node->right = nodes.top();
nodes.pop();
nodes.push(node);
return nodes.top();
}

void printTree(Node *root, string indent, bool last)

{
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 112
Compiler design Practical (CS-654) C020328

if (root != NULL)
{
cout << indent;
if (last)
{
cout << "!- ";
indent += " ";
}
else
{
cout << "|-- ";
indent += "| ";
}
cout << root->data << endl;
printTree(root->left, indent, false);
printTree(root->right, indent, true);
}
}

int infixToPostfix(char *exp)

{
int i, k;
struct Stack *stack = createStack(strlen(exp));
if (!stack)
return -1;

for (i = 0, k = -1; exp[i]; ++i)

{
if (isOperand(exp[i]))
exp[++k] = exp[i];
else if (exp[i] == '(')
push(stack, exp[i]);
else if (exp[i] == ')')
{
while (!isEmpty(stack) && peek(stack) != '(')
exp[++k] = pop(stack);
if (!isEmpty(stack) && peek(stack) != '(')
return -1;
else
pop(stack);
}
else
{
while (!isEmpty(stack) &&
Prec(exp[i]) <= Prec(peek(stack)))
exp[++k] = pop(stack);
push(stack, exp[i]);
}
}

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 113
Compiler design Practical (CS-654) C020328

while (!isEmpty(stack))
exp[++k] = pop(stack);

exp[++k] = '\0';
printf("%s", exp);
}

int main()
{
char process = 1;
while (process)
{
int choice;
printf("Enter the choice of intermediate code generation you want to perform:-
\n1.Postfix\n2.Three Address Code\n3.Syntax tree\n4. Exit\n");
printf("User's Choice: ");
scanf("%d", &choice);

printf("Enter the Expression: ");

scanf("%s", str);
if (choice == 1)
{
printf("Intermediate Code using postfix Expression: ");
infixToPostfix(str);
printf("\n");
}
else if (choice == 2)
{
printf("Intermediate Code using three Address code: \n");
intermediateCode();
printf("\n");
}
else if (choice == 3)
{
string expression = "";
expression += str;
Node *root = buildSyntaxTree(str);
cout << "Syntax tree:" << endl;
printTree(root, "", true);
}
else if (choice == 4)
{
break;
}

printf("Do you want to continue the process(0/1): ");

scanf("%d", &process);
}

return 0;
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 114
Compiler design Practical (CS-654) C020328

void intermediateCode()
{
strcpy(expr, str);
printf("\tThe Intermediate code is:\n");
scan();
}

void threeAddressCode(int i)
{
a[0] = b[0] = '\0';
if (!isdigit(expr[i + 2]) && !isdigit(expr[i - 2]))
{
a[0] = expr[i - 1];
b[0] = expr[i + 1];
}
if (isdigit(expr[i + 2]))
{
a[0] = expr[i - 1];
b[0] = 't';
b[1] = expr[i + 2];
}
if (isdigit(expr[i - 2]))
{
b[0] = expr[i + 1];
a[0] = 't';
a[1] = expr[i - 2];
b[1] = '\0';
}
if (isdigit(expr[i + 2]) && isdigit(expr[i - 2]))
{
a[0] = 't';
b[0] = 't';
a[1] = expr[i - 2];
b[1] = expr[i + 2];
sprintf(ch, "%d", c);
expr[i + 2] = expr[i - 2] = ch[0];
}
if (expr[i] == '*')
printf("\tt%d=%s*%s\n", c, a, b);
if (expr[i] == '/')
printf("\tt%d=%s/%s\n", c, a, b);
if (expr[i] == '+')
printf("\tt%d=%s+%s\n", c, a, b);
if (expr[i] == '-')
printf("\tt%d=%s-%s\n", c, a, b);
if (expr[i] == '=')
printf("\t%c=t%d", expr[i - 1], --c);
sprintf(ch, "%d", c);
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 115
Compiler design Practical (CS-654) C020328

expr[i] = ch[0];
c++;
scan();
}

void scan()
{
pi = 0;
l = 0;
for (int i = 0; i < strlen(expr); i++)
{
for (int m = 0; m < 5; m++)
if (expr[i] == sw[m])
if (pi <= p[m])
{
pi = p[m];
l = 1;
kp = i;
}
}
if (l == 1)
threeAddressCode(kp);
}

10.8. Output:

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 116
Compiler design Practical (CS-654) C020328

10.9. Frequently Asked Questions (FAQs):

Q1. How does an intermediate code generator using postfix notation work?
Answer- An intermediate code generator that utilizes postfix notation transforms the source
code of the input program into postfix notation. It employs a stack to monitor the operands and
operators, and subsequently produces three-address code based on the postfix notation,
utilizing temporary variables to store intermediate outcomes.
Q2. What is postfix notation?
Answer- Postfix notation refers to a method of writing mathematical expressions, whereby the
operands appear before the operator. As an illustration, the infix expression "3 + 4" would be
presented as "3 4 +" in postfix notation.
Q3. How does an intermediate code generator using a syntax tree work?
Answer- When employing a syntax tree, an intermediate code generator moves through the
tree in a depth-first fashion and produces three-address code for each node, taking into account
its type and children. The generator may also apply techniques such as peephole optimization
and code motion to enhance the efficiency of the resulting code and decrease duplication.
Q4. What is three-address code?
Answer- Three-address code is a low-level intermediate representation of code in which each
statement has at most three operands and one operator. The operands can be variables or
constants, and the operator can be any arithmetic or logical operator.
Q5. What is a syntax tree?
Answer- A syntax tree is a data structure used in compilers to represent the syntactic structure
of a program. It is a hierarchical tree-like structure in which each node represents a construct
in the program, such as a function call or a loop, and its children represent its arguments or
sub-expressions.

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 117
Compiler design Practical (CS-654) C020328

Practical – 11 (a)
11.1. Aim
Write a program to implement minimum 5 optimizations

11.2. Input
From user

11.3. Expected Output

Optimized code

11.4. Method

Code optimisation, a programme transformation technique, is used in the synthesis phase to try
to optimise the intermediate code by making it use fewer resources (such as CPU, Memory),
which should lead to faster-running machine code. The following goals should be achieved by
the compiler optimisation process:

• The optimisation must be accurate and cannot in any way alter the program's intent.

• Optimisation should improve the program's performance and speed.

• A reasonable compilation time must be maintained.

• The entire compilation process shouldn't be delayed by the optimisation process.

11.5. Algorithm
1. Prompt the user to enter an expression to optimize.
2. Read the expression from the user and store it in a string variable.
3. Use a regular expression to tokenize the expression
into individual operands andoperators, and store them
in a vector.
4. Perform the following optimizations on the expression:
• Constant folding: if the expression contains any
sub-expressions that can be evaluated at compile
time, evaluate them and replace the sub-expression
withthe resulting value.
• Constant propagation: if the expression contains

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 118
Compiler design Practical (CS-654) C020328

any variables whose valuesare known at compile

time, replace the variables with their known
values.
• Strength reduction: replace expensive operations
(such as multiplication) withequivalent cheaper
operations (such as addition or bit shifting).
• Dead code elimination: remove any sub-
expressions that do not contribute tothe final result
of the expression.
• Common sub-expression elimination: identify
and eliminate redundant sub-expressions that are
computed more than once.
5. Generate and print the optimized expression.
6. End the program

11.6. Flowchart

Figure 11.1
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 119
Compiler design Practical (CS-654) C020328

11.7. Source Code:

#include <stdio.h>
#include <conio.h>
#include <string.h >
#include <ctype.h>
struct op
{
char l;
char r[20];
}
op[10], pr[10];
typedef struct
{ char var[10];
int alive;
}
regist;
regist preg[10];
void substring(char exp[],int st,int end)
{ int i,j=0;
char dup[10]="";
for(i=st;i<end;i++){
dup[j++]=exp[i];
}
dup[j]='0';
strcpy(exp,dup);
} int getregister(char var[])
{ int i;
for(i=0;i<10;i++)
{
if(preg[i].alive==0)
{
strcpy(preg[i].var,var);
break;
}}
return(i);
}
void getvar(char exp[],char v[])
{ int i,j=0;
char var[10]="";
for(i=0;exp[i]!='\0';i++)
if(isalpha(exp[i]))
var[j++]=exp[i];
else
break;
strcpy(v,var);
}

main()
{
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 120
Compiler design Practical (CS-654) C020328

int a, i, k, j, n, z = 0, m, q;
char * p, * l;
char temp, t;
char * tem;
printf("enter no of values");
scanf("%d", & n);
for (i = 0; i < n; i++)
{
printf("\tleft\t");
op[i].l = getche();
printf("\tright:\t");
scanf("%s", op[i].r);
}
printf("intermediate Code\n");
for (i = 0; i < n; i++)
{
printf("%c=", op[i].l);
printf("%s\n", op[i].r);
}
for (i = 0; i < n - 1; i++)
{
temp = op[i].l;
for (j = 0; j < n; j++)
{
p = strchr(op[j].r, temp);
if (p)
{
pr[z].l = op[i].l;
strcpy(pr[z].r, op[i].r);
z++;

}
}
}
pr[z].l = op[n - 1].l;
strcpy(pr[z].r, op[n - 1].r);
z++;
printf("\nafter dead code elimination\n");
for (k = 0; k < z; k++)
{
printf("%c\t=", pr[k].l);
printf("%s\n", pr[k].r);
}

//sub expression elimination

for (m = 0; m < z; m++)
{
tem = pr[m].r;
for (j = m + 1; j < z; j++)
{
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 121
Compiler design Practical (CS-654) C020328

p = strstr(tem, pr[j].r);
if (p)
{
t = pr[j].l;
pr[j].l = pr[m].l;
for (i = 0; i < z; i++)
{
l = strchr(pr[i].r, t);
if (l) {
a = l - pr[i].r;
//printf("pos: %d",a);
pr[i].r[a] = pr[m].l;
}
}
}
}
}
for (i = 0; i < z; i++) {
printf("%c\t=", pr[i].l);
printf("%s\n", pr[i].r);
}
// duplicate production elimination

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

{
for (j = i + 1; j < z; j++)
{
q = strcmp(pr[i].r, pr[j].r);
if ((pr[i].l == pr[j].l) && !q)

{
pr[i].l = '\0';
strcpy(pr[i].r, '\0');
}
}
}

char basic[10][20],var[100][100],fstr[10],op;
int reg,vc,flag=0;

printf("optimized code");
k=0;
for (i = 0; i < z; i++)
{
if (pr[i].l != '\0') {
basic[i][k]=pr[i].l;
k++;
basic[i][k]=pr[i].r[0];
basic[i][k]=pr[i].r[1];
k++;
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 122
Compiler design Practical (CS-654) C020328

printf("%c=", pr[i].l);
printf("%s\n", pr[i].r);
} }

printf("\nThe Equivalent Assembly Code is:\n");

for(j=0;j<z;j++)
{
getvar(basic[j],var[vc++]);
strcpy(fstr,var[vc-1]);
substring(basic[j],strlen(var[vc-1])+1,strlen(basic[j]));
getvar(basic[j],var[vc++]);
reg=getregister(var[vc-1]);
if(preg[reg].alive==0)
{
printf("\nMov R%d,%s",reg,var[vc-1]);
preg[reg].alive=1;
}
op=basic[j][strlen(var[vc-1])];
substring(basic[j],strlen(var[vc-1])+1,strlen(basic[j]));
getvar(basic[j],var[vc++]);
switch(op)
{ case '+': printf("\nAdd"); break;
case '-': printf("\nSub"); break;
case '*': printf("\nMul"); break;
case '/': printf("\nDiv"); break;
}
flag=1;
for(k=0;k<=reg;k++)
{ if(strcmp(preg[k].var,var[vc-1])==0)
{
printf("R%d, R%d",k,reg);
preg[k].alive=0;
flag=0;
break;
}} if(flag)
{
printf(" %s,R%d",var[vc-1],reg);
printf("\nMov %s,R%d",fstr,reg);
}strcpy(preg[reg].var,var[vc-3]);
getch();
}

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 123
Compiler design Practical (CS-654) C020328

11.8. Output:

Figure 11.2

11.9. Frequently Asked Questions (FAQs):

Q1. What is code optimization?
Answer-Code optimisation is the process of increasing a computer program's efficiency by reducing
the resources it uses, like memory or CPU cycles, while keeping or even improving its usefulness.
Q2. What is loop optimization?
Answer- By minimising memory accesses, lowering the number of instructions performed, and
enhancing cache locality, loop optimisation can improve a program's speed.
Q3. What is constant folding?
Answer- Constant folding is a method for evaluating constant expressions at the time of compilation
as opposed to runtime. As a result, the programme runs more efficiently and executes fewer
instructions.
Q4. What is code motion?
Answer- When possible, code is moved out of loops or conditional statements using the technique
known as "code motion," which lowers the amount of instructions that must be executed and boosts
programme speed.
Q5. What are the benefits of code optimization?
Answer- Code optimisation can result in quicker programme execution, less memory utilisation, and
higher programme efficiency, which improves user experience and requires less resources.

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 124
Compiler design Practical (CS-654) C020328

Practical – 11 (b)
11.1. Aim
Write a program to implement code generation

11.2. Input
Three-address code

11.3. Expected Output

Code generated from the three address code

11.4. Method

The process of code generation can be thought of as the culmination of compilation. The
optimisation method can be applied to the code through post code generation, although that
can be considered as a component of the code generation step itself. The code that the compiler
produces is an object code for a certain low-level programming language, like assembly. We've
seen how lower-level object code is produced by converting source code written in a higher-
level language into a lower-level language. Lower-level object code must contain the following
minimal characteristics:

• It must accurately reflect the meaning of the source code;

• It must effectively manage memory and the CPU

11.5. Algorithm

1. Define a struct called "Instruction" to represent an instruction in three-

address codewith four fields "op", "arg1", "arg2" and "result"
2. Define main function
3. Open output file for writing
4. Generate some code in three-address code format and store it in a
vector of"Instruction" structs
5. Write code to output file by iterating through the vector of "Instruction"
structs usinga for loop and writing each instruction in the desired format
6. Close output file
7. Return

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 125
Compiler design Practical (CS-654) C020328

11.6. Flowchart

11.7. Source Code:

#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

// A struct to represent an instruction in three-address code

struct Instruction
{
string op; string arg1; string arg2;
string result;
};
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 126
Compiler design Practical (CS-654) C020328

int main() {
// Open output file for writing
ofstream outFile("output.txt");

// Generate some code in three-address

vector<Instruction> code = {
{"=", "5", "", "x"},
{"=", "10", "", "y"},
{"+", "x", "y", "temp"},
{"=", "temp", "", "z"}
};

// Write code to output file

for (auto instr : code) {
outFile << instr.result << " = " << instr.arg1 << " " << instr.op << " " << instr.arg2 << ";\n";
}

// Close output file

outFile.close();

return 0;
}

11.8. Output:

Figure 11(b).2

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 127
Compiler design Practical (CS-654) C020328

11.9. Frequently Asked Questions (FAQs):

Q1. What are the stages of code generation?

Answer-The stages of code generation typically include lexical analysis, syntax analysis,
semantic analysis, intermediate code generation, optimization, and code generation.

Q2. What is assembly language?

Answer- A low-level programming language called assembly language is used to create

programmes that are more similar to machine code than high-level programming languages.
System software, device drivers, and other types of software that communicate with hardware
directly are frequently written using it.

Q3. What is machine code?

Answer- The central processing unit (CPU) of a computer executes machine code, a low-level
programming language. It is made up of binary instructions that are tailored to a given CPU
architecture.

Q4. What are the advantages of code generation?

Answer- Software engineers can design programmes in high-level programming languages

that are simpler to comprehend and maintain while also saving time and effort by using code
generation. It can also increase the accuracy and correctness of the produced code.

Q5. What is code generation?

Answer- Code generation is the process of converting high-level programming languages or

other intermediate representations into machine-readable code or instructions.
-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 128
Compiler design Practical (CS-654) C020328

Practical – 12
12.1. Aim

A software program designed to compute the Leading and Trailing sets of Non-Terminals.

12.2. Input

a) The software takes Context Free Grammar, represented as G, as its input.

b) The user is asked to provide the number of production rules for grammar G.
c) Subsequently, the program asks the user to input each production rule of grammar G
individually. Each production rule comprises a non-terminal symbol on the left-hand side, an
arrow symbol "->" in the middle, followed by a sequence of symbols (terminals and/or non-
terminals) on the right-hand side. Each production rule is entered on a separate line.
12.3. Expected Output

a) The trailing set of a non-terminal symbol A is determined to be a if the corresponding

Boolean array T[A,a] has a value of true.
b) For a given non-terminal symbol A, the leading set is identified as an if the associated
Boolean array L[A,a] is evaluated as true.

12.4. Method

Establishing operator-precedence relations can be achieved through creating a language that

uses parse trees that accurately capture associativity and precedence. One type of grammar
used for this is the operator-precedence grammar, which has certain characteristics such as
having no null productions and never having two consecutive non-terminals in any of its
productions. Additionally, only one of the three potential relations (a b, a = b, and a > b) can
be legitimate and true for any pair of terminals a and b in the grammar.

In the Leading method, the set of FIRST terminals that can be deduced from the non-terminal
symbol A is represented as LEADING(A) = a | A => ya0, where y is either an empty string or
a single non-terminal symbol. This set can be computed using a 2D array of booleans, where
LIA,a is true if the terminal symbol an is a member of the LEADING(A) set; otherwise, it is
false. Furthermore, a collection of pairs between non-terminal symbols and terminal symbols
is used to discover new pairs according to rule (b).

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 129
Compiler design Practical (CS-654) C020328

In the Trailing method, a non-terminal symbol A can be used to deduce the final or last terminal
symbol in a string, referred to as "TRAILING(A)". The set of terminal symbols that can be
used as the final character in a string deriving from a non-terminal symbol is represented by
TRAILING(A), where TRAILING(A) = a | A => yas, and y can be either an empty symbol or
a single non-terminal symbol. Similar to the Leading method, TRAILING(A) can be computed
by applying production-specific derivations to find the first terminal symbol from the right side
of a production.

Both Leading and Trailing methods can only be used with an operator precedence grammar to
produce an operator-precedence parser. An operator precedence grammar is a specific instance
of an operator grammar, in which no production rule has two consecutive non-terminal
symbols. When a non-terminal symbol is passed as an input, the Leading and Trailing functions
return a group of terminals that could represent the beginning or last terminal symbol in a string
produced from the non-terminal. Another way to think of the Leading set is the set of terminal
symbols that are "visible" from the beginning of a production rule. The term "transparent"
refers to non-terminal symbols, while a terminal symbol may be seen by gazing through a
leading non-terminal symbol or through a leading non-terminal symbol.

12.4.1. LEADING TERMINAL:

1. Initialize an empty set as the leading set for the non-terminal.

2. For each production rule in the grammar:
1. If the right-hand side of the production rule starts with a terminal symbol and
the left-hand side is the non-terminal being evaluated for leading set, then add
that terminal symbol to the leading set.
2. If the left-hand side of the production rule is the non-terminal being evaluated
for leading set and the right-hand side starts with another non-terminal symbol,
add the first set of that non-terminal. Continue to the next symbol on the right-
hand side until a non-empty string is found or all symbols have been processed
if that non-terminal can produce an empty string.
3. Repeat step 2 until no more symbols can be added to the leading set. The resulting set
is the leading set of the non-terminal. TRAILING TERMINAL:
4. Begin the algorithm.
5. Initialize the corresponding value of each non-terminal and terminal pair to false.
6. Invoke the INSTALL(A,a) function for each production of the form A->a(alpha) or A-
>Ba(alpha).
7. Repeat steps 5 and 6 until the stack is empty.
8. Pop the top pair from the stack.
9. Invoke the INSTALL(A,a) function for each production of the form A->B(alpha).
10. Reverse the algorithm. The INSTALL(A,a) function performs the following steps:

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 130
Compiler design Practical (CS-654) C020328

11. Start the process.

12. If L(A,a) is not present, repeat steps 3 and 4.
13. Set L(A,a) to True.
14. Push the pair (A,a) onto the stack.
15. Stop the process.

12.6. Flowchart

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 131
Compiler design Practical (CS-654) C020328

12.7. Source Code:

#include <iostream>

#include <vector>

#include <string>

#include <unordered_map>

#include <set>

using namespace std;

unordered_map<string, vector<string>> productions;

void find_leading(string non_terminal, set<string>& leading_set) {

for (auto& production : productions[non_terminal]) {

if (islower(production[0])) {

leading_set.insert(production.substr(0, 1));

else if (isupper(production[0])) {

set<string> new_leading_set;

find_leading(production.substr(0, 1), new_leading_set);

leading_set.insert(new_leading_set.begin(), new_leading_set.end());

void find_trailing(string non_terminal, set<string>& trailing_set) {

for (auto& production : productions[non_terminal]) {

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 132
Compiler design Practical (CS-654) C020328

if (islower(production.back()))

trailing_set.insert(production.substr(production.size() - 1, 1));

else if (isupper(production.back()))

set<string> new_trailing_set;

find_trailing(production.substr(production.size() - 1, 1), new_trailing_set);

trailing_set.insert(new_trailing_set.begin(), new_trailing_set.end());

int main() {

int num_productions;

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

cin >> num_productions;

cout << "Enter the productions in the form A -> B | C | D, one per line:\n";

string production_str;

getline(cin, production_str);

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

getline(cin, production_str);

size_t arrow_pos = production_str.find("->");

string non_terminal = production_str.substr(0, arrow_pos);

string rhs = production_str.substr(arrow_pos + 2);

size_t pipe_pos = 0;

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 133
Compiler design Practical (CS-654) C020328

while ((pipe_pos = rhs.find("|")) != string::npos) {

productions[non_terminal].push_back(rhs.substr(0, pipe_pos));

rhs = rhs.substr(pipe_pos + 1);

productions[non_terminal].push_back(rhs);

cout << "Enter the non-terminal to find the leading and trailing of: ";

string target_non_terminal;

cin >> target_non_terminal;

set<string> leading_set;

set<string> trailing_set;

find_leading(target_non_terminal, leading_set);

find_trailing(target_non_terminal, trailing_set);

cout << "Leading of " << target_non_terminal << ": ";

for (auto& s : leading_set) {

cout << s << " ";

cout << endl;

cout << "Trailing of " << target_non_terminal << ": ";

for (auto& s : trailing_set) {

cout << s << " ";

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 134
Compiler design Practical (CS-654) C020328

cout << endl;

return 0;

12.8. Output:

12.9. Discussion:
Creating an operator precedence table is an important step in building a parser for a
programming language. The table serves as a guide for the parser to correctly interpret the
grammar rules and generate the appropriate output. Without an operator precedence table, the
parser may misinterpret the input string and produce incorrect results.

To determine the LEADING() and TRAILING() functions, one needs to analyze the grammar
rules carefully and identify the terminals that can appear at the beginning and end of each

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 135
Compiler design Practical (CS-654) C020328

production. These functions play a crucial role in constructing the operator precedence table as
they help in establishing the order of evaluation of operators.

The process of constructing an operator precedence table involves assigning a precedence level
to each operator pair based on a comparison of their LEADING() and TRAILING() sets. The
precedence level determines the order in which the operators should be evaluated. Operators
with a higher precedence level are evaluated first, followed by operators with a lower
precedence level.

Once the operator precedence table is constructed, the parser can use it to determine the correct
order of evaluation of operators in the input string. This ensures that the output generated by
the parser is correct and meets the requirements of the programming language.

12.10. Frequently Asked Questions (FAQs):

Q1: What is Leading and Trailing in parsing?

A: Leading and Trailing are sets of terminals that can appear as the first and last symbols of a
production rule in a grammar.
Q2: Why do we need to calculate Leading and Trailing?
A: We need to calculate Leading and Trailing to create an operator precedence table that
specifies the relative importance of different operators in the grammar.
Q3: How do we calculate Leading and Trailing?
A: We calculate Leading and Trailing by analyzing the production rules in the grammar and
identifying the terminals that can appear at the beginning and end of each rule.
Q4: What is the purpose of the operator precedence table?
A: The purpose of the operator precedence table is to enable the parser to accurately interpret
the meaning of the input string by specifying the relative importance of different operators.
Q5: How is the level of precedence of each operator pair determined?
A: The level of precedence of each operator pair is determined by comparing the Leading and
Trailing sets of the terminals involved.

-------------------------------------------------------------------------------------
Department of computer science and engineering pg. 136