徐艷群 張 斌

（南陽理工學(xué)院 計算機(jī)與信息工程學(xué)院，河南 南陽 473004）

基于PBL的教學(xué)方法在編譯原理課程教學(xué)中的應(yīng)用探究
——以LR類語法分析為例

徐艷群 張 斌

（南陽理工學(xué)院 計算機(jī)與信息工程學(xué)院，河南 南陽 473004）

編譯原理課程是計算機(jī)專業(yè)最能鍛煉學(xué)生計算思維能力的一門課程。但截至到目前編譯原理的課堂教學(xué)還是采用傳統(tǒng)滿堂灌的教學(xué)方式，學(xué)生沒有參與到課堂中來。因此作者提出采取“以問題為中心、學(xué)生為主體的自主學(xué)習(xí)方式”即PBL的教學(xué)方法，并將其應(yīng)用于編譯原理LR類語法分析方法的教學(xué)實踐中，取得了較好的教學(xué)效果。

編譯原理；問題導(dǎo)向；LR類分析法

一、PBL的涵義

為了提高學(xué)生的學(xué)習(xí)能力，英美一些發(fā)達(dá)國家被廣泛采用“以問題為中心、學(xué)生為主體的自主學(xué)習(xí)方式”即PBL（Problem-Based Learning，問題式學(xué)習(xí)）的教學(xué)方法，教師通過設(shè)立問題，在課前引導(dǎo)學(xué)生查閱相關(guān)資料，采取自主學(xué)習(xí)或分組討論的形式解決問題，課堂上可以讓學(xué)生分組講等方式完成教學(xué)內(nèi)容，目的是通過知識的主動建構(gòu)，激發(fā)學(xué)生的學(xué)習(xí)激情，挖掘?qū)W生的學(xué)習(xí)潛力。文章針對以往編譯原理課程教學(xué)特點，在編譯原理LR類語法分析大膽采用PBL教學(xué)方法進(jìn)行改革和教學(xué)實踐，取得了良好的教學(xué)效果。

二、編譯原理課程教學(xué)現(xiàn)狀

《編譯原理》是計算機(jī)專業(yè)的一門很重要的課程，集中體現(xiàn)了計算機(jī)的思維方式。但該課程涉及的理論抽象，算法復(fù)雜：幾乎每一章都有很多知識點，很多新的理論算法思想，很多需要學(xué)生動手實踐的環(huán)節(jié)等。但目前編譯原理教學(xué)缺少互動，效果差，學(xué)生如果上課能認(rèn)真聽講，可以按照老師課堂講的內(nèi)容，回答大部分問題，但如果學(xué)生不會去思考“為什么”“如何做”等問題，學(xué)生的這種學(xué)習(xí)方式就是一種被動的接受知識的過程，學(xué)生學(xué)完這門課程，不知道一個編譯器到底應(yīng)該怎么設(shè)計？怎樣實現(xiàn)？在設(shè)計的過程中到底應(yīng)該選取哪種語法分析方法，生成的代碼優(yōu)化到什么程度就達(dá)到最優(yōu)等。因此如何改變目前《編譯原理》課程死板的教學(xué)模式，提高教學(xué)效果，改善教學(xué)質(zhì)量，讓學(xué)生積極主動地投身到編譯原理的課程學(xué)習(xí)中，獲得更多更有用的編譯原理課程的理論知識，提高學(xué)生發(fā)現(xiàn)問題、分析問題、解決問題的能力，是各位編譯原理教師應(yīng)該思考和關(guān)注的問題。針對目前在編譯原理課程教學(xué)中存在的問題，作者將PBL教學(xué)方法引入到編譯原理課程教學(xué)中，文章將以LR類語法分析為類進(jìn)行介紹。

三、基于PBL的教學(xué)方法在編譯原理課程教學(xué)中的應(yīng)用

按照PBL教學(xué)方法，教師在具體實施中可以按照以下步驟來進(jìn)行教學(xué)設(shè)計，最終幫助學(xué)生解決問題：發(fā)現(xiàn)問題→引導(dǎo)學(xué)生分析問題→組織并幫助學(xué)生進(jìn)行小組討論或自主學(xué)習(xí)→知識建構(gòu)→自我反思，最后進(jìn)行教師進(jìn)行內(nèi)容總結(jié)并補充。

通過課程的合理設(shè)計及問題的巧妙提出，讓同學(xué)通過問題的引導(dǎo)明確本節(jié)課的教學(xué)目標(biāo)，通過教師的引導(dǎo)學(xué)生明確問題的解決思路，通過問題的解決讓學(xué)生理解課程知識體系，采用循序漸進(jìn)引導(dǎo)啟發(fā)的方式讓學(xué)生主動的學(xué)習(xí)，掌握編譯原理課程知識。文章以LR語法分析法為例來幫助大家理解。

（一）創(chuàng)設(shè)問題

問題不能來的太突然，因此需創(chuàng)設(shè)情境，進(jìn)行帶入。可以先給出一個文法如下：

G：（0）S'→S（1）S→aAd（2）S→bAc（3）S→aec（4）S→bed（5）A→e

1.先要求學(xué)生采用已學(xué)過的LR（0）分析法進(jìn)行分析。由于前面學(xué)生學(xué)習(xí)過LR（0）分析法，學(xué)生就可以完成此題。在構(gòu)造LR（0）識別活前綴的確定化有限自動機(jī)過程中出現(xiàn)了項目集:I7=｛A→e.，S→ae.c｝中，按照LR（0）分析法構(gòu)造分析表時對于第I7狀態(tài)，遇到超前搜索符c時可以進(jìn)行移進(jìn)，在分析表中填S9，同時對于項目A→e.，需要在這個表中填R5，即在一個表格中填兩個動作，即狀態(tài)I7中出現(xiàn)了歸約-移進(jìn)沖突，當(dāng)對符合串進(jìn)行分析的時候，查到這個狀態(tài)I7遇到符號c時，不知道改采用哪個動作，這時可以讓學(xué)生按照兩種動作分別做一下，識別出為什么一種正確，而另外一種不行呢？學(xué)生通過思考發(fā)現(xiàn)采用LR（0）分析法顯然不行。重新審視這種方法。

2.引導(dǎo)學(xué)生進(jìn)一步思考采用SLR（1）分析法，對于移進(jìn)項目跟LR（0）完全相同，對于歸約項目需求歸約項目產(chǎn)生式左部非終結(jié)符號的Follow集，即求項目A→e.產(chǎn)生式左部非中介符號A的Follow集，F(xiàn)ollow（A）=｛c，d｝，很明顯A的Follow集中還有c，說明沖突解決不了。

3.引導(dǎo)學(xué)生進(jìn)行思考：為什么不行？顯然當(dāng)棧里邊的符號為ae，輸入符號c時，如果對把棧頂符號e歸約為A，當(dāng)前符號串就變?yōu)閍Ac，而它不是一個規(guī)范句型，A后面可以跟c，因為有規(guī)范句型bAc，這也就是SLR（1）分析法求Follow集的原因。很自然地讓學(xué)生自己發(fā)現(xiàn)采用SLR（1）分析法顯然不行。情境帶入學(xué)生主動思考采用哪種方法解決該問題，給學(xué)生這次課到下次課之間的思考時間。

（二）引導(dǎo)學(xué)生分析問題

經(jīng)過思考之后學(xué)生深入理解采用前兩種方法不行的原因，組織學(xué)生分組講解原因，教師進(jìn)行歸納補充?？紤]LR（0）分析表的造表算法規(guī)則（2），對于歸約項目A→α·，不管下一輸入符號是誰，均進(jìn)行歸約。這顯然是一個武斷的決定。若Ii中同時含有［B→α·bβ及C→α·］兩類項目時，上述填表方法必然得到?jīng)_突的分析表。一般地，Ii=｛A1→α·a1β1，…，Am→α· amβm，B1→α·，…，Bn→α·｝如果能根據(jù)下一輸入符號a對上述沖突加以區(qū)分，則沖突可解決。當(dāng)Follow（Bk）（1≦k≦n）與｛a1，a2，…，am｝兩兩互不相交時，則可按下述方法解決沖突：從SLR（1）解決問題的方法看，對于歸約項目A→α·，只要是Follow（A）中的符號均可按此產(chǎn)生式進(jìn)行歸約，這也有一定的片面性，因為沒有考慮α所在的“環(huán)境”。當(dāng)α在棧頂形成時（設(shè)此時棧內(nèi)容為#δα，輸入符為a），若強(qiáng)行將α歸約為A（棧內(nèi)容：#δA），但#δAa又不是任何規(guī)范句型的前綴時，這個歸約就是無效的。

（三）自主學(xué)習(xí)或分組討論

知道了什么是LR（1）分析法，分組討論如何采用LR（1）分析法做題，就需要構(gòu)造LR（1）識別活前綴的DFA，構(gòu)造的過程跟LR（0）、SLR（1）進(jìn)行比較，找到不同處：每個項目都有超前搜索字符，如何確定LR（1）每個項目集，顯然跟LR（0）或SLR（1）一樣，基本項目為［S′→.S］，LR（1）需要考慮超前搜索字符，文法開始符號的超前搜索字符為#，因此確定［S′→.S，#］為LR（1）的基本項目，其他項目的確定方法的難點就是確定每個項目的超前搜索字符。根據(jù)以下定義確定：

LR（1）項目［A→α·β，α］對活前綴γ=δα有效，iff存在規(guī)范推導(dǎo)S?*δAy?δαβy y∈VT*且滿足條件：

（1）當(dāng)y≠ε時，a∈FIRST（y）；（2）當(dāng)y=ε時，a=#.

這樣可以求出每個項目集的閉包。

（四）知識主動建構(gòu)

通過閱讀教材和小組討論，教師引導(dǎo)啟發(fā)，學(xué)生主動學(xué)習(xí)運用比較分析法掌握LR（1）語法分析方法，從而完成了對知識的主動建構(gòu)。LR（0）只要出現(xiàn)歸約項目，不管當(dāng)前識別符號是什么，就無條件歸約，這樣可能出現(xiàn)歸約-移進(jìn)，歸約-歸約沖突；SLR（1）在有歸約-歸約沖突，歸約-移進(jìn)沖突，需要看向前搜索一次，求歸約項目產(chǎn)生式左部非終結(jié)符號的Follow集，有些沖突解決不了，因為這種方法只注意到歸約之后該非結(jié)符號后面可以跟的符號，不考慮歸約后能否構(gòu)成規(guī)范句型。

LR（1）分析法通過求超前搜索符號，歸約的時候看超前搜索符號，能夠保證每次歸約之后棧里面的符號串是規(guī)范句型的活前綴。這種分析方法的取得，不是教師通過講課學(xué)生掌握的，是學(xué)生通過查閱資料分析討論主動建構(gòu)得到的，這就是研究性自主學(xué)習(xí)的過程，即PBL教學(xué)方法的重現(xiàn)。把科研的思路應(yīng)用到具體的教學(xué)環(huán)節(jié)中，學(xué)生們主動思考、主動討論、主動掌握知識。

（五）自我思考

在這個階段教師要對學(xué)生所做的工作進(jìn)行歸納總結(jié)，根據(jù)需要進(jìn)行補充。最后組織學(xué)生對本次學(xué)習(xí)過程進(jìn)行有意識的總結(jié)和反思。例如LR分析法學(xué)完之后讓學(xué)生大膽思考，考慮當(dāng)前的有限自動機(jī)跟詞法分析過程中有限自動機(jī)之間的聯(lián)系，能不能先構(gòu)造非確定化的有限自動機(jī)再對其進(jìn)行確定化，確定化的方法跟以前詞法分析一樣還是不一樣，詞法分析與語法分析的銜接之處。這種反思有利于發(fā)展學(xué)生的高層次思維能力。

四、結(jié)束語

根據(jù)編譯原理課程教學(xué)特點：抽象、邏輯性強(qiáng)，知識點多、算法復(fù)雜。學(xué)生學(xué)習(xí)狀態(tài)一直處于被動獲取知識的方式，教學(xué)效果很不理想。經(jīng)過大膽改革，嘗試采用基于PBL教學(xué)方法，并在編譯原理LR類分析中進(jìn)行了具體應(yīng)用，從問題的提出、分析、討論、知識主動建構(gòu)和自我反思等環(huán)節(jié)進(jìn)行了論述。這種方法非常適合編譯原理教學(xué)過程，相信以后的教學(xué)實踐中能夠取得了較好的教學(xué)效果，提高學(xué)生的主動獲取知識、探索知識、解決實際問題的能力，達(dá)到提升學(xué)生計算思維能力，達(dá)到在計算機(jī)專業(yè)中理想就業(yè)的目的。

［1］周汝雁，張云，韓彥嶺.計算機(jī)專業(yè)課程PBL教學(xué)方法探究與實踐——以“編譯原理”課程為例［J］.工業(yè)和信息化教育，2014（5）：39-43.

［2］馮阿芳.PBL在編譯原理課程教學(xué)中的應(yīng)用研究［J］.哈爾濱職業(yè)技術(shù)學(xué)院學(xué)報，2008（4）：94.

The compilation principle is the most suitable course to exercise the students' computational thinking ability.But at present，the classroom teaching of compiling principle still adopts the traditional teaching way and students are not involved in the classroom.Therefore，the author puts forward an autonomic learning way which centered on problems and takes students as subject，that is the PBL teaching method and applies it to the teaching practice of LR syntax analysis in compiling principle，which has achieved good teaching effect.

compilation principle；problem oriented；LR analysis

G642

A

2096-000X（2016）20-0125-02

徐艷群（1978-），女，陜西韓城人，講師，碩士，研究方向：計算機(jī)應(yīng)用。