-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathFol_.java
More file actions
166 lines (153 loc) · 3.44 KB
/
Fol_.java
File metadata and controls
166 lines (153 loc) · 3.44 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
import java.io.*;
import java.lang.*;
import java.util.*;
public class Fol_
{
static char ntermnl[],termnl[];
static int ntlen,tlen;
static String grmr[][],fst[],flw[];
public static void main(String args[]) throws IOException
{
String nt,t;
int i,j,n;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter the non-terminals without space");
nt=br.readLine();
ntlen=nt.length();
ntermnl=new char[ntlen];
ntermnl=nt.toCharArray();
System.out.println("Enter the terminals without space");
t=br.readLine();
tlen=t.length();
termnl=new char[tlen];
termnl=t.toCharArray();
System.out.println("Specify the grammar(Enter Z for epsilon production)");
grmr=new String[ntlen][];
for(i=0;i<ntlen;i++)
{
System.out.println("Enter the number of productions for "+ntermnl[i]);
n=Integer.parseInt(br.readLine());
grmr[i]=new String[n];
System.out.println("Enter the productions");
for(j=0;j<n;j++)
{
grmr[i][j]=br.readLine();
System.out.println();
}
}
fst=new String[ntlen];
for(i=0;i<=ntlen;i++)
fst[i]=first(i);
System.out.println("First Set");
for(i=0;i<ntlen;i++)
System.out.println(removeDuplicates(fst[i]));
flw=new String[ntlen];
for(i=0;i<ntlen;i++)
flw[i]=follow(i);
System.out.println("Follow Set");
for(i=0;i<ntlen;i++)
System.out.println(removeDuplicates(flw[i]));
}
static String first(int i)
{
int j,k=0,l=0,found=0;
String temp="",str="";
for(j=0;j<=grmr[i].length;j++)
{
for(k=0;k<=grmr[i][j].length();k++,found=0)
{
for(l=0;l<=ntlen;l++)
{
if(grmr[i][j].charAt(k)==ntermnl[l])
{
str=first(l);
if(!(str.length()==1 && str.charAt(0)=='Z'))
temp=temp+str;
found=1;
break;
}
}
if(found==1)
{
if(str.contains("Z"))
continue;
}
else
temp=temp+grmr[i][j].charAt(k);
break;
}
}
return temp;
}
static String follow(int i)
{
char pro[],chr[];
String temp="";
int j,k,l,m,n,found=0;
if(i==0)
temp="$";
for(j=0;j<ntlen;j++)
{
for(k=0;k<grmr[j].length;k++) //entering grammar matrix
{
pro=new char[grmr[j][k].length()];
pro=grmr[j][k].toCharArray();
for(l=0;l<pro.length;l++) //entering each production
{
if(pro[l]==ntermnl[i]) //finding the nonterminal whose follow set is to be found
{
if(l==pro.length-1) //if it is the last terminal/non-terminal then follow of current non-terminal
{
if(j<i)
temp=temp+flw[j];
}
else
{
for(m=0;m<ntlen;m++)
{
if(pro[l+1]==ntermnl[m]) //first of next non-terminal otherwise (else later…)
{
chr=new char[fst[m].length()];
chr=fst[m].toCharArray();
for(n=0;n<chr.length;n++)
{
if(chr[n]=='Z') //if first includes epsilon
{
if(l+1==pro.length-1)
temp=temp+follow(j); //when non-terminal is second last
else
temp=temp+follow(m);
}
else
temp=temp+chr[n]; //include whole first set except epsilon
}
found=1;
}
}
if(found!=1)
temp=temp+pro[l+1]; //follow set will include terminal(else is here)
}
}
}
}
}
return temp;
}
static String removeDuplicates(String str)
{
int i;
char ch;
boolean seen[] = new boolean[256];
StringBuilder sb = new StringBuilder(seen.length);
for(i=0;i<str.length();i++)
{
ch=str.charAt(i);
if (!seen[ch])
{
seen[ch] = true;
sb.append(ch);
}
}
return sb.toString();
}
}