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

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

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

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

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

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

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

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

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

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

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

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

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

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

活前綴和句柄關(guān)系——?jiǎng)偤煤芯浔幕钋熬Y稱為可歸前綴。

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

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

LR(1)有效項(xiàng)目

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

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

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

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

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

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

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

② 活前綴中只含有句柄的一部分符號(hào)。

③ 活前綴中不包含句柄的任何符號(hào)。

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

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

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

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

do{

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

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

把B→#8226;γ加入J;

}while(沒(méi)有更多的項(xiàng)目可以加入J);

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

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

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

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

3LR文法的判定

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

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

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

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

4結(jié)語(yǔ)

LR分析法是編譯程序語(yǔ)法分析中最常用且有效的自下而上的分析方法，理論較完善，適用于大多數(shù)上下文無(wú)關(guān)語(yǔ)言的分析。LR分析法是一種逐步產(chǎn)生文法規(guī)范句型活前綴過(guò)程的分析方法，可以從尋找活前綴入手，確定句柄和分析動(dòng)作，從而構(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è)計(jì)語(yǔ)言編譯原理[M]. 3版. 北京:國(guó)防工業(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