案例驱动法在编译原理课程教学中的应用

案例驱动法在编译原理课程教学中的应用

计算机语言之所以能由单一的机器语言发展到现今的命令式编程语言、面向对象的编程语言、函数式编程语言和逻辑式编程语言，就是编译技术的支持。学生对编译技术已经不再陌生，如何激发他们从事编译器开发的热情，进而发展我国的汉语编程语言，把我国的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)文法的判定

2.1 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)。

2.2 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事业的发展。