案例驱动法在编译原理课程教学中的应用
案例驱动法在编译原理课程教学中的应
计算机语言之所以能由单一的机器语言发展到现今的命令式编程语言、面向对象的编
程语言、函数式编程语言和逻辑式编程语言，就是编译技术的支持。学生对编译技术已经
不再陌生，如何激发他们从事编译器开发的热情，进而发展我国的汉语编程语言，把我国
的 IT行业发展到国际先进水平，是我们教学过程中亟待解决的问题。
编译技术中，自顶向下的语法分析分为预测分析和递归下降分析。预测分析中最常用
的是 LL(1)分析，其中第一个 L表示从左向右扫描输入串，第二个 L表示最左推导过程。
给定一个文法如何判定它是否是 LL(1)的，这个问题一直是我们教学过程中的一个重点，
同时也是一个难点，可能有些老师也会觉得，自己明明讲的很清楚了，学生在实际判定过
程中怎么还觉得困难呢。问题的关键是我们是采用什么样的案例，怎么引入，以及怎么总
结的。笔者就根据自己多年的教学总结，来谈谈这个问题，希望给老师和同学一个借鉴。
1 LL(1)文法的引入
自顶向下的语法分析的思想是，从文法的开始符号出发，为符号串构造一个最左推导
过程，如果成功，说明符号串是给定文法可以产生的。因此，我们仍然以推导为主线，看
一下，LL(1)到底要满足什么样的条件。
(1)考虑文法 G[A]:
A→Ax
A→y
和符号串 yxxx。
G[A]的第一个产生式是左递归，在推导 yxxx符号串时，分析程序无法通过有穷的向
前看符号，了解需要应用几次递归后才选择一条可令递归终止的产生式。
(2)如果一个文法没有递归产生式，是否就能顺利推导呢？考虑文法 G[S]：
S→aAb
A→bAc|bBc
B→aB|a
G[S]没有递归产生式，但在推导符号串 abacb时，从文法的开始符号 S开始，为了匹
配第一个字符 a，由于 S只有一个产生式，可以选择 aAb，a匹配成功。为了匹配第二个字
符 b，需要将 A替换，但 A有两个产生式并且都以 b开始，就存在不确定选择哪个产生式
的问题，必须进行回溯才能确定这个符号串是否是该文法可以产生的。因此，一个文法没
有左递归但有左因子也是不能顺利推导的。
(3)如果一个文法不含左递归和左因子，是否就能很顺利地进行推导呢。考虑文法
G[P]：
P→Bc|ad
B→aA|b
在输入串 abc的推导过程中，P有两个候选式 Bc和 ad，对于 Bc，要看 B的候选式 aA
和 b，因此，P的两个候选式 Bc和 ad，都是以 a开始的，因此，当文法中同一个非终结符
的候选式的 First集有交集也不能很顺利地进行推导。
(4)如果一个文法不含左递归、左因子、候选式的 First集也没有交集，是否就能很
顺利地进行推导呢。考虑文法 G[Q]：
Q→Aa|Bb
A→a|cA|ε
B→b|d 本文由论文联盟 收集整理
在输入串 cca的推导过程中，第一个字符是 c，对于 Q的两个候选式，选择以 c开始
的，但 Q的两个候选式是以 A和 B开始的，考虑 A和 B中以 c开始的，有 cA，因此选择
Aa，第一个字符匹配成功，第二个字符是 c，选择 cA，第三个要匹配 a，A中有定义 a的
候选式，如果选择，就多了一个符号 a，只能选择ε。原因就是 A的候选式的 First集和
A的 Follow集有交集 a。
因此，通过前边几个文法的举例，LL(1)文法的判定就可以总结为:
(1)文法中不能有左递归的产生式；
(2)文法中不能有左因子；
(3)对于一个非终结符来说，如果它有多个候选式，并且都不为空，那么要求候选式
的 FIRST集合不能有交集.
(4)对于一个非终结符来说，如果它有多个候选式，并且有定义为空，那么要求候选
式的 FIRST集合和这个非终结符的 FOLLOW不能有交集。
2 LL(1)文法的判定
对于(1)(2)这两个条件是否满足要求，我们是可以从文法中直观的看出来的，但是
(3)是要通过求 FIRST集合，(4)要通过求 FIRST集合 FOLLOW集合才能判断。因此，我们
要总结 FIRST集合的构造方法和 FOLLOW集合的构造方法。
FIRST集合和 FOLLOW集合的构造方法
同样要以文法为例，直观的说明。考虑 G[E]：
E→TA
A→+TA|ε
T→FB|ε
B→*FB
F→(E)|i
FIRST集合的构造方法：
(1)对于 F→i这样的产生式，F的候选式 i是一个终结符，i不经过推导就能见到第
一个终结符，所以 FIRST（i）={i}；
(2)对于 F→(E)这样的产生式，虽然 F的候选是（E）不是一个终结符，而是终结符和
非终结符组成的符号串，但是(E)是以终结符（开始的，所以它的 FIRST集合也不难求，
FIRST（（E））={（}；
(3)对于 E→TA 这样的产生是，E的候选是是以非终结符开始，我们直观上是看不到第
一个终结符，因此，我们就应该根据最左推导的思想替换 T，因此，第一个终结符要有 T
推导产生，也就是需要 FIRST（T），因为 T→FB|ε，所以 FIRST(T)= FIRST（F）∪{ε}=
{(,i,ε}。由于 T→ε那么 TA=εA=A，E→TA 就变成了 E→A，FIRST(TA)= FIRST(A)=
{+,ε}。因此，FIRST(TA)= FIRST(T)-{ε}∪FIRST(A)={（,i}∪{+,ε}
FOLLOW集合的构造方法：
(1)对于文法的开始符号 S来说，有#∈FOLLOW(S).
(2)对于 F→(E)这样的产生式来说，非终结符 E后有终结符），因此，）
∈FOLLOW(E)。
(3)对于 T→FB 这样的产生式来说，非终结符 F后有非终结符 B，因此，F后的第一个
终结符要有 B推导产生，因此，FIRST（B）∈
FOLLOW(F)。
(4)对于 T→FB 这样的产生式来说，非终结符 B后既没有终结符，也没有非终结符，
那能不能说明ε属于 FOLLOW(B)呢？不能。我们看看 B是怎么出现的。E=>TA=>FBA，从文
法的开始符号出发经过两步推导，就能出现 B，这个时候我们看到 B后是 A，它和 T后的
符号相同，因此，FOLLOW(T)∈FOLLOW(B)。
LL(1)的具体判定过程
FIRST集合和 FOLLOW集合的构造方法已经总结，通过实例说明，大家也不觉得太困难
了，但是对一个文法来说，要判定一个文法是不是 LL(1)的具体应该怎么做呢，我们仍以
文法 G[E]为例来进行说明。
对于 F→(E)|i，FIRST（(E)）∩FIRST（i）={(}∩{i}=Φ
B→*FBFIRST（*FB）={*}
T→FB|εFIRST（FB）∩FOLLOW(T)={ (,i }∩{+,#，)} =Φ
A→+TA|εFIRST（+TA）∩FOLLOW(A)={+}∩{#，)} =Φ
E→TAFIRST（TA）={(,i}
因此，G[E]是 LL(1)文法。
由于上边这种描述形式很不直观，会出现求集合不全的现象。如果采用表格法把同一
个非终结符定义的不同产生式都写在一个方格里，并且分别表示。对于一个非终结符来
说，如果它的候选式不包含空，我们只需比较候选式的 FIRST集是否有交集，如果它的候
选式包含空，只需比较 FIRST集和 FOLLOW是否有交集。很显然这样会比较直观。
3小结
以 LL(1)文法的判定为例，将案例驱动法引入教学过程中，使得抽象的理论变得具
体，这是在编译原理课程教学中行之有效的方法。因此，教师要多研究案例，把课程内容
的讲解变的引人入胜，从而提高教学质量，提高学生的编译能力，促进我国的 IT事业的
发展
