实验七：LL(1)文法的判断
一：要求
输入：任意的上下文无关文法。
输出：判断是否为 LL（1）文法
二：实验目的
1． 掌握 LL(1)的判断，掌握求 first 和 follow 集合的算法
2． 熟悉运用 C/C++语言对求 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）；
