Compiler Design Lab

Shivam Bindal (BT19CSE008)
Compiler Design Lab

CSP352
Lab File
Department of Computer Science Engineering
National Institute of Technology,

Uttarakhand
Submitted by: Shivam Bindal (BT19CSE008)

Submitted to: Dr Maroti Deshmukh
1
INDEX
S.No Program Name Date

1 Identify the total number of tokens 7 Jan 2022
as output & Automata for
Identifiers
2 Left Recursive Grammar 21 Jan 2022
3 Remove Left Recursion 21 Jan 2022
4 LL1 Parser 11 Feb 2022
5 Check if a string matches the input 18 Feb 2022
grammar
6 LR(0) Parser 4 Mar 2022
7 SLR(1) Parser 11 Mar 2022
8 LALR Parser 25 Mar 2022
9 CLR Parser 8 Apr 2022
2
Q- Write a program by taking input as C File. (i) Identify the total number of
tokens as output. (ii) Identify the total number of unique tokens as output.
Code:
////////////////////////////////////////////////////
// //
// Coded by Shivam Bindal //
// //
////////////////////////////////////////////////////
#include <bits/stdc++.h>
#define int long long
using namespace std;
bool iskeyword(string s){
string keywords[32] =
{"auto","break","case","char","const","continue","default","do",
"double","else","enum","extern","float",
"for","goto","if","int","long","register","return","short","
signed","sizeof","static","struct","switch","typedef","union","u
nsigned",
"void","volatile","while"};
for(int i = 0; i < 32; ++i){
if(s == keywords[i]){
return true;
}
}
return false;
}
bool isOperator(char ch){
if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch
== '>' || ch == '<' || ch == '=')
return true;
return false;
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
char ch;
string s="";
ifstream fin("ddd.txt");
int i,j=0;
if(!fin.is_open()){
cout<<"error while opening the file\n";
exit(0);
3
}
int tt=0;
int x=0 ,y=0 , z=0 , p=0;
while(!fin.eof()){
ch = fin.get();
if(isOperator(ch)){
// cout<<ch<<" is operator\n";
x++;
tt++;
}
if(isalnum(ch)){
s+=ch;
}
else if((ch == ' ' || ch == '\n')){
// cout<<s<<endl;
if(iskeyword(s) == 1){
// cout<<s<<" is keyword\n";
z++;
tt++;
}
else{
//cout<<s<<" is indentifier\n";
p++;
tt++;
}
s="";
}
}
cout<<"Total Number of Tokens = "<<tt<<endl;
cout<<"Total Number of keyword = "<<z<<endl;
cout<<"Total Number of identifiers = "<<p<<endl;
cout<<"Total Number of operators = "<<x<<endl;
fin.close();
return 0;
}
Output:
4
Q- Remove Left Recursion in given grammar and take input from file and give
output in a file.
Code:
#include <bits/stdc++.h>
#define SIZE 10
int main(){
int n , index=3;
char p[10][SIZE] ,a , b , c;
cout<<"Enter number of p : "<<endl;
cin>>n;
cout<<"Enter the grammar as E->E-A :"<<endl;
for(int i=0;i<n;i++) cin>>p[i];
for(int i=0;i<n;i++){
cout<<"\nGRAMMAR : : :"<<p[i]<<endl;
a=p[i][0];
if(a==p[i][index]) {
c=p[i][index+1];
cout<<" is left recursive.\n";
while(p[i][index]!=0 && p[i][index]!='|') index++;
if(p[i][index]!=0) { b=p[i][index+1];
cout<<"Grammar without left recursion:\n";
cout<<a<<"->"<<b<<a<<endl;
cout<<a<<"->"<<c<<a<<endl;
}
else cout<<" can't be reduced\n";
}
else cout<<" is not left recursive.\n";
index=3;
}
return 0;
}
Output:
5
Q- Implement LL1 parser with input Grammar.
Code:
////////////////////////////////////////////////////
// //
// //
////////////////////////////////////////////////////
#include<stdio.h>
#include<ctype.h>
#include<string.h>
void followfirst(char , int , int);
void findfirst(char , int , int);
void follow(char c);
int count,n=0;
char calc_first[10][100];
char calc_follow[10][100];
int m=0;
char production[10][10], first[10];
char f[10];
int k;
char ck;
int e;
int main(int argc,char **argv)
{
int jm=0;
int km=0;
int i,choice;
char c,ch;
printf("How many productions ? :");
scanf("%d",&count);
printf("\nEnter %d productions in form A=B where A and B are
grammar symbols :\n\n",count);
for(i=0;i<count;i++)
{
scanf("%s%c",production[i],&ch);
}
int kay;
char done[count];
int ptr = -1;
for(k=0;k<count;k++){
for(kay=0;kay<100;kay++){
calc_first[k][kay] = '!';
}
6
}
int point1 = 0,point2,xxx;
for(k=0;k<count;k++)
{
c=production[k][0];
point2 = 0;
xxx = 0;
for(kay = 0; kay <= ptr; kay++)
if(c == done[kay])
xxx = 1;
if (xxx == 1)
continue;
findfirst(c,0,0);
ptr+=1;
done[ptr] = c;
printf("\n First(%c)= { ",c);
calc_first[point1][point2++] = c;
for(i=0+jm;i<n;i++){
int lark = 0,chk = 0;
for(lark=0;lark<point2;lark++){
if (first[i] == calc_first[point1][lark]){
chk = 1;
break;
}
}
if(chk == 0){
printf("%c, ",first[i]);
calc_first[point1][point2++] = first[i];
}
}
printf("}\n");
jm=n;
point1++;
}
printf("\n");
printf("-----------------------------------------------
\n\n");
char donee[count];
ptr = -1;
calc_follow[k][kay] = '!';
}
}
point1 = 0;
7
int land = 0;
for(e=0;e<count;e++)
{
ck=production[e][0];
point2 = 0;
xxx = 0;
if(ck == donee[kay])
xxx = 1;
if (xxx == 1)
continue;
land += 1;
follow(ck);
ptr+=1;
donee[ptr] = ck;
printf(" Follow(%c) = { ",ck);
calc_follow[point1][point2++] = ck;
for(i=0+km;i<m;i++){
int lark = 0,chk = 0;
for(lark=0;lark<point2;lark++){
if (f[i] == calc_follow[point1][lark]){
chk = 1;
break;
}
}
if(chk == 0){
printf("%c, ",f[i]);
calc_follow[point1][point2++] = f[i];
}
}
printf(" }\n\n");
km=m;
point1++;
}
char ter[10];
for(k=0;k<10;k++){
ter[k] = '!';
}
int ap,vp,sid = 0;
for(kay=0;kay<count;kay++){
if(!isupper(production[k][kay]) &&
production[k][kay]!= '#' && production[k][kay] != '=' &&
production[k][kay] != '\0'){
vp = 0;
8
for(ap = 0;ap < sid; ap++){

if(production[k][kay] == ter[ap]){
vp = 1;
break;
}
}
if(vp == 0){
ter[sid] = production[k][kay];
sid ++;
}
}
}
}
ter[sid] = '$';
sid++;
printf("\n\t\t\t\t\t\t\t The LL(1) Parsing Table for the
above grammer :-");
printf("\n\t\t\t\t\t\t\t^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
^^^^^^^^^^^^^^\n");
printf("\n\t\t\t============================================
================================================================
=========\n");
printf("\t\t\t\t|\t");
for(ap = 0;ap < sid; ap++){
printf("%c\t\t",ter[ap]);
}
printf("\n\t\t\t============================================
================================================================
=========\n");
char first_prod[count][sid];
for(ap=0;ap<count;ap++){
int destiny = 0;
k = 2;
int ct = 0;
char tem[100];
while(production[ap][k] != '\0'){
if(!isupper(production[ap][k])){
tem[ct++] = production[ap][k];
tem[ct++] = '_';
tem[ct++] = '\0';
k++;
break;
}
else{
int zap=0;
9
int tuna = 0;
for(zap=0;zap<count;zap++){
if(calc_first[zap][0] == production[ap][k]){
for(tuna=1;tuna<100;tuna++){
if(calc_first[zap][tuna] != '!'){
tem[ct++] =
calc_first[zap][tuna];
}
else
break;
}
break;
}
}
tem[ct++] = '_';
}
k++;
}
int zap = 0,tuna;
for(tuna = 0;tuna<ct;tuna++){
if(tem[tuna] == '#'){
zap = 1;
}
else if(tem[tuna] == '_'){
if(zap == 1){
zap = 0;
}
else
break;
}
else{
first_prod[ap][destiny++] = tem[tuna];
}
}
}
char table[land][sid+1];
ptr = -1;
for(ap = 0; ap < land ; ap++){
for(kay = 0; kay < (sid + 1) ; kay++){
table[ap][kay] = '!';
}
}
for(ap = 0; ap < count ; ap++){
ck = production[ap][0];
xxx = 0;
10

if(ck == table[kay][0])
xxx = 1;
if (xxx == 1)
continue;
else{
ptr = ptr + 1;
table[ptr][0] = ck;
}
}
for(ap = 0; ap < count ; ap++){
int tuna = 0;
while(first_prod[ap][tuna] != '\0'){
int to,ni=0;
for(to=0;to<sid;to++){
if(first_prod[ap][tuna] == ter[to]){
ni = 1;
}
}
if(ni == 1){
char xz = production[ap][0];
int cz=0;
while(table[cz][0] != xz){
cz = cz + 1;
}
int vz=0;
while(ter[vz] != first_prod[ap][tuna]){
vz = vz + 1;
}
table[cz][vz+1] = (char)(ap + 65);
}
tuna++;
}
}
for(k=0;k<sid;k++){
if(calc_first[k][kay] == '!'){
break;
}
else if(calc_first[k][kay] == '#'){
int fz = 1;
while(calc_follow[k][fz] != '!'){
char xz = production[k][0];
int cz=0;
while(table[cz][0] != xz){
11
cz = cz + 1;
}
int vz=0;
while(ter[vz] != calc_follow[k][fz]){
vz = vz + 1;
}
table[k][vz+1] = '#';
fz++;
}
break;
}
}
}
for(ap = 0; ap < land ; ap++){
printf("\t\t\t %c\t|\t",table[ap][0]);
for(kay = 1; kay < (sid + 1) ; kay++){
if(table[ap][kay] == '!')
printf("\t\t");
else if(table[ap][kay] == '#')
printf("%c=#\t\t",table[ap][0]);
else{
int mum = (int)(table[ap][kay]);
mum -= 65;
printf("%s\t\t",production[mum]);
}
}
printf("\n");
printf("\t\t\t------------------------------------------
----------------------------------------------------------------
-----------");
printf("\n");
}
int j;
printf("\n\nPlease enter the desired INPUT STRING = ");
char input[100];
scanf("%s%c",input,&ch);
printf("\n\t\t\t\t\t========================================
===================================\n");
printf("\t\t\t\t\t\tStack\t\t\tInput\t\t\tAction");
printf("\n\t\t\t\t\t========================================
===================================\n");
int i_ptr = 0,s_ptr = 1;
char stack[100];
stack[0] = '$';
stack[1] = table[0][0];
12
while(s_ptr != -1){
printf("\t\t\t\t\t\t");
int vamp = 0;
for(vamp=0;vamp<=s_ptr;vamp++){
printf("%c",stack[vamp]);
}
printf("\t\t\t");
vamp = i_ptr;
while(input[vamp] != '\0'){
printf("%c",input[vamp]);
vamp++;
}
printf("\t\t\t");
char her = input[i_ptr];
char him = stack[s_ptr];
s_ptr--;
if(!isupper(him)){
if(her == him){
i_ptr++;
printf("POP ACTION\n");
}
else{
printf("\nString Not Accepted by LL(1) Parser
!!\n");
exit(0);
}
}
else{
for(i=0;i<sid;i++){
if(ter[i] == her)
break;
}
char produ[100];
for(j=0;j<land;j++){
if(him == table[j][0]){
if (table[j][i+1] == '#'){
printf("%c=#\n",table[j][0]);
produ[0] = '#';
produ[1] = '\0';
}
else if(table[j][i+1] != '!'){
int mum = (int)(table[j][i+1]);
mum -= 65;
strcpy(produ,production[mum]);
printf("%s\n",produ);
13
}
else{
printf("\nString Not Accepted by LL(1)
Parser !!\n");
exit(0);
}
}
}
int le = strlen(produ);
le = le - 1;
if(le == 0){
continue;
}
for(j=le;j>=2;j--){
s_ptr++;
stack[s_ptr] = produ[j];
}
}
}
printf("\n\t\t\t============================================
================================================================
===========\n");
if (input[i_ptr] == '\0'){
printf("\t\t\t\t\t\t\t\tYOUR STRING HAS BEEN ACCEPTED
!!\n");
}
else
printf("\n\t\t\t\t\t\t\t\tYOUR STRING HAS BEEN REJECTED
!!\n");
printf("\t\t\t==============================================
================================================================
=========\n");
}
void follow(char c)
{
int i ,j;
if(production[0][0]==c){
f[m++]='$';
}
for(i=0;i<10;i++)
{
for(j=2;j<10;j++)
{
if(production[i][j]==c)
14
{
if(production[i][j+1]!='\0'){
followfirst(production[i][j+1],i,(j+2));
}
if(production[i][j+1]=='\0'&&c!=production[i][0]
){
follow(production[i][0]);
}
}
}
}
}
void findfirst(char c ,int q1 , int q2)

{
int j;
if(!(isupper(c))){
first[n++]=c;
}
for(j=0;j<count;j++)
{
if(production[j][0]==c)
{
if(production[j][2]=='#'){
if(production[q1][q2] == '\0')
first[n++]='#';
else if(production[q1][q2] != '\0' && (q1 != 0
|| q2 != 0))
{
findfirst(production[q1][q2], q1, (q2+1));
}
else
first[n++]='#';
}
else if(!isupper(production[j][2])){
first[n++]=production[j][2];
}
else {
findfirst(production[j][2], j, 3);
}
}
}
}
void followfirst(char c, int c1 , int c2)
15
{
int k;
if(!(isupper(c)))
f[m++]=c;
else{
int i=0,j=1;
for(i=0;i<count;i++)
{
if(calc_first[i][0] == c)
break;
}
while(calc_first[i][j] != '!')
{
if(calc_first[i][j] != '#'){
f[m++] = calc_first[i][j];
}
else{
if(production[c1][c2] == '\0'){
follow(production[c1][0]);
}
else{
followfirst(production[c1][c2],c1,c2+1);
}
}
j++;
}
}
}
Output:
16
Q- Take input as grammar and check if a string gets accepted or not.
Code:
////////////////////////////////////////////////////
// //
// //
////////////////////////////////////////////////////
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <stack>
void find_first(vector< pair<char, string> > gram,
map< char, set<char> > &firsts,
char non_term);
void find_follow(vector< pair<char, string> > gram,
map< char, set<char> > &follows,
map< char, set<char> > firsts,
char non_term);
int main(int argc, char const *argv[])
{
if(argc != 3) {
cout<<"Arguments should be <grammar file> <input
string>\n";
return 1;
}
// Arguments check
// cout<<argv[1]<<argv[2];
// Parsing the grammar file

fstream grammar_file;
grammar_file.open(argv[1], ios::in);
if(grammar_file.fail()) {
cout<<"Error in opening grammar file\n";
return 2;
}
cout<<"Grammar parsed from grammar file: \n";

vector< pair<char, string> > gram;
int count = 0;
17
while(!grammar_file.eof()) {
char buffer[20];
grammar_file.getline(buffer, 19);
char lhs = buffer[0];

string rhs = buffer+3;
pair <char, string> prod (lhs, rhs);
gram.push_back(prod);
cout<<count++<<". "<<gram.back().first<<" ->
"<<gram.back().second<<"\n";
}
cout<<"\n";
// Gather all non terminals

set<char> non_terms;
for(auto i = gram.begin(); i != gram.end(); ++i) {
non_terms.insert(i->first);
}
cout<<"The non terminals in the grammar are: ";
for(auto i = non_terms.begin(); i != non_terms.end(); ++i) {
cout<<*i<<" ";
}
cout<<"\n";
// Gather all terminals
set<char> terms;
for(auto i = gram.begin(); i != gram.end(); ++i) {
for(auto ch = i->second.begin(); ch != i->second.end();
++ch) {
if(!isupper(*ch)) {
terms.insert(*ch);
}
}
}
// Remove epsilon and add end character $
terms.erase('e');
terms.insert('$');
cout<<"The terminals in the grammar are: ";
for(auto i = terms.begin(); i != terms.end(); ++i) {
cout<<*i<<" ";
}
cout<<"\n\n";
// Start symbol is first non terminal production in grammar

char start_sym = gram.begin()->first;
18
map< char, set<char> > firsts;

for(auto non_term = non_terms.begin(); non_term !=
non_terms.end(); ++non_term) {
if(firsts[*non_term].empty()){
find_first(gram, firsts, *non_term);
}
}
cout<<"Firsts list: \n";

for(auto it = firsts.begin(); it != firsts.end(); ++it) {
cout<<it->first<<" : ";
for(auto firsts_it = it->second.begin(); firsts_it !=
it->second.end(); ++firsts_it) {
cout<<*firsts_it<<" ";
}
cout<<"\n";
}
cout<<"\n";
map< char, set<char> > follows;

// Find follow of start variable first
char start_var = gram.begin()->first;
follows[start_var].insert('$');
find_follow(gram, follows, firsts, start_var);
// Find follows for rest of variables
for(auto it = non_terms.begin(); it != non_terms.end();
++it) {
if(follows[*it].empty()) {
find_follow(gram, follows, firsts, *it);
}
}
cout<<"Follows list: \n";

for(auto it = follows.begin(); it != follows.end(); ++it) {
cout<<it->first<<" : ";
for(auto follows_it = it->second.begin(); follows_it !=
it->second.end(); ++follows_it) {
cout<<*follows_it<<" ";
}
cout<<"\n";
}
cout<<"\n";
int parse_table[non_terms.size()][terms.size()];
19
fill(&parse_table[0][0], &parse_table[0][0] +
sizeof(parse_table)/sizeof(parse_table[0][0]), -1);
for(auto prod = gram.begin(); prod != gram.end(); ++prod) {
string rhs = prod->second;
set<char> next_list;
bool finished = false;
for(auto ch = rhs.begin(); ch != rhs.end(); ++ch) {
if(!isupper(*ch)) {
if(*ch != 'e') {
next_list.insert(*ch);
finished = true;
break;
}
continue;
}
set<char> firsts_copy(firsts[*ch].begin(),
firsts[*ch].end());
if(firsts_copy.find('e') == firsts_copy.end()) {
next_list.insert(firsts_copy.begin(),
firsts_copy.end());
finished = true;
break;
}
firsts_copy.erase('e');
next_list.insert(firsts_copy.begin(),
firsts_copy.end());
}
// If the whole rhs can be skipped through epsilon or
reaching the end
// Add follow to next list
if(!finished) {
next_list.insert(follows[prod->first].begin(),
follows[prod->first].end());
}
for(auto ch = next_list.begin(); ch != next_list.end();

++ch) {
int row = distance(non_terms.begin(),
non_terms.find(prod->first));
int col = distance(terms.begin(), terms.find(*ch));
int prod_num = distance(gram.begin(), prod);
if(parse_table[row][col] != -1) {
20
cout<<"Collision at ["<<row<<"]["<<col<<"] for

production "<<prod_num<<"\n";
continue;
}
parse_table[row][col] = prod_num;
}
}
// Print parse table
cout<<"Parsing Table: \n";
cout<<" ";
for(auto i = terms.begin(); i != terms.end(); ++i) {
cout<<*i<<" ";
}
cout<<"\n";
for(auto row = non_terms.begin(); row != non_terms.end();
++row) {
cout<<*row<<" ";
for(int col = 0; col < terms.size(); ++col) {
int row_num = distance(non_terms.begin(), row);
if(parse_table[row_num][col] == -1) {
cout<<"- ";
continue;
}
cout<<parse_table[row_num][col]<<" ";
}
cout<<"\n";
}
cout<<"\n";
string input_string(argv[2]);
input_string.push_back('$');
stack<char> st;
st.push('$');
st.push('S');
// Check if input string is valid

for(auto ch = input_string.begin(); ch !=
input_string.end(); ++ch) {
if(terms.find(*ch) == terms.end()) {
cout<<"Input string is invalid\n";
return 2;
}
}
21
// cout<<"Processing input string\n";

bool accepted = true;
while(!st.empty() && !input_string.empty()) {
// If stack top same as input string char remove it
if(input_string[0] == st.top()) {
st.pop();
input_string.erase(0, 1);
}
else if(!isupper(st.top())) {
cout<<"Unmatched terminal found\n";
accepted = false;
break;
}
else {
char stack_top = st.top();
int row = distance(non_terms.begin(),
non_terms.find(stack_top));
int col = distance(terms.begin(),
terms.find(input_string[0]));
int prod_num = parse_table[row][col];
if(prod_num == -1) {
cout<<"No production found in parse table\n";
accepted = false;
break;
}
st.pop();
string rhs = gram[prod_num].second;
if(rhs[0] == 'e') {
continue;
}
for(auto ch = rhs.rbegin(); ch != rhs.rend(); ++ch)
{
st.push(*ch);
}
}
}
if(accepted) {
cout<<"Input string is accepted\n";
}
else {
cout<<"Input string is rejected\n";
22
return 0;
}
void find_first(vector< pair<char, string> > gram,

map< char, set<char> > &firsts,
char non_term) {
// cout<<"Finding firsts of "<<non_term<<"\n";
for(auto it = gram.begin(); it != gram.end(); ++it) {

// Find productions of the non terminal
if(it->first != non_term) {
continue;
}
string rhs = it->second;
for(auto ch = rhs.begin(); ch != rhs.end(); ++ch) {
if(!isupper(*ch)) {
firsts[non_term].insert(*ch);
break;
}
else {
if(firsts[*ch].empty()) {
find_first(gram, firsts, *ch);
}
// If variable doesn't have epsilon, stop loop
if(firsts[*ch].find('e') == firsts[*ch].end()) {
firsts[non_term].insert(firsts[*ch].begin(),
firsts[*ch].end());
break;
}
set<char> firsts_copy(firsts[*ch].begin(),
firsts[*ch].end());
// Remove epsilon from firsts if not the last

variable
if(ch + 1 != rhs.end()) {
}
// Append firsts of that variable

firsts[non_term].insert(firsts_copy.begin(),
firsts_copy.end());
23
}
}
}
}
void find_follow(vector< pair<char, string> > gram,

map< char, set<char> > &follows,
map< char, set<char> > firsts,
char non_term) {
// cout<<"Finding follow of "<<non_term<<"\n";
for(auto it = gram.begin(); it != gram.end(); ++it) {
// finished is true when finding follow from this

production is complete
bool finished = true;
auto ch = it->second.begin();
// Skip variables till reqd non terminal

for(;ch != it->second.end() ; ++ch) {
if(*ch == non_term) {
finished = false;
break;
}
}
++ch;
for(;ch != it->second.end() && !finished; ++ch) {

// If non terminal, just append to follow
if(!isupper(*ch)) {
follows[non_term].insert(*ch);
finished = true;
break;
}
set<char> firsts_copy(firsts[*ch]);
// If char's firsts doesnt have epsilon follow
search is over
if(firsts_copy.find('e') == firsts_copy.end()) {
follows[non_term].insert(firsts_copy.begin(),
firsts_copy.end());
finished = true;
break;
24
}
// Else next char has to be checked after appending
firsts to follow
follows[non_term].insert(firsts_copy.begin(),
firsts_copy.end());
// If end of production, follow same as follow of

variable
if(ch == it->second.end() && !finished) {
// Find follow if it doesn't have
if(follows[it->first].empty()) {
find_follow(gram, follows, firsts, it->first);
}
follows[non_term].insert(follows[it->first].begin(),
follows[it->first].end());
}
Output:
25
Q- Implement LR(0) Parser:
Code:
"""
////////////////////////////////////////////////////
// //
// //
////////////////////////////////////////////////////
"""
# 1 ----------------- To Find Closure ----------------
def closure(I,nonT):
J = I
for item in J :
#print(item)
index = item[1].index('.')
if(index<(len(item[1])-1) and item[1][index+1] in nonT):
#print('item : ',item[1][index+1])
for production in nonT[item[1][index+1]]:
if( [item[1][index+1],str('.')+str(production)]
not in J):
J.append([item[1][index+1],str('.')+str(prod
uction)])
#print([item[1][index+1],str('.')+str(produc
tion)])
return J
state = []
I = []
def setOfItems(start,nonTer,ter):
I.append(closure([['start','.'+start+'$']],nonTer))
#print(I)
ter += list(nonTer.keys())
#print("list of inputs : " , ter)
for conI in I:
for grammar in ter:
if(grammar == '$'):
continue
#print("grammar : ",grammar)
goto = False
goto1 = False
shift = False
26
shift1 = False
reduce = False
close = []
for item in conI:
#print("item : ",item)
if(item[1].index('.')<(len(item[1])-1) and
item[1][item[1].index('.')+1] is grammar):
close.append([item[0],item[1][:item[1].index
('.')]+grammar+'.'+item[1][item[1].index('.')+2:]])
#else:
# print(item)
#print("close : ",close)
l = closure(close,nonTer)
if(len(l) == 0):
continue
#print("closure : ", l)
if(grammar in nonTer.keys()):
goto1 = True
else:
shift1 = True
if(l not in I):
if(goto1):
state.append(['g',I.index(conI)+1,len(I)+1,g
rammar])
goto = True
elif(shift1):
shift = True
state.append(['s',I.index(conI)+1,len(I)+1,g
rammar])
I.append(l)
else:
if(goto1):
goto = True
state.append(['g',I.index(conI)+1,I.index(l)
+1,grammar])
elif(shift1):
shift = True
state.append(['s',I.index(conI)+1,I.index(l)+
1,grammar])
# --------------------------------------------------------------
---
# 3. -----------------Create a Parse Table ---------------------
---
reduce = []
27
accept = -1
def toReduce(rule,accept,start):
s = ['start',start+'.$']
for parState in I:
#print(s,parState)
if(s in parState):
#print("here;")
accept = I.index(parState)
for item in parState:
if( item in rule):
reduce[I.index(parState)].append(rule.index(item
))
return accept
# --------------------------------------------------------------
----
# 4. --------------------- To Parse ----------------------------
----
symbolMap = dict()
parseTable = []
def createParseTable(ter):
for i in state:
parseTable[i[1]-1][symbolMap[i[3]]] = i[0]+str(i[2]-1)
parseTable[accept][symbolMap['$']] = 'a'
for i in reduce:
if(len(i)>0):
for j in ter:
parseTable[reduce.index(i)][symbolMap[j]] =
'r'+str(i[0])
# (i) Stack -------------------------

class Stack:
def __init__(self):
self.__storage = []
def isEmpty(self):
return len(self.__storage) == 0
def push(self,p):
self.__storage.append(p)
def pop(self):
28
return self.__storage.pop()
def top(self):
return self.__storage[len(self.__storage) - 1]
def length(self):
return len(self.__storage)
def __str__(self):
"""
Because of using list as parent class for stack, our
last element will
be first for stack, according to FIFO principle. So, if
we will use
parent's implementation of str(), we will get reversed
order of
elements.
"""
#: You can reverse elements and use supper `__str__`
method, or
#: implement it's behavior by yourself.
#: I choose to add 'stack' in the begging in order to
differ list and
#: stack instances.
return 'stack [{}]'.format(', '.join([ str(i) for i in
reversed(self.__storage) ]))
#--------------------Stack Defn ENDS ---------------------------

---------------
def parseString(rule,string):
index = 0
flag = False
st = Stack()
st.push('0')
while(index < len(string)):
print(st , string , index , sep = '\t\t ')
c =
parseTable[int(st.top())][symbolMap[string[index]]][0]
if(c == 'a'):
flag = True
break
pt =
parseTable[int(st.top())][symbolMap[string[index]]][1:]
pt = int(pt)
if( c == 'r'):
l = len(rule[pt][1])
l *= 2
l -= 2 #'.' is also considered
29
if(l >= st.length()):

break
else:
for i in range(l):
st.pop()
top = int(st.top())
st.push(rule[pt][0])
st.push(parseTable[top][symbolMap[st.top()]][1:]
)
else:
st.push(string[index])
st.push(str(pt))
index+=1
return flag
# --------------------------------------------------------------
----
# ---------------------------- Driver Program ------------------
-------
terminals = []
nonTerminals = dict()
terminals = input("Enter Terminals (|) : ").split("|")
n = int(input("No. of Non - Terminals : "))
for i in range(n):
ch = input("NonTerminals : ").strip()
rules = input("Productions (|) : ").split("|")
nonTerminals[ch] = rules
# --- Old Rules-------
S = input("Start Symbol : ")
terminals+=['$']
print("Productions : ")
for i in nonTerminals.keys():
print(i,"-->",end=' ')
for j in nonTerminals[i]:
print(j,end= ' | ')
print()
setOfItems(S,nonTerminals,terminals)
print("canonicals Items : ")
for count , i in enumerate(I):
print(count+1 , i)
print("state Transitions : ")

for count , i in enumerate(state):
print(count+1, i)
30
rule = []
accept = -1
for j in nonTerminals[i]:
rule.append([i,j+str('.')])
print('rule :')
for i in rule:
print(i)
# ------- To find the reduction rules - -- - -- ---
reduce = [ [] for i in range(len(I)) ]
accept = toReduce(rule,accept,S)
print("reduce")
for count,i in enumerate(reduce):
print(count+1,i)
print("accept : ",accept+1)
# --- - - - parse Table - -- -- - -- -- - -- - - -- -
symbols = []
symbols += terminals
for count , i in enumerate(symbols):
symbolMap[i] = count
print(symbols)
parseTable = [ ['-' for i in range(len(symbols))] for j in

range(len(I)) ]
terminals.remove(i)
createParseTable(terminals)
# ---Parse Table-----
print('Parse Table')
print(" \t\t",end='')
for i in symbols:
print(i,end= '\t')
print()
for count,j in enumerate(parseTable):
print(count,end='\t\t')
for i in j:
print(i,end='\t')
print()
31
string = input("String : ")

string+='$'
if(parseString(rule,string)):
print("Accepted")
else:
print("Not accepted")
Output:
32
Q- Implement SLR(1) Parser:
Code:
////////////////////////////////////////////////////
// //
// //
////////////////////////////////////////////////////
#include<bits/stdc++.h>
#include <algorithm>
#include <set>
#include <math.h>
#include <vector>
#define MOD 1000000007
#define mode 998244353
#define mo 10000005
set<char> ss;
map<char,vector<vector<char>>> mp;
bool dfs(char i, char org, char last,
map<char,vector<vector<char>>> &mp){
bool rtake = false;
for(auto r : mp[i]){
bool take = true;
for(auto s : r){
if(s == i) break;
if(!take) break;
if(!(s>='A'&&s<='Z')&&s!='e'){
ss.insert(s);
break;
}
else if(s == 'e'){
if(org == i||i == last)
ss.insert(s);
rtake = true;
break;
}
else{
take = dfs(s,org,r[r.size()-1],mp);
rtake |= take;
}
}
}
return rtake;
33
map<int,map<char,set<pair<deque<char>,deque<char>>>>> f;
map<int,vector<pair<int,char>>> g;
int num = -1;

void dfs2(char c, char way, int last,
pair<deque<char>,deque<char>> curr){
map<char,set<pair<deque<char>,deque<char>>>> mp2;
int rep = -2;
if(last != -1){
for(auto q : g[last]){
if(q.second == way){
rep = q.first;
mp2 = f[q.first];
}
}
}
mp2[c].insert(curr);
int count = 10;
while(count--){
for(auto q : mp2){
for(auto r : q.second){
if(!r.second.empty()){
if(r.second.front()>='A'&&r.second.front()<=
'Z'){
for(auto s : mp[r.second.front()]){
deque<char> st,emp;
for(auto t : s) st.push_back(t);
mp2[r.second.front()].insert({emp,st
});
}
}
}
}
}
}
for(auto q : f){
if(q.second == mp2){
g[last].push_back({q.first,way});
return;
}
}
if(rep == -2){
f[++num] = mp2;
34
if(last != -1)
g[last].push_back({num,way});
}
else{
f[rep] = mp2;
}
int cc = num;
for(auto q : mp2){
if(!r.second.empty()){
r.first.push_back(r.second.front());
r.second.pop_front();
dfs2(q.first,r.first.back(),cc,r);
}
}
}
}
int main(){
int i,j;
ifstream fin("input.txt");
string num;
vector<int> fs;
vector<vector<int>> a;
char start;
bool flag = 0;
cout<<"Grammar: "<<'\n';
while(getline(fin,num)){
if(flag == 0) start = num[0],flag = 1;
cout<<num<<'\n';
vector<char> temp;
char s = num[0];
for(i=3;i<num.size();i++){
if(num[i] == '|'){
mp[s].push_back(temp);
temp.clear();
}
else temp.push_back(num[i]);
}
mp[s].push_back(temp);
}
map<char,set<char>> fmp;
for(auto q : mp){
ss.clear();
35
dfs(q.first,q.first,q.first,mp);
for(auto g : ss) fmp[q.first].insert(g);
}
cout<<'\n';
cout<<"FIRST: "<<'\n';
for(auto q : fmp){
string ans = "";
ans += q.first;
ans += " = {";
for(char r : q.second){
ans += r;
ans += ',';
}
ans.pop_back();
ans+="}";
cout<<ans<<'\n';
}
map<char,set<char>> gmp;
gmp[start].insert('$');
int count = 10;
while(count--){
for(auto q : mp){
for(i=0;i<r.size()-1;i++){
if(r[i]>='A'&&r[i]<='Z'){
if(!(r[i+1]>='A'&&r[i+1]<='Z'))
gmp[r[i]].insert(r[i+1]);
else {
char temp = r[i+1];
int j = i+1;
while(temp>='A'&&temp<='Z'){
if(*fmp[temp].begin()=='e'){
for(auto g : fmp[temp]){
if(g=='e') continue;
gmp[r[i]].insert(g);
}
j++;
if(j<r.size()){
temp = r[j];
if(!(temp>='A'&&temp<='Z
')){
gmp[r[i]].insert(tem
p);
36
break;
}
}
else{
for(auto g :
gmp[q.first]) gmp[r[i]].insert(g);
break;
}
}
else{
for(auto g : fmp[temp]){
}
break;
}
}
}
}
}
if(r[r.size()-1]>='A'&&r[r.size()-1]<='Z'){
for(auto g : gmp[q.first])
}
}
}
}
cout<<'\n';
cout<<"FOLLOW: "<<'\n';
for(auto q : gmp){
string ans = "";
ans += q.first;
ans += " = {";
for(char r : q.second){
ans += r;
ans += ',';
}
ans.pop_back();
ans+="}";
cout<<ans<<'\n';
}
string temp = "";
temp+='.';
temp+=start;
37
deque<char> emp;
deque<char> st;
st.push_back(start);
dfs2('!','k',-1,{emp,st});
cout<<"\nProductions: "<<'\n';
int cc = 1;
set<char> action,go;
map<pair<char,deque<char>>,int> pos;
for(auto q : mp){
go.insert(q.first);
cout<<"r"<<cc<<": ";
string ans = "";
ans += q.first;
ans+="->";
deque<char> temp;
for(auto s : r) ans += s,temp.push_back(s);
pos[{q.first,temp}] = cc;
for(auto s : r){
if(s>='A'&&s<='Z') go.insert(s);
else action.insert(s);
}
cout<<ans<<'\n';
cc++;
}
}
cout<<"\nGraph: "<<'\n';
for(auto mp2 : f){
cout<<'\n';
cout<<"I";
cout<<mp2.first<<": \n";
for(auto q : mp2.second){
string ans = "";
ans += q.first;
ans += "->";
for(auto t : r.first) ans+=t;
ans+='.';
for(auto t : r.second) ans+=t;
ans+='|';
}
ans.pop_back();
for(auto tt : ans){
38
if(tt == '!') cout<<start<<'\'';

else cout<<tt;
}
cout<<'\n';
}
}
cout<<'\n';
cout<<"Edges: "<<'\n';
for(auto q : g){
cout<<"I"<<q.first<<" -> "<<r.second<<" ->
"<<"I"<<r.first<<"\n";
}
}
action.insert('$');
cout<<"\nParsing Table:"<<'\n';
cout<<"St.\t\tAction & Goto"<<'\n';
int tot = f.size();
cout<<" \t";
for(auto q : action) cout<<q<<'\t';
for(auto q : go) cout<<q<<'\t';
cout<<'\n';
for(i=0;i<tot;i++){
cout<<"I"<<i<<'\t';
for(auto q : action){
if(g.count(i)){
int flag = 0;
for(auto r : g[i]){
if(r.second == q){
flag = 1;
cout<<"S"<<r.first<<"\t";
break;
}
}
if(!flag) cout<<"-"<<'\t';
}
else{
int flag = 0;
for(auto r : f[i]){
if(r.first == '!'){
if(q == '$'){
cout<<"AC\t";
flag = 1;
}
else cout<<"-\t";
39
}
if(!flag){
for(auto r : f[i]){
char ccc = r.first;
deque<char> chk =
(*r.second.begin()).first;
int cou = 1;
for(auto r : gmp[ccc]){
if(q == r){
cout<<"r"<<pos[{ccc,chk}]<<"\t";
}
cou++;
}
}
}
}
}
for(auto q : go){
if(g.count(i)){
int flag = 0;
for(auto r : g[i]){
if(r.second == q){
flag = 1;
cout<<r.first<<"\t";
break;
}
}
if(!flag) cout<<"-"<<'\t';
}
else{
cout<<"-"<<'\t';
}
}
cout<<'\n';
}
return 0;
}
40
Output:
41
Q- Program to find First and Follow.

Code:
from re import *
from collections import OrderedDict
t_list=OrderedDict()
nt_list=OrderedDict()
production_list=[]
class Terminal:
def __init__(self, symbol):
self.symbol=symbol
def __str__(self):
return self.symbol
class NonTerminal:
def __init__(self, symbol):
self.symbol=symbol
self.first=set()
self.follow=set()
def __str__(self):
return self.symbol
def add_first(self, symbols): self.first |= set(symbols)
#union operation
def add_follow(self, symbols): self.follow |= set(symbols)
def compute_first(symbol):
global production_list, nt_list, t_list
if symbol in t_list:
return set(symbol)
for prod in production_list:
head, body=prod.split('->')
if head!=symbol: continue
if body=='':
nt_list[symbol].add_first(chr(1013))
continue
for i, Y in enumerate(body):
if body[i]==symbol: continue
t=compute_first(Y)
nt_list[symbol].add_first(t-set(chr(1013)))
if chr(1013) not in t:
break
if i==len(body)-1:
nt_list[symbol].add_first(chr(1013))
return nt_list[symbol].first
def get_first(symbol):
return compute_first(symbol)
def compute_follow(symbol):
42

if symbol == list(nt_list.keys())[0]:
nt_list[symbol].add_follow('$')
for i, B in enumerate(body):
if B != symbol: continue
if i != len(body)-1:
nt_list[symbol].add_follow(get_first(body[i+1])
- set(chr(1013)))
if i == len(body)-1 or chr(1013) in
get_first(body[i+1]) and B != head:
nt_list[symbol].add_follow(get_follow(head))
def get_follow(symbol):
global nt_list, t_list
if symbol in t_list.keys():
return None
return nt_list[symbol].follow
def main(pl=None):
print('''Enter the grammar productions (enter 'end' or
return to stop)
#(Format: "A->Y1Y2..Yn" {Yi - single char} OR "A->"
{epsilon})''')
global production_list, t_list, nt_list
ctr=1
if pl==None:
while True:
production_list.append(input().replace(' ', ''))
if production_list[-1].lower() in ['end', '']:
del production_list[-1]
break
head, body=production_list[ctr-1].split('->')
if head not in nt_list.keys():
nt_list[head]=NonTerminal(head)
for i in body:
if not 65<=ord(i)<=90:
if i not in t_list.keys():
t_list[i]=Terminal(i)
elif i not in nt_list.keys():
nt_list[i]=NonTerminal(i)
ctr+=1
return pl,production_list
if __name__=='__main__':
main()
43
Q- Implement LALR Parser:

Code: Using above Program to find first and follow
"""
////////////////////////////////////////////////////
// //
// //
////////////////////////////////////////////////////
"""
from graphviz import Digraph
import firstfollow
from firstfollow import production_list, nt_list as ntl, t_list
as tl
nt_list, t_list=[], []
dot = Digraph(comment='DFA for LALR')
class State:
_id=0
def __init__(self, closure):
self.closure=closure
self.no=State._id
State._id+=1
class Item(str):
def __new__(cls, item, lookahead=list()):
self=str.__new__(cls, item)
self.lookahead=lookahead
return self
def __str__(self):
return super(Item, self).__str__()+",
"+'|'.join(self.lookahead)
def closure(items):
def exists(newitem, items):
for i in items:
if i==newitem and
sorted(set(i.lookahead))==sorted(set(newitem.lookahead)):
return True
return False
global production_list
while True:
flag=0
for i in items:
if i.index('.')==len(i)-1: continue
Y=i.split('->')[1].split('.')[1][0]
if i.index('.')+1<len(i)-1:
44
lastr=list(firstfollow.compute_first(i[i.index('
.')+2])-set(chr(1013)))
else:
lastr=i.lookahead
if head!=Y: continue
newitem=Item(Y+'->.'+body, lastr)
if not exists(newitem, items):
items.append(newitem)
flag=1
if flag==0: break
return items
def goto(items, symbol):
dot.node(symbol,str(items))
initial=[]
for i in items:
head, body=i.split('->')
seen, unseen=body.split('.')
if unseen[0]==symbol and len(unseen) >= 1:
initial.append(Item(head+'-
>'+seen+unseen[0]+'.'+unseen[1:], i.lookahead))
return closure(initial)
def calc_states():
def contains(states, t):
for s in states:
if len(s) != len(t): continue
if sorted(s)==sorted(t):
for i in range(len(s)):
if s[i].lookahead!=t[i].lookahead: break
else: return True
return False
head, body=production_list[0].split('->')
states=[closure([Item(head+'->.'+body, ['$'])])]
45
while True:
flag=0
for s in states:
for e in nt_list+t_list:
t=goto(s, e)
if t == [] or contains(states, t): continue
states.append(t)
flag=1
if not flag: break
return states
def make_table(states):
def getstateno(t):
for s in states:
if len(s.closure) != len(t): continue
if sorted(s.closure)==sorted(t):
for i in range(len(s.closure)):
if
s.closure[i].lookahead!=t[i].lookahead: break
else: return s.no
return -1
def getprodno(closure):
closure=''.join(closure).replace('.', '')
return production_list.index(closure)
SLR_Table=OrderedDict()
for i in range(len(states)):
states[i]=State(states[i])
46
for s in states:
SLR_Table[s.no]=OrderedDict()
for item in s.closure:

head, body=item.split('->')
if body=='.':
for term in item.lookahead:
if term not in SLR_Table[s.no].keys():
SLR_Table[s.no][term]={'r'+str(getprodno
(item))}
else: SLR_Table[s.no][term] |=
{'r'+str(getprodno(item))}
continue
nextsym=body.split('.')[1]
if nextsym=='':
if getprodno(item)==0:
SLR_Table[s.no]['$']='accept'
else:
SLR_Table[s.no][term]={'r'+str(getpr
odno(item))}
continue
nextsym=nextsym[0]
t=goto(s.closure, nextsym)
if t != []:
if nextsym in t_list:
if nextsym not in SLR_Table[s.no].keys():
SLR_Table[s.no][nextsym]={'s'+str(getsta
teno(t))}
else: SLR_Table[s.no][nextsym] |=
{'s'+str(getstateno(t))}
else: SLR_Table[s.no][nextsym] =
str(getstateno(t))
return SLR_Table
def augment_grammar():
47
for i in range(ord('Z'), ord('A')-1, -1):

if chr(i) not in nt_list:
start_prod=production_list[0]
production_list.insert(0, chr(i)+'-
>'+start_prod.split('->')[0])
return
#global production_list, ntl, nt_list, tl, t_list
pl,prod_list = firstfollow.main()
pro = prod_list.copy()
for nt in ntl:
firstfollow.compute_first(nt)
firstfollow.compute_follow(nt)
print(nt)
print("\tFirst:\t", firstfollow.get_first(nt))
print("\tFollow:\t", firstfollow.get_follow(nt), "\n")
augment_grammar()
nt_list=list(ntl.keys())
t_list=list(tl.keys()) + ['$']
cs=calc_states()
items = []
ctr=0
m = [ ]
for s in cs:
items.append(str(ctr))
ctr+=1
check = []
count = 0
ind = []
for i in cs:
if i not in check:
check.append(i)
else:
ind.append(count)
count += 1
merge_ind = []
48
combine = []
for i in ind:
if cs[i] in check:
merge_ind.append(cs.index(cs[i]))
combine.append(str(cs.index(cs[i]))+str(i))
for i in range(len(combine)):
combine.append("s"+combine[i])
#for i in cs:
#for j in i:
#print(j,j.lookahead)
table=make_table(cs)
sym_list = nt_list + t_list
for i in ind:
val = ind.index(i)
for j in table[i]:
if j not in table[int(merge_ind[val])]:
table[int(merge_ind[val])][j] = table[i][j]
table.pop(i)
for i in range(len(ind)):
s_list = []
s = "s" + str(ind[i])
s_list.append(s)
ind.append(set(s_list))
for i in range(len(merge_ind)):
s_list = []
s = "s" + str(merge_ind[i])
s_list.append(s)
merge_ind.append(set(s_list))
for i in range(0,int(len(merge_ind)/2)):
merge_ind[i] = str(merge_ind[i])
ind[i] = str(ind[i])
for i in table:
for j in table[i]:
if (table[i][j] in ind):
ind1 = ind.index(table[i][j])
49
table[i][j] = combine[ind1]
elif (table[i][j] in merge_ind):
ind1 = merge_ind.index(table[i][j])
table[i][j] = combine[ind1]
for i in items:
if i in merge_ind:
indexof = merge_ind.index(i)
c = combine[indexof]
j = ind[indexof]
j_ind = items.index(j)
items.pop(j_ind)
item_index = items.index(i)
items.pop(item_index)
items.insert(item_index,c)
print()
print("*******----STRING-----**********")
print()
lookahead = []
ctr = 0
for s in check:
string = []
st=[]
if items[ctr] in combine:
com_ind = combine.index(items[ctr])
for j in cs[int(ind[com_ind])].closure:
st.append(j.lookahead)
string_i=[]
for k in s[i].lookahead:
string_i.append(k)
string_i.append(st[i][0])
string.append(string_i)
lookahead.append(string)
else:
string_i=[]
for k in s[i].lookahead:
string_i.append(k)
string.append(string_i)
lookahead.append(string)
ctr+=1
50
ctr = 0
for s in check:
print("Item {}:".format(items[ctr]))
string = ""
string += s[i]
string += " "
string += str(lookahead[ctr][i])
string += "\n"
print(string)
if len(items[ctr]) == 2:
for j in table[int(items[ctr][0])]:
if isinstance(table[int(items[ctr][0])][j],set):
pass
elif table[int(items[ctr][0])][j][0] == "s":
print(j,"->",table[int(items[ctr][0])][j][1:])
else:
print(j,"->",table[int(items[ctr][0])][j])
else:
for j in table[int(items[ctr])]:
if isinstance(table[int(items[ctr])][j],set):
pass
elif table[int(items[ctr][0])][j][0] == "s":
print(j,"->",table[int(items[ctr])][j][1:])
else:
print(j,"->",table[int(items[ctr])][j])
print()
ctr+=1
dis_arr = []
print("*******----PARSING TABLE-----**********")
print('_________________________________________________________
____________')
print("LALR(1) TABLE")
sr, rr=0, 0
print("\t GOTO \t\t ACTION")
print('_________________________________________________________
___________')
print('\t| ','\t| '.join(sym_list),'\t\t|')
print('_________________________________________________________
____________')
for i, j in table.items():
inti = str(i)
if inti in merge_ind:
51
inti = combine[merge_ind.index(inti)]
print(inti, "\t| ", '\t| '.join(list(j.get(sym,' ') if

type(j.get(sym))in (str , None) else next(iter(j.get(sym,'
'))) for sym in sym_list)),'\t\t|')
s, r=0, 0
dis_arr.append(inti)
for p in j.values():
if p!='accept' and len(p)>1:
p=list(p)
if('r' in p[0]): r+=1
else: s+=1
if('r' in p[1]): r+=1
else: s+=1
if r>0 and s>0: sr+=1
elif r>0: rr+=1
print('_________________________________________________________
____________')
print()
dfa={}
counter = 0
for i,j in table.items():
od={}
for k,l in j.items():
if isinstance(l,set):
od[k]=''.join(l)
elif l.isdigit():
od[k]=int(l)
else:
od[k]=l
dfa[dis_arr[counter]]=od
counter+=1
print("*******----STRING PARSING-----**********")
print()
string=input('Enter string to parse: ')
string+='$'
stack=['0']
pointer=0
try:
while True:
lookahead=string[pointer]
if dfa[stack[-1]][lookahead][0] =='s':
act = dfa[stack[-1]][lookahead][1:]
stack.append(lookahead)
52
stack.append(act)
print(stack)
pointer+=1
elif dfa[stack[-1]][lookahead][0] =='r':
r_no=int(dfa[stack[-1]][lookahead][1])
to_pop=pro[r_no-1][3:]
for i in range(2*len(to_pop)):
stack.pop()
stack.append(pro[r_no-1][0])
stack.append(str(dfa[stack[-2]][pro[r_no-1][0]]))
print(stack)
elif dfa[stack[-1]][lookahead] =='accept':

print('Accepted')
break
except:
print('Not Accepted')
Output:
53
54
Q- Implement CLR Parser:

Code: Using above Program to find first and follow
"""
////////////////////////////////////////////////////
// //
// //
////////////////////////////////////////////////////
"""
from collections import deque
from pprint import pprint
import firstfollow
from firstfollow import production_list, nt_list as ntl, t_list
as tl
nt_list, t_list=[], []
class State:
_id=0
def __init__(self, closure):
self.closure=closure
self.no=State._id
State._id+=1
class Item(str):
def __new__(cls, item, lookahead=list()):
self=str.__new__(cls, item)
self.lookahead=lookahead
return self
def __str__(self):
return super(Item, self).__str__()+",
"+'|'.join(self.lookahead)
def closure(items):
def exists(newitem, items):
for i in items:
if i==newitem and
sorted(set(i.lookahead))==sorted(set(newitem.lookahead)):
return True
return False
while True:
flag=0
for i in items:
Y=i.split('->')[1].split('.')[1][0]
if i.index('.')+1<len(i)-1:
55
lastr=list(firstfollow.compute_first(i[i.index('
.')+2])-set(chr(1013)))
else:
lastr=i.lookahead
if head!=Y: continue
newitem=Item(Y+'->.'+body, lastr)
if not exists(newitem, items):
items.append(newitem)
flag=1
if flag==0: break
return items
def goto(items, symbol):
initial=[]
for i in items:
head, body=i.split('->')
seen, unseen=body.split('.')
if unseen[0]==symbol and len(unseen) >= 1:
initial.append(Item(head+'-
>'+seen+unseen[0]+'.'+unseen[1:], i.lookahead))
return closure(initial)
def calc_states():
def contains(states, t):
for s in states:
if len(s) != len(t): continue
if sorted(s)==sorted(t):
if s[i].lookahead!=t[i].lookahead: break
else: return True
return False
head, body=production_list[0].split('->')
states=[closure([Item(head+'->.'+body, ['$'])])]
while True:
flag=0
for s in states:
for e in nt_list+t_list:
t=goto(s, e)
if t == [] or contains(states, t): continue
states.append(t)
flag=1
if not flag: break
56
return states
def make_table(states):
def getstateno(t):
for s in states:
if len(s.closure) != len(t): continue
if sorted(s.closure)==sorted(t):
for i in range(len(s.closure)):
if
s.closure[i].lookahead!=t[i].lookahead: break
else: return s.no
return -1
def getprodno(closure):
closure=''.join(closure).replace('.', '')
return production_list.index(closure)
SLR_Table=OrderedDict()
for i in range(len(states)):
states[i]=State(states[i])
for s in states:
SLR_Table[s.no]=OrderedDict()
for item in s.closure:
head, body=item.split('->')
if body=='.':
SLR_Table[s.no][term]={'r'+str(getprodno
(item))}
continue
nextsym=body.split('.')[1]
if nextsym=='':
if getprodno(item)==0:
SLR_Table[s.no]['$']='accept'
else:
SLR_Table[s.no][term]={'r'+str(getpr
odno(item))}
continue
nextsym=nextsym[0]
t=goto(s.closure, nextsym)
if t != []:
57
if nextsym in t_list:
if nextsym not in SLR_Table[s.no].keys():
SLR_Table[s.no][nextsym]={'s'+str(getsta
teno(t))}
else: SLR_Table[s.no][nextsym] |=
{'s'+str(getstateno(t))}
else: SLR_Table[s.no][nextsym] =
str(getstateno(t))
return SLR_Table
def augment_grammar():
for i in range(ord('Z'), ord('A')-1, -1):
if chr(i) not in nt_list:
start_prod=production_list[0]
production_list.insert(0, chr(i)+'-
>'+start_prod.split('->')[0])
return
def main():
global production_list, ntl, nt_list, tl, t_list
firstfollow.main()
print("\tFIRST AND FOLLOW OF NON-TERMINALS")
for nt in ntl:
firstfollow.compute_first(nt)
firstfollow.compute_follow(nt)
print(nt)
print("\tFirst:\t", firstfollow.get_first(nt))
print("\tFollow:\t", firstfollow.get_follow(nt), "\n")
augment_grammar()
nt_list=list(ntl.keys())
t_list=list(tl.keys()) + ['$']
print(nt_list)
print(t_list)
j=calc_states()
ctr=0
for s in j:
print("Item{}:".format(ctr))
for i in s:
print("\t", i)
ctr+=1
table=make_table(j)
print('_____________________________________________________
________________')
print("\n\tCLR(1) TABLE\n")
sr, rr=0, 0
58
print('_____________________________________________________
________________')
print('\t| ','\t| '.join(sym_list),'\t\t|')
print('_____________________________________________________
________________')
for i, j in table.items():
print(i, "\t| ", '\t| '.join(list(j.get(sym,' ') if
type(j.get(sym))in (str , None) else next(iter(j.get(sym,'
'))) for sym in sym_list)),'\t\t|')
s, r=0, 0
for p in j.values():
if p!='accept' and len(p)>1:
p=list(p)
if('r' in p[0]): r+=1
else: s+=1
if('r' in p[1]): r+=1
else: s+=1
if r>0 and s>0: sr+=1
elif r>0: rr+=1
print('_____________________________________________________
________________')
print("\n", sr, "s/r conflicts |", rr, "r/r conflicts")
print('_____________________________________________________
________________')
print("Enter the string to be parsed")
Input=input()+'$'
try:
stack=['0']
a=list(table.items())
'''print(a[int(stack[-1])][1][Input[0]])
b=list(a[int(stack[-1])][1][Input[0]])
print(b[0][0])
print(a[0][1]["S"])'''
print("productions\t:",production_list)
print('stack',"\t \t\t \t",'Input')
print(*stack,"\t \t\t \t",*Input,sep="")
while(len(Input)!=0):
b=list(a[int(stack[-1])][1][Input[0]])
if(b[0][0]=="s" ):
#s=Input[0]+b[0][1:]
stack.append(Input[0])
stack.append(b[0][1:])
Input=Input[1:]
elif(b[0][0]=="r" ):
59
s=int(b[0][1:])
#print(len(production_list),s)
l=len(production_list[s])-3
#print(l)
prod=production_list[s]
l*=2
l=len(stack)-l
stack=stack[:l]
s=a[int(stack[-1])][1][prod[0]]
#print(s,b)
stack+=list(prod[0])
stack.append(s)
elif(b[0][0]=="a"):
print("\n\tString Accepted\n")
break
except:
print('\n\tString INCORRECT for given Grammar!\n')
return
if __name__=="__main__":
main()
Output :
60
61

Compiler Design Lab

Uploaded by

Copyright:

Available Formats

Compiler Design Lab

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Compiler Design Lab

Uploaded by

Copyright:

Available Formats

Shivam Bindal (BT19CSE008)

Compiler Design Lab

Department of Computer Science Engineering

National Institute of Technology,

Submitted by: Shivam Bindal (BT19CSE008)

S.No Program Name Date

Q- Implement LL1 parser with input Grammar.

for(ap = 0;ap < sid; ap++){

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

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

void followfirst(char c, int c1 , int c2)

Q- Take input as grammar and check if a string gets accepted or not.

// Parsing the grammar file

cout<<"Grammar parsed from grammar file: \n";

char lhs = buffer[0];

// Gather all non terminals

// Start symbol is first non terminal production in grammar

map< char, set<char> > firsts;

cout<<"Firsts list: \n";

map< char, set<char> > follows;

cout<<"Follows list: \n";

for(auto ch = next_list.begin(); ch != next_list.end();

cout<<"Collision at ["<<row<<"]["<<col<<"] for

// Check if input string is valid

// cout<<"Processing input string\n";

void find_first(vector< pair<char, string> > gram,

// cout<<"Finding firsts of "<<non_term<<"\n";

for(auto it = gram.begin(); it != gram.end(); ++it) {

// Remove epsilon from firsts if not the last

// Append firsts of that variable

void find_follow(vector< pair<char, string> > gram,

// cout<<"Finding follow of "<<non_term<<"\n";

for(auto it = gram.begin(); it != gram.end(); ++it) {

// finished is true when finding follow from this

// Skip variables till reqd non terminal

for(;ch != it->second.end() && !finished; ++ch) {

// If end of production, follow same as follow of

Q- Implement LR(0) Parser:

# (i) Stack -------------------------

#--------------------Stack Defn ENDS ---------------------------

if(l >= st.length()):

print("state Transitions : ")

parseTable = [ ['-' for i in range(len(symbols))] for j in

string = input("String : ")

Q- Implement SLR(1) Parser:

int num = -1;

if(tt == '!') cout<<start<<'\'';

Q- Program to find First and Follow.

global production_list, nt_list, t_list

Q- Implement LALR Parser:

def contains(states, t):

global production_list, nt_list, t_list

if t == [] or contains(states, t): continue

if not flag: break

global nt_list, t_list

for item in s.closure:

for i in range(ord('Z'), ord('A')-1, -1):

#global production_list, ntl, nt_list, tl, t_list