Notes

# 1.lexical analyzer



file = open("add.c", 'r')
lines = file.readlines()
keywords = ["void", "main", "int", "float", "bool", "if", "for", "else", "while", "char", "return"]
operators = ["=", "==", "+", "-", "*", "/", "++", "--", "+=", "-=", "!=", "||", "&&"]
punctuations= [";", "(", ")", "{", "}", "[", "]"]
def is_int(x):
try:
int(x)
return True
except:
return False
for line in lines:
for i in line.strip().split(" "):
if i in keywords:
print (i, " is a keyword")
elif i in operators:
print (i, " is an operator")
elif i in punctuations:
print (i, " is a punctuation")
elif is_int(i):
print (i, " is a number")
else:
print (i, " is an identifier")




#2.RE TO NFA




transition_table = [ [0]*3 for _ in range(20) ]
re = input("Enter the regular expression : ")
re += " "
i = 0
j = 1
while(i<len(re)):
if re[i] == 'a':
try:
if re[i+1] != '|' and re[i+1] !='*':
transition_table[j][0] = j+1
j += 1
elif re[i+1] == '|' and re[i+2] =='b':
transition_table[j][2]=((j+1)*10)+(j+3)
j+=1
transition_table[j][0]=j+1
j+=1
transition_table[j][2]=j+3
j+=1
transition_table[j][1]=j+1
j+=1
transition_table[j][2]=j+1
j+=1
i=i+2
elif re[i+1]=='*':
transition_table[j][2]=((j+1)*10)+(j+3)
j+=1
transition_table[j][0]=j+1
j+=1
transition_table[j][2]=((j+1)*10)+(j-1)
j+=1
except:
transition_table[j][0] = j+1
elif re[i] == 'b':
try:
if re[i+1] != '|' and re[i+1] !='*':
transition_table[j][1] = j+1
j += 1
elif re[i+1]=='|' and re[i+2]=='a':
transition_table[j][2]=((j+1)*10)+(j+3)
j+=1
transition_table[j][1]=j+1
j+=1
transition_table[j][2]=j+3
j+=1
transition_table[j][0]=j+1
j+=1
transition_table[j][2]=j+1
j+=1
i=i+2
elif re[i+1]=='*':
transition_table[j][2]=((j+1)*10)+(j+3)
j+=1
transition_table[j][1]=j+1
j+=1
transition_table[j][2]=((j+1)*10)+(j-1)
j+=1
except:
transition_table[j][1] = j+1
elif re[i]=='e' and re[i+1]!='|'and re[i+1]!='*':
transition_table[j][2]=j+1
j+=1
elif re[i]==')' and re[i+1]=='*':
transition_table[0][2]=((j+1)*10)+1
transition_table[j][2]=((j+1)*10)+1
j+=1
i +=1
print ("Transition function:")
for i in range(j):
if(transition_table[i][0]!=0):
print("q[{0},a]-->{1}".format(i,transition_table[i][0]))
if(transition_table[i][1]!=0):
print("q[{0},b]-->{1}".format(i,transition_table[i][1]))
if(transition_table[i][2]!=0):
if(transition_table[i][2]<10):
print("q[{0},e]-->{1}".format(i,transition_table[i][2]))
else:
print("q[{0},e]-->{1} &
{2}".format(i,int(transition_table[i][2]/10),transition_table[i][2]%10))
# INPUT : (a|b)*abb




#3.CONVERSION OF NFA TO DFA




import pandas as pd
nfa = {}
n = int(input("No. of states : "))
t = int(input("No. of transitions : "))
for i in range(n):
state = input("state name : ")
nfa[state] = {}
for j in range(t):
path = input("path : ")
print("Enter end state from state {} travelling through path {} : ".format(state, path))
reaching_state = [x for x in input().split()]
nfa[state][path] = reaching_state
print("nNFA :- n")
print(nfa)
print("nPrinting NFA table :- ")
nfa_table = pd.DataFrame(nfa)
print(nfa_table.transpose())
print("Enter final state of NFA : ")
nfa_final_state = [x for x in input().split()]
new_states_list = []
dfa = {}
keys_list = list(
list(nfa.keys())[0])
path_list = list(nfa[keys_list[0]].keys())
dfa[keys_list[0]] = {}
for y in range(t):
var = "".join(nfa[keys_list[0]][
path_list[y]])
dfa[keys_list[0]][path_list[y]] = var
if var not in keys_list:
new_states_list.append(var)
keys_list.append(var)
while len(new_states_list) != 0:
dfa[new_states_list[0]] = {}
for _ in range(len(new_states_list[0])):
for i in range(len(path_list)):
temp = []
for j in range(len(new_states_list[0])):
temp += nfa[new_states_list[0][j]][path_list[i]]
s = ""
s = s.join(temp)
if s not in keys_list:
new_states_list.append(s)
keys_list.append(s)
dfa[new_states_list[0]][path_list[i]] = s
new_states_list.remove(new_states_list[0])
print("nDFA :- n")
print(dfa)
print("nPrinting DFA table :- ")
dfa_table = pd.DataFrame(dfa)
print(dfa_table.transpose())
dfa_states_list = list(dfa.keys())
dfa_final_states = []
for x in dfa_states_list:
for i in x:
if i in nfa_final_state:
dfa_final_states.append(x)
break
print("nFinal states of the DFA are : ", dfa_final_states)
INPUT :
No. of states : 3
No. of transitions : 2
state name : A
path : 0
Enter end state from state A travelling through path 0 :
A
path : 1
Enter end state from state A travelling through path 1 :
A B
state name : B
path : 0
Enter end state from state B travelling through path 0 :
C
path : 1
Enter end state from state B travelling through path 1 :
C
state name : C
path : 0
Enter end state from state C travelling through path 0 :
path : 1
Enter end state from state C travelling through path 1 :
NFA :-
{'A': {'0': ['A'], '1': ['A', 'B']}, 'B': {'0': ['C'], '1': ['C']}, 'C': {'0': [], '1': []}}
Printing NFA table :-
0 1
A [A] [A, B]
B [C] [C]
C [] []
Enter final state of NFA :
C



#4A.ELIMINATION OF LEFT RECURSION




#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main()
{
int n;
cout<<"nEnter number of non terminals: ";
cin>>n;
cout<<"nEnter non terminals one by one: ";
int i;
vector<string> nonter(n);
vector<int> leftrecr(n,0);
for(i=0;i<n;++i) {
cout<<"nNon terminal "<<i+1<<" : ";
cin>>nonter[i];
}
vector<vector<string> > prod;
cout<<"nEnter '^' for null";
for(i=0;i<n;++i) {
cout<<"nNumber of "<<nonter[i]<<" productions: ";
int k;
cin>>k;
int j;
cout<<"nOne by one enter all "<<nonter[i]<<" productions";
vector<string> temp(k);
for(j=0;j<k;++j) {
cout<<"nRHS of production "<<j+1<<": ";
string abc;
cin>>abc;
temp[j]=abc;
if(nonter[i].length()<=abc.length()&&nonter[i].compare(abc.substr(0,nonter[i].length()))==0)
leftrecr[i]=1;
}
prod.push_back(temp);
}
for(i=0;i<n;++i) {
cout<<leftrecr[i];
}
for(i=0;i<n;++i) {
if(leftrecr[i]==0)
continue;
int j;
nonter.push_back(nonter[i]+"'");
vector<string> temp;
for(j=0;j<prod[i].size();++j) {
if(nonter[i].length()<=prod[i][j].length()&&nonter[i].compare(prod[i][j].substr(0,nonter[i].length
()))==0) {
string
abc=prod[i][j].substr(nonter[i].length(),prod[i][j].length()-nonter[i].length())+nonter[i]+"'";
temp.push_back(abc);
prod[i].erase(prod[i].begin()+j);
--j;
}
else {
prod[i][j]+=nonter[i]+"'";
}
}
temp.push_back("^");
prod.push_back(temp);
}
cout<<"nn";
cout<<"nNew set of non-terminals: ";
for(i=0;i<nonter.size();++i)
cout<<nonter[i]<<" ";
cout<<"nnNew set of productions: ";
for(i=0;i<nonter.size();++i) {
int j;
for(j=0;j<prod[i].size();++j) {
cout<<"n"<<nonter[i]<<" -> "<<prod[i][j];
}
}
return 0;
}



#4B LEFT FACTORING




#include <iostream>
#include <math.h>
#include <vector>
#include <string>
#include <stdlib.h>
using namespace std;
int main()
{
cout<<"nEnter number of productions: ";
int p;
cin>>p;
vector<string> prodleft(p),prodright(p);
cout<<"nEnter productions one by one: ";
int i;
for(i=0;i<p;++i) {
cout<<"nLeft of production "<<i+1<<": ";
cin>>prodleft[i];
cout<<"nRight of production "<<i+1<<": ";
cin>>prodright[i];
}
int j;
int e=1;
for(i=0;i<p;++i) {
for(j=i+1;j<p;++j) {
if(prodleft[j]==prodleft[i]) {
int k=0;
string com="";
while(k<prodright[i].length()&&k<prodright[j].length()&&prodright[i][k]==prodright[j][k]) {
com+=prodright[i][k];
++k;
}
if(k==0)
continue;
char* buffer;
string comleft=prodleft[i];
if(k==prodright[i].length()) {
prodleft[i]+=string(itoa(e,buffer,10));
prodleft[j]+=string(itoa(e,buffer,10));
prodright[i]="^";
prodright[j]=prodright[j].substr(k,prodright[j].length()-k);
}
else if(k==prodright[j].length()) {
prodleft[i]+=string(itoa(e,buffer,10));
prodleft[j]+=string(itoa(e,buffer,10));
prodright[j]="^";
prodright[i]=prodright[i].substr(k,prodright[i].length()-k);
}
else {
prodleft[i]+=string(itoa(e,buffer,10));
prodleft[j]+=string(itoa(e,buffer,10));
prodright[j]=prodright[j].substr(k,prodright[j].length()-k);
prodright[i]=prodright[i].substr(k,prodright[i].length()-k);
}
int l;
for(l=j+1;l<p;++l) {
if(comleft==prodleft[l]&&com==prodright[l].substr(0,fmin(k,prodright[l].length()))) {
prodleft[l]+=string(itoa(e,buffer,10));
prodright[l]=prodright[l].substr(k,prodright[l].length()-k);
}
}
prodleft.push_back(comleft);
prodright.push_back(com+prodleft[i]);
++p;
++e;
}
}
}
cout<<"nnNew productions";
for(i=0;i<p;++i) {
cout<<"n"<<prodleft[i]<<"->"<<prodright[i];
}
return 0; }


#5.FIRST AND FOLLOW




import re
import string
import pandas as pd
def parse(user_input,start_symbol,parsingTable):
#flag
flag = 0
#appending dollar to end of input
user_input = user_input + "$"
stack = []
stack.append("$")
stack.append(start_symbol)
input_len = len(user_input)
index = 0
while len(stack) > 0:
#element at top of stack
top = stack[len(stack)-1]
print ("Top =>",top)
#current input
current_input = user_input[index]
print ("Current_Input => ",current_input)
if top == current_input:
stack.pop()
index = index + 1
else:
#finding value for key in table
key = top , current_input
print (key)
#top of stack terminal => not accepted
if key not in parsingTable:
flag = 1
break
value = parsingTable[key]
if value !='@':
value = value[::-1]
value = list(value)
#poping top of stack
stack.pop()
#push value chars to stack
for element in value:
stack.append(element)
else:
stack.pop()
if flag == 0:
print ("String accepted!")
else:
print ("String not accepted!")
def ll1(follow, productions):
print ("nParsing Tablen")
table = {}
for key in productions:
for value in productions[key]:
if value!='@':
for element in first(value, productions):
table[key, element] = value
else:
for element in follow[key]:
table[key, element] = value
for key,val in table.items():
print (key,"=>",val)
new_table = {}
for pair in table:
new_table[pair[1]] = {}
for pair in table:
new_table[pair[1]][pair[0]] = table[pair]
print ("n")
print ("nParsing Table in matrix formn")
print (pd.DataFrame(new_table).fillna('-'))
print ("n")
return table
def follow(s, productions, ans):
if len(s)!=1 :
return {}
for key in productions:
for value in productions[key]:
f = value.find(s)
if f!=-1:
if f==(len(value)-1):
if key!=s:
if key in ans:
temp = ans[key]
else:
ans = follow(key, productions, ans)
temp = ans[key]
ans[s] = ans[s].union(temp)
else:
first_of_next = first(value[f+1:], productions)
if '@' in first_of_next:
if key!=s:
if key in ans:
temp = ans[key]
else:
ans = follow(key, productions, ans)
temp = ans[key]
ans[s] = ans[s].union(temp)
ans[s] = ans[s].union(first_of_next) - {'@'}
else:
ans[s] = ans[s].union(first_of_next)
return ans
def first(s, productions):
c = s[0]
ans = set()
if c.isupper():
for st in productions[c]:
if st == '@' :
if len(s)!=1 :
ans = ans.union( first(s[1:], productions) )
else :
ans = ans.union('@')
else :
f = first(st, productions)
ans = ans.union(x for x in f)
else:
ans = ans.union(c)
return ans
if __name__=="__main__":
productions=dict()
grammar = open("grammar2", "r")
first_dict = dict()
follow_dict = dict()
flag = 1
start = ""
for line in grammar:
l = re.split("( |->|n|||)*", line)
lhs = l[0]
rhs = set(l[1:-1])-{''}
if flag :
flag = 0
start = lhs
productions[lhs] = rhs
print ('nFirstn')
for lhs in productions:
first_dict[lhs] = first(lhs, productions)
for f in first_dict:
print (str(f) + " : " + str(first_dict[f]))
print ("")
print ('nFollown')
for lhs in productions:
follow_dict[lhs] = set()
follow_dict[start] = follow_dict[start].union('$')
for lhs in productions:
follow_dict = follow(lhs, productions, follow_dict)
for lhs in productions:
follow_dict = follow(lhs, productions, follow_dict)
for f in follow_dict:
print (str(f) + " : " + str(follow_dict[f]))
ll1Table = ll1(follow_dict, productions)
#parse("a*(a+a)",start,ll1Table)
parse("ba=a+23",start,ll1Table)
# tp(ll1Table)


#6.PREDICTIVE PARSING



#include<stdio.h>
#include<conio.h>
#include<string.h>
void main()
{
char fin[10][20],st[10][20],ft[20][20],fol[20][20];
int a=0,e,i,t,b,c,n,k,l=0,j,s,m,p;
clrscr();
printf("enter the no. of nonterminalsn");
scanf("%d",&n);
printf("enter the productions in a grammarn");
for(i=0;i<n;i++)
scanf("%s",st[i]);
for(i=0;i<n;i++)
fol[i][0]='';
for(s=0;s<n;s++)
{
for(i=0;i<n;i++)
{
j=3;
l=0;
a=0;
l1:if(!((st[i][j]>64)&&(st[i][j]<91)))
{
for(m=0;m<l;m++)
{
if(ft[i][m]==st[i][j])
goto s1;
}
ft[i][l]=st[i][j];
l=l+1;
s1:j=j+1;
}
else
{
if(s>0)
{
while(st[i][j]!=st[a][0])
{
a++;
}
b=0;
while(ft[a][b]!='')
{
for(m=0;m<l;m++)
{
if(ft[i][m]==ft[a][b])
goto s2;
}
ft[i][l]=ft[a][b];
l=l+1;
s2:b=b+1;
}
}
}
while(st[i][j]!='')
{
if(st[i][j]=='|')
{
j=j+1;
goto l1;
}
j=j+1;
}
ft[i][l]='';
}
}
printf("first n");
for(i=0;i<n;i++)
printf("FIRS[%c]=%sn",st[i][0],ft[i]);
fol[0][0]='$';
for(i=0;i<n;i++)
{
k=0;
j=3;
if(i==0)
l=1;
else
l=0;
k1:while((st[i][0]!=st[k][j])&&(k<n))
{
if(st[k][j]=='')
{
k++;
j=2;
}
j++;
}
j=j+1;
if(st[i][0]==st[k][j-1])
{
if((st[k][j]!='|')&&(st[k][j]!=''))
{
a=0;
if(!((st[k][j]>64)&&(st[k][j]<91)))
{
for(m=0;m<l;m++)
{
if(fol[i][m]==st[k][j])
goto q3;
}
fol[i][l]=st[k][j];
l++;
q3:
}
else
{
while(st[k][j]!=st[a][0])
{
a++;
}
p=0;
while(ft[a][p]!='')
{
if(ft[a][p]!='@')
{
for(m=0;m<l;m++)
{
if(fol[i][m]==ft[a][p])
goto q2;
}
fol[i][l]=ft[a][p];
l=l+1;
}
else
e=1;
q2:p++;
}
if(e==1)
{
e=0;
goto a1;
}
}
}
else
{
a1:c=0;
a=0;
while(st[k][0]!=st[a][0])
{
a++;
}
while((fol[a][c]!='')&&(st[a][0]!=st[i][0]))
{
for(m=0;m<l;m++)
{
if(fol[i][m]==fol[a][c])
goto q1;
}
fol[i][l]=fol[a][c];
l++;
q1:c++;
}
}
goto k1;
}
fol[i][l]='';
}
printf("follow n");
for(i=0;i<n;i++)
printf("FOLLOW[%c]=%sn",st[i][0],fol[i]);
printf("n");
s=0;
for(i=0;i<n;i++)
{
j=3;
while(st[i][j]!='')
{
if((st[i][j-1]=='|')||(j==3))
{
for(p=0;p<=2;p++)
{
fin[s][p]=st[i][p];
}
t=j;
for(p=3;((st[i][j]!='|')&&(st[i][j]!=''));p++)
{
fin[s][p]=st[i][j];
j++;
}
fin[s][p]='';
if(st[i][k]=='@')
{
b=0;
a=0;
while(st[a][0]!=st[i][0])
{
a++;
}
while(fol[a][b]!='')
{
printf("M[%c,%c]=%sn",st[i][0],fol[a][b],fin[s]);
b++;
}
}
else if(!((st[i][t]>64)&&(st[i][t]<91)))
printf("M[%c,%c]=%sn",st[i][0],st[i][t],fin[s]);
else
{
b=0;
a=0;
while(st[a][0]!=st[i][3])
{
a++;
}
while(ft[a][b]!='')
{
printf("M[%c,%c]=%sn",st[i][0],ft[a][b],fin[s]);
b++;
}
}
s++;
}
if(st[i][j]=='|')
j++;
}
}
getch();
}
Output:
Enter the no. of nonterminals
2
Enter the productions in a grammar
S->CC
C->eC | d
First
FIRS[S] = ed
FIRS[C] = ed
Follow
FOLLOW[S] =$
FOLLOW[C] =ed$
M [S , e] =S->CC
M [S , d] =S->CC
M [C , e] =C->eC
M [C , d] =C->d



#7.SHIFT REDUCE PARSER


#include<stdio.h>
#include<conio.h>
#include<string.h>
struct prodn
{
char p1[10];
char p2[10];
};
void main()
{
char input[20],stack[50],temp[50],ch[2],*t1,*t2,*t;
int i,j,s1,s2,s,count=0;
struct prodn p[10];
FILE *fp=fopen("sr_input.txt","r");
stack[0]='';
clrscr();
printf("n Enter the input stringn");
scanf("%s",&input);
while(!feof(fp))
{
fscanf(fp,"%sn",temp);
t1=strtok(temp,"->");
t2=strtok(NULL,"->");
strcpy(p[count].p1,t1);
strcpy(p[count].p2,t2);
count++;
}
i=0;
while(1)
{
if(i<strlen(input))
{
ch[0]=input[i];
ch[1]='';
i++;
strcat(stack,ch);
printf("%sn",stack);
}
for(j=0;j<count;j++)
{
t=strstr(stack,p[j].p2);
if(t!=NULL)
{
s1=strlen(stack);
s2=strlen(t);
s=s1-s2;
stack[s]='';
strcat(stack,p[j].p1);
printf("%sn",stack);
j=-1;
}
}
if(strcmp(stack,"E")==0&&i==strlen(input))
{
printf("n Accepted");
break;
}
if(i==strlen(input))
{
printf("n Not Accepted");
break;
}
}
getch();
}

Input File: sr_input.txt

E->E+E
E->E*E
E->i

Output 1:
Enter the input string
i*i+i
i
E
E*
E*i
E*E
E
E+
E+i
E+E
E

Accepted


#8.LEADING AND TRAILING




#include<iostream.h>
#include<conio.h>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int vars,terms,i,j,k,m,rep,count,temp=-1;
char var[10],term[10],lead[10][10],trail[10][10];
struct grammar
{
int prodno;
char lhs,rhs[20][20];
}gram[50];
void get()
{
cout<<"n------------- LEADING AND TRAILING ---------------n";
cout<<"nEnter the no. of variables : ";
cin>>vars;
cout<<"nEnter the variables : n";
for(i=0;i<vars;i++)
{
cin>>gram[i].lhs;
var[i]=gram[i].lhs;
}
cout<<"nEnter the no. of terminals : ";
cin>>terms;
cout<<"nEnter the terminals : ";
for(j=0;j<terms;j++)
cin>>term[j];
cout<<"n------------- PRODUCTION DETAILS -----------------n";
for(i=0;i<vars;i++)
{
cout<<"nEnter the no. of production of "<<gram[i].lhs<<":";
cin>>gram[i].prodno;
for(j=0;j<gram[i].prodno;j++)
{
cout<<gram[i].lhs<<"->";
cin>>gram[i].rhs[j];
}
}
}
void leading()
{
for(i=0;i<vars;i++)
{
for(j=0;j<gram[i].prodno;j++)
{
for(k=0;k<terms;k++)
{
if(gram[i].rhs[j][0]==term[k])
lead[i][k]=1;
else
{
if(gram[i].rhs[j][1]==term[k])
lead[i][k]=1;
}
}
}
}
for(rep=0;rep<vars;rep++)
{
for(i=0;i<vars;i++)
{
for(j=0;j<gram[i].prodno;j++)
{
for(m=1;m<vars;m++)
{
if(gram[i].rhs[j][0]==var[m])
{
temp=m;
goto out;
}
}
out:
for(k=0;k<terms;k++)
{
if(lead[temp][k]==1)
lead[i][k]=1;
}
}
}
}
}
void trailing()
{
for(i=0;i<vars;i++)
{
for(j=0;j<gram[i].prodno;j++)
{
count=0;
while(gram[i].rhs[j][count]!='x0')
count++;
for(k=0;k<terms;k++)
{
if(gram[i].rhs[j][count-1]==term[k])
trail[i][k]=1;
else
{
if(gram[i].rhs[j][count-2]==term[k])
trail[i][k]=1;
}
}
}
}
for(rep=0;rep<vars;rep++)
{
for(i=0;i<vars;i++)
{
for(j=0;j<gram[i].prodno;j++)
{
count=0;
while(gram[i].rhs[j][count]!='x0')
count++;
for(m=1;m<vars;m++)
{
if(gram[i].rhs[j][count-1]==var[m])
temp=m;
}
for(k=0;k<terms;k++)
{
if(trail[temp][k]==1)
trail[i][k]=1;
}
}
}
}
}
void display()
{
for(i=0;i<vars;i++)
{
cout<<"nLEADING("<<gram[i].lhs<<") = ";
for(j=0;j<terms;j++)
{
if(lead[i][j]==1)
cout<<term[j]<<",";
}
}
cout<<endl;
for(i=0;i<vars;i++)
{
cout<<"nTRAILING("<<gram[i].lhs<<") = ";
for(j=0;j<terms;j++)
{
if(trail[i][j]==1)
cout<<term[j]<<",";
}
}
}
void main()
{
clrscr();
get();
leading();
trailing();
display();
getch();
}


#9.LR(0)



#include<iostream.h>
#include<conio.h>
#include<string.h>
char prod[20][20],listofvar[26]="ABCDEFGHIJKLMNOPQR";
int novar=1,i=0,j=0,k=0,n=0,m=0,arr[30];
int noitem=0;
struct Grammar
{
char lhs;
char rhs[8];
}g[20],item[20],clos[20][10];
int isvariable(char variable)
{
for(int i=0;i<novar;i++)
if(g[i].lhs==variable)
return i+1;
return 0;
}
void findclosure(int z, char a)
{
int n=0,i=0,j=0,k=0,l=0;
for(i=0;i<arr[z];i++)
{
for(j=0;j<strlen(clos[z][i].rhs);j++)
{
if(clos[z][i].rhs[j]=='.' && clos[z][i].rhs[j+1]==a)
{
clos[noitem][n].lhs=clos[z][i].lhs;
strcpy(clos[noitem][n].rhs,clos[z][i].rhs);
char temp=clos[noitem][n].rhs[j];
clos[noitem][n].rhs[j]=clos[noitem][n].rhs[j+1];
clos[noitem][n].rhs[j+1]=temp;
n=n+1;
}
}
}
for(i=0;i<n;i++)
{
for(j=0;j<strlen(clos[noitem][i].rhs);j++)
{
if(clos[noitem][i].rhs[j]=='.' && isvariable(clos[noitem][i].rhs[j+1])>0)
{
for(k=0;k<novar;k++)
{
if(clos[noitem][i].rhs[j+1]==clos[0][k].lhs)
{
for(l=0;l<n;l++)
if(clos[noitem][l].lhs==clos[0][k].lhs &&
strcmp(clos[noitem][l].rhs,clos[0][k].rhs)==0)
break;
if(l==n)
{
clos[noitem][n].lhs=clos[0][k].lhs;
strcpy(clos[noitem][n].rhs,clos[0][k].rhs);
n=n+1;
}
}
}
}
}
}
arr[noitem]=n;
int flag=0;
for(i=0;i<noitem;i++)
{
if(arr[i]==n)
{
for(j=0;j<arr[i];j++)
{
int c=0;
for(k=0;k<arr[i];k++)
if(clos[noitem][k].lhs==clos[i][k].lhs &&
strcmp(clos[noitem][k].rhs,clos[i][k].rhs)==0)
c=c+1;
if(c==arr[i])
{
flag=1;
goto exit;
}
}
}
}
exit:;
if(flag==0)
arr[noitem++]=n;
}
void main()
{
clrscr();
cout<<"ENTER THE PRODUCTIONS OF THE GRAMMAR(0 TO END) :n";
do
{
cin>>prod[i++];
}while(strcmp(prod[i-1],"0")!=0);
for(n=0;n<i-1;n++)
{
m=0;
j=novar;
g[novar++].lhs=prod[n][0];
for(k=3;k<strlen(prod[n]);k++)
{
if(prod[n][k] != '|')
g[j].rhs[m++]=prod[n][k];
if(prod[n][k]=='|')
{
g[j].rhs[m]='';
m=0;
j=novar;
g[novar++].lhs=prod[n][0];
}
}
}
for(i=0;i<26;i++)
if(!isvariable(listofvar[i]))
break;
g[0].lhs=listofvar[i];
char temp[2]={g[1].lhs,''};
strcat(g[0].rhs,temp);
cout<<"nn augumented grammar n";
for(i=0;i<novar;i++)
cout<<endl<<g[i].lhs<<"->"<<g[i].rhs<<" ";
getch();
for(i=0;i<novar;i++)
{
clos[noitem][i].lhs=g[i].lhs;
strcpy(clos[noitem][i].rhs,g[i].rhs);
if(strcmp(clos[noitem][i].rhs,"ε")==0)
strcpy(clos[noitem][i].rhs,".");
else
{
for(int j=strlen(clos[noitem][i].rhs)+1;j>=0;j--)
clos[noitem][i].rhs[j]=clos[noitem][i].rhs[j-1];
clos[noitem][i].rhs[0]='.';
}
}
arr[noitem++]=novar;
for(int z=0;z<noitem;z++)
{
char list[10];
int l=0;
for(j=0;j<arr[z];j++)
{
for(k=0;k<strlen(clos[z][j].rhs)-1;k++)
{
if(clos[z][j].rhs[k]=='.')
{
for(m=0;m<l;m++)
if(list[m]==clos[z][j].rhs[k+1])
break;
if(m==l)
list[l++]=clos[z][j].rhs[k+1];
}
}
}
for(int x=0;x<l;x++)
findclosure(z,list[x]);
}
cout<<"n THE SET OF ITEMS ARE nn";
for(z=0;z<noitem;z++)
{
cout<<"n I"<<z<<"nn";
for(j=0;j<arr[z];j++)
cout<<clos[z][j].lhs<<"->"<<clos[z][j].rhs<<"n";
getch();
}
getch();
}


#10.Intermediate code generation – Quadruple, Triple, Indirect triple



#include<stdio.h>
#include<ctype.h>
#include<stdlib.h>
#include<string.h>
void small();
void dove(int i);
int p[5]={0,1,2,3,4},c=1,i,k,l,m,pi;
char sw[5]={'=','-','+','/','*'},j[20],a[5],b[5],ch[2];
void main()
{
printf("Enter the expression:");
scanf("%s",j);
printf("tThe Intermediate code is:n");
small();
}
void dove(int i)
{
a[0]=b[0]='';
if(!isdigit(j[i+2])&&!isdigit(j[i-2]))
{
a[0]=j[i-1];
b[0]=j[i+1];
}
if(isdigit(j[i+2])){
a[0]=j[i-1];
b[0]='t';
b[1]=j[i+2];
}
if(isdigit(j[i-2]))
{
b[0]=j[i+1];
a[0]='t';
a[1]=j[i-2];
b[1]='';
}
if(isdigit(j[i+2]) &&isdigit(j[i-2]))
{
a[0]='t';
b[0]='t';
a[1]=j[i-2];
b[1]=j[i+2];
sprintf(ch,"%d",c);
j[i+2]=j[i-2]=ch[0];
}
if(j[i]=='*')
printf("tt%d=%s*%sn",c,a,b);
if(j[i]=='/')
printf("tt%d=%s/%sn",c,a,b);
if(j[i]=='+')
printf("tt%d=%s+%sn",c,a,b);if(j[i]=='-')
printf("tt%d=%s-%sn",c,a,b);
if(j[i]=='=')
printf("t%c=t%d",j[i-1],--c);
sprintf(ch,"%d",c);
j[i]=ch[0];
c++;
small();
}
void small()
{
pi=0;l=0;
for(i=0;i<strlen(j);i++)
{
for(m=0;m<5;m++)
if(j[i]==sw[m])
if(pi<=p[m])
{
pi=p[m];
l=1;
k=i;
}
}
if(l==1)
dove(k);
else
exit(0);}




#11.POSTIX PREFIX





OPERATORS = set(['+', '-', '*', '/', '(', ')'])
PRI = {'+': 1, '-': 1, '*': 2, '/': 2}
### INFIX ===> POSTFIX ###
def infix_to_postfix(formula):
stack = [] # only pop when the coming op has priority
output = ''
for ch in formula:
if ch not in OPERATORS:
output += ch
elif ch == '(':
stack.append('(')
elif ch == ')':
while stack and stack[-1] != '(':
output += stack.pop()
stack.pop() # pop '('
else:
while stack and stack[-1] != '(' and PRI[ch] <= PRI[stack[-1]]:
output += stack.pop()
stack.append(ch)
# leftover
while stack:
output += stack.pop()
print(f'POSTFIX: {output}')
return output
### INFIX ===> PREFIX ###
def infix_to_prefix(formula):
op_stack = []
exp_stack = []
for ch in formula:
if not ch in OPERATORS:
exp_stack.append(ch)
elif ch == '(':
op_stack.append(ch)
elif ch == ')':
while op_stack[-1] != '(':
op = op_stack.pop()
a = exp_stack.pop()
b = exp_stack.pop()
exp_stack.append(op + b + a)
op_stack.pop() # pop '('
else:
while op_stack and op_stack[-1] != '(' and PRI[ch] <= PRI[op_stack[-1]]:
op = op_stack.pop()
a = exp_stack.pop()
b = exp_stack.pop()
exp_stack.append(op + b + a)
op_stack.append(ch)
# leftover
while op_stack:
op = op_stack.pop()
a = exp_stack.pop()
b = exp_stack.pop()
exp_stack.append(op + b + a)
print(f'PREFIX: {exp_stack[-1]}')
return exp_stack[-1]
expres = input("INPUT THE EXPRESSION: ")
pre = infix_to_prefix(expres)
pos = infix_to_postfix(expres)




#12.DAG



#include<stdio.h>
#include<ctype.h>
#include<stdlib.h>
#include<string.h>
void small();
void dove(int i);
int p[5]={0,1,2,3,4},c=1,i,k,l,m,pi;
char sw[5]={'=','-','+','/','*'},j[20],a[5],b[5],ch[2];
void main()
{
printf("Enter the expression:");
scanf("%s",j);
printf("tThe Intermediate code is:n");
small();
}
void dove(int i)
{
a[0]=b[0]='';
if(!isdigit(j[i+2])&&!isdigit(j[i-2]))
{
a[0]=j[i-1];
b[0]=j[i+1];
}
if(isdigit(j[i+2])){
a[0]=j[i-1];
b[0]='t';
b[1]=j[i+2];
}
if(isdigit(j[i-2]))
{
b[0]=j[i+1];
a[0]='t';
a[1]=j[i-2];
b[1]='';
}
if(isdigit(j[i+2]) &&isdigit(j[i-2]))
{
a[0]='t';
b[0]='t';
a[1]=j[i-2];
b[1]=j[i+2];
sprintf(ch,"%d",c);
j[i+2]=j[i-2]=ch[0];
}
if(j[i]=='*')
printf("tt%d=%s*%sn",c,a,b);
if(j[i]=='/')
printf("tt%d=%s/%sn",c,a,b);
if(j[i]=='+')
printf("tt%d=%s+%sn",c,a,b);if(j[i]=='-')
printf("tt%d=%s-%sn",c,a,b);
if(j[i]=='=')
printf("t%c=t%d",j[i-1],--c);
sprintf(ch,"%d",c);
j[i]=ch[0];
c++;
small();
}
void small()
{
pi=0;l=0;
for(i=0;i<strlen(j);i++)
{
for(m=0;m<5;m++)
if(j[i]==sw[m])
if(pi<=p[m])
{
pi=p[m];
l=1;
k=i;
if(l==1)
dove(k);
else
exit(0);}