張亞娟 馮靈霞

摘要：編譯原理課程是計(jì)算機(jī)相關(guān)專(zhuān)業(yè)的一門(mén)重要專(zhuān)業(yè)課，抽象性、理論性強(qiáng)，在多年的教學(xué)基礎(chǔ)上，以LL(1)文法的判定為例，提出將案例驅(qū)動(dòng)法引入教學(xué)過(guò)程中，從而不僅讓學(xué)生掌握學(xué)習(xí)編譯原理的方法，而且也可以對(duì)學(xué)生邏輯思考能力進(jìn)行培養(yǎng)。

關(guān)鍵詞：編譯原理；案例驅(qū)動(dòng)；LL(1)文法

中圖分類(lèi)號(hào)：G642文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2012)24-5858-02

計(jì)算機(jī)語(yǔ)言之所以能由單一的機(jī)器語(yǔ)言發(fā)展到現(xiàn)今的命令式編程語(yǔ)言、面向?qū)ο蟮木幊陶Z(yǔ)言、函數(shù)式編程語(yǔ)言和邏輯式編程語(yǔ)言，就是編譯技術(shù)的支持。學(xué)生對(duì)編譯技術(shù)已經(jīng)不再陌生，如何激發(fā)他們從事編譯器開(kāi)發(fā)的熱情，進(jìn)而發(fā)展我國(guó)的漢語(yǔ)編程語(yǔ)言，把我國(guó)的IT行業(yè)發(fā)展到國(guó)際先進(jìn)水平，是我們教學(xué)過(guò)程中亟待解決的問(wèn)題。

編譯技術(shù)中，自頂向下的語(yǔ)法分析分為預(yù)測(cè)分析和遞歸下降分析。預(yù)測(cè)分析中最常用的是LL(1)分析，其中第一個(gè)L表示從左向右掃描輸入串，第二個(gè)L表示最左推導(dǎo)過(guò)程。給定一個(gè)文法如何判定它是否是LL(1)的，這個(gè)問(wèn)題一直是我們教學(xué)過(guò)程中的一個(gè)重點(diǎn)，同時(shí)也是一個(gè)難點(diǎn)，可能有些老師也會(huì)覺(jué)得，自己明明講的很清楚了，學(xué)生在實(shí)際判定過(guò)程中怎么還覺(jué)得困難呢。問(wèn)題的關(guān)鍵是我們是采用什么樣的案例，怎么引入，以及怎么總結(jié)的。筆者就根據(jù)自己多年的教學(xué)總結(jié)，來(lái)談?wù)勥@個(gè)問(wèn)題，希望給老師和同學(xué)一個(gè)借鑒。

1 LL(1)文法的引入

自頂向下的語(yǔ)法分析的思想是，從文法的開(kāi)始符號(hào)出發(fā)，為符號(hào)串構(gòu)造一個(gè)最左推導(dǎo)過(guò)程，如果成功，說(shuō)明符號(hào)串是給定文法可以產(chǎn)生的。因此，我們?nèi)匀灰酝茖?dǎo)為主線(xiàn)，看一下，LL(1)到底要滿(mǎn)足什么樣的條件。

(1)考慮文法G[A]:

A→Ax

A→y

和符號(hào)串yxxx。

G[A]的第一個(gè)產(chǎn)生式是左遞歸，在推導(dǎo)yxxx符號(hào)串時(shí)，分析程序無(wú)法通過(guò)有窮的向前看符號(hào)，了解需要應(yīng)用幾次遞歸后才選擇一條可令遞歸終止的產(chǎn)生式。

(2)如果一個(gè)文法沒(méi)有遞歸產(chǎn)生式，是否就能順利推導(dǎo)呢？考慮文法G[S]：

S→aAb

A→bAc|bBc

B→aB|a

G[S]沒(méi)有遞歸產(chǎn)生式，但在推導(dǎo)符號(hào)串a(chǎn)bacb時(shí)，從文法的開(kāi)始符號(hào)S開(kāi)始，為了匹配第一個(gè)字符a，由于S只有一個(gè)產(chǎn)生式，可以選擇aAb，a匹配成功。為了匹配第二個(gè)字符b，需要將A替換，但A有兩個(gè)產(chǎn)生式并且都以b開(kāi)始，就存在不確定選擇哪個(gè)產(chǎn)生式的問(wèn)題，必須進(jìn)行回溯才能確定這個(gè)符號(hào)串是否是該文法可以產(chǎn)生的。因此，一個(gè)文法沒(méi)有左遞歸但有左因子也是不能順利推導(dǎo)的。

(3)如果一個(gè)文法不含左遞歸和左因子，是否就能很順利地進(jìn)行推導(dǎo)呢?？紤]文法G[P]：

P→Bc|ad

B→aA|b

在輸入串a(chǎn)bc的推導(dǎo)過(guò)程中，P有兩個(gè)候選式Bc和ad，對(duì)于Bc，要看B的候選式aA和b，因此，P的兩個(gè)候選式Bc和ad，都是以a開(kāi)始的，因此，當(dāng)文法中同一個(gè)非終結(jié)符的候選式的First集有交集也不能很順利地進(jìn)行推導(dǎo)。

(4)如果一個(gè)文法不含左遞歸、左因子、候選式的First集也沒(méi)有交集，是否就能很順利地進(jìn)行推導(dǎo)呢?？紤]文法G[Q]：

Q→Aa|Bb

A→a|cA|ε

B→b|d

在輸入串cca的推導(dǎo)過(guò)程中，第一個(gè)字符是c，對(duì)于Q的兩個(gè)候選式，選擇以c開(kāi)始的，但Q的兩個(gè)候選式是以A和B開(kāi)始的，考慮A和B中以c開(kāi)始的，有cA，因此選擇Aa，第一個(gè)字符匹配成功，第二個(gè)字符是c，選擇cA，第三個(gè)要匹配a，A中有定義a的候選式，如果選擇，就多了一個(gè)符號(hào)a，只能選擇ε。原因就是A的候選式的First集和A的Follow集有交集a。

因此，通過(guò)前邊幾個(gè)文法的舉例，LL(1)文法的判定就可以總結(jié)為:

(1)文法中不能有左遞歸的產(chǎn)生式；

(2)文法中不能有左因子；

(3)對(duì)于一個(gè)非終結(jié)符來(lái)說(shuō)，如果它有多個(gè)候選式，并且都不為空，那么要求候選式的FIRST集合不能有交集.

(4)對(duì)于一個(gè)非終結(jié)符來(lái)說(shuō)，如果它有多個(gè)候選式，并且有定義為空，那么要求候選式的FIRST集合和這個(gè)非終結(jié)符的FOLLOW不能有交集。

2 LL(1)文法的判定

對(duì)于(1)(2)這兩個(gè)條件是否滿(mǎn)足要求，我們是可以從文法中直觀的看出來(lái)的，但是(3)是要通過(guò)求FIRST集合，(4)要通過(guò)求FIRST集合FOLLOW集合才能判斷。因此，我們要總結(jié)FIRST集合的構(gòu)造方法和FOLLOW集合的構(gòu)造方法。

2.1 FIRST集合和FOLLOW集合的構(gòu)造方法

同樣要以文法為例，直觀的說(shuō)明?？紤]G[E]：

E→TA

A→+TA|ε

T→FB|ε

B→*FB

F→(E)|i

FIRST集合的構(gòu)造方法：

(1)對(duì)于F→i這樣的產(chǎn)生式，F(xiàn)的候選式i是一個(gè)終結(jié)符，i不經(jīng)過(guò)推導(dǎo)就能見(jiàn)到第一個(gè)終結(jié)符，所以FIRST（i）={i}；

(2)對(duì)于F→(E)這樣的產(chǎn)生式，雖然F的候選是（E）不是一個(gè)終結(jié)符，而是終結(jié)符和非終結(jié)符組成的符號(hào)串，但是(E)是以終結(jié)符（開(kāi)始的，所以它的FIRST集合也不難求，F(xiàn)IRST（（E））={（}；

(3)對(duì)于E→TA這樣的產(chǎn)生是，E的候選是是以非終結(jié)符開(kāi)始，我們直觀上是看不到第一個(gè)終結(jié)符，因此，我們就應(yīng)該根據(jù)最左推導(dǎo)的思想替換T，因此，第一個(gè)終結(jié)符要有T推導(dǎo)產(chǎn)生，也就是需要FIRST（T），因?yàn)門(mén)→FB|ε，所以FIRST(T)= FIRST（F）∪{ε}={(,i,ε}。由于T→ε那么TA=εA=A，E→TA就變成了E→A，F(xiàn)IRST(TA)= FIRST(A)={+,ε}。因此，F(xiàn)IRST(TA)= FIRST(T)-{ε}∪FIRST(A)={（,i}∪{+,ε}

FOLLOW集合的構(gòu)造方法：

(1)對(duì)于文法的開(kāi)始符號(hào)S來(lái)說(shuō)，有#∈FOLLOW(S).

(2)對(duì)于F→(E)這樣的產(chǎn)生式來(lái)說(shuō)，非終結(jié)符E后有終結(jié)符），因此，）∈FOLLOW(E)。

(3)對(duì)于T→FB這樣的產(chǎn)生式來(lái)說(shuō)，非終結(jié)符F后有非終結(jié)符B，因此，F(xiàn)后的第一個(gè)終結(jié)符要有B推導(dǎo)產(chǎn)生，因此，F(xiàn)IRST（B）∈

FOLLOW(F)。

(4)對(duì)于T→FB這樣的產(chǎn)生式來(lái)說(shuō)，非終結(jié)符B后既沒(méi)有終結(jié)符，也沒(méi)有非終結(jié)符，那能不能說(shuō)明ε屬于FOLLOW(B)呢？不能。我們看看B是怎么出現(xiàn)的。E=>TA=>FBA，從文法的開(kāi)始符號(hào)出發(fā)經(jīng)過(guò)兩步推導(dǎo)，就能出現(xiàn)B，這個(gè)時(shí)候我們看到B后是A，它和T后的符號(hào)相同，因此，F(xiàn)OLLOW(T)∈FOLLOW(B)。

2.2 LL(1)的具體判定過(guò)程

FIRST集合和FOLLOW集合的構(gòu)造方法已經(jīng)總結(jié)，通過(guò)實(shí)例說(shuō)明，大家也不覺(jué)得太困難了，但是對(duì)一個(gè)文法來(lái)說(shuō)，要判定一個(gè)文法是不是LL(1)的具體應(yīng)該怎么做呢，我們?nèi)砸晕姆℅[E]為例來(lái)進(jìn)行說(shuō)明。

對(duì)于F→(E)|i，F(xiàn)IRST（(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)文法。

由于上邊這種描述形式很不直觀，會(huì)出現(xiàn)求集合不全的現(xiàn)象。如果采用表格法把同一個(gè)非終結(jié)符定義的不同產(chǎn)生式都寫(xiě)在一個(gè)方格里，并且分別表示。對(duì)于一個(gè)非終結(jié)符來(lái)說(shuō)，如果它的候選式不包含空，我們只需比較候選式的FIRST集是否有交集，如果它的候選式包含空，只需比較FIRST集和FOLLOW是否有交集。很顯然這樣會(huì)比較直觀。

3小結(jié)

以LL(1)文法的判定為例，將案例驅(qū)動(dòng)法引入教學(xué)過(guò)程中，使得抽象的理論變得具體，這是在編譯原理課程教學(xué)中行之有效的方法。因此，教師要多研究案例，把課程內(nèi)容的講解變的引人入勝，從而提高教學(xué)質(zhì)量，提高學(xué)生的編譯能力，促進(jìn)我國(guó)的IT事業(yè)的發(fā)展。

參考文獻(xiàn)：

[1]張亞娟,馮靈霞,王學(xué)春.編譯技術(shù)的發(fā)展及應(yīng)用[M].軟件導(dǎo)刊,2010, (9):78-80.

[2]蔣立源,康慕寧.編譯原理[M]. 3版.西安:西北工業(yè)大學(xué), 2007.

[3] (美)Thomas Pittman, James Peter.編譯程序設(shè)計(jì)藝術(shù):理論與實(shí)踐[M].李文軍,高曉燕,譯.北京:機(jī)械工業(yè)出版社, 2010,1.

[4]李勁華,丁潔玉.編譯原理與技術(shù)[M].北京:北京郵電大學(xué)出版社,2006.