计算first集合和follow集合

学号:E10914066 专业:计算机科学与技术二班姓名:王安

实验日期: 2012/6/8 教师签字: 成绩:

《编译原理》

课程实验报告

实验六:计算first集合和follow集合

计算first 集合和follow 集合

【实验目的】

掌握first 集合和follow 集合的概念和计算方法

【实验原理】

计算first 集合（根据定义）：

根据first 集定义对每一文法符号V X ∈计算)(X FIRST 。 （1） 若T V X ∈，则}{)(X X FIRST =。

（2） 若N V X ∈，且有产生式T V a a X ∈→, 则)(X FIRST a ∈。 （3） 若N V X ∈，ε→X ，则)(X FIRST ∈ε。

（4） 若n Y Y Y X ,,,,21 都N V ∈，而有产生式n Y Y Y X 21→。当1

21,,,-i Y Y Y 都

?→

?*

ε时，（其中

n

i ≤≤1），则)

(},{)(},{)(},{)(121i i Y FIRST Y FIRST Y FIRST Y FIRST εεε---- 都包

含在)(X FIRST 中。

（5） 当（4）中所有ε?→?

*

i Y ，（n i ,,3,2,1 =），则

}{)()()()(21ε n

Y F I R S T Y F I R S T Y F I R S T X F I R S T =。 反复使用上述（2）~（5）步知道每个符号的FIRST 集合不再增大。

【实验程序代码】

#include

#include

#include

using namespace std;

#define MAXS 50

int NONE[MAXS]={0};

string strings,noend,End;

string first[MAXS];// 用于存放每个终结符的first集

string First[MAXS];// 用于存放每个非终结符的first集

string Follow[MAXS]; // 用于存放每个非终结符的follow集int N;

struct STR

{

string left;

string right;

};

//求VN和VT

void VNVT(STR *p)

{

int i,j;

for(i=0;i

{

for(j=0;j<(int)p[i].left.length();j++)

{

if((p[i].left[j]>='A'&&p[i].left[j]<='Z'))

{

if(noend.find(p[i].left[j])>100)

noend+=p[i].left[j];

}

else

{

if(End.find(p[i].left[j])>100)

End+=p[i].left[j];

}

}

for(j=0;j<(int)p[i].right.length();j++)

{

if(!(p[i].right[j]>='A'&&p[i].right[j]<='Z'))

{

if(End.find(p[i].right[j])>100)

End+=p[i].right[j];

}

else

{

if(noend.find(p[i].right[j])>100)

noend+=p[i].right[j];

}

}

}

}

void getlr(STR *p,int i)

{

int j;

for(j=0;j

{

if(strings[j]=='-'&&strings[j+1]=='>')

{

p[i].left=strings.substr(0,j);

p[i].right=strings.substr(j+2,strings.length()-j);

}

}

}

//对每个文法符号求first集

string Letter_First(STR *p,char ch)

{

if(!(End.find(ch)>100))

{

first[End.find(ch)]="ch";

return first[End.find(ch)-1];

}

if(!(noend.find(ch)>100))

{

for(int i=0;i

{

if(p[i].left[0]==ch)

{

if(!(End.find(p[i].right[0])>100))

{

if(First[noend.find(ch)].find(p[i].right[0])>100)

{

First[noend.find(ch)]+=p[i].right[0];

}

}

if(p[i].right[0]=='*')

{

if(First[noend.find(ch)].find('*')>100)

{

First[noend.find(ch)]+='*';

}

}

if(!(noend.find(p[i].right[0])>100))

{

if(p[i].right.length()==1)

{

string ff;

ff=Letter_First(p,p[i].right[0]);

for(int i_i=0;i_i

{

if( First[noend.find(ch)].find(ff[i_i])>100)

{

First[noend.find(ch)]+=ff[i_i];

}

}

}

else

{

for(int j=0;j

{

string TT;

TT=Letter_First(p,p[i].right[j]);

if(!(TT.find('*')>100)&&(j+1)

{

sort(TT.begin(),TT.end());

string tt;

for(int t=1;t

{

tt+=TT[t];

}

TT=tt;

tt="";

for(int t=0;t

{

if( First[noend.find(ch)].find(TT[t])>100)

{

First[noend.find(ch)]+=TT[t];

}

}

}

else

{

for(int t=0;t

{

if( First[noend.find(ch)].find(TT[t])>100)

{

First[noend.find(ch)]+=TT[t];

}

}

break;

}

}

}

}

}

}

return First[noend.find(ch)];

}

}

// 求每个非终结符的Follow集

string Letter_Follow(STR *p,char ch)

{

NONE[noend.find(ch)]++;

if(NONE[noend.find(ch)]==2)

{

NONE[noend.find(ch)]=0;

return Follow[noend.find(ch)];

}

for(int i=0;i

{

for(int j=0;j

{

if(p[i].right[j]==ch)

{

if(j+1==p[i].right.length())

{

string gg;

gg=Letter_Follow(p,p[i].left[0]);

NONE[noend.find(p[i].left[0])]=0;

for(int k=0;k

{

if(Follow[noend.find(ch)].find(gg[k])>100)

{

Follow[noend.find(ch)]+=gg[k];

}

}

}

else

{

string FF;

for(int jj=j+1;jj

{

string TT;

TT=Letter_First(p,p[i].right[jj]);

if(!(TT.find('*')>100)&&(jj+1)

{

sort(TT.begin(),TT.end());

string tt;

for(int t=1;t

{

tt+=TT[t];

}

TT=tt;

tt="";

for(int t=0;t

{

if( FF.find(TT[t])>100&&TT[t]!='*')

{

FF+=TT[t];

}

}

}

else

{

for(int t=0;t

{

if( FF.find(TT[t])>100)

{

FF+=TT[t];

}

}

break;

}

}

if(FF.find('*')>100)

{

for(int k=0;k

{

if(Follow[noend.find(ch)].find(FF[k])>100)

{

Follow[noend.find(ch)]+=FF[k];

}

}

}

else

{

for(int k=0;k

{

if((Follow[noend.find(ch)].find(FF[k])>100)&&FF[k]!='*')

{

Follow[noend.find(ch)]+=FF[k];

}

}

string dd;

dd=Letter_Follow(p,p[i].left[0]);

NONE[noend.find(p[i].left[0])]=0;

for(int k=0;k

{

if(Follow[noend.find(ch)].find(dd[k])>100)

{

Follow[noend.find(ch)]+=dd[k];

}

}

}

}

}

}

}

return Follow[noend.find(ch)];

}

//主函数

int main()

{

cout<<"请输入产生式总数及各产生式：*代表空\n"<

cin>>N;

STR *p=new STR[MAXS];

for(int i=0;i

{

cin>>strings;

getlr(p,i);

}

VNVT(p);

cout<<"\n各非终结符的FIRST集为：\n"<

for(int i=0;i

{

cout<<"\tFIRST("<

string pp;

pp=Letter_First(p,noend[i]);

for(int j=0;j+1

{

cout<

}

cout<

}

cout<<"\n各非终结符的FOLLOW集为：\n"<

Follow[0]+='#';

for(int i=0;i

{

cout<<"\tFOLLOW("<

string pp;

pp=Letter_Follow(p,noend[i]);

for(int j=0;j+1

{

cout<

}

cout<

}

return 0;

}

【实验结果】

first集和follow集生成算法模拟

课程设计(论文)任务书 软件学院学院软件测试专业 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 日

【8A版】编译原理实验报告FIRST集和FOLLOW集

编译原理实验报告 实验名称计算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 ）；

编译原理一点就通first follow LL()

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集

————————————————————————————————作者：————————————————————————————————日期：

编译原理实验报告实验名称计算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集姓名： 学号： 教师签字： 成绩：

一．实验目的： .掌握和了解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 #include #include #include #include using namespace std; //********************* struct define //产生式 { char left; string right; }; //*************** int N,K1=0,K2=0; char B; struct define *p=new define[10]; //************************ bool find(char b) //查找是否有产生空的产生式 { int i; for(i=0;i

构造FIRST集和FOLLOW集的方法

构造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) 。

离散数学39偏序关系

偏序关系

一、偏序关系和哈斯图 1、定义3-12.1 若集合A上的二元关系R是自反的、反对称的和传递的，则称R是A的偏序关系，记作?.设?为偏序关系，如果∈?，则记作x?y，读作“小于或等于”。.序偶称为偏序集合.（Partially Ordered Relations） 注意：这里的“小于或等于”不是指数的大小，而是在偏 序关系中的顺序性.x“小于或等于”y的含义是：依照这个序， x排在y的前边或者x就是y.

根据不同偏序的定义，对序有着不同的解释. 例如整除关系是偏序关系， 3 ? 6的含义是3整除6. 大于或等于关系也是偏序关系，针对这个关系写5?4是说大于或等于4,关系?中5排在4的前边，也就是5比4大. 注： 和空关系都是A上的偏序关系， 1. 集合A上的恒等关系I A 但全域关系E 一般不是A上的偏序关系. A 2. 实数域上的小于等于关系（大于等于关系），自然数域上的整除关系，集合的包含关系等都是偏序关系.

定义设R为非空集合A上的偏序关系，定义 (1) ?x, y∈A, x ? y当且仅当 x ? y且x≠y; (2) ?x, y∈A, x 与 y 可比当且仅当 x ? y 或 y ? x. 注： 在具有偏序关系的集合A中任二元素 x 和 y 之间必有下列四种情形之一： x ? y ，y ? x ，x=y ，x 与 y 不可比.

例设A={1, 2, 3} (1) ?是A上的整除关系，则：1 ? 2, 1 ? 3, 1＝1, 2＝2, 3＝3， 2 和 3 不可比； (2) ?是 A 上的大于等于关系，则: 2 ? 1, 3 ? 1, 3 ? 2, 1＝1, 2＝2，3＝3.

正规文法的First集合Follow集求解过程动态模拟-实验报告

华东交通大学 课程设计（论文）任务书 软件学院专业项目管理班级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)

离散编程,求偏序关系的极大元与极小元

求偏序集中的极大元与极小元 成绩: 10 / 折扣: 0.9 输入 输入偏序集 ， A 中的元素数不超过 20 个，分别用单个小写的英文字母表示。 输入的第一行给出 A 中的各个元素，两个相邻的元素之间用逗号隔开。 输入的第二行给出偏序关系￡，用有序对的形式给出，如 , 等等，两个相邻的有序对之间用逗号隔开。 输出 输出 A 的极小元与极大元。 输出的第一行给出各个极小元，两个相邻元素之间用逗号隔开，输出的元素要求按照英文字母的自然顺序排列输出。 输出的第二行给出各个极大元，两个相邻元素之间用逗号隔开，输出的元素要求按照英文字母的自然顺序排列输出。 测试输入期待的输出时间限制内存限制额外进程 测试用例 1 以文本方式显示 1.a,b,c,d? 2.,,,,,? 以文本方式显示 1.a,c? 2.b,d? 无限制 1024KB 0 测试用例 2 以文本方式显示 1.a,b,c,d,e,f? 2.,,,,,,,,? 以文本方式显示 1.a,c,e? 2.b,d,f? 无限制 1024KB 0 源程序 #define N 100 #include"stdio.h" #include"string.h" int main( ) { char b[N],c[N],d[N],e[N]; /* b放元素，c放偏序关系，d放极小元，e放极大元 */ int i,j,m=0,n=0,len1,len2,s; scanf ( "%s%s",b,c ); len1 = strlen( b );

计算first集合和follow集合--编译原理

计算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

LL1 first follow集

课程名称: LL1文法的判别 年级/专业/班: 11级计算机类（二）班 姓名: 徐勇兵 学号： E01114278

import java.util.Vector; import javax.swing.JOptionPane; class Tools{ public Vector protection(Vector vs){ Vector newvector=new Vector(); for(int i=0;i> doubleprotection(Vector> vs){ Vector> newvector=new Vector>();

for(int i=0;i produce=(Vector)vs.get(i); Vector temp=new V ector(); for(int j=0;j end=new V ector();//表示终结符 Vector noend=new Vector();//表示非终结符 Vector> produce=new Vector>();//产生式 public void setend(){//终结符元素添加 while(true) { String s=JOptionPane.showInputDialog(null,"请输入终结符"); if(s==null) { return; }//if end.add(s); }//while }//public void addend(){//元素添加 public void setnoend(){//非终结符元素添加 while(true) { String s=JOptionPane.showInputDialog(null,"非请输入终结符"); if(s==null) { return; }//if noend.add(s); }//while }//public void addnoend(){// public void setproduce(){ while(true) { String s=JOptionPane.showInputDialog(null,"请输入产生式，->隔开"); if(s==null) return; Vector temp=new Vector(); temp.add(s.split("->")[0]); temp.add(s.split("->")[1]);

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

计算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 #include //产生式 struct css{ char left; char zhuan;//用“-”表示箭头 char right[20]; }; //空标志 struct kong {

编译原理第五章

第五章 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集和FOLLOW集的求法

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｝。

偏序关系

4.6偏序关系 偏序关系：同时具有自反、反对称和传递性

4.6 偏序关系 定义4.21 设R为非空集合A上的一个二元关系，如果R是自反的、反对称的和传递的，则称R为A上的偏序关系，记作≤。设≤是偏序关系，若∈≤，则记作x≤y，读作x“小于或等于”y。集合A与A上的偏序关系≤一起组成的有序对叫做偏序集。 如以下关系都是偏序关系： （1）非空集合A上的恒等关系I A。 （2）实数集R上的“≤”、“≥”关系。

4.6 偏序关系 定义4.22 设为偏序集，定义 （1）?x, y∈A，x < y ?x ≤ y ∧x≠y，x是偏序集，其中A＝{1, 2, 3, 4, 5}，是A上的整除关 系，则有 （1）1<2<4，1<3等。 （2）1=1，2=2，3=3等。 （3）2与3是不可比的。

4.6 偏序关系 Sed ut perspiciatis unde omnis.68% 设为偏序集，若?x, y ∈A ，x 与y 都是可比的，则称≤为A 上 的全序关系（或线序关系）。且称为全序集。 例如，集合A = {1, 2, 3, 4, 5}上的（1）“小于等于”关系是全序关系，因为任何两个数总是可比大小 的。（2）“整除关系”不是全序关系，因为2与3是不可比的。 定义4.23

4.6 偏序关系 定义4.24 设为偏序集，对于任意的x, y∈A，如果x < y并且不存在z∈A使得x | x, y∈A∧y盖住x} 根据定义4.24，?， ∈COV A ?y盖住x ?x ≤ y ?∈ ≤ 所以COV A ?≤。

计算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

偏序关系整理

●定义：集合S上的关系R，如果它是自反的，反对称的和传递的，就称为偏序。集 合S与偏序R一起叫做偏序集，记做(S, R) ●例子： ●1、整数集合上的“大于或等于”关系 ●2、正整数集合上的整除关系 ●3、集合S的幂集合上的包含关系 ●符号： ●通常用?表示偏序关系,读作“小于等于” ●∈R ? xRy ? x?y ●使用这个记号是由于“小于或等于”关系是偏序关系的范例。 ●“严格小于”: x?y ? x?y ∧x≠y ●当a与b是偏序关系（S, ≤）的元素时，不一定有a ≤b或b ≤a。 ●定义2：偏序集（S, ≤）的元素a和b叫做可比的，如果a ≤b或b ≤a。当a和b是S 的元素且没有a ≤b，也没有b ≤a，则称a和b是不可比的。 ●极大元素：偏序集的一个元素，它不小于这个偏序集的任何其他元素 ●极小元素：偏序集的一个元素，它不大于这个偏序集的任何其他元素 ●最大元素：偏序集的一个元素，它大于这个偏序集的所有其他元素 ●最小元素：偏序集的一个元素，它小于这个偏序集的所有其他元素 设为偏序集, A?S, u,l∈A ●上界(upper bound): u是A的上界??x( x∈A → x?u ) ●下界(lower bound): l是A的下界??x( x∈A → l?x ) ●例：, S={1,2,3,4,5,6,9,10,15} ●A1={1,2,3}, A2={3,5,15}, A3=S. ●A1的上界是{6}, A1的下界是{1} ●A2的上界是{15}, A2的下界是{1} ●A3的上界集合的最小上界：集合的一个上界，它小于所有其他的上界 ●集合的最大下界：集合的一个下界，它大于所有其他的下界 是{}, A3的下界 I A R R∩I A=R=R R∩R-1 I A R R R 最小元与极小元是不一样的。最小元是B中最小的元素，它与B中其它元素都可比；而极小元不一定与B中元素可比，只要没有比它小的元素，它就是极小元。对于有穷集B，极小元一定存在，但最小元不一定存在。最小元如果存在，一定是唯一的，但

LL(1)中First和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集合也是顾名思义的，就是文法符号后面可能跟随的终结符的集合（不包括空串ε）。 Follow(X)就是求X后面可能跟随的符号集合。 求Follow集合可分如下几种情况: 终结符的Follow集合没有定义，只有非终结符才会有Follow集合。 A-->…Ua…要求的Follow集合的非终结符后跟终结符