计算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
#include
//产生式
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)："< cin>>n; cout<<"请从开始符输入产生式(空用“#”表示，产生式由字母组成)："< for(i=0;i { cin>>shizi[i].left>>shizi[i].zhuan>>shizi[i].right; int l,m,j,h,g,f; for(l=0;l for(m=0;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 { 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 { 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;//第三部-1 sum=0; for(e=0;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 { 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 { 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 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 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 { fw[b1].fow[0]='\0'; } fw[0].fow[0]='#'; fw[0].fow[1]='\0'; for(b8=0;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 for(b3=0;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 {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 {if(shizi[b2].right[b3+1]==shizi[b4].left) { if(kongshi[b4].kongzuo!=1) { for(b10=0;b10 strcat(fw[b10].fow,fji[b4].fjihe); } } else { for(b5=0;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 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 { fji2[a11].fjihe2[0]='\0'; } for(a12=0;a12<=n;a12++) for(a13=0;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 { {for(a21=0;a21<99;a21++) linshi3[a21]='\0'; } {for(a16=0;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 { fw2[b11].fow2[0]='\0'; } for(b12=0;b12<=n;b12++) for(b13=0;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 { { {for(b21=0;b21<99;b21++) linshi6[b21]='\0'; } {for(b16=0;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集合"< cout<<" "< { for(c2=0;c2 { if(shizi[c1].left!=shizi[c2].left&&c2==(c1-1)) cout<<" "< } } int d1,d2; cout<<"非终结符"<<" "<<"follow集合"< cout<<" "< for(d1=1;d1 { for(d2=0;d2 { if(shizi[d1].left!=shizi[d2].left&&d2==(d1-1)) cout<<" "< } } } 四、运行截图 课程设计(论文)任务书 软件学院学院软件测试专业 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 日 《编译原理》期末试题（一） 一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分） 1．编译程序是对高级语言程序的解释执行。(× ) 2．一个有限状态自动机中，有且仅有一个唯一的终态。(×) 3．一个算符优先文法可能不存在算符优先函数与之对应。(√ ) 4．语法分析时必须先消除文法中的左递归。(×) 5．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。(√) 6．逆波兰表示法表示表达式时无须使用括号。(√ ) 7．静态数组的存储空间可以在编译时确定。(×) 8．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。(×) 9．两个正规集相等的必要条件是他们对应的正规式等价。(× ) 10．一个语义子程序描述了一个文法所对应的翻译工作。(×) 二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分) 1．词法分析器的输出结果是_____。 A．( ) 单词的种别编码B．( ) 单词在符号表中的位置 C．( ) 单词的种别编码和自身值D．( ) 单词自身值 2．正规式M 1 和M 2 等价是指_____。 A．( ) M1和M2的状态数相等B．( ) M1和M2的有向边条数相等C．( ) M1和M2所识别的语言集相等D．( ) M1和M2状态数和有向边条数相等3．文法G：S→xSx|y所识别的语言是_____。 A．( ) xyx B．( ) (xyx)* C．( ) xnyxn(n≥0) D．( ) x*yx* 4．如果文法G是无二义的，则它的任何句子α_____。 A．( )最左推导和最右推导对应的语法树必定相同 B．( ) 最左推导和最右推导对应的语法树可能不同 C．( ) 最左推导和最右推导必定相同 D．( )可能存在两个不同的最左推导，但它们对应的语法树相同 5．构造编译程序应掌握______。 A．( )源程序B．( ) 目标语言 C．( ) 编译方法D．( ) 以上三项都是 6．四元式之间的联系是通过_____实现的。 编译原理实验报告 实验名称计算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} ?? 第七章语义分析和中间代码产生 本章要点 1. 中间语言，各种常见中间语言形式； 2. 说明语句、赋值语句、布尔表达式、控制语句等的翻译； 3. 过程调用的处理； 4. 类型检查； 本章目标 掌握和理解中间语言，各种常见中间语言形式；各种语句到中间语言的翻译；以及类型检查等内容。 本章重点 1．中间代码的几种形式，它们之间的相互转换：四元式、三元式、逆波兰表示； 3．赋值语句、算术表达式、布尔表达式的翻译及其中间代码格式； 4．各种控制流语句的翻译及其中间代码格式； 5．过程调用的中间代码格式； 6．类型检查； 本章难点 1. 各种语句的翻译； 2. 类型系统和类型检查； 作业题 一、单项选择题： 1. 布尔表达式计算时可以采用某种优化措施，比如A and B用if-then-else可解释为_______。 a. if A then true else B； b. if A then B else false； c. if A then false else true； d. if A then true else false； 2. 为了便于优化处理，三地址代码可以表示成________。 a. 三元式 b. 四元式 c. 后缀式 d. 间接三元式 3. 使用三元式是为了________： a. 便于代码优化处理 b. 避免把临时变量填入符号表 c. 节省存储代码的空间 d. 提高访问代码的速度 4. 表达式-a+b*(-c+d)的逆波兰式是________。 a. ab+-cd+-*； b. a-b+c-d+*； c. a-b+c-d+*； d. a-bc-d+*+； 5. 赋值语句x:=-(a+b)/(c-d)-(a+b*c)的逆波兰式表示是_______。 a. xab+cd-/-bc*a+-:=；a. xab+/cd-bc*a+--:=；a. xab+-cd-/abc*+-:=；a. xab+cd-/abc*+--:=； 6. 在一棵语法树中结点的继承属性和综合属性之间的相互依赖关系可以由________来描述。 a. 抽象语法树； b. 语法规则； c. 依赖图； d. 三地址代码； 7. 按照教材中的约定，三地址语句if x relop y then L表示成四元式为。 a. (relop，x，y，L)； b. (relop，L，x，y)； c. (relop，x，L，y)； d. (L，x，y，relop)； 8. 在编译程序中，不是常见的中间语言形式。 a.波兰式； b. 三元式； c. 四元式； d. 抽象语法树； 9. 在编译程序中安排中间代码生成的目的是________。 a. 便于提高编译效率； b. 便于提高分析的正确性； c. 便于代码优化和目标程序的移植； d.便于提高编译速度； 10. 按照教材中的约定，下面不是类型表达式： a. boolean； b. type-error； c. real； d. DAG； 11. 一个Pascal函数 function f ( a, b:char ) :↑integer; …… 其作用域类型是： a. char×integer； b. char×char； c. char×pointer(integer)； d. integer×integer； 12. 因为标识符可用于多种情况，比如常量标识符、变量标识符、过程标识符等等。因此，在符号表中为了给出各个符号的标志，常给标识符引入一个属性kind，然后在相应产生式的语义动作中添加给kind属性赋值的语句。比如，在在产生式D id:T的语义动作中添加赋值语句id.kind=。 a. V AR； b. CONSTANT； c. PROC； d. FUNC； 13. 下面情况下，编译器需要创建一张新的符号表。 a. 过程调用语句； b. 标号说明语句； c. 数组说明语句； d.记录说明语句； 14. 函数function f(a,b:char):↑integer;… 所以f函数的类型表达式为： a. char×char→pointer(integer)； b. char×char→pointer； c. char×char→integer； d. char×char→integer (pointer) 15. 如果一个语言的编译器能保证编译通过的程序，在运行时不会出现类型错误，则称该语言是。 a. 静态的； b. 强类型的； c. 动态的； d. 良类型的； 一．答案：1. b；2. d；3. b；4. d；5. c；6. c.；7. a；8. a；9. c；10. d；11. b；12. a；13. d； 14. a；15. b； 编译原理实验报告记录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 第一章引论 一.单项选择题 1. 如果一个编译程序能产生不同于其宿主机的机器代码，则称它为：___________________ 。 a. 诊断编译程序 b. 优化编译程序 c. 交叉编译程序 d. 可变目标编译程序 2. 编译程序将高级语言程序翻译成_________ 。 a. 机器语言程序或高级语言程序 b. 汇编语言或机器语言程序 c. 汇编语言程序或高级 语言程序d. 中间语言程序或高级语言程序 3. 下面的四个选项中，__________不是编译程序的组成部分。 a. 词法分析程序 b. 代码生成程序 c. 设备管理程序 d. 语法分析程序 4. 现代多数实用编译程序所产生的目标代码都是一种可重定位的指令代码，在运行前必须借助于一个_______把各个目标模块，包括系统提供的库模块连接在一起，确定程序变量或常 数在主存中的位置，装入内存中制定的起始地址，使之成为一个可运行的绝对指令代码的程序。 a. 重定位程序； b. 解释程序； c. 连接装配程序； d. 诊断程序； 5. 从编译程序的角度说，源程序中的错误通常分为________两大类。 a. 词法错误和语法错误； b. 语法错误和语义错误； c. 编辑错误和诊断错误； d. 词法错误和语义错误； 6. 下面对编译原理的有关概念正确描述的是：____。 a. 目标语言只能是机器语言 b. 编译程序处理的对象是源语言。 c. Lex是语法分析自动生成器 d. 解释程序属于编译程序 7. 目标代码生成阶段所生成的目标代码的形式不可能是____。 a. 绝对指令代码 b. 可充定位的指令代码。 c. 汇编指令代码 d. 三地址代码 8. 语义错误是指源程序中不符合语义规则的错误，不包括：____ a. 非法字符错误 b. 类型不一致错误。 c. 作用域错误 d. 说明错误 1-01.编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析，之间代码生成,代码优化等几个基本阶段,同时还会伴有表格处理和出错处理 . 1-02.若源程序是用高级语言编写的,目标程序是机器语言程序或汇编程序,则其翻译程序称为编译程序. 1-03.编译方式与解释方式的根本区别在于是否生成目标代码 . 1-04.翻译程序是这样一种程序,它能够将用甲语言书写的程序转换成与其等价的用乙语言书写的程序 . 1-05.对编译程序而言,输入数据是源程序,输出结果是目标程序. 1-06.如果编译程序生成的目标程序是机器代码程序,则源程序的执行分为两大阶段: 编译阶段和运行阶段 .如果编译程序生成的目标程序是汇编语言程序,则源程序的执行分 为三个阶段:编译阶段, 汇编阶段和运行阶段 . 1-07.若源程序是用高级语言编写的，目标程序是机器语言程序或汇编程序，则其翻译程序称为编译程序。 1-08.一个典型的编译程序中，不仅包括词法分析、语法分析、中间代码生成、代码优化、目标代码生成等五个部分，还应包括表格处理和出错处理。其中，词法分析器用于识别单词。 1-09.编译方式与解释方式的根本区别为是否生成目标代码。 2-01.所谓最右推导是指：任何一步α?β都是对α中最右非终结符进行替换的。 2-02.一个上下文无关文法所含四个组成部分是一组终结符号、一组非终结符号、一个开始符号、一组产生式。 2-03.产生式是用于定义语法成分的一种书写规则。 2-04.设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为：L(G)＝{x│S x,x∈VT*} 。 2-05.设G是一个给定的文法，S是文法的开始符号，如果S x（其中x∈V*），则称x是文法的一个句型。 2-06.设G是一个给定的文法，S是文法的开始符号，如果S x(其中x∈VT*),则称x是文法的一个句子。 3-01.扫描器的任务是从源程序中识别出一个个单词符号。 4-01.语法分析最常用的两类方法是自上而下和自下而上分析法。 4-02.语法分析的任务是识别给定的终极符串是否为给定文法的句子。 4-03.递归下降法不允许任一非终极符是直接左递归的。 4-04.自顶向下的语法分析方法的关键是如何选择候选式的问题。 4-05.递归下降分析法是自顶向上分析方法。 4-06.自顶向下的语法分析方法的基本思想是：从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导，试图推导出文法的句子，使之与给定的输入串匹配。 5-01.自底向上的语法分析方法的基本思想是：从给定的终极符串开始，根据文法的规则一步一步的向上进行直接归约，试图归约到文法的开始符号。 5-02.自底向上的语法分析方法的基本思想是：从输入串入手，利用文法的产生式一步一步地向上进行直接归约，力求归约到文法的开始符号。 5-03.简单优先方法每次归约当前句型的句柄，算符优先方法每次归约当前句型的最左素短语，二者都是不断移进输入符号，直到符号栈顶出现可归约串的尾，再向前找到可归约串的头，然后归约。 5-04.在LR（0）分析法的名称中，L的含义是自左向右的扫描输入串，R 的含义是最左归约，0 的含义是向貌似句柄的符号串后查看0个输入符号。 5-05.在SLR（1）分析法的名称中，S的含义是简单的。 构造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) 。 第三章词法分析 本章要点 １．词法分析器设计， ２．正规表达式与有限自动机， ３．词法分析器自动生成。 本章目标： １．理解对词法分析器的任务，掌握词法分析器的设计； ２．掌握正规表达式与有限自动机； ３．掌握词法分析器的自动产生。 本章重点： 1．词法分析器的作用和接口，用高级语言编写词法分析器等内容，它们与词法分析器的实现有关。应重点掌握词法分析器的任务与设计，状态转换图等内容。 2．掌握下面涉及的一些概念，它们之间转换的技巧、方法或算法。 （1）非形式描述的语言?正规式 （2）正规式→ NFA（非确定的有限自动机） （3）NFA → DFA（确定的有限自动机） （4）DFA →最简DFA 本章难点 （1）非形式描述的语言?正规式 （2）正规式→ NFA（非确定的有限自动机） （3）NFA → DFA（确定的有限自动机） （4）DFA →最简DFA 作业题 一、单项选择题 （按照组卷方案，至少15道） 1. 程序语言下面的单词符号中，一般不需要超前搜索 a. 关键字 b. 标识符 c. 常数 d. 算符和界符 2. 在状态转换图的实现中，一般对应一个循环语句 a. 不含回路的分叉结点 b. 含回路的状态结点 c. 终态结点 d. 都不是 3. 用了表示字母，d表示数字， ={l，d}，则定义标识符的正则表达式可以是：。 (a)ld*(b)ll*(c)l(l | d)*(d)ll* | d* 4. 正规表达式(ε|a|b)2表示的集合是 (a){ε，ab，ba，aa，bb} (b){ab，ba，aa，bb} (c){a，b，ab，aa，ba，bb} (d){ε，a，b，aa，bb，ab，ba} 5. 有限状态自动机可用五元组（V T，Q，δ，q0，Q f）来描述，设有一有限状态自动机M的定义如下： V T={0，1}，Q={q0，q1，q2}，Q f={q2}，δ的定义为： δ（q0，0）=q1δ（q1，0）=q2 δ（q2，1）=q2δ（q2，0）=q2 M所对应的状态转换图为。 华东交通大学 课程设计（论文）任务书 软件学院专业项目管理班级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) 第4章词法分析 重点内容：正规式转化为DFA a、正规式->NFA b、NFA -> DFA（子集法） c、DFA化简（分割法） 题目1：课件例题： a、为R=(a|b)*(aa|bb)(a|b)*构造NFA b、从NFA构造DFA的算法 c、化简 题目2： 4.7 例1：构造正规式相应的DFA：1(0|1)*101 按照以下三步： （1）由正规表达式构造转换系统（NFA） （2）由转换系统（NFA）构造确定的有穷自动机DFA （3）DFA的最小化 答：（1）构造与1(0|1)*101等价的NFA （2）将NFA转换成DFA：采用子集法，即DFA的每个状态对应NFA的一个状态集合： 除X，A外，重新命名其他状态： 1、将M 的状态分成非终态和终态集{X,A,B,C}和{D}。 2、寻找子集中不等价状态{X,A,B,C}=>{X}，{A,B}{C}=>{X}{A}{B}{C}，无需合并。 最后生成 DFA ： 题目3：自习、书本练习4.7，参考答案见《z4 书本练习4.7.doc 》 已知文法G[S]： S →aA|bQ A →aA|bB|b B →bD|aQ Q →aQ|bD|b E →aB|bF F →bD|aE|b 1、 构由于不可到达，去除E 、F 相关的多余产生式 2、 由新的G[S]构造NFA 如下 5、使用分割法化简以上DFA G： 5.1 令G={(0,1,3,4,6),(2,5)}// 分别为非终态和终态集 5.2 由{0,1,3,4,6}a={1,3}，{0,1,3,4,6}b={3,2,5,6,4} 将{0,1,3,4,6}划分为 {0,4,6}{1,3}，得G={(0,4,6),(1,3),(2,5)} 5.3 由{0,4,6}b={3,6,4}，将之划分为{0},{4,6}，得G={(0),(4,6),(1,3),(2,5)} 5.4 观察后，G中状态不可再分，为最小化DFA。 6、分别用 0，4，1，2代表各状态，DFA状态转换图如下： 造相应的最小的DFA 第5章自顶向下的语法分析 重点内容：LL（1）文法 a、去除左递归 b、LL（1）文法的判定（first、follow、select集） c、预测分析表 d、使用栈和预测分析表对输入串的分析 题目1：课件例题：消除左递归+判定+分析 算术表达式文法G E→E+T│T T→T*F│F F→(E)│I d、分析输入串i+i*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 课程名称: 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 《编译原理》习题（一）——词法分析 一、是非题（请在括号内，正确的划√，错误的划×） 1．编译程序是对高级语言程序的解释执行。(× ) 2．一个有限状态自动机中，有且仅有一个唯一的终态。(×) 9．两个正规集相等的必要条件是他们对应的正规式等价。(× ) 二、选择题 1．词法分析器的输出结果是_____。 A．( ) 记号 B．( ) 相应条目在符号表中的位置 C．( ) 记号和属性二元组D．( ) 属性值 2．正规式 M 1 和 M 2 等价是指_____。 A．( ) M1和M2的状态数相等 B．( ) M1和M2的有向边条数相等 C．( ) M1和M2所识别的语言集相等D．( ) M1和M2状态数和有向边条数相等3．语言是 A．句子的集合 B．产生式的集合 C．符号串的集合 D．句型的集合 4．编译程序前三个阶段完成的工作是 A．词法分析、语法分析和代码优化 B．代码生成、代码优化和词法分析 C．词法分析、语法分析、语义分析和中间代码生成 D．词法分析、语法分析和代码优化 5．扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即 A．字符 B．单词 C．句子 D．句型 6．构造编译程序应掌握______。 A．( )源程序B．( ) 目标语言 C．( ) 编译方法D．( ) 以上三项都是 7．词法分析的任务是 A．识别单词 B．分析句子的含义 C．识别句子 D．生成目标代码 三、填空题 1．计算机执行用高级语言编写的程序主要有两种途径：___解释__和__编译___。 3.编译过程可分为（词法分析），（语法分析），（语义分析与中间代码生成），（优化）和（目标代码生成）五个阶段。 6.扫描器的任务是从（源程序中）中识别出一个个（单词符号）。 17.一张转换图只包含有限个状态,其中有一个被认为是（初）态;而且实际上至少要有一个（终）态。 1．编译程序首先要识别出源程序中每个(单词)，然后再分析每个(句子)并翻译其意义。3．通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的(分析)，中间代码生成、代码优化与目标代码的生成则是对源程序的(综合)。 5．对编译程序而言，输入数据是(源程序)，输出结果是(目标程序)。first集和follow集生成算法模拟
编译原理期末试题(8套含答案+大题集)
【8A版】编译原理实验报告FIRST集和FOLLOW集
编译原理一点就通first follow LL()
编译原理作业集第七章
编译原理实验报告记录FIRST集和FOLLOW集
求first集和follow集
编译原理试题集33493
编译原理填空集锦
构造FIRST集和FOLLOW集的方法
编译原理作业集-第三章-修订版
正规文法的First集合Follow集求解过程动态模拟-实验报告
编译原理复习题目集答案
计算first集合和follow集合--编译原理
LL1 first follow集
计算first集合和follow集合--编译原理教案资料
编译原理词法分析习题集带答案
相关主题
文本预览