计算first集follow集
编译原理实验报告
实验名称计算first集合和follow集合实验时间 2016年6月8日
院系计算机科学与技术
班级计算机科学与技术（1）班学号
姓名
1.试验目的：
输入：任意的上下文无关文法。
输出：所输入的上下文无关文法一切非终结符的first 集合和follow 集合。
2.实验原理：
设文法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）；
3.实验代码与结果：
输入格式：
每行输入一个产生式，左部右部中间的→用空格代替。
非终结符等价于大写字母
^ 表示空
输入到文件结束，或用 0 0 结尾。
以编译原理（清华大学第二版）5.6典型例题及答案中的例题一为例（96页）：
#include
#include
#include
#include
#include
using namespace std;
char l;
string r;
multimap
multimap
set
map
bool flag;
set
vector
char Begin;
bool capL(char c) //字母是否大写
{
if(c<='Z' && c>='A')
return true;
return false;
}
bool CapLString(string s) // 大写字符串
{
for(int i=0; i if(!capL(s[i])) { return false; } } return true; } bool isToEmpty(char ch) // 判断终结符能否推出空 { bool flag; flag = false; multimap int cnt = sentence.count(ch); for(int i=0; i if(mIter->second=="^") { return true; } else if(CapLString(mIter->second)){ string s(mIter->second); bool flag2 = true; for(int j=0; j if(!isToEmpty(s[j]) || s[j]==ch) { flag2 = false; break; } } if(flag2) { // 右部全为终结符，全能推出空 return true; } } } // } return false; } void getFirst(char ch, set { multimap if(imul==sentence.end()) return; int sum = sentence.count(imul->first); for(int i=0; i string s(imul->second); for(int j=0; j if(!capL(s[j])) { First.insert(s[j]); break; } else if(capL(s[j])) { if(s[j]==ch) { //有左递归,跳出循 环 break;; } getFirst(s[j], First); if(toEmpty[s[j] ]==false) { break; } } } } flag = true; } bool isLast(string s, char ch) //ch 是否是 s 的直接或间接的最后一个非终结符 { if(!capL(ch)) return false; for(int i=s.size()-1; i>=0; i--) { if(ch==s[i]) return true; if(!capL(s[i]) || toEmpty[s[i] ]==false) { return false; } } return false; } void getFollow(char ch, set { if(!capL(ch)) return; for(vector for(int i=0; i<(*iter).size(); i++) { if(ch==(*iter)[i] && i!=(*iter).size()-1) { if(!capL((*iter)[i+1])) { follow.insert((*iter)[i+1]); } else { getFirst((*iter)[i+1], follow); } } if(ch==(*iter)[i] && i==(*iter).size()-1) { //判断是否是右部的最后一个非终结符 follow +# follow.insert('#'); } else if(ch==(*iter)[i] && i<(*iter).size()-1){ // 不是最后一个但之后全是非终结符且都能推出空 follow +# bool flag1=true; for(int j=i+1;j<(*iter).size(); j++) { if(!capL((*iter)[j]) || toEmpty[(*iter)[j]]==false) { flag1 = false; if(!capL((*iter)[j])) { follow.insert((*iter)[j]); } break; } } if(flag1 == true) { follow.insert('#'); } } } if(isLast(*iter, ch)) { //ch是*iter的最后一个符号（直接或间接） int n = senRever.count(*iter); multimap for(int i=0 ;i if(mIter->second!=ch ) getFollow(mIter->second, follow); } } } } int main() { int cnt=0; while(cin>>l>>r) { if(cnt==0) { Begin = l; cnt++; } if(l=='0') break; sentence.insert(make_pair(l, r)); //产生式 senRever.insert(make_pair(r,l)); ter.insert(l); //非终结符集合(左部) rightSide.push_back(r); //右部的集合} for(set if(isToEmpty(*sIter) ) { toEmpty[*sIter] = true; } else { toEmpty[*sIter] = false; } } for(set cout<<*iter<<" FIRST集 :"; fir.clear(); getFirst(*iter, fir); for(set cout<<" "<<*iterF; } cout< follow.clear(); getFollow(*iter, follow); cout<<" FOLLOW集:"; if(*iter==Begin) { cout<<" #"; } for(set if(*iterF!='^') cout<<" "<<*iterF; } cout< } system("pause"); return 0; } 课程设计(论文)任务书 软件学院学院软件测试专业 1 班 一、课程设计(论文)题目 first集和follow集生成算法模拟 二、课程设计(论文)工作自2015 年 6 月16 日起至2013 年6 月 19 日止。 三、课程设计(论文) 地点: 软件学院实训中心 四、课程设计(论文)内容要求： 1．本课程设计的目的 进一步培养学生编译器设计的思想，加深对编译原理和应用程序的理解，针对编译过程的重点和难点内容进行编程，独立完成有一定工作量的程序设计任务，同时，强调好的程序设计风格，并综合使用程序设计语言、数据结构和编译原理的知识, 熟悉使用开发工具VC /JA V A/C#/.NET 。 2．课程设计的任务及要求 1）课程设计任务： 设计一个由正规文法生成First集和Follow集并进行简化的算法动态模拟。 2）创新要求： 动态模拟算法的基本功能是： （１）输入一个文法Ｇ （２）输出由文法G构造的FIRST集算法 （３）输出FIRST算法 （４）输出由文法G构造的FOLLOW集算法 （５）输出FOLLOW集 3）课程设计论文编写要求 （1）课程设计任务及要求 （2）设计思路--工作原理、功能规划 （3）详细设计---数据分析、算法思路、功能实现（含程序流程图、主要代码及注释）、界面等。 （4）运行调试与分析讨论---给出运行屏幕截图，分析运行结果，有何改进想法等。 （5）设计体会与小结---设计遇到的问题及解决办法，通过设计学到了哪些新知识，巩固了哪些知识，有哪些提高。 （6）报告按规定排版打印，要求装订平整，否则要求返工； （7）课设报告的装订顺序如下：封面---任务书---中文摘要---目录----正文---附录(代码及相关图片) （8）严禁抄袭，如有发现，按不及格处理。 4）课程设计评分标准： （1）学习态度：20分； （2）系统设计：20分； （3）编程调试：20分； （4）回答问题：20分； （5）论文撰写：20分。 5）参考文献： （1）张素琴，吕映芝. 编译原理[M]., 清华大学出版社 （2）蒋立源、康慕宁等，编译原理（第2版）[M]，西安：西北工业大学出版社 6）课程设计进度安排 1．准备阶段（4学时）：选择设计题目、了解设计目的要求、查阅相关资料 2．程序模块设计分析阶段（4学时）：程序总体设计、详细设计 3．代码编写调试阶段（8学时）：程序模块代码编写、调试、测试 4．撰写论文阶段（4学时）：总结课程设计任务和设计内容，撰写课程设计论文 学生签名： 2015 年 6 月19 日 课程设计(论文)评审意见 （1）学习态度（20分）：优（）、良（）、中（）、一般（）、差（）；（2）系统设计（20分）：优（）、良（）、中（）、一般（）、差（）；（3）编程调试（20分）：优（）、良（）、中（）、一般（）、差（）；（4）回答问题（20分）：优（）、良（）、中（）、一般（）、差（）；（5）论文撰写（20分）：优（）、良（）、中（）、一般（）、差（）； 评阅人：职称：讲师 2015 年 6 月19 日 编译原理实验报告 实验名称计算first集合和follow集合实验时间 院系计算机科学与技术 班级软件工程1班 学号 姓名 输入：任意的上下文无关文法。 输出：所输入的上下文无关文法一切非终结符的first 集合和follow 集合。 2. 实验原理 设文法G[S]＝（V N ，V T ，P ，S ），则首字符集为： FIRST （α）＝{a|α?* a β，a ∈V T ，α,β∈V G }。 若α?* ε，ε∈FIRST （α）。 由定义可以看出，FIRST （α）是指符号串α能够推导出的所有符号串中处于串首的终结符号组成的集合。所以FIRST 集也称为首符号集。 设α＝G 1G 2…G n ，FIRST （α）可按下列方法求得： 令FIRST （α）＝Φ，i ＝1； （1） 若G i ∈V T ，则G i ∈FIRST （α）； （2） 若G i ∈V N ； ①若ε?FIRST （G i ），则FIRST （G i ）∈FIRST （α）； ②若ε∈FIRST （G i ），则FIRST （G i ）－{ε}∈FIRST （α）； （3） i ＝i+1，重复（1）、（2），直到G i ∈V T ，（i ＝2，3，…，n ）或G i ∈V N 且若ε?FIRST （G 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 →GAy 的规则，其中G ，y ∈V G ，则FIRST （y ）－{ε}∈FOLLOW （A ）； （3） 若文法G[S]中有形如B →GA 的规则，或形如B →GAy 的规则且ε ∈FIRST （y ），其中G ，y ∈V G ，则FOLLOW （B ）∈FOLLOW （A ）； 1 编译原理 2013年11月28日 LL 的含义 －自左向右扫描分析输入符号串 －从识别符号开始生成句子的最左推导 LL(1):向前看一个输入符号，便能唯一确定当前应选择的规则LL(k):向前看k 个输入符号，才能唯一确定当前应选择的规则 4.2.3 LL(1)文法的判别 要构造确定的自顶向下分析程序要求描述文法必须是LL(1)文法 2 编译原理 2013年11月28日 同一非终结符有多个候选式时 引起回溯的原因 【例4.1】α=acb G[S]:S →aAb A →cd|c （1）候选式的终结首符号相同 （2）候选式的终结首符号相同 【例4.8】S →Aa A →a| 3 编译原理 2013年11月28日 1. FIRST 集 FIRST(α)：从α可能推导出的所有开头终结符号或ε对于文法G 的所有非终结符的每个候选式α，其终结首符号集称为FIRST 集，定义如下： ε，则规定ε∈FIRST(α) 若α 【例】S →aAb A →cd|c a …，a ∈V T FIRST(α)={a|α FIRST(aAb )={a}FIRST(cd )={c}FIRST(c )={c} 【例】S →Aa A →a|ε FIRST(a )={a}FIRST(ε)= {ε}FIRST(Aa)={a} FIRST(S )={a}FIRST(A )={c} FIRST(S )={a}FIRST(A )={a, ε} 4 编译原理 2013年11月28日 （1）若α=a α′，且a ∈V T ，则a ∈FIRST(α)； 例：FIRST(i)={i} FIRST(+TE')={+} E →TE'E'→+TE'|ε T →FT'T'→*FT'|ε F →(E)|i 构造FIRST 集的算法 （2）若α=X α′，X ∈V N ，且有产生式X →b …，则把b 加入到FIRST(α)中；例：FIRST(FT')={(,i} ?? 编译原理实验报告记录FIRST集和FOLLOW集 ————————————————————————————————作者：————————————————————————————————日期： 编译原理实验报告实验名称计算first集合和follow集合实验时间 院系计算机科学与技术 班级软件工程1班 学号 姓名 输入：任意的上下文无关文法。 输出：所输入的上下文无关文法一切非终结符的first 集合和follow 集合。 2. 实验原理 设文法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 ）； 编译原理实验 实验名称：求first集和follow集姓名： 学号： 教师签字： 成绩： 一．实验目的： .掌握和了解first集和follow集的求解过程。 二．实验原理： 1.first集的求解：（1）若X∈Vt,则FIRST(X)={X}; (2)若X∈Vn,且有产生式X->a……,a∈Vt，则a∈FIRST(X); (3)若X∈Vn,X->@,则@∈FIRST(X) (4)若X,Y1,Y2,Y3,Y4…………Yn都∈Vn,而产生式X->Y1,Y2……Yn.当 Y1,Y2,Y3,Y4…………Yn都能=>@那么FIRST(X)=并集的 FIRST(Yi)-{@}(0<=i<=n) (5)若Yi=>@(i=1,2,3……)，则FIRST(X)=并集的FIRST(Yi)-{@}并上{@} 2.follow集的求解：（1）若为文法开始符号S，则FOLLOW(S)={#} (2)若为文法A->aBb是一个产生式，则把FIRST（b）的非空元素加入 FOLLOW(B)中。如果b->@则把FOLLOW(A)也加入FOLLOW(B)中。三．实验代码 #include 构造FIRST集和FOLLOW集的方法 1、构造FIRST集的算法 (1) 对于G中的每个文法符号X,为求FIRST(X),反复应用如下规则,直到集合不再增大: ①若X∈V T，则FIRST(X)是{X} ②若X∈V N ,且X→aα(a∈V T )，则{ a } ? FIRST(X) X→ε，则{ε} ? FIRST(X) ③若X->Y1Y2…Y i-1 Y i…Y K∈P,Y1∈V N ,则 FIRST(Y1)-{ε} ? FIRST(X) 而对所有的j(1≤j ≤i-1), Y j∈V N，且Y j??ε，则令 FIRST(Y j)-{ε} ? FIRST(X) (1≤j ≤i) 特别，当ε∈FIRST(Y j) (1≤j ≤k)时，令ε∈FIRST(X) (2) 对文法G的任何符号串α=X1X2…X n构造集合FIRST(α) ①置FIRST(X1)-{ε} ? FIRST(α) ②若对任何1≤j≤i-1，ε∈FIRST(X j)， 则FIRST(X i) -{ε} ? FIRST(α) 特别是，若所有的FIRST(X j)均含有ε，1≤j≤n，则{ε} ? FIRST(α)。 显然，若α＝ε则FIRST(α)＝{ε}。 2、构造FOLLOW集的算法 对于G中的每一A∈V N，为构造FOLLOW(A)，可反复使用如下的规则，直到每个FOLLOW集不再增大为止: ①对于文法的开始符号S，令# ∈FOLLOW(S)。 ②对于每一A→αBβ∈P， 令FIRST(β) - {ε} ? FOLLOW(B) 。 ③对于每一A→αB∈P， 或A→αBβ∈P，且ε∈FIRST(β)， 则令FOLLOW(A) ? FOLLOW(B) 。 华东交通大学 课程设计（论文）任务书 软件学院专业项目管理班级2005－4一、课程设计（论文）题目正规文法的First集合Follow集求解过程动态模拟 二、课程设计（论文）工作：自2008年6月23 日起至2008年 6 月27 日止。 三、课程设计（论文）的内容要求： 1、基本要求： 进一步培养学生编译器设计的思想，加深对编译原理和应用程序的理解，针对编译过程的重点和难点内容进行编程，独立完成有一定工作量的程序设计任务，同时强调好的程序设计风格，并综合使用程序设计语言、数据结构和编译原理的知识，熟悉使用开发工具VC 6.0 或其它软件编程工具。 为了使学生从课程设计中尽可能取得比较大的收获，对课程设计题目可根据自己的兴趣选题（须经老师审核），或从老师给定题目中选择完成（具体见编译原理课程设计题目要求）。 通过程序实现、总结报告和学习态度综合考评，并结合学生的动手能力，独立分析解决问题的能力和创新精神。成绩分优、良、中、及格和不及格五等。 2、具体要求 设计一个由正规文法生成Fisrt集Follow集的动态过程模拟 动态模拟算法的基本功能是： ●输入一个正规文法； ●输出由文法构造的First集的算法； ●输出First集； ●输出由文法构造的Follow集的算法； ●输出Follow集； 学生签名： 2008 年 6 月 27 日 课程设计（论文）评阅意见 评阅人职称副教授 2008 年 6 月 27 日 目录 一、需求分析 (3) 二、总体设计 (4) 三、详细设计 (9) 四、课设小结 (12) 五、谢辞 (13) 六、参考文献 (14) 计算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 课程名称: LL1文法的判别 年级/专业/班: 11级计算机类（二）班 姓名: 徐勇兵 学号： E01114278 import java.util.Vector; import javax.swing.JOptionPane; class Tools{ public Vector for(int i=0;i 计算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 后的终结符号的集合。 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 第五章 2．对下面的文法G： E→TE/ E/→+E|ε T→FT/ T/→T|ε F→PF/ F/→*F/|ε P→(E)|a|b|^ (1)计算这个文法的每个非终结符的FIRST集和FOLLOW集。 (2)证明这个方法是LL(1)的。 (3)构造它的预测分析表。 (4)构造它的递归下降分析程序。 解： （1）计算这个文法的每个非终结符的FIRST集和FOLLOW集。FIRST集合有： FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^}; FIRST(E/)={+,ε} FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^}; FIRST(T/)=FIRST(T)∪{ε}={(,a,b,^,ε}; FIRST(F)=FIRST(P)={(,a,b,^}; FIRST(F/)=FIRST(P)={*,ε}; 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)的。 各产生式的SELECT集合有： SELECT(E→TE/)=FIRST(T)={(,a,b,^}; SELECT(E/→+E)={+}; SELECT(E/→ε)=FOLLOW(E/)={),#} SELECT(T→FT/)=FIRST(F)={(,a,b,^}; SELECT(T/→T)=FIRST(T)={(,a,b,^}; SELECT(T/→ε)=FOLLOW(T/)={+,),#}; SELECT(F→PF/)=FIRST(P)={(,a,b,^}; SELECT(F/→*F/)={*}; SELECT(F/→ε)=FOLLOW(F/)={(,a,b,^,+,),#}; SELECT(P→(E))={(} SELECT(P→a)={a} 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集合的求法是：紧跟随其后面的终结符号或＃。但文法的识别符号包含＃，在求的时候还要考虑到ε。具体做法是把所有包含你要求的符号的产生式都找出来，再看哪个有用。 Follow（S）=｛＃｝如求A的，产生式：S→ABc A→a|ε，但只有S→ABc 有用。跟随在A后年的终结符号是FIRST（B）=｛b，ε｝，当FIRST（B）的元素为ε时，跟随在A 后的符号就是c，所以 Follow（A）=｛b，c｝同理Follow（B）=｛c｝。 编译原理实验报告 实验名称 计算first 集合和follow 集合 实验时间 2016年6月8日 院 系 计算机科学与技术 班 级 计算机科学与技术（1）班 学 号 姓 名 1.试验目的： 输入：任意的上下文无关文法。 输出：所输入的上下文无关文法一切非终结符的first 集合和follow 集合。 2.实验原理： 设文法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 ）； 3.实验代码与结果： 输入格式： 每行输入一个产生式，左部右部中间的→用空格代替。 非终结符等价于大写字母 ^ 表示 空 输入到文件结束，或用 0 0 结尾。 以编译原理（清华大学第二版）5.6典型例题及答案中的例题一为例（96页）： #include 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集合也是顾名思义的，就是文法符号后面可能跟随的终结符的集合（不包括空串ε）。 Follow(X)就是求X后面可能跟随的符号集合。 求Follow集合可分如下几种情况: 终结符的Follow集合没有定义，只有非终结符才会有Follow集合。 A-->…Ua…要求的Follow集合的非终结符后跟终结符 构造预测分析表 源程序： #include char empty[20]; /*记录可直接推出@的符号*/ char TEMP[50]; /*求FOLLOW时存放某一符号串的FIRST集合*/ int validity=1; /*表示输入文法是否有效*/ int ll=1; /*表示输入文法是否为LL(1)文法*/ int M[20][20]; /*分析表*/ char choose; /*用户输入时使用*/ char empt[20]; /*求_emp()时使用*/ char fo[20]; /*求FOLLOW集合时使用*/ /******************************************* 判断一个字符是否在指定字符串中 ********************************************/ int in(char c,char *p) { int i; if(strlen(p)==0) return(0); for(i=0;;i++) { if(p[i]==c) FOLLOW集的那些事儿 一、学习FOLLOW集运算的重要性（男生必看） mm说：“我爱你。” 他脸红了，他不想害她：“我没钱，更没有房子和车。” mm盯着他的眼睛：“我知道。” “我的月薪只有一千五。” mm的目光仍然坚定无比：“以后会多的。” 他用颤抖的双手拿出一支烟叼在嘴上：“我每天要抽一包烟，一喝酒就闹事。” mm笑了，“以后有我在，你放心。” 他的脊梁上冒起一阵寒意，结结巴巴地对她说：“其实……其实我很流氓……幼儿园就喜欢去女厕所，小学就没了初吻，中学就……” mm没等他说完就软在了他的怀里，声音细若蚊鸣：“早知道你好色，你老偷偷瞄我…” 他抱紧了mm，温热娇小的身体让他热血沸腾。这时他忽然想到了一件很重要的事情，他决定把这事告诉mm...... 五秒钟后mm抬头问他：“真的？”他决然地点点头。mm沉默片刻挣开他的怀抱抬手给了他一个耳光，她愤怒地朝他喊道：“你丫竟然不懂编译原理中的FOLLOW集！” 二、为什么需要FOLLOW集运算 在开讲之前，吾先假设汝应该而且必须已经明白了FIRST集的作用—帮助编译器在语法分析时无回溯、敏捷高效、一键式地挑选用来替换某个非终结符的多个候选式中的一个。 所以，FIRST集的思想对于建设一个和谐的语法分析器是多么的重要啊！（摘自<万老师学编译>之“FIRST集,他好我也好，耶！”） 但是科学的发展观告诉我们花无百日好，人无完人，FIRST集也有其自身的制约，那就是，对于包含ε的候选式不能用FIRST来说明何时用ε来替换。 补充说明：在文法中，如果某个非终结符的候选式是ε，就说明该非终结符代表的语法成分在句子中是可选的（可有可无，不是必须得）。例如，如下的 《编译原理》 课程实验报告 实验六：计算first集合和follow集合 编译原理实验报告 姓名：滕雯娟学号：E10914008 专业：计算机科学与技术年级：09 级2班实验时间：2012/6/7 成绩： 实验六：计算first集合和follow集合 实验目的： 1．掌握求first和follow集合的算法 2．熟悉运用C/C++语言对求first和follow集合进行实现 实验要求： 输入：任意的上下文无关文法。 输出：所输入的上下文无关文法一切非终结符的first集合和follow集合 实验原理： 设α＝x1x2…xn，FIRST（α）可按下列方法求得： 令FIRST（α）＝Φ，i＝1； （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为止。 当一个文法中存在ε产生式时，例如，存在A→ε，只有知道哪些符号可以合法地出现在非终结符A之后，才能知道是否选择A→ε产生式。这些合法地出现在非终结符A之后的符号组成的集合被称为FOLLOW集合。下面我们给出文法的FOLLOW集的定义。 设文法G[S]＝（VN，VT，P，S），则 FOLLOW（A）＝{a | S …Aa …，a∈VT}。 若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）； 求解FOLLOW集的方法 刚刚学习FOLLOW集时总是容易忽略一些条件而造成错误，学会FOLLOW集的求解对于编译原理的学习很重要，一旦求错就容易造成分析SLR(1)分析表时出现错误。 1、对文法中的每个A属于V n，计算FOLLOW(A): (1)、对文法的开始符号S，将“$”加到FOLLOW(S)中; (2)、若A->aBb是一条规则，则把FIRST(b)中的非ε元素加到FOLLOW(B)中; (3)、若A->aB或A->aBb是一条规则且b=>ε,则把FOLLOW(A)加到FOLLOW(B)中; (4)、反复使用(2)、(3)，直到每个非终结符的FOLLOW集不再增大为止。 看完规则，难免觉得有些许枯燥，下面我将列举一个较复杂的例子，可以使用到上述的全部规则。 eg: 设有文法G[A]： A→BCc | gDB B→bCDE |ε C→DaB | ca D→dD |ε E→gAf | c 计算该文法的每一个非终结符的FIRST集和FOLLOW集。 解：（1）、FIRST集的求解： FIRST(A) = FIRST(BCc) ∪ FIRST(gDB) = FIRST(B) ∪ FIRST(C) ∪ {c} ∪ {g} = {b} ∪ FIRST(D) ∪ {a} ∪ {c,,g} = {a,b,c,d,g} 同理： FIRST(B) = {b,ε} FIRST(C) = {a,c,d} FIRST(D) = {d,ε} FIRST(E) = {g,c} （2）、接下来求解FOLLOW集： a、由于A是文法的开始符号，所以$属于FOLLOW(A)，由E→gAf | c l利用规则(2)可知f属于FOLLOW(A),所以FOLLOW(A)={f,$} b、由A→BCc利用规则(2)把FIRST(C)中的非ε元素加到FOLLOW(B)中，利用规则(3)把FOLLOW(A)加到FOLLOW(B)中;所以a,c,d,f,$属于FOLLOW(B).此外，由A→gDB ，C→DaB利用规则(3)把 FOLLOW(A),FOLLOW(C)加到FOLLOW(B)中,由于还没求FOLLOW(C)，暂不求FOLLOW(B). c、由A→BCc利用规则(2)把FIRST(c)加入FOLLOW(C),则c属于first集和follow集生成算法模拟
【8A版】编译原理实验报告FIRST集和FOLLOW集
编译原理一点就通first follow LL()
编译原理实验报告记录FIRST集和FOLLOW集
求first集和follow集
构造FIRST集和FOLLOW集的方法
正规文法的First集合Follow集求解过程动态模拟-实验报告
计算first集合和follow集合--编译原理
LL1 first follow集
计算first集合和follow集合--编译原理教案资料
编译原理第五章
编译原理 FIRST集和FOLLOW集的求法
计算first集follow集
LL(1)中First和Follow集合的求法
first集follow集求解算法与构造预测分析表
LL(1)文法讲解之二 Follow集的计算
实验六计算first集合和follow集合
求解FOLLOW集的方法
- LL(1)中First和Follow集合的求法
- 编译原理习题课
- 计算first集follow集
- 编译原理一点就通first follow LL()
- 计算first集合和follow集合--编译原理
- 编译原理实验报告FIRST集和FOLLOW集
- 编译原理实验报告FIRST集和FOLLOW集
- 编译原理(清华大学第二版)第05章习题第二题参考答案
- first集follow集求法
- 编译原理JAVA求First集Follow集
- first集follow集求解算法及构造预测分析表
- 编译原理(求First集)
- LL1 first follow集
- 计算first集follow集
- 求first和follow集合c++
- first和follow集
- 编译原理JAVA求First集Follow集
- FIRST、FOLLOW集求法
- LL(1)文法讲解之二 Follow集的计算
- sun编译原理总复习(第24讲)PPT课件