计算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推出的串的⾸部，就不是那些推出空串的⾮终结符了，⽽是这些推出空串的⾮终结符后⾯的⽂法符号所推导出的字串。

4、运行结果分析 5、总结
2、分析、设计、实现 通过对产生式的顺序扫描，运用上述规则，把每种规则都转换为相应的算法，经过规则后 将产生的 First 集存下来。 流程图 3、函数与过程的功能(MFC) CString CFirstAndFollow::First(char Vn,char PVn) { CString result,tmpresult; char tmpmid; int tmpflag; if(Vns.Find(Vn,0)==-1&&Vn!=';'&&Vn!='|') { result.Insert(result.GetLength(),Vn); return result; } for(int ix=0;ix<Vpro.GetLength();ix++) { ix=Vpro.Find(Vn,ix); if(Vpro.GetAt(ix-1)==';') { tmpflag=ix; break; } } tmpflag+=3; for(ቤተ መጻሕፍቲ ባይዱnt index=tmpflag;index<Vpro.GetLength();index++) { char tmp=Vpro.GetAt(index); tmpmid=tmp; if(Vns.Find(tmp,0)>=0) // Vn { if(tmp==PVn || tmp==Vn) { do
1、问题描述
题目： First 集和 Follow 集生成算法模拟 设计一个由正规文法生成 First 集和 Follow 集并进行简化的算法动态模拟。 动态模拟算法的基本功能是： ⅰ. 输入一个文法 G； ⅱ. 输出由文法 G 构造 FIRST 集的算法； ⅲ. 输出 First 集； ⅳ. 输出由文法 G 构造 FOLLOW 集的算法； ⅴ. 输出 FOLLOW 集。

【编译原理】语法分析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)，

计算f i r s t集合和f o l l o w集合--编译原理计算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 后的终结符号的集合。

{
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集合的求法是：紧跟随其后面的终结符号或＃。

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

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

LL(1)文法判别之First集合、Follow集合说明：所有大写字母代表非终结符，小写字母代表终结符，省略号代表未知数目（可能为0）的不确定类型的文法符号。

First集合：First集合顾名思义就是求一个文法符号串所可能推导出的符号串的第一个终结符的集合。

First（X）就是求X所有推导出的符号串的第一个符号的集合。

求First集合可分如下几种情况:单个符号的First集合：单个终结符的First集合就是它自己。

单个非终结符的First集合：A-->a…产生式右部以终结符开头根据定义，这种情况下显然可以看出a属于First(A)。

A-->B…产生式右部以非终结符开头根据定义，既然可以把A替换成B……，也可以看出First（B）属于First（A）。

这是一个递归的推导。

多个符号形成的符号串的First结合：符号串ABC…，并且A不能推导出空串ε当A不能推导出空串ε，显然根据定义First（ABC…）=First（A）符号串ABC…，并且A可能推导出空串ε当A不是空串的时候，显然First（A）属于First（ABC…），但当A是空串的时候，ABC…就成了BC…，此时根据B是否能推出空串来决定是否将First（B）加入First （ABC…）。

这是一个递归的推导，综上所述，符号串中的第一个不能推出空串的符号前面所有符号的First集合减去空串ε都属于First（ABC…），第一个不能推出空串的符号的First集合也属于First（ABC…）。

也就是假设A、B都可以推出空串，C不能推出空串，First（ABC…）=First（A）-ε∪First（B）-ε∪First（C）。

符号串ABC…，并且所有的符号ABC…都可能推导出空串ε此时First（ABC…）就是所有符号的First集合的并集注意：First集合中的符号一定是终结符，终结符也包括空串ε。

Follow集合：Follow集合也是顾名思义的，就是文法符号后面可能跟随的终结符的集合（不包括空串ε）。

编译原理第三章练习题答案编译原理第三章练习题答案编译原理是计算机科学中的重要学科，它研究的是如何将高级语言代码转化为机器语言的过程。

在编译原理的学习过程中，练习题是不可或缺的一部分，通过完成练习题可以更好地理解和掌握编译原理的知识。

本文将为大家提供编译原理第三章练习题的答案，希望对大家的学习有所帮助。

1. 什么是语法分析？语法分析是编译器中的一个重要模块，它的主要任务是根据给定的语法规则，对输入的源代码进行分析和解释。

语法分析器会根据语法规则构建一个语法树，用于表示源代码的结构和含义。

常用的语法分析方法有递归下降法、LL(1)分析法和LR分析法等。

2. 什么是LL(1)文法？LL(1)文法是一种特殊的上下文无关文法，它具有以下两个特点：(1) 对于任何一个句子，最左推导和最右推导是唯一的。

(2) 在预测分析过程中，只需要向前看一个输入符号就可以确定所采用的产生式。

LL(1)文法是一种常用的文法形式，它适用于递归下降法和LL(1)分析法。

3. 什么是FIRST集合和FOLLOW集合？FIRST集合是指对于一个文法符号，它能够推导出的终结符号的集合。

FOLLOW 集合是指在一个句型中，某个非终结符号的后继终结符号的集合。

计算FIRST集合和FOLLOW集合可以帮助我们进行语法分析，特别是LL(1)分析。

4. 什么是递归下降语法分析法？递归下降语法分析法是一种基于产生式的自顶向下的语法分析方法。

它的基本思想是从文法的开始符号开始，递归地根据产生式进行分析，直到推导出输入符号串或发现错误。

递归下降语法分析法的实现比较简单，但对于某些文法可能会出现回溯现象，影响分析效率。

5. 什么是LR分析法？LR分析法是一种自底向上的语法分析方法，它的基本思想是从输入符号串开始，逐步构建语法树，直到推导出文法的开始符号。

LR分析法具有较好的分析效率和广泛的适用性，常用的LR分析方法有LR(0)、SLR(1)、LR(1)和LALR(1)等。

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

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

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

我们这次课程设计的主要任务是编程实现对给定文法的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 集构造分析表，分析给定句子的合法性。

2first集确定了每一个非终结符在扫描输入串时所允许遇到的输入符号及所应采用的推导产生式集确定了每一个非终结符在扫描输入串时所允许遇到的输入符号及所应采用的推导产生式该非终结符所对应的产生式中的哪一个候选式33自顶向下的语法分析式中的哪一个候选式3follow集是针对文法中形如a这样的产生式的即在使用这样的产生式的即在使用a的产生式进行推导时面临输入串中哪些输入符号时有一空字的产生式进行推导时面临输入串中哪些输入符号时有一空字即匹配而不出错
课本例题3.8 第二步：计算非终结符的FOLLOW集合
G[E]: E→TE' E'→ + TE' | ε T→FT' T'→*FT' | ε F→(E) | i ③由E→TE' 知FOLLOW(E) ⊂ FOLLOW(E' )， 即FOLLOW(E' ) = {),#}； 由E→TE ' 且E ' → ε知FOLLOW(E)FOLLOW(T)，即 FOLLOW(T) = {+,),#}；
特别是当Y1～Yk均含有ε产生式时，应把ε也加到FIRST(X)中。
课本例题3.8 第一步：计算非终结符的FIRST集合 例3.8 试构造表达式文法G[E]的LL(1)分析表，其中： G[E]: E→TE' E'→ + TE' | ε T→FT' T'→*FT' | ε F→(E) | i
[解答] 首先构造FIRST集，步骤如下： ① FIRST(E') = {+, ε}； FIRST(T') = {*, ε}； FIRST(F) = {(, i}； ② T→F… 和E→T…知:FIRST(F) ⊂ FIRST(T) ⊂ FIRST(E) 即有FIRST(F) = FIRST(T) = FIRST(E) = {(,i}。

计算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;{ 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++){{ 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;}}}四、运行截图（注：专业文档是经验性极强的领域，无法思考和涵盖全面，素材和资料部分来自网络，供参考。

【编译原理】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。

first集合和follow集合的求法编译原理是计算机专业中的重要学科，其中语法分析是编译原理的基础。

而语法分析器（Parser）的核心就是构建语法分析表格。

而在构建语法分析表格的过程中，first集合和follow集合的求法是一个非常重要的问题，本文就将详细介绍first集合和follow集合的求法。

一、first集合first集合指的是文法中每个非终结符号的经过一次推导得到的所有终结符号的集合，也就是最小前缀（First）的集合。

例如对于一个简单的文法表达式E→E+T|T,其中E和T是非终结符号，+是终极符号。

那么开始寻找E的first集合时，我们应该先判断E能够推导出哪些符号，根据文法表达式，E可以推导出E+T和T。

接着我们可以判断E+T和T 所能推导出的所有终结符号，并将这些终结符号加入到E的first集合中。

具体步骤可以参考下面的推导过程：E → E + TE → TT → a那么最终E的first集合就是{a,+}。

二、follow集合follow集合指的是文法中每个非终结符号在所有推导过程中后跟的符号的集合。

例如对于一个简单的文法表达式E→E+T|T,其中E和T是非终结符号，+是终极符号。

求解E的follow集合时，首先要考虑的是E出现在了哪些地方。

通过分析E在文法表达式中的位置，我们可以发现E出现在了三种不同的情况下：1. E是文法的起始符号，此时E的follow集合中必须包含结束符$。

2. E出现在某些规则的右侧，此时E的follow集合中必须包含右侧的符号的first集合，但是需要注意的是，如果推导出空串，则应该将右侧的非终结符号所在位置的follow集合添加进来。

3. E的右侧是其所在规则的最末尾，此时需要将E所在规则的左侧符号所在位置的follow集合添加到E的follow集合中。

根据以上三种情况，我们可以结合上面的文法表达式来推导出E的follow集合。

具体步骤可以参考下面的推导过程：S → EE → E + TE → TT → a1. $ ∈ follow(E)2. follow(T) = {+, $}follow(E) = first(T) ∪ {+, $}follow(E) = {+, a, $}3. follow(E) = {+, $}那么最终E的follow集合就是{+, a, $}。

XXX-编译原理-命题作业-LL(1)文法的判断(完整答案)LL(1)文法的判断LL(1)文法本质含义是第一个L表明自顶向下分析是从左向右扫描输入串，第2个L表明分析过程中将使用最左推导，1表明只需向右看一个符号便可决定如何推导，即选择哪个产生式进行推导。

给定文法G：E ->TE'E'->+E|εT ->FT'T' ->T|εF-。

PF'F'-。

*F'|εP->(E)|a|b|^1) 计算该文法每个非终结符的FIRST集和FOLLOW集。

首先计算FIRST集合：FIRST(E) = FIRST(T) = FIRST(F) = FIRST(P) = {(。

a。

b。

^)}FIRST(E') = {+。

ε}FIRST(T') = FIRST(T) + {ε} = {(。

a。

b。

^。

ε)}FIRST(F') = {*。

ε}FIRST(P) = {(。

a。

b。

^)}然后计算FOLLOW集合：FOLLOW(E) = {)。

#}FOLLOW(E') = FOLLOW(E) = {)。

#}FOLLOW(T) = FIRST(E') ∪ FOLLOW(E) = {+。

)。

#}FOLLOW(T') = FOLLOW(T) = FIRST(E') ∪ FOLLOW(E) = {+。

)。

#}FOLLOW(F) = FIRST(T') ∪ FOLLOW(T) = {(。

a。

b。

^。

+。

)。

#}FOLLOW(F') = FOLLOW(F) = FIRST(T') ∪ FOLLOW(T) = {(。

a。

b。

^。

+。

)。

#}FOLLOW(P) = FIRST(F') ∪ FOLLOW(F) = {*。

(。

a。

b。

^。

+。

)。

#}2) 证明该方法是LL(1)的。