LR分析的教學(xué)法探討

摘要:LR分析法是編譯程序語法分析中最常用且有效的自下而上的分析方法，理論較完善，適用于大多數(shù)上下文無關(guān)語言的分析。本文主要探討LR分析的教學(xué)方法，采用“啟發(fā)+關(guān)聯(lián)式”教學(xué)法，引導(dǎo)學(xué)生理解LR分析的內(nèi)涵。

關(guān)鍵詞:LR分析法;項目集規(guī)范族;LR分析表;LR文法

“編譯原理”是計算機(jī)學(xué)科的一門重要專業(yè)基礎(chǔ)課，列入國際ACM教程和IEEE計算機(jī)學(xué)科的主干課程。該課程使學(xué)生了解針對高級程序設(shè)計語言的通用編譯程序設(shè)計的基本理論;學(xué)習(xí)、掌握編譯程序設(shè)計與實現(xiàn)的基本方法和原理;學(xué)習(xí)軟件自動生成的原理、技術(shù)和工具;培養(yǎng)其對系統(tǒng)軟件的規(guī)劃、組織、設(shè)計和實現(xiàn)的綜合能力和素質(zhì);訓(xùn)練其對大型軟件工程實施的技術(shù)與能力[1-3]。該課程需要以離散數(shù)學(xué)、操作系統(tǒng)、數(shù)據(jù)結(jié)構(gòu)、形式語言與自動機(jī)、編程語言等多門先修課程作鋪墊，理論知識覆蓋面廣、內(nèi)容抽象、算法多而復(fù)雜，因此學(xué)生普通反映知識難以理解、理論很難與實踐結(jié)合。如何在教學(xué)過程中改進(jìn)教學(xué)方法和手段，幫助學(xué)生理解編譯原理的理論，有效提高學(xué)生的實踐能力，是一個有待解決的課題。

語法分析是教學(xué)重點內(nèi)容，而LR分析法又是語法分析中較難掌握的一種分析方法。本文主要介紹LR分析的教學(xué)方法，以使學(xué)生系統(tǒng)靈活地掌握LR分析的本質(zhì)。

1學(xué)生學(xué)習(xí)LR分析法存在的問題

學(xué)習(xí)LR分析法時，學(xué)生能夠正確理解教師講解的定義，如活前綴、句柄、LR有效項目等，也能正確解答教師布置的LR分析習(xí)題，但在深層次理解LR分析的內(nèi)涵、各個知識點的關(guān)聯(lián)性方面仍存在問題，主要體現(xiàn)在如何深刻理解LR分析的實現(xiàn)思想和LR分析的實現(xiàn)機(jī)制;LR分析的思想在其他領(lǐng)域的拓廣應(yīng)用等，這些都是教師講解LR分析法時著重培養(yǎng)學(xué)生思考的問題。教師不僅要教會學(xué)生如何使用LR分析法分析具體題目，更為重要的是應(yīng)讓學(xué)生深刻理解LR分析法的內(nèi)涵和本質(zhì)，使學(xué)生能夠?qū)R分析法的思想轉(zhuǎn)化為一種思考問題的方法，教會學(xué)生將學(xué)到的知識轉(zhuǎn)化為能力。筆者正是將LR分析的概念和實現(xiàn)思想融為一體，用“啟發(fā)+關(guān)聯(lián)式”教學(xué)法融會貫通地講解LR分析法，讓學(xué)生真正理解LR分析法的內(nèi)涵。

2LR分析實現(xiàn)思想的“啟發(fā)+關(guān)聯(lián)式”教學(xué)法

LR分析法是語法分析的重點內(nèi)容，學(xué)生理解這部分內(nèi)容比較困難。教師在講解時，不僅要講解基礎(chǔ)概念和原理，更要讓學(xué)生深刻理解LR分析的內(nèi)涵以及各種LR分析法之間的關(guān)聯(lián)與特點。經(jīng)過多年的教學(xué)探索和實踐，我們采用“啟發(fā)+關(guān)聯(lián)式”教學(xué)法，啟發(fā)引導(dǎo)學(xué)生理解活前綴、句柄等基本概念，然后基于LR分析法的核心，利用LR各種分析法之間的關(guān)聯(lián)性，使學(xué)生融會貫通地理解LR分析法。

LR(k)是指從左向右掃描輸入串并進(jìn)行自下而上的語法分析，在分析的每一步，只需要根據(jù)分析棧當(dāng)前已移進(jìn)和歸約出的全部文法符號，再向前查看k個輸入符號，就能確定適合于文法規(guī)則的句柄是否已在分析棧頂部形成，從而確定當(dāng)前的分析動作[1-3]。教師應(yīng)讓學(xué)生明確LR分析法的關(guān)鍵兩點:自下而上的分析;分析棧頂是否形成句柄。

LR分析器的工作是一個逐步產(chǎn)生文法G規(guī)范句型活前綴的過程。在分析過程中，必須使分析棧中的符號始終是活前綴，然后通過對余留符號串的繼續(xù)掃描，逐步在分析棧中構(gòu)成最長活前綴，此時分析棧頂部形成句柄，可立即歸約。所以，教師講授時要給學(xué)生樹立這樣的認(rèn)知:分析過程中，句柄的確定是通過尋找規(guī)范句型的活前綴來實現(xiàn)的，可從尋找活前綴入手確定句柄和分析動作，從而構(gòu)造出LR分析表。

本文圍繞圖1所示內(nèi)容和提出的問題討論LR分析法的內(nèi)涵。

自下而上分析法的關(guān)鍵:可歸約串;歸約原則。

LR分析核心思想:通過識別活前綴識別句柄——歸結(jié)到構(gòu)造識別活前綴的FA。

活前綴和句柄關(guān)系——剛好含有句柄的活前綴稱為可歸前綴。

LR(0)項目與活前綴關(guān)系?“#8226; ”含義。

LR(1)項目含義——搜索符求解。

LR(1)有效項目

LR(1)項目集規(guī)范族的構(gòu)造:Closure(待約項目擴(kuò)展求解);GO(產(chǎn)生后繼項目集，跟蹤活前綴識別)。

LR(1)分析表的構(gòu)造。

圖1LR分析法的內(nèi)涵

講授LR分析法時，關(guān)鍵是讓學(xué)生深刻理解LR分析法的核心是通過識別活前綴識別句柄。因此教師在講解活前綴和句柄的概念(規(guī)范句型的一個不含句柄之后任何符號的前綴，稱為該句型的一個活前綴。一個句型的最左直接短語，稱為該句型的句柄。)之后，應(yīng)啟發(fā)學(xué)生理解活前綴與句柄之間的關(guān)系以及活前綴和句柄的作用。如果句柄在棧頂形成，就進(jìn)行“歸約”動作。LR分析法的關(guān)鍵就是找到可歸前綴(剛好含有句柄的活前綴稱為可歸前綴)實施歸約，具體方法是構(gòu)造識別文法可歸前綴的有限自動機(jī)。

為了識別活前綴，要引入LR(0)項目。LR(0)項目是在文法G的每個產(chǎn)生式的右部(候選式)的任何位置上添加一個圓點所構(gòu)成的產(chǎn)生式。LR(0)項目中的圓點可看成是分析棧棧頂與輸入串的分界線，圓點左邊為已進(jìn)入分析棧的部分，右邊是當(dāng)前輸入或繼續(xù)掃描的符號串。

通過LR(0)項目，教師啟發(fā)學(xué)生加深對活前綴與句柄的理解，并采用實例鞏固學(xué)生對這部分知識的掌握，以便為后續(xù)學(xué)習(xí)LR的各種分析法打下基礎(chǔ)。在一個規(guī)范句型的活前綴中，不會含有句柄右邊的任何符號，因此，活前綴與句柄間的關(guān)系有三種情況:

① 活前綴中已含有句柄的全部符號，這是一個特殊活前綴，通常稱為可歸前綴。

② 活前綴中只含有句柄的一部分符號。

③ 活前綴中不包含句柄的任何符號。

第一種情況表明，此時某一產(chǎn)生式A→β的右部符號串β已出現(xiàn)在棧頂，分析動作應(yīng)是用該產(chǎn)生式進(jìn)行歸約。第二種情況意味著形如A→β1β2的產(chǎn)生式的左子串β1已出現(xiàn)在棧頂，正期待著從余留輸入串中看到由β2推出的符號串。而第三種情況則意味著期望從余留輸入串中看到某一產(chǎn)生式A→α中的α符號串。這幾種情況可以用LR(0)項目來表示。

LR(0)分析是僅僅根據(jù)當(dāng)前分析棧頂狀態(tài)(該狀態(tài)記錄著已進(jìn)行過的分析歷史情況)而不需要從當(dāng)前輸入字符串再向前查看輸入符號，來決定當(dāng)前的分析動作。也就是說LR(0)分析的實現(xiàn)是只根據(jù)“歷史”資料即可決定當(dāng)前分析棧是否已構(gòu)成句柄，從而確定分析動作。

教師在具體講解不同的LR分析法時，要著重講解它們之間的區(qū)別與特點，采用關(guān)聯(lián)式教學(xué)方法可取得不錯的教學(xué)效果。不同于LR(0)分析，LR(1)分析需要向前搜索1個字符，LR(1)項目實際上是進(jìn)行求解搜索符。為了使分析的每一步都能使棧中保持一個規(guī)范句型的活前綴，必須要求每一個LR(1)項目對應(yīng)的活前綴是有效的。若文法G的一個LR(1)項目[A→ a #8226;b ，a]對活前綴g是有效的，當(dāng)且僅當(dāng)存在規(guī)范推導(dǎo)S=>dAω=>dabω，其中:ω∈VT*，g=ad，aIcirc;FIRST(w)或a為’#’(當(dāng)w=e)，a為搜索符。 識別文法G可歸前綴的DFA項目集的全體稱為文法G的LR(0)項目集規(guī)范族。構(gòu)造LR(0)項目集規(guī)范族的方法主要有兩種。一種是基于自動機(jī)理論構(gòu)造法:構(gòu)造文法G的LR(0)項目;基于LR(0)項目，構(gòu)造識別文法所有活前綴的非確定有限自動機(jī)(NFA);NFA確定化為確定有限自動機(jī)(DFA)，該DFA的各個狀態(tài)所包含的項目集合即構(gòu)成了G的LR(0)項目集規(guī)范族。另一種是基于拓廣文法的方法:構(gòu)造文法的拓廣方法;構(gòu)造文法項目集的閉包;求狀態(tài)轉(zhuǎn)換函數(shù)GO(I ， X)。這兩種方法本質(zhì)是一致的，都是最終求得有限自動機(jī)。第一種方法是直接求有限自動機(jī);第二種方法是項目集閉包對應(yīng)有限自動機(jī)的狀態(tài)，一個項目集中項目圓點的移動(對應(yīng)移進(jìn)項目)和待約項目的變化對應(yīng)有限自動狀態(tài)的轉(zhuǎn)移。

一個LR(1)項目集合與LR(0)分析的情況類似，表示識別文法全部可歸前綴的DFA的每個狀態(tài)。構(gòu)造有效的LR(1)項目集規(guī)范族的辦法和構(gòu)造LR(0)項目集規(guī)范族的方法在本質(zhì)上是一樣的，同樣需要涉及兩個重要的環(huán)節(jié):項目集的閉包Closure和GO函數(shù)的求解。Closure用于進(jìn)行待約項目擴(kuò)展求解;GO函數(shù)用于產(chǎn)生后繼項目集，跟蹤活前綴識別。對于LR(1)項目集規(guī)范族，難點在于LR(1)項目集閉包的求解。文法項目集閉包的求解核心思想是:

do{

if(J的每個項目A→α#8226;Bβ和G的每個產(chǎn)生式

B→γ，若B→#8226;γ不在J中)

把B→#8226;γ加入J;

}while(沒有更多的項目可以加入J);

學(xué)生需要明確的是，對于每個LR(1)項目集中的項目，要考慮是否是待約項目，如果是待約項目，就要進(jìn)行擴(kuò)展，從而求得項目集的閉包。

給定一個文法，當(dāng)識別其所有可歸前綴的DFA，可據(jù)此直接構(gòu)造LR(0)分析表及相應(yīng)的LR分析器，或者基于項目集規(guī)范族和GO函數(shù)構(gòu)造LR(0)分析表。LR分析器的實質(zhì)是一個帶棧的確定有限狀態(tài)自動機(jī)。

LR分析表是LR分析法的關(guān)鍵。LR分析表分為兩部分:action表和goto表。教師在講解時，需要讓學(xué)生明確action表是在上述項目集規(guī)范族求得的有限自動機(jī)基礎(chǔ)上，針對其狀態(tài)轉(zhuǎn)移弧的標(biāo)記是終結(jié)符而設(shè)計的表，具體動作有移進(jìn)、歸約、接受和出錯;而goto表則是針對非終結(jié)符設(shè)計的表。對于action表，“移進(jìn)”動作表示句柄尚未在分析棧頂形成，正期待繼續(xù)移進(jìn)符號以形成句柄;“歸約”動作表示當(dāng)前在棧頂處已經(jīng)形成當(dāng)前句型的句柄，可按相應(yīng)的歸約式立即歸約;“接受”動作表示已經(jīng)歸約到文法的開始符號，分析成功;依據(jù)求LR分析項目規(guī)范族的兩種方法，則對應(yīng)求解LR(0)分析表也有兩種方法:根據(jù)識別活前綴的DFA構(gòu)造LR(0)分析表和從LR(0)項目集規(guī)范族C和GO函數(shù)構(gòu)造LR(0)分析表。

教師在講解上述內(nèi)容之后，要讓學(xué)生理解如何驅(qū)動完成LR分析。LR分析器主要由三部分組成:下推分析棧、LR分析表和LR分析總控程序。LR分析是在總控程序的控制下自左向右掃描輸入串，并根據(jù)當(dāng)前分析棧頂所存放的文法符號狀態(tài)及當(dāng)前掃描讀入的符號，依據(jù)LR分析表的指示驅(qū)動完成分析動作。

3LR文法的判定

LR(0)、LR(1)、SLR(0)和LALR(1)四種LR分析方法相應(yīng)地對應(yīng)四種LR文法和LR分析器，判斷一個給定文法G屬于哪一類LR文法的方法如圖2所示。

圖2判定文法G屬于哪類LR文法的流程

教師講解這部分內(nèi)容時，重點強(qiáng)調(diào)判定的方法和流程。

教師講解判斷給定文法G屬于哪類LR文法的流程時，要特別強(qiáng)調(diào)LR(1)文法的判定過程。構(gòu)造LR(1)的項目集規(guī)范族后，判斷是否有沖突，若沒有沖突，再判斷是否有同心項目集，若沒有同心項目集，可判定此文法為LR(1)文法;否則，構(gòu)造LALR(1)的項目集規(guī)范族，若有沖突，此文法是LR(1)方法，若無沖突，此文法是LALR(1)方法。

4結(jié)語

LR分析法是編譯程序語法分析中最常用且有效的自下而上的分析方法，理論較完善，適用于大多數(shù)上下文無關(guān)語言的分析。LR分析法是一種逐步產(chǎn)生文法規(guī)范句型活前綴過程的分析方法，可以從尋找活前綴入手，確定句柄和分析動作，從而構(gòu)造出LR分析表。本文主要探討LR分析的教學(xué)法，采用“啟發(fā)+關(guān)聯(lián)式”教學(xué)法引導(dǎo)學(xué)生理解LR分析的內(nèi)涵，使學(xué)生系統(tǒng)并靈活地理解和掌握LR分析法的核心思想和本質(zhì)。

參考文獻(xiàn):

[1] 陳英，王貴珍，李侃，等. 編譯原理[M]. 北京:清華大學(xué)出版社，2009.

[2] 陳火旺，劉春林，譚慶平，等. 程序設(shè)計語言編譯原理[M]. 3版. 北京:國防工業(yè)出版社，2000.

[3]Alfred V. Aho， Ravi Sethi， Jeffrey D. Ullman. Compilers: Principles， Techniques and Tools[M]. USA: Addison Wesley， Pearson Education，1986.

Teaching Method of LR Parsing

LI Kan， WANG Gui-zhen， JI Wei-xing

(School of Computer， Beijing Institute of Technology， Beijing 100081， China)

Abstract: LR parsing， which has relatively completed theory， is the most commonly used and effective bottom-top method in the syntax analysis of compiler， and is applied to the analysis of most of context-free languages. Teaching method of LR parsing is discussed in the paper. Heuristic and relational teaching method is used to guide students to understand meaning of LR parsing.

Key words: LR parsing; canonical collection of set of items; LR parsing table; LR grammar