張亞娟 馮靈霞

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

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

中圖分類號：G642文獻標識碼：A文章編號：1009-3044(2012)24-5858-02

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

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

1 LL(1)文法的引入

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

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

A→Ax

A→y

和符號串yxxx。

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

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

S→aAb

A→bAc|bBc

B→aB|a

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

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

P→Bc|ad

B→aA|b

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

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

Q→Aa|Bb

A→a|cA|ε

B→b|d

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

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

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

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

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

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

2 LL(1)文法的判定

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

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

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

E→TA

A→+TA|ε

T→FB|ε

B→*FB

F→(E)|i

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

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

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

(3)對于E→TA這樣的產(chǎn)生是，E的候選是是以非終結(jié)符開始，我們直觀上是看不到第一個終結(jié)符，因此，我們就應(yīng)該根據(jù)最左推導(dǎo)的思想替換T，因此，第一個終結(jié)符要有T推導(dǎo)產(chǎn)生，也就是需要FIRST（T），因為T→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)對于文法的開始符號S來說，有#∈FOLLOW(S).

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

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

FOLLOW(F)。

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

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

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

對于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)文法。

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

3小結(jié)

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

參考文獻：

[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è)計藝術(shù):理論與實踐[M].李文軍,高曉燕,譯.北京:機械工業(yè)出版社, 2010,1.

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