计算first集合和follow集合--编译原理教案资料

转First集合和Follow集合的求法（修改含例⼦）对于终结符和⾮终结符的理解：终结符：通俗的说就是不能单独出现在推导式左边的符号，也就是说终结符不能再进⾏推导。

⾮终结符：不是终结符的都是⾮终结符。

如：A->B，则A是⾮终结符；A->id,则id是终结符。

（⼀般书上终结符⽤⼩写，⾮终结符⽤⼤写。

）⽂法产⽣语⾔句⼦的基本思想：从识别符号（开始符）开始，把当前产⽣的符号串中的⾮终结符替换为相应规则右部的符号串，直到全部由终结符组成。

所以⽂法产⽣句⼦的基本思想就是基于产⽣式（例如A->num）的替换，当所有的⾮终结符都被终结符替换时，推导结束。

FIRST集求法：我对First集的理解：first集应该就是求⼀个表⽰⽂法的字串（⼀般指⾮终结符，终结符的first集就是它⾃⾝）开头的所有可能出现的字符的集合。

例如A->aC | bB | cD,根据这个产⽣式，就可以知道，⾮终结符A，被替换后，它开头可能出现字符有a、b 、c, 所以 {a,b,c}是First（A）的⼀个⼦集。

求First集的步骤：1. 若X->a..，则将终结符ａ加⼊FIRST(X)中;（注意⾮终结符的情况）2. 若X->e ,则将终结符e加⼊FIRST(X)中(e表⽰空集)；3. 若 X->BC..D,则将First（B）所有元素（除了空集）加⼊First（A），然后检测First（B），若First（B）中不存在空集, 即e,则停⽌，若存在则向B的后⾯查看，将First（C）中所有元素（除了空集）加⼊First（A），然后再检测First（C）中是否有e...直到最后，若D之前的所有⾮终结符的First集中都含有e,则检测到D时，将First（D）也加⼊First（A），若First（D）中含有e,则将 e加⼊First（A）。

对于第三条，其实也很好理解，就是说当X推导出⼀个字串时，D前⾯的⾮终结符都可能推出空串，这个时候，X推出的串的⾸部，就不是那些推出空串的⾮终结符了，⽽是这些推出空串的⾮终结符后⾯的⽂法符号所推导出的字串。

【编译原理】语法分析LL（1）分析法的FIRST和FOLLOW集 近来复习编译原理，语法分析中的⾃上⽽下LL(1)分析法，需要构造求出⼀个⽂法的FIRST和FOLLOW集，然后构造分析表，利⽤分析表+⼀个栈来做⾃上⽽下的语法分析（递归下降/预测分析），可是这个FIRST集合FOLLOW集看得我头⼤。

教课书上的规则如下，⽤我理解的语⾔描述的：任意符号α的FIRST集求法：1. α为终结符，则把它⾃⾝加⼊FIRSRT(α)2. α为⾮终结符，则：（1）若存在产⽣式α->a...，则把a加⼊FIRST(α),其中a可以为ε（2）若存在⼀串⾮终结符Y1,Y2, ..., Yk-1，且它们的FIRST集都含空串，且有产⽣式α->Y1Y2...Yk...，那么把FIRST(Yk)-{ε}加⼊FIRST(α)。

如果k-1抵达产⽣式末尾，那么把ε加⼊FIRST(α) 注意（2）要连续进⾏，通俗地描述就是：沿途的Yi都能推出空串，则把这⼀路遇到的Yi的FIRST集都加进来，直到遇到第⼀个不能推出空串的Yk为⽌。

重复1,2步骤直⾄每个FIRST集都不再增⼤为⽌。

任意⾮终结符A的FOLLOW集求法：1. A为开始符号，则把#加⼊FOLLOW(A)2. 对于产⽣式A-->αBβ： （1）把FIRST(β)-{ε}加到FOLLOW(B) （2）若β为ε或者ε属于FIRST(β)，则把FOLLOW(A)加到FOLLOW(B)重复1,2步骤直⾄每个FOLLOW集都不再增⼤为⽌。

⽼师和同学能很敏锐地求出来，⽽我只能按照规则，像程序⼀样⼀条条执⾏。

于是我把这个过程写成了程序，如下：数据元素的定义：1const int MAX_N = 20;//产⽣式体的最⼤长度2const char nullStr = '$';//空串的字⾯值3 typedef int Type;//符号类型45const Type NON = -1;//⾮法类型6const Type T = 0;//终结符7const Type N = 1;//⾮终结符8const Type NUL = 2;//空串910struct Production//产⽣式11 {12char head;13char* body;14 Production(){}15 Production(char h, char b[]){16 head = h;17 body = (char*)malloc(strlen(b)*sizeof(char));18 strcpy(body, b);19 }20bool operator<(const Production& p)const{//内部const则外部也为const21if(head == p.head) return body[0] < p.body[0];//注意此处只适⽤于LL(1)⽂法，即同⼀VN各候选的⾸符不能有相同的，否则这⾥的⼩于符号还要向前多看⼏个字符，就不是LL(1)⽂法了22return head < p.head;23 }24void print() const{//要加const25 printf("%c -- > %s\n", head, body);26 }27 };2829//以下⼏个集合可以再封装为⼀个⼤结构体--⽂法30set<Production> P;//产⽣式集31set<char> VN, VT;//⾮终结符号集，终结符号集32char S;//开始符号33 map<char, set<char> > FIRST;//FIRST集34 map<char, set<char> > FOLLOW;//FOLLOW集3536set<char>::iterator first;//全局共享的迭代器，其实觉得应该⽤局部变量37set<char>::iterator follow;38set<char>::iterator vn;39set<char>::iterator vt;40set<Production>::iterator p;4142 Type get_type(char alpha){//判读符号类型43if(alpha == '$') return NUL;//空串44else if(VT.find(alpha) != VT.end()) return T;//终结符45else if(VN.find(alpha) != VN.end()) return N;//⾮终结符46else return NON;//⾮法字符47 }主函数的流程很简单，从⽂件读⼊指定格式的⽂法，然后依次求⽂法的FIRST集、FOLLOW集1int main()2 {3 FREAD("grammar2.txt");//从⽂件读取⽂法4int numN = 0;5int numT = 0;6char c = '';7 S = getchar();//开始符号8 printf("%c", S);9 VN.insert(S);10 numN++;11while((c=getchar()) != '\n'){//读⼊⾮终结符12 printf("%c", c);13 VN.insert(c);14 numN++;15 }16 pn();17while((c=getchar()) != '\n'){//读⼊终结符18 printf("%c", c);19 VT.insert(c);20 numT++;21 }22 pn();23 REP(numN){//读⼊产⽣式24 c = getchar();25int n; RINT(n);26while(n--){27char body[MAX_N];28 scanf("%s", body);29 printf("%c --> %s\n", c, body);30 P.insert(Production(c, body));31 }32 getchar();33 }3435 get_first();//⽣成FIRST集36for(vn = VN.begin(); vn != VN.end(); vn++){//打印⾮终结符的FIRST集37 printf("FIRST(%c) = { ", *vn);38for(first = FIRST[*vn].begin(); first != FIRST[*vn].end(); first++){39 printf("%c, ", *first);40 }41 printf("}\n");42 }4344 get_follow();//⽣成⾮终结符的FOLLOW集45for(vn = VN.begin(); vn != VN.end(); vn++){//打印⾮终结符的FOLLOW集46 printf("FOLLOW(%c) = { ", *vn);47for(follow = FOLLOW[*vn].begin(); follow != FOLLOW[*vn].end(); follow++){48 printf("%c, ", *follow);49 }50 printf("}\n");51 }52return0;53 }主函数其中⽂法⽂件的数据格式为（按照平时做题的输⼊格式设计的）：第⼀⾏：所有⾮终结符，⽆空格，第⼀个为开始符号；第⼆⾏：所有终结符，⽆空格；剩余⾏：每⾏描述了⼀个⾮终结符的所有产⽣式，第⼀个字符为产⽣式头（⾮终结符），后跟⼀个整数位候选式的个数n，之后是n个以空格分隔的字符串为产⽣式体。

构造 FIRST 集和 FOLLOW 集的方法
1、构造 FIRST 集的算法 (1) 对于 G 中的每个文法符号 X,为求 FIRST(X),反复应用如下规则,直到集合不再增大: ① 若 X∈VT，则 FIRST(X)是{X} ② 若 X∈VN ,且 X→aα (a∈VT )，则{ a } FIRST(X) X→ε， 则{ε} FIRST(X) ③ 若 X->Y1Y2 … Yi-1 Yi … YK∈P,Y1∈VN ,则 FIRST(Y1)-{ε} FIRST(X)
则 FIRST(Xi) -{} FIRST() 特别是，若所有的 FIRST(Xj)均含有，1jn，则{} FIRST()。 显然，若＝则 FIRST()＝{}。
2、构造 FOLLOW 集的算法 对于 G 中的每一 AFOLLOW 集不再增大为止: ① 对于文法的开始符号 S，令# ∈ FOLLOW(S)。 ② 对于每一 A→αBβ∈P， 令 FIRST(β) - {ε} FOLLOW(B) 。 ③ 对于每一 A→αB∈P， 或 A→αBβ∈P，且ε∈FIRST(β)， 则令 FOLLOW(A) FOLLOW(B) 。
∗
而对所有的 j(1≤j ≤i-1), Yj ∈VN，且 Yj⇒ ε，则令 FIRST(Yj)-{ε} FIRST(X) (1≤j ≤i) 特别，当ε∈FIRST(Yj) (1≤j ≤k)时，令ε∈FIRST(X)
(2) 对文法 G 的任何符号串=X1X2…Xn 构造集合 FIRST() ① 置 FIRST(X1)-{} FIRST() ② 若对任何 1ji-1，FIRST(Xj)，

则 FIRST(Xi) -{} FIRST() 特别是，若所有的 FIRST(Xj)均含有，1jn，则{} FIRST()。 显然，若＝则 FIRST()＝{}。
2、构造 FOLLOW 集的算法 对于 G 中的每一 A∈VN，为构造 FOLLOW(A)，可反复使用如下的规则，直到每个
FOLLOW 集不再增大为止: ① 对于文法的开始符号 S，令# ∈ FOLLOW(S)。 ② 对于每一 A→αBβ∈P， 令 FIRST(β) - {ε} FOLLOW(B) 。 ③ 对于每一 A→αB∈P， 或 A→αBβ∈P，且ε∈FIRST(β)， 则令 FOLLOW(A) FOLLOW(B) 。
∗ห้องสมุดไป่ตู้
而对所有的 j(1≤j ≤i-1), Yj ∈VN，且 Yj⇒ ε，则令 FIRST(Yj)-{ε} FIRST(X) (1≤j ≤i) 特别，当ε∈FIRST(Yj) (1≤j ≤k)时，令ε∈FIRST(X)
(2) 对文法 G 的任何符号串=X1X2…Xn 构造集合 FIRST() ① 置 FIRST(X1)-{} FIRST() ② 若对任何 1ji-1，FIRST(Xj)，
构造 FIRST 集和 FOLLOW 集的方法
1、构造 FIRST 集的算法 (1) 对于 G 中的每个文法符号 X,为求 FIRST(X),反复应用如下规则,直到集合不再增大: ① 若 X∈VT，则 FIRST(X)是{X} ② 若 X∈VN ,且 X→aα (a∈VT )，则{ a } FIRST(X) X→ε， 则{ε} FIRST(X) ③ 若 X->Y1Y2 … Yi-1 Yi … YK∈P,Y1∈VN ,则 FIRST(Y1)-{ε} FIRST(X)

{
if(!capL(ch))
}
void getFirst(char ch, set<char> &First)//求单个元素的FIRST集
{
multimap<char, string>::iterator imul = sentence.find(ch);
if(imul==sentence.end())
return;
int sum = sentence.count(imul->first);
（1）若xi∈VT，则xi∈FIRST（α）；
（2）若xi∈VN；
①若ε FIRST（xi），则FIRST（xi）∈FIRST（α）；
②若ε∈FIRST（xi），则FIRST（xi）－{ε}∈FIRST（α）；
（3）i＝i+1，重复（1）、（2），直到xi∈VT，（i＝2，3，…，n）或xi∈VN且若ε FIRST（xi）或i>n为止。
int cnt = sentence.count(ch);
for(int i=0; i<cnt; ++i, ++mIter) {
if(mIter->second=="^") {
return true;
}
else if(CapLString(mIter->second)){
string s(mIter->second);
bool flag2 = true;
for(int j=0; j<s.size(); j++) {
if(!isToEmpty(s[j]) || s[j]==ch) {
flag2 = false;

first集合和follow集合的求法
FIRST集合和FOLLOW集合的求法如下：
1、FIRST集合的求法：
直接收取：如果X是终结符或为空，则First(X) = {X}。

反复传送：如果X是非终结符，则First集合一直传送下去，直到遇到终结符。

第一个状态减去ε（即空字符串）后加入到First集合中。

注意传送时非终结符是否可以为空，如果可以为空，则看下一个字符。

对于形如“…UP…”（P是非终结符）的组合，把First(P)直接收入到First集合中。

遇到形如E →TE’这样的产生式时，先把First(T)放入First(E)，然后查看T是否能推导出ε（即空字符串）。

如果能，则把First(E’)放入First(E)，以此类推。

若T不能推出ε，则First(E)求完。

2、FOLLOW集合的求法：
对于文法的开始符号S，将识别符号“#”置于FOLLOW(S)中。

若存在产生式A →αBβ，则将First(β) - {ε}加至FOLLOW(B)中。

这里，First(β)表示β能推导出的第一个终结符或非终结符的集合，但要去掉ε。

如果β可以推导出ε，则将FOLLOW(A)加至FOLLOW(B)中。

这意味着，如果B有可能是最后一个符号，那么A的FOLLOW集合应该加入到B的FOLLOW集合中。

反复使用上述规则，直到所求FOLLOW集合不再增大为止。

以上是对FIRST集合和FOLLOW集合求法的简要概述。

在实际应用中，需要根据具体的文法和产生式进行具体的分析和计算。

编译原理：FIRST（x）FOLLOW（x）SELECT（x）的计算⽬录已知⽂法G[S]：S→MH|aH→LSo|εK→dML|εL→eHfM→K|bLM判断G是否是LL（1）⽂法。

First计算First集合的定义就是某个⾮终结符表达式可以推导出来的第⼀个字符可以是什么⽐如表达式S --> abb,它的First(S)={a}First(S)={a}+First(M)+First(H)+{ε}={a,b,d,e,ε}# S表达式存在单个的终结符a,添加{a}# S表达式以M开头,添加First(M)# 根据后⾯的表达式判断,M可以推出K,K可以推出空,所以M可以为空,此时S以H开头,添加First(H)# 由于H也可以推出空,所以S最终也会指向空,添加空集First(M)={b}+First(K)+{ε}={b,d,ε}# M表达式以终结符b开头,添加{b}# M表达式可以推导出单个的K表达式,所以添加First(K)# K有可能推导出空集,即M可以推导出空,所以添加空集First(K)={d}+{ε}={d,ε}# K可以以终结符d开头,添加{d}# K可以推导出空,添加空集First(H)=First(L)+{ε}={e,ε}# H可以推导出以L开头的表达式,所以添加First(L)# H可以推导出空,所以添加空集First(L)={e}# L只能推导出⼀个表达式,并且开头是终结符,所以添加{e}## 最后将已知的表达式代⼊到未知的表达式当中去,即可求出全部First集合Follow计算Follow表⽰某个⾮终结符后⾯可以跟着什么样的字符Follow集不存在空集为表达式编号1: S→MH|a2: H→LSo|ε3: K→dML|ε4: L→eHf5: M→K|bLMFollow(S)={$}+{o}={o,$}# 在表达式1中,S是⼀个⾮终结符,S是孤⽴的⼀个表达式,其Follow可以添加$,即添加{$}# 在表达式2中,S后⾯跟上了o,所以添加{o}Follow(H)=Follow(S)+{f}={f,o,$}# 在表达式1中,S后⾯跟了什么,MH后⾯就跟了什么,所以添加Follow(S)# 在表达式4中,H后⾯跟了f,所以添加{f}Follow(M)=First(H)+Follow(S)+First(L)={e,o,$}# 在表达式1中,M后⾯跟了H,所以添加First(H)# 在表达式2中可知,H可以推导出空,所以回到表达式1,S后⾯跟了什么,M后⾯就跟了什么,所以添加Follow(S)# 在表达式3中,M后⾯跟了⾮终结符L,所以添加First(L)# 在表达式5中,M后⾯跟了什么,bLM后⾯就跟什么,都是Follow(M),表达式不变Follow(L)=First(S)+Follow(K)+{o}+{$}+First(M)+Follow(M)={a,b,d,e,o,$}# 在表达式2中,L后⾯跟了⾮终结符S,所以添加First(S)# 在表达式2中,First(S)可以推出空,所以此时L后⾯跟着o,添加{o}# 在表达式3中,K后⾯跟了什么,dML后⾯就跟了什么,所以添加Follow(K)# 在表达式4中,L属于单⼀元素,所以添加$# 在表达式5中,L后⾯跟上了⾮终结符M,所以添加First(M)# 在表达式5中,从上得知,First(M)可以推导出空,所以此时M后⾯跟着什么,L后⾯就要跟着什么,所以添加Follow(M) Follow(K)={$}+Follow(M)={e,o,$}# 在表达式3中,K是单⼀字符,添加{$}# 在表达式5中,M后⾯跟着什么,K后⾯就跟着什么,所以添加Follow(M)注意:在书写Follow集中要时刻检查First集是否可以为空.Select计算分割表达式,如果⾮空则是First集,是空则为Follow集Select(S→MH)=First(M)+First(H)+Follow(S)={b,d,e,o,$}# S以M开头,加⼊First(M)# First(M)可以为空,加⼊First(H)# M和H都可以为空,加⼊Follow(S)Select(S→a)={a}# S只能推导出a,加⼊{a}Select(H→LSo)=First(L)={e}# H以L开头,并且First(L)不可以为空,即加⼊First(L)Select(H→ε)=Follow(H)={f,o,$}# H推导出空,加⼊Follow(H)Select(K→dML)={d}# K以终结符d开头,加⼊{d}Select(K→ε)=Follow(K)={e,o,$}# K可以为空,加⼊Follow(K)Select(L→eHf)={e}# L以终结符e开头,加⼊{e}Select(M→K)=First(K)+Follow(M)={d,e,o,$}# M可以推出K,加⼊First(K)# First(K)可以为空,即M可以加⼊Follow(M)Select(M→bLM)={b}# M可以推出以终结符b开头,加⼊{b}判断是否是LL(1)⽂法LL(1)⽂法就是同⼀⾮终结符推出来的Select集合相交为空，现在开始逐⼀判断Select(S→MH)∩Select(S→a)Select(H→LSo)∩Select(H→ε)Select(K→dML)∩Select(K→ε)# L只有⼀个表达式，省略LSelect(M→K)∩Select(M→bLM)易知，上述表达式都为空，所以这个表达式是LL(1)⽂法预测分析表的书写先列出First集和Follow集的表格First FollowS{a,d,b,e, ε}{$,o}H{e,ε}{f,o,$}K{d,ε}{e,o,$}L{e}{a,b,d,e,o,$}M{b,d,ε}{e,o,$}然后将⾮终结符、终结符作为横纵⾏，填⼊表达式。

First集合的求法：First集合最终是对产生式右部的字符串而言的，但其关键是求出非终结符的First集合，由于终结符的First集合就是它自己，所以求出非终结符的First集合后，就可很直观地得到每个字符串的First集合。

1. 直接收取：对形如U－a…的产生式（其中a是终结符），把a收入到First(U)中2. 反复传送：对形入U－P…的产生式（其中P是非终结符），应把First(P)中的全部内容传送到First(U)中。

Follow集合的求法：Follow集合是针对非终结符而言的，Follow(U)所表达的是句型中非终结符U所有可能的后随终结符号的集合，特别地，“#”是识别符号的后随符。

1. 直接收取：注意产生式右部的每一个形如“…Ua…”的组合，把a直接收入到Follow(U)中。

2．直接收取：对形如“…UP…”(P是非终结符)的组合，把First(P)除ε直接收入到Follow(U)中。

3．反复传送：对形如P－…U的产生式（其中U是非终结符），应把Follow(P)中的全部内容传送到Follow(U)中。

(或 P－…UB且First(B)包含ε，则把First(B)除ε直接收入到Follow(U)中，并把Follow(P)中的全部内容传送到Follow(U)中)例1：判断该文法是不是LL(1)文法，说明理由 S→ABc A→a|ε B→b|ε？First集合求法就是：能由非终结符号推出的所有的开头符号或可能的ε，但要求这个开头符号是终结符号。

如此题A可以推导出a和ε，所以FIRST（A）=｛a，ε｝；同理FIRST （B）={b,ε};S可以推导出aBc，还可以推导出bc，还可以推导出c，所以FIRST(S）=｛a，b，c｝。

Follow集合的求法是：紧跟随其后面的终结符号或＃。

但文法的识别符号包含＃，在求的时候还要考虑到ε。

具体做法是把所有包含你要求的符号的产生式都找出来，再看哪个有用。

}
}
for(set<char>::iterator iter=ter.begin(); iter!=ter.end(); iter++) {
flag = false;
cout<<*iter<<" FIRST集:";
fir.clear();
getFirst(*iter, fir);
for(set<char>::iterator iterF=fir.begin(); iterF!=fir.end(); iterF++) {
vector<string> rightSide; //右部
char Begin;
bool capL(char c) //字母是否大写
{
if(c<='Z' && c>='A')
return true;
return false;
}
bool CapLString(string s) //大写字符串
{
for(int i=0; i<s.size(); i++) {
if(!capL(s[i])) {
return false;
}
}
return true;
}
bool isToEmpty(char ch) //判断终结符能否推出空
{
bool flag;
flag = false;
multimap<char, string>::iterator mIter = sentence.find(ch);
if(s[j]==ch) {//有左递归,跳出循环

摘要：编译原理是计算机科学与技术专业最重要的一门专业基础课程，内容庞大，涉及面广，知识点多。

由于该课程教、学难度都非常大，往往费了大量时间而达不到预期教学效果俗语说：学习的最好方法是实践。

本次课程设计的目的正是基于此，力求为学生提供一个理论联系实际的机会，通过布置一定难度的课题，要求学生独立完成。

我们这次课程设计的主要任务是编程实现对给定文法的FIRST 集和FOLLOW集的求解。

通过实践，建立系统设计的整体思想，锻炼编写程序、调试程序的能力，学习文档编写规范，培养独立学习、吸取他人经验、探索前言知识的习惯，树立团队协作精神。

同时，课程设计可以充分弥补课堂教学及普通实验中知识深度与广度有限的缺陷，更好地帮助学生从全局角度把握课程体系。

关键词：编译原理；FIRST集；FOLLOW集目录1 课题综述 (1)1.1 课题来源 (1)1.2 课题意义 (1)1.3 预期目标 (1)1.4 面对的问题 (1)1.5 需解决的关键技术 (1)2 系统分析 (2)2.1 基础知识 (2)2.1.1 FIRST集定义 (2)2.1.2FIRST集求解算法.................................................................... 错误!未定义书签。

2.1.3FOLLOW集的定义 (4)2.1.4 FOLLOW集算法 (4)2.2 解决问题的基本思路 (4)2.3 总体方案 (4)3 系统设计 (5)3.1 算法实现 (5)3.2 流程图 (6)4 代码编写 (10)5 程序调试 (15)6 运行与测试 (15)1 课题综述1.1 课题来源文法：包含若干终结符，非终结符，由终结符与非终结符组成的产生式。

本次课程设计就是对产生式进行左递归分析，待无左递归现象后进行FIRST集与FOLLOW集的求解。

1.2 课题意义由文法产生的若干个句子有可能是合法的或者不合法的，也有可能产生歧义，所以要消除歧义先消除文法左递归，然后根据求得的FIRST集与FOLLOW 集构造分析表，分析给定句子的合法性。

FIRST、FOLLOW
copyright @ huji不能单独出现在推导式左边的符号。终结符不能再推导。 非终结符：不是终结符的都是非终结符。
FIRST 集：比如求 FIRST (U ) ，在推导式的左边找到它，然后在推导式的右边锁定
其所有产生式，作如下： 1、 直接收取：对形如 U a... 的产生式( a 是终结符)，把 a 加入到 FIRST (U ) 中， 即 {a} FIRST (U ) 特别的，对产生式 U ，那么将 加入到 FIRST (U ) 中。即
FOLLOW (T ') FOLLOW (T ) {$, ,)}
（10） 求 FOLLOW ( F ) 我们在（3） 、 （4）中找到 F 于是加入 FIRST (T ') 中所有非 字符，而且我们 看到 FIRST (T ') {*, } 中有 ，于是加入 FOLLOW (T ) ，则，结束。
FOLLOW 集：比如求 FOLLOW ( B) ，在推导式的右边找到所有含 B 的产生式，锁
定： 1、 直接收取：若 B 是开始符号（什么是开始符号？一般就是文法的第一个式子的左 部） ，那么就将 $ 加入 FOLLOW ( B) 。 （ $ 是输入有段的结束标记，对我们来说没 有什么意义，有的辅导书以 # 来代替。 ）即 {$} FOLLOW ( B) 注意产生式右部每一个形如 ...Ba.. 的组合，那么把终结符 a 加入到
FOLLOW ( F ) {*} FOLLOW (T ) {*,$, ,)}
再举一个例子。 有如下文法，
S AaBb | BbBa A B
这个例子是我们龙书 153 页联系 4.6.5 的文法，在这里我们主要求 FIRST 集。

♨自上而下语法分析 Top-Down Parsing
G1: S → pA |qB A → a | cA B → b | dB 输入串 pca G2: S → Ap | Bq A → a | cA B → b | dB 输入串 cap
FIRST 集
FIRST集 / 开始符号集 / 终结首符集
* a…, a∈VT} FIRST(α) = {a|α * ε, 则规定 ε∈FIRST(α) 若α
G: S→ AB A→aA |ε B→bA |ε
自上而下语法分析面临的问题
G: S → cAd A → a|ab 输入串 cabd

－ 回溯 Backtrack S
c A d
S
c A d a b
a A→ α1 |α2 |…|αn 如何决定用哪个候选式替换A? 不确定分析: 带回溯 (试探) 确定分析 : 不带回溯
练习: 求 First 集
G: S → ABC A → aA |ε B → bB |b C → cC |c First(S) = { a, b }
First(A) = { a, ε }
First(B) = { b}
First(C) = { c}
例: 自上而下语法分析
G5: E → TE' E'→ +TE'|ε T → FT' T'→ *FT'|ε F → (E) | i 输入串 i＋i
Select 集
SELECT集 选择集合
给定上下文无关文法的产生式A→α, * ε， • 若α SELECT(A→α) = FIRST(α) * ε， • 若α SELECT(A→α) = (FIRST(α)－{ε})∪FOLLOW(A)

计算first 集合和follow 集合姓名：彦清 学号：E10914127一、实验目的输入：任意的上下文无关文法。

输出：所输入的上下文无关文法一切非终结符的first 集合和follow 集合。

二、实验原理设文法G[S]＝（V N ，V T ，P ，S ），则首字符集为：FIRST （α）＝{a | α⇒*a β，a ∈V T ，α,β∈V *}。

若α⇒*ε，ε∈FIRST （α）。

由定义可以看出，FIRST （α）是指符号串α能够推导出的所有符号串中处于串首的终结符号组成的集合。

所以FIRST 集也称为首符号集。

设α＝x 1x 2…x n ，FIRST （α）可按下列方法求得：令FIRST （α）＝Φ，i ＝1；（1） 若x i ∈V T ，则x i ∈FIRST （α）；（2） 若x i ∈V N ；① 若ε∉FIRST （x i ），则FIRST （x i ）∈FIRST （α）；② 若ε∈FIRST （x i ），则FIRST （x i ）－{ε}∈FIRST （α）；（3） i ＝i+1，重复（1）、（2），直到x i ∈V T ，（i ＝2，3，…，n ）或x i∈V N 且若ε∉FIRST （x i ）或i>n 为止。

当一个文法中存在ε产生式时，例如，存在A →ε，只有知道哪些符号可以合法地出现在非终结符A 之后，才能知道是否选择A →ε产生式。

这些合法地出现在非终结符A 之后的符号组成的集合被称为FOLLOW 集合。

下面我们给出文法的FOLLOW 集的定义。

设文法G[S]＝（V N ，V T ，P ，S ），则FOLLOW （A ）＝{a | S ⇒… Aa …，a ∈V T }。

若S *…A ，#∈FOLLOW （A ）。

由定义可以看出，FOLLOW （A ）是指在文法G[S]的所有句型中，紧跟在非终结符A 后的终结符号的集合。

FOLLOW 集可按下列方法求得：（1） 对于文法G[S]的开始符号S ，有#∈FOLLOW （S ）；（2） 若文法G[S]中有形如B →xAy 的规则，其中x ，y ∈V *，则FIRST（y ）－{ε}∈FOLLOW （A ）；（3） 若文法G[S]中有形如B →xA 的规则，或形如B →xAy 的规则且ε∈FIRST （y ），其中x ，y ∈V *，则FOLLOW （B ）∈FOLLOW （A ）；三、源程序#include<iostream.h>#include<string.h>//产生式struct css{char left;char zhuan;//用“-”表示箭头char right[20];};//空标志struct kong{int kongzuo;int kongyou;};struct biaoji//第三步扫描式子的右部标记号{int r[100];};struct first//初步求first 集合时用{ char fjihe[200];};struct first2//保存最终的first 集合{ char fjihe2[200];};struct follow//初步求follow 集合时用{ char fow[200];};struct follow2//保存最终的follow 集合{ char fow2[200];};void main(){ int i,n,k;//产生式条数css shizi[100];kong kongshi[100];cout<<"请输入产生式的条数n(n<100)："<<endl;cin>>n;cout<<"请从开始符输入产生式(空用“#”表示，产生式由字母组成)："<<endl;for(i=0;i<n;i++){cin>>shizi[i].left>>shizi[i].zhuan>>shizi[i].right;}int l,m,j,h,g,f;for(l=0;l<n;l++)for(m=0;m<sizeof(shizi[l].right);m++){ if(shizi[l].right[m]=='#'){kongshi[l].kongzuo=1;break;}else while(shizi[l].right[m]>='a' && shizi[l].right[m]<='z' ){kongshi[l].kongyou=0; break;}}for(j=0;j<=n;j++)for(h=0;h<n;h++){ if(j==h)break;if(shizi[j].left==shizi[h].left){if(kongshi[j].kongyou==0 && kongshi[h].kongyou==0)kongshi[j].kongzuo=kongshi[h].kongzuo=0;break;}}int d,s,a,q,w,e;char linshi;biaoji biaoyou[100];for(d=0;d<n;d++){if(!(kongshi[d].kongzuo==1||kongshi[d].kongyou==0)){for(s=0;shizi[d].right[s]!='\0';s++)for(a=0;a<=n;a++){ linshi=shizi[d].right[s];if(linshi==shizi[a].left && kongshi[a].kongzuo==1){ biaoyou[d].r[s]=1;}else {kongshi[d].kongyou=0;}}}}int sum,t,y;//第三部-1sum=0;for(e=0;e<n;e++){for(q=0;shizi[e].right[q]!='\0';q++){ t=biaoyou[e].r[q];if(t==1){ for(sum;shizi[e].right[q]!='\0';){sum++;y=sum-1;if(q==y)kongshi[e].kongzuo=1;break;}}else break;}}int a1,a2;/*第二次扫描判断转为否的式子*/for(a1=0;a1<=n;a1++)for(a2=0;a2<n;a2++){ if(a1==a2)break;if(shizi[a1].left==shizi[a2].left&&kongshi[a1].kongzuo!=1&&kongsh i[a2].kongzuo!=1){if(kongshi[a1].kongyou==0 && kongshi[a2].kongyou==0)kongshi[a1].kongzuo=kongshi[a2].kongzuo=0;break;}}//计算first集合first fji[100];int u,a3,a5,a6,a7,a8;//char linshi2[2]="-";//for(u=0;u<n;u++){ fji[u].fjihe[0]='\0';}for(a3=0;a3<=n;a3++){if(shizi[a3].right[0]>='a' && shizi[a3].right[0]<='z') {linshi2[0]=shizi[a3].right[0];strcat(fji[a3].fjihe,linshi2);}else { if(kongshi[a3].kongzuo==1){ strcat(fji[a3].fjihe,"#");}}}for(a5=0;a5<=n;a5++)for(a6=0;shizi[a5].right[a6]!='\0';a6++)if(shizi[a5].right[a6]>='A' && shizi[a5].right[a6]<='Z'){ if(shizi[a5].right[0]>='a' && shizi[a5].right[0]<='z')break;for(a7=0;a7<n;a7++)if(a5!=a7 && shizi[a5].right[a6]==shizi[a7].left){ {if(kongshi[a7].kongzuo!=1)strcat(fji[a5].fjihe,fji[a7].fjihe);if(a6==(strlen(shizi[a5].right)-1))for(a8=0;a8<n;a8++)if(a5!=a8 && shizi[a5].right[a6]==shizi[a8].left)if(kongshi[a5].kongzuo!=1){strcat(fji[a5].fjihe,fji[a8].fjihe);}else{strcat(fji[a5].fjihe,fji[a8].fjihe);strcat(fji[a5].fjihe,"#");}}}}//求follow集合follow fw[100];int b1,b2,b3,b4,b5,b6,b7,b8,b9,b10;char linshi5[2];for(b1=0;b1<n;b1++){ fw[b1].fow[0]='\0';}fw[0].fow[0]='#';fw[0].fow[1]='\0';for(b8=0;b8<n;b8++){ if(shizi[b8].left==shizi[0].left)fw[b8].fow[0]='#';fw[b8].fow[1]='\0';}int e1;for(e1=0;e1<2;e1++)for(b2=0;b2<n;b2++)for(b3=0;b3<n;b3++){ if(shizi[b2].right[b3]>='A'&&shizi[b2].right[b3]<='Z')if(shizi[b2].right[b3+1]>='a'&&shizi[b2].right[b3+1]<='z'){ linshi5[0]=shizi[b2].right[b3+1];linshi5[1]='\0';for(b9=0;b9<n;b9++){if(shizi[b2].right[b3]==shizi[b9].left)strcat(fw[b9].fow,linshi5);}}if(shizi[b2].right[b3+1]>='A'&&shizi[b2].right[b3+1]<='Z'){ for(b4=0;b4<n;b4++){if(shizi[b2].right[b3+1]==shizi[b4].left){ if(kongshi[b4].kongzuo!=1){for(b10=0;b10<n;b10++){if(shizi[b2].right[b3]==shizi[b10].left)strcat(fw[b10].fow,fji[b4].fjihe);}}else { for(b5=0;b5<n;b5++)if(shizi[b2].right[b3]==shizi[b5].left)strcat(fw[b5].fow,fw[b2].fow);}}}}if((b3+1)==strlen(shizi[b2].right)){ for(b7=0;b7<n;b7++)if(shizi[b2].right[b3]==shizi[b7].left)strcat(fw[b7].fow,fw[b2].fow);}}first2 fji2[100];int a11,a12,a13;for(a11=0;a11<n;a11++){ fji2[a11].fjihe2[0]='\0';}for(a12=0;a12<=n;a12++)for(a13=0;a13<n;a13++){ if(a12!=a13 && shizi[a12].left==shizi[a13].left)strcat(fji[a12].fjihe,fji[a13].fjihe);}char linshi3[100];char linshi4[2];int a15,a16,a17=0,a19=0,a21,a18;//for(a15=0;a15<n;a15++){ {for(a21=0;a21<99;a21++)linshi3[a21]='\0';}{for(a16=0;a16<strlen(fji[a15].fjihe);a16++){if(a16==0){linshi4[0]=fji[a15].fjihe[a16];linshi4[1]='\0';strcat(linshi3,linshi4);a16++;}for(a17=0;a17<=strlen(linshi3);a17++)if(linshi3[a17]==fji[a15].fjihe[a16])break;//if(linshi3[a17]=='\0'){ linshi4[0]=fji[a15].fjihe[a16];linshi4[1]='\0';strcat(linshi3,linshi4);}}}strcat(fji2[a15].fjihe2,linshi3);}follow2 fw2[100];int b11,b12,b13;for(b11=0;b11<n;b11++){ fw2[b11].fow2[0]='\0';}for(b12=0;b12<=n;b12++)for(b13=0;b13<n;b13++){ if(b12!=b13 && shizi[b12].left==shizi[b13].left) strcat(fw[b12].fow,fw[b13].fow);}char linshi6[100];char linshi7[2];int b15,b16,b17,b19=0,b21,b18;//for(b15=0;b15<n;b15++){ { {for(b21=0;b21<99;b21++)linshi6[b21]='\0';}{for(b16=0;b16<strlen(fw[b15].fow);b16++){if(b16==0){linshi7[0]=fw[b15].fow[b16];linshi7[1]='\0';strcat(linshi6,linshi7);b16++;}for(b17=0;b17<=strlen(linshi6);b17++)if(linshi6[b17]==fw[b15].fow[b16])break;//if(linshi6[b17]=='\0'){ linshi7[0]=fw[b15].fow[b16];linshi7[1]='\0';strcat(linshi6,linshi7);}}}}strcat(fw2[b15].fow2,linshi6);}int c1,c2;cout<<"非终结符"<<" "<<"first集合"<<endl;cout<<" "<<shizi[0].left<<" "<<fji2[0].fjihe2<<endl;for(c1=1;c1<n;c1++){for(c2=0;c2<c1;c2++){ if(shizi[c1].left!=shizi[c2].left&&c2==(c1-1))cout<<" "<<shizi[c1].left<<" "<<fji2[c1].fjihe2<<endl;}}int d1,d2;cout<<"非终结符"<<" "<<"follow集合"<<endl;cout<<" "<<shizi[0].left<<" "<<fw2[0].fow2<<endl;for(d1=1;d1<n;d1++){for(d2=0;d2<d1;d2++){ if(shizi[d1].left!=shizi[d2].left&&d2==(d1-1))cout<<" "<<shizi[d1].left<<" "<<fw2[d1].fow2<<endl;}}}四、运行截图。

};
struct biaoji//第三步扫描式子的右部标记号
{
int r[100];
};
struct first//初步求first集合时用
{ char fjihe[200];
};
struct first2//保存最终的first集合
{ char fjihe2[200];
};
{ fji[u].fjihe[0]='\0';
}
for(a3=0;a3<=n;a3++)
{if(shizi[a3].right[0]>='a' && shizi[a3].right[0]<='z')
{
linshi2[0]=shizi[a3].right[0];
if(kongshi[a5].kongzuo!=1)
{strcat(fji[a5].fjihe,fji[a8].fjihe);
}
else{strcat(fji[a5].fjihe,fji[a8].fjihe);
for(b1=0;b1<n;b1++)
{ fw[b1].fow[0]='\0';
}
fw[0].fow[0]='#';
fw[0].fow[1]='\0';
for(b8=0;b8<n;b8++)
{ if(shizi[b8].left==shizi[0].left)
fw[b8].fow[0]='#';
{if(shizi[b2].right[b3]==shizi[b9].left)

求First集的步骤：若X->a..，则将终结符ａ加入FIRST(X)中;若X->e ,则将终结符e加入FIRST(X)中(e表示空集)；若X->BC..D,则将First（B）所有元素（除了空集）加入First（A），然后检测First（B），若First（B）中不存在空集,即e,则停止，若存在则向B的后面查看，将First（C）中所有元素（除了空集）加入First（A），然后再检测First（C）中是否有e...直到最后，若D之前的所有非终结符的First集中都含有e,则检测到D时，将First（D）也加入First（A），若First （D）中含有e,则将e加入First（A）。

求Follow集的步骤：对文法开始符号S,置$于FOLLOW(S)中；对于产生式：A->aBC,将除去空集e的First（C）加入Follow（B）中;对于产生式：A->aB或者A->aBC,(其中C可以推导出空串，C=>*e),则将Follow（A）加入Follow（B）中。

注意：此处a可以是空，也可以是其他文法符号）；对第二条步骤的理解：Follow（B）是B推出的串末端后的字符集合，在A->aBC的情形下，B推出串末端后的字符集，也就是C推出串首部字符的集合，即First（C）中除去e的集合。

对于第三条，其实也比较好理解，A->aB ,那么A推出字串的末端后字符集合，与B推出字串的末端后字符集合，是等价的。

求Firstvt集找Firstvt的三条规则：如果要找A的Firstvt，A的候选式中出现：A->a.......，即以终结符开头，该终结符入FirstvtA->B.......，即以非终结符开头，该非终结符的Firstvt入A的FirstvtA->Ba.....，即先以非终结符开头，紧跟终结符，则终结符入Firstvt求Lastvt集找Lastvt的三条规则：如果要找A的Lastvt，A的候选式中出现：A->.......a，即以终结符结尾，该终结符入LastvtA->.......B，即以非终结符结尾，该非终结符的Lastvt入A的LastvtA->.....aB，即先以非终结符结尾，前面是终结符，则终结符入Lastvt。

【编译原理】FIRST集、FOLLOW集算法原理和实现书中⼀些话，不知是翻译的原因。

还是我个⼈理解的原因感觉不是⾮常好理解。

个⼈重新整理了⼀下。

不过相对于消除左递归和提取左公因,FIRST集和FOLLOW集的算法相对来说⽐较简单。

书中的重点给出:FIRST:⼀个⽂法符号的FIRST集就是这个符号能推导出的第⼀个终结符号的集合, 包括空串。

例: A -> abc | def | ε那么FIRST(A) 等于 { a, d, ε }。

FOLLOW：蓝线画的部分很重要。

特别是这句话：请注意，在这个推导的某个阶段，A和a之间可能存在⼀些⽂法符号。

单如果这样，这些符号会推导得到ε并消失。

这句话的意思就是好⽐说： S->ABa B->c | ε 这个⽂法 FOLLOW(A)的值应该是FIRST(B)所有的终结符的集合（不包含ε），但是FIRST(B)是包含ε的，说明B是可空的，既然B是可空的S->ABa 也可以看成 S->Aa。

那么a就可以跟在A的后⾯.所以在这种情况下，FOLLOW(A)的值是包含a的。

换句话说就是。

⼀个⽂法符号A的FOLLOW集合就是它的下⼀个⽂法符号B的FIRST集合。

如果下⼀个⽂法符号B的FIRST集合包含ε，那么我们就要获取下⼀个⽂法符号B的FOLLOW集添加到FOLLOW(A)中代码中的注释已经很详细// 提取First集合func First(cfg []*Production, sym *Symbolic) map[string] *Symbolic {result := make(map[string] *Symbolic)// 规则⼀如果符号是⼀个终结符号，那么他的FIRST集合就是它⾃⾝if sym.SymType() == SYM_TYPE_TERMINAL || sym.SymType() == SYM_TYPE_NIL {result[sym.Sym()] = symreturn result}// 规则⼆如果⼀个符号是⼀个⾮终结符号// (1) A -> XYZ 如果 X 可以推导出nil 那么就去查看Y是否可以推导出nil// 如果 Y 推导不出nil，那么把Y的First集合加⼊到A的First集合// 如果 Y 不能推导出nil，那么继续推导 Z 是否可以推导出nil,依次类推// (2) A -> XYZ 如果XYZ 都可以推导出 nil, 那么说明A这个产⽣式有可能就是nil，这个时候我们就把nil加⼊到FIRST(A)中for _, production := range cfg {if production.header == sym.Sym() {nilCount := 0for _, rightSymbolic := range production.body { // 对于⼀个产⽣式ret := First(cfg, rightSymbolic) // 获取这个产⽣式体的First集合hasNil := falsefor k, v := range ret {if v.SymType() == SYM_TYPE_NIL { // 如果推导出nil, 标识当前产⽣式体的符号可以推导出nilhasNil = true} else {result[k] = v}}if false == hasNil { // 当前符号不能推导出nil, 那么这个产⽣式的FIRST就计算结束了，开始计算下⼀个产⽣式break}// 当前符号可以推导出nil，那么开始推导下⼀个符号nilCount++if nilCount == len(production.body) { // 如果产⽣式体都可以推导出nil，那么这个产⽣式就可以推导出nilresult["@"] = &Symbolic{sym: "@", sym_type: SYM_TYPE_NIL}}}}}return result}// 提取FOLLOW集合func Follow(cfg []*Production, sym string) [] *Symbolic {fmt.Printf("Follow ------> %s\n", sym)result := make([] *Symbolic, 0)// ⼀个⽂法符号的FOLLOW集就是可能出现在这个⽂法符号后⾯的终结符// ⽐如 S->ABaD, 那么FOLLOW(B)的值就是a。

#include<iostream>#include"string.h"#define MAX 100using namespace std;//产生式结构体struct product{int rl;char l,r[20];}p[100];//first 和follow 集struct set{int n;//元素数量char elm[100];}first[MAX],follow[MAX];int table[MAX][MAX];//预测分析表char v[100],t[100];//变量和终结符int n,vnum,tnum;//产生式数量,变量数量和终结符数量//判断是否为终结符inline bool isterminal(char x){if(x>='A'&&x<='Z')return false;return true;}//判断符号x是否从未出现过bool ex(char x){int i;if(isterminal(x)){for(i=1;i<=tnum;i++)if(t[i]==x) return true;return false;}for(i=1;i<=vnum;i++)if(v[i]==x) return true;return false;}//读入文法void load(){int i,j,k;char tmp[25];//printf("输入产生式的数量："); scanf("%d",&n);for(vnum=tnum=0,i=1;i<=n;i++) {scanf("%s",tmp);p[i].l=tmp[0];if(!ex(tmp[0])) v[++vnum]=tmp[0]; for(k=0,j=3;tmp[j];j++){p[i].r[k++]=tmp[j];if(isterminal(tmp[j])){if(!ex(tmp[j]))t[++tnum]=tmp[j];}else if(!ex(tmp[j]))v[++vnum]=tmp[j];}p[i].r[k]=0,p[i].rl=k-1;}t[++tnum]=v[++vnum]='#';}//输出用户输入的文法void show(){int i;for(i=1;i<=n;i++)printf("%c->%s\n",p[i].l,p[i].r);}//把符号x变为对应的编号int cid(char x){int i;if(!isterminal(x)){for(i=1;i<=vnum;i++)if(v[i]==x) return i;}for(i=1;i<=tnum;i++)if(t[i]==x) return i+1000;return -1;}//判断集合st里面是否包含符号idtbool inclu(struct set &st,char idt){int i;for(i=1;i<=st.n;i++)if(st.elm[i]==idt)return true;return false;}//把符号e添加到集合st里面inline void add(struct set &st,char e){st.n++;st.elm[st.n]=e;}//求first集void makefirst(){int i,j,k,idl,idr;bool inc;inc=true;while(inc){inc=false;for(i=1;i<=n;i++) //遍历所有产生式{idl=cid(p[i].l);for(j=0;p[i].r[j];j++){idr=cid(p[i].r[j]);//如果当前为终结符//并且first[idl]中不包含这个终结符就把这个终结符加入first[idl] if(idr>1000){if(!inclu(first[idl],p[i].r[j])){add(first[idl],p[i].r[j]);inc=true;}break;}//否则把该变量的first集里面的元素加入first[idl]else{for(k=1;k<=first[idr].n;k++)if(!inclu(first[idl],first[idr].elm[k])){add(first[idl],first[idr].elm[k]);inc=true;}}//.....if(!inclu(first[idl],'~')) break;}}// 若idl可以转换为空,则‘~’应属于first[idl]if(p[i].r[j]==0&&!inclu(first[idl],'~')){add(first[idl],'~');inc=true;}}}}//输出集合,flag用于表示是first还是followvoid print(struct set *st,int flag){int i,j;char *s;puts("\n");flag==0? s="FIRST":s="FOLLOW";for(i=1;i<=vnum;i++){printf("%s(%c): ",s,v[i]);for(j=1;j<=st[i].n;j++)printf("%c ",st[i].elm[j]);puts("");}}//求follow集void makefollow(){int i,j,k,idl,idr,idf;bool flag,inc=true;add(follow[1],'#');//把结束标志"#"加入起始符的follow集while(inc){inc=false;for(i=1;i<=n;i++)idl=cid(p[i].l);for(flag=true,j=p[i].rl;j>=0;j--){idr=cid(p[i].r[j]);if(idr>1000){flag=false; continue;}if(flag){for(k=1;k<=follow[idl].n;k++){if(!inclu(follow[idr],follow[idl].elm[k])){add(follow[idr],follow[idl].elm[k]);inc=true;}}}if(j<p[i].rl) idf=cid(p[i].r[j+1]);else continue;if(idf>1000){if(!inclu(follow[idr],p[i].r[j+1]))add(follow[idr],p[i].r[j+1]);continue;}for(k=1;k<=first[idf].n;k++){if(!inclu(follow[idr],first[idf].elm[k])&&first[idf].elm[k]!='~') {add(follow[idr],first[idf].elm[k]);inc=true;}}}}}}void maketable(){int i,j,k,idl,idr,idt;char ch;bool flag;memset(table,0,sizeof(table));table[vnum][tnum]=-1;for(i=1;i<=n;i++){idl=cid(p[i].l);for(j=0;j<=p[i].rl;j++){ch=p[i].r[j];idr=cid(ch);if(idr>1000){idr-=1000;if(ch!='~'){if(table[idl][idr]) goto end;table[idl][idr]=i;}else{for(k=1;k<=follow[idl].n;k++){idt=cid(follow[idl].elm[k])-1000;if(table[idl][idt]) goto end;table[idl][idt]=i;}}break;}for(flag=false,k=1;k<=first[idr].n;k++) {idt=cid(first[idr].elm[k])-1000;if(first[idr].elm[k]=='~') flag=true; if(table[idl][idt]) goto end;table[idl][idt]=i;}if(!flag) break;}if(j>p[i].rl){for(k=1;k<=follow[idl].n;k++){idt=cid(follow[idl].elm[k])-1000;if(table[idl][idt]) goto end;table[idl][idt]=i;}}}return;end: printf("It's not a LL(1) language,and if you want to use this program to compile you may get a wrong answer!\n");return;}void compile(char *exp){int i,j,top,idl,idr,t,step[MAX],c=0;char stack[MAX];top=1;t=strlen(exp);stack[0]='#',stack[1]=v[1];exp[t]='#',exp[t+1]=0;for(i=0;;){idl=cid(stack[top]);idr=cid(exp[i])-1000;if(idl>1000) goto fail;t=table[idl][idr];if(t==0) goto fail;step[++c]=t;for(top--,j=p[t].rl;j>=0;j--){if(p[t].r[j]!='~')stack[++top]=p[t].r[j];}while(top>=0&&exp[i]&&stack[top]==exp[i]){if(stack[top]=='#') goto pass;top--,i++;}}pass: printf("Accept!\n");for(i=1;i<=c;i++)printf("%c->%s\n",p[step[i]].l,p[step[i]].r);return;fail: printf("Compile Error!\n");return;}int main(){char exp[MAX];freopen("LL(1).txt","r",stdin); load();show();makefirst();print(first,0);makefollow();print(follow,1);maketable();while(scanf("%s\n",exp)!=EOF) compile(exp);return 0;}。