标准文档

编译原理实验报告

实验名称 计算first集合和follow集合

实验时间 2016年6月8日

院 系 计算机科学与技术

班 级 计算机科学与技术（1）班

学 号

姓 名

实用文案

标准文档

1.试验目的：

输入：任意的上下文无关文法。

输出：所输入的上下文无关文法一切非终结符的first集合和follow集合。

2.实验原理：

设文法G[S]＝（VN，VT，P，S），则首字符集为：

* FIRST（α）＝{a | α?aβ，a∈VT，α,β∈V *}。

*若α?ε，ε∈FIRST（α）。

由定义可以看出，FIRST（α）是指符号串α能够推导出的所有符号串中处于串首的终结符号组成的集合。所以FIRST集也称为首符号集。

设α＝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）；

3.实验代码与结果：

输入格式：

每行输入一个产生式，左部右部中间的→用空格代替。 非终结符等价于大写字母 ^ 表示 空

输入到文件结束，或用 0 0 结尾。

以编译原理（清华大学第二版）5.6典型例题及答案中的例题一为例（96页）：

#include #include #include

实用文案