文档介绍：first集和follow集生成算法模拟
编译原理课程设计
编译原理课设
-第 2 页 -
-第 8 页 -
课程设计(论文)任务书
软 件 学 院 学 院 软件测试 论 8
六、设计体会与小结 10
七、参考文献 11
八、附录.......................................11
编译原理课程设计
编译原理课设
-第 2 页 -
-第 8 页 -
第 0 页
一、课程设计任务及要求
：设计一个由正规文法生成First集和Follow集并进行简化的算法动态模拟。
First集和Follow集生成模拟算法的基本功能：
输入一个文法G
输入由文法G构造First集的算法
输出First集
输入由文法Ｇ构造Follow集的算法
输出Follow集
实验目的：
输入：任意的上下文无关文法。
输出：所输入的上下文无关文法一切非终结符的first集合和follow 集合。
[S]＝（VN，VT，P，S），则首字符集为：
FIRST（α）＝{a | αaβ，a∈VT，α,β∈V *}。
若αε，ε∈FIRST（α）。
由定义可以看出，FIRST（α）是指符号串α能够推导出的所有符号串中处于串首的终结符号组成的集合。所以FIRST集也称为首符号集。
设α＝x1x2…xn，FIRST（α）可按下列方法求得：
令FIRST（α）＝Φ，i＝1；
若xi∈VT，则xi∈FIRST（α）；
若xi∈VN；
① 若εFIRST（xi），则FIRST（xi）∈FIRST（α）；
② 若ε∈FIRST（xi），则FIRST（xi）－{ε}∈FIRST（α）；
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），则
编译原理课程设计
编译原理课设
-第 2 页 -
第 1 页
FOLLOW（A）＝{a | S… Aa …，a∈VT}。
若S…A，#∈FOLLOW（A）。
由定义可以看出，FOLLOW（A）是指在文法G[S]的所有句型中，紧跟在非终结符A后的终结符号的集合。
FOLLOW集可按下列方法求得：
对于文法G[S]的开始符号S，有#∈FOLLOW（S）；
若文法G[S]中有形如B→xAy的规则，其中x，y∈V *，则FIRST（y）－{ε}∈FOLLOW（A）；
若文法G[S]中有形如B→xA的规则，或形如B→xAy的规则且ε∈FIRST（y），其中x，y∈V *，则FOLLOW（B）∈FOLLOW（A）；
实验内容：计算FIRST集和FOLLOW集
二、需求分析
：
动态模拟算法的基本功能是：
输入一个文法G；
输出由文法G构造FIRST集的算法；
输出First集；i
)
(
*
+
F的first集
T的first集
E的first集
1
1
1
1
1
1
1
1
1
输出由文法G构造FOLLOW集的算法；
输出FOLLOW集。
：
输入文法Ｇ[E]：
E → TE’
E’ → +TE’|ε
编译原理课程设计
编译原理课设
-第 2 页 -
第 2 页
T → FT’
T’ → *FT’|ε
F->(E)|i
实现提示：
用数据库存储多行文法，用LIST控件显示算法，用GRID类依据算法进行作图。并实现算法与生成过程的关联。
三、设计思路
开始
结束
计算产生式的总数N
输入要分析的文法G\