編譯原理課程教學(xué)之思考

摘要：結(jié)合編譯原理課程教學(xué)工作，從課程特點(diǎn)、教學(xué)內(nèi)容的合理取舍、語法和語義分析等難點(diǎn)內(nèi)容的講授方式、實(shí)驗(yàn)內(nèi)容的設(shè)計(jì)等方面進(jìn)行深入探討，對(duì)教學(xué)過程進(jìn)行總結(jié)，講述如何提高教學(xué)質(zhì)量。

關(guān)鍵詞：編譯原理；課程內(nèi)容；實(shí)驗(yàn)環(huán)節(jié)

文章編號(hào)：1672-5913（2013）18-0066-03

中圖分類號(hào)：G642

0 引言

編譯原理是計(jì)算機(jī)專業(yè)本科生的重要核心課程，通常開設(shè)在大學(xué)3年級(jí)。編譯器是計(jì)算機(jī)3大系統(tǒng)軟件之一，其構(gòu)造原理和技術(shù)是計(jì)算機(jī)科學(xué)技術(shù)領(lǐng)域的重要組成部分。雖然絕大多數(shù)計(jì)算機(jī)專業(yè)學(xué)生未來不可能去構(gòu)造或維護(hù)一個(gè)主流程序設(shè)計(jì)語言的編譯器，但與編譯原理相關(guān)的模型、理論和算法可以用在多種應(yīng)用領(lǐng)域，將對(duì)研究開發(fā)產(chǎn)生有益的影響。學(xué)習(xí)該課程可以培養(yǎng)學(xué)生抽象思維、獨(dú)立解決復(fù)雜問題、編程和調(diào)試等涉及多門專業(yè)課程知識(shí)的綜合應(yīng)用能力。

編譯原理課程內(nèi)容抽象、理論性強(qiáng)、形式化方法不易理解，對(duì)學(xué)生編程實(shí)踐有較高的要求。對(duì)于教師而言，如何在有限的學(xué)時(shí)內(nèi)優(yōu)化教學(xué)內(nèi)容，合理安排實(shí)驗(yàn)環(huán)節(jié)，是值得探討的問題。

1 課程特點(diǎn)

編譯領(lǐng)域里的經(jīng)典教材作者Alfred V.Aho認(rèn)為編寫編譯器的原理和技術(shù)還可以用于編譯器設(shè)計(jì)之外的眾多領(lǐng)域，這些原理和技術(shù)通常會(huì)在一個(gè)計(jì)算機(jī)科學(xué)家的職業(yè)生涯中多次被用到。這句話給出了編譯原理課程的教學(xué)定位——兼具理論與實(shí)踐兩方面的高要求。

編譯器構(gòu)造各階段的工作均有其抽象理論基礎(chǔ)，涉及多種數(shù)學(xué)模型，詞法分析階段涉及正則表達(dá)式與有窮狀態(tài)自動(dòng)機(jī)理論；語法分析階段涉及上下文無關(guān)文法；語義分析階段涉及屬性文法、類型系統(tǒng)；而樹形結(jié)構(gòu)是表示程序語法結(jié)構(gòu)以及源程序到中間代碼翻譯的重要模型。編譯器中的算法研究同樣重要，必須考慮算法的功能、通用性，其中語法分析階段的算法最為典型，依次引入了一系列算法。而編譯器開發(fā)的實(shí)踐性強(qiáng)，需要學(xué)生實(shí)際動(dòng)手實(shí)現(xiàn)一個(gè)規(guī)模較大的編譯器，這本身是一個(gè)較復(fù)雜的軟件工程項(xiàng)目，必須考慮子模塊劃分、模塊之間信息傳遞、算法效率、編譯器構(gòu)造自動(dòng)工具等多方面因素。

編譯原理融合多門專業(yè)課程，包括來自于計(jì)算機(jī)科學(xué)不同領(lǐng)域的思想，如高級(jí)語言程序設(shè)計(jì)、形式語言與自動(dòng)機(jī)理論、數(shù)據(jù)結(jié)構(gòu)中樹及圖形算法；操作系統(tǒng)中存儲(chǔ)分配方式、人工智能中的貪婪算法、啟發(fā)式搜索技術(shù)；匯編指令系統(tǒng)等。編譯原理和高級(jí)語言程序設(shè)計(jì)聯(lián)系緊密，學(xué)好該門課程有利于學(xué)生對(duì)程序設(shè)計(jì)語言的理解，可以迅速掌握新的語言工具，在遇到新的程序語言時(shí)，學(xué)生不會(huì)因?yàn)闆]有學(xué)過某一門語言而無從人手，這對(duì)學(xué)生今后從事軟件開發(fā)工作有重要價(jià)值。編譯原理課程蘊(yùn)含著計(jì)算機(jī)學(xué)科中解決問題的思路和方法。學(xué)習(xí)編譯原理課程，不僅要學(xué)習(xí)如何構(gòu)造編譯器，還要學(xué)習(xí)解決復(fù)雜和開放性問題的一般方法，從中接受的思維訓(xùn)練將會(huì)在今后的學(xué)習(xí)、工作中逐漸體現(xiàn)其價(jià)值。

2 合理安排課程內(nèi)容，突出重點(diǎn)，注重方法

廈門大學(xué)計(jì)算機(jī)科學(xué)系的編譯原理課程歷年采用經(jīng)典編譯教材“編譯原理、技術(shù)與工具”，其中講解的核心編譯原理是教學(xué)內(nèi)容的重要部分，包括詞法分析、語法分析、語義分析、中間代碼生成以及運(yùn)行時(shí)環(huán)境、優(yōu)化和代碼生成方法的基本技術(shù)，教材中對(duì)編譯前端的技術(shù)進(jìn)行了詳細(xì)的闡述，但在一個(gè)學(xué)期60～64學(xué)時(shí)課堂講授中，往往無法詳盡地介紹所有內(nèi)容，需要突出重點(diǎn)，對(duì)某些章節(jié)適當(dāng)選擇。

例如，運(yùn)行時(shí)環(huán)境中有關(guān)源程序語言相關(guān)問題的討論、非局部命名的訪問、參數(shù)傳遞等高級(jí)程序語言設(shè)計(jì)可略講，向?qū)W生列舉這些技術(shù)在哪些相關(guān)課程、書籍或文獻(xiàn)中找到參考，拓寬學(xué)生思路，培養(yǎng)其自學(xué)能力。代碼生成、代碼優(yōu)化等編譯器后端技術(shù)限于學(xué)時(shí)數(shù)，往往涉及甚少，匆匆?guī)н^。而這一部分內(nèi)容對(duì)于編譯器構(gòu)造十分重要，關(guān)系到生成代碼的質(zhì)量，也是現(xiàn)代編譯技術(shù)的研究重點(diǎn)。在教學(xué)中可介紹代碼優(yōu)化的主要來源、幾種經(jīng)典的優(yōu)化方法，優(yōu)化的主要數(shù)據(jù)結(jié)構(gòu)和實(shí)現(xiàn)技術(shù)，讓學(xué)生對(duì)這部分知識(shí)有所了解，便于將來深入學(xué)習(xí)。

又如，語法分析方法是編譯教學(xué)的重點(diǎn)，詳細(xì)介紹自頂向下分析和自底向上分析，LR分析中有LR（0）、SLR、LR（1）、LALR不同方法，若拘泥于教材逐一講授，學(xué)生較難接受，沒有頭緒。教師注重講授方法，在講解過程中不斷提出問題，尋求解決技術(shù)及其背后的原理。在語法分析講授中先介紹遞歸子程序法，可以用該方法編寫某些語法的語法分析器，但這必須對(duì)于每個(gè)文法手工編寫相應(yīng)的編譯程序，教師提出是否可以找到非遞歸的自動(dòng)生成語法分析器的方法問題，由此引出LL（1）分析方法。進(jìn)一步提出LL（1）分析方法適應(yīng)的文法是有限定的，是否有更普遍適用的分析方法問題，由此引出自底向上的LR分析方法，從SLR、LR（1）到LALR方法，每一種分析方法的引入相互關(guān)聯(lián)。這一方法能夠保證語法分析這一要點(diǎn)有清晰的脈絡(luò)貫穿，讓學(xué)生能把握這一主線。

語法制導(dǎo)定義及翻譯方案的設(shè)計(jì)是教學(xué)的重點(diǎn)和難點(diǎn)，也是學(xué)生學(xué)習(xí)中反映困難最大的內(nèi)容。因?yàn)樗鼪]有普適的一般方法，本質(zhì)上是一種事件驅(qū)動(dòng)的程序設(shè)計(jì)，這對(duì)于3、4年級(jí)的本科生較難掌握。如何把握課程難點(diǎn)的講授，值得深入探討。這一部分內(nèi)容教師采用“歸納法”，在講解過程中圍繞語義描述和計(jì)算問題，結(jié)合具體實(shí)例尋求解決技術(shù)，闡述語法制導(dǎo)定義和翻譯的作用，強(qiáng)調(diào)這些技術(shù)將運(yùn)用于解決類型分析和中間代碼生成的語義問題?？梢詫⒄Z義規(guī)則求值方法歸納為4點(diǎn)：

（1）由下向上計(jì)算S屬性定義：用帶屬性值的語法分析棧實(shí)現(xiàn)；

（2）由上向下計(jì)算L屬性定義：消除左遞歸后引入繼承屬性，擴(kuò)充遞歸的語法分析器，可以實(shí)現(xiàn)預(yù)測(cè)翻譯器；

（3）由下向上計(jì)算繼承屬性：用加標(biāo)記非終結(jié)符的方法，使得嵌入產(chǎn)生式右部的語義動(dòng)作全部出現(xiàn)在產(chǎn)生式末尾，從而能在歸約之前執(zhí)行語義動(dòng)作；

（4）遍歷分析樹的翻譯方法，上述3種翻譯方法均和語法分析同時(shí)進(jìn)行，但不是所有的SDD都能在語法分析同時(shí)完成，給出一般化的求值方法，先建立帶語義動(dòng)作的語法分析樹，后遍歷執(zhí)行語義動(dòng)作，要求屬性依賴關(guān)系圖無環(huán)。

這一講解方法能更好地幫助學(xué)生理解抽象的問題，提高分析和綜合能力。

3 精心設(shè)計(jì)實(shí)踐環(huán)節(jié)

編譯原理是實(shí)踐性很強(qiáng)的課程，要真正理解編譯系統(tǒng)，單純依靠課堂講解理論知識(shí)是不夠的。實(shí)驗(yàn)課程是培養(yǎng)學(xué)生實(shí)踐能力，鞏固和驗(yàn)證所學(xué)理論知識(shí)，培養(yǎng)學(xué)生分析問題、解決問題能力的重要環(huán)節(jié)。通過實(shí)驗(yàn)環(huán)節(jié)，使學(xué)生對(duì)編譯程序各功能部分間的接口有更好地理解，對(duì)算法的實(shí)現(xiàn)細(xì)節(jié)更明了。

在理想的情況下，完成一個(gè)完整的編譯系統(tǒng)構(gòu)造，從詞法分析到目標(biāo)代碼生成，直至匯編程序的執(zhí)行，這有助于真正理解整個(gè)編譯過程，以及系統(tǒng)的運(yùn)行過程。但在實(shí)際教學(xué)過程中，限于課時(shí)安排，實(shí)驗(yàn)課和課堂講授同步進(jìn)行，通常只能完成到中間代碼生成階段。編譯程序構(gòu)造是復(fù)雜的程序開發(fā)，不可能在課堂教學(xué)中把所有細(xì)節(jié)講清楚，學(xué)生往往難以人手，在有限的時(shí)間內(nèi)，實(shí)驗(yàn)的效果不好。為了達(dá)到好的實(shí)驗(yàn)效果，促進(jìn)學(xué)生對(duì)編譯原理的理解，教師從以下幾個(gè)方面開展實(shí)驗(yàn)環(huán)節(jié)教學(xué)實(shí)踐：

（1）注重自動(dòng)工具的使用。利用kex/Yacc編譯器自動(dòng)生成工具，先實(shí)現(xiàn)簡(jiǎn)單的程序（如算術(shù)表達(dá)式的轉(zhuǎn)換/求值、HTML文件轉(zhuǎn)化成純文本文件、C源程序格式化轉(zhuǎn)化），所需知識(shí)限于正則表達(dá)式和自動(dòng)生成工具本身的使用方法，對(duì)語義分析知識(shí)要求較少，可以提供相關(guān)的資料和網(wǎng)上相關(guān)教程，學(xué)生易于入手。目的是使學(xué)生體會(huì)到編譯原理的實(shí)用性，提高學(xué)習(xí)興趣，并獲得編譯器自動(dòng)生成工具的使用經(jīng)驗(yàn)，提高解決實(shí)際問題的能力。

（2）分階段進(jìn)行實(shí)驗(yàn)。根據(jù)課程的特點(diǎn)和大綱的要求，可以設(shè)置4個(gè)階段的實(shí)驗(yàn)內(nèi)容，詞法分析器的設(shè)計(jì)實(shí)現(xiàn)、由上向下遞歸下降分析器的設(shè)計(jì)實(shí)現(xiàn)、利用工具生成的自底向上語法分析器、語義分析和中間代碼生成器的設(shè)計(jì)實(shí)現(xiàn)。每個(gè)階段需要利用之前得到的實(shí)驗(yàn)成果，逐步完成編譯器系統(tǒng)的構(gòu)造，通過明確的階段劃分，接口的定義，提高編譯原理實(shí)驗(yàn)的完成質(zhì)量。

（3）提供編譯器源代碼。編譯器構(gòu)造是一個(gè)具有相當(dāng)規(guī)模和相當(dāng)復(fù)雜度的系統(tǒng)，對(duì)于本科學(xué)生獨(dú)立動(dòng)手編寫小型語言的編譯器是有難度的。為了幫助學(xué)生掌握，結(jié)合一個(gè)小型語言編譯器構(gòu)造的完整實(shí)例，提供編譯器構(gòu)造的源代碼，要求學(xué)生對(duì)源代碼進(jìn)行分析、擴(kuò)充和改造，有助于學(xué)生的理解和掌握編譯原理的構(gòu)造技術(shù)。例如Alfred Aho著的“編譯原理（第2版）”和“編譯原理（本科教學(xué)版）”附錄均給出了一個(gè)用Java語言實(shí)現(xiàn)的完整的編譯器前端，包括：源語言的文法描述、詞法分析器、語法分析器、符號(hào)表和類型、表達(dá)式的中間代碼、布xGT1aYGzCCzvU6NlgsCgNw==爾表達(dá)式的跳轉(zhuǎn)代碼、控制流語句的中間代碼，實(shí)現(xiàn)源程序到等價(jià)中間代碼的轉(zhuǎn)換。Kenneth C，Louden編著的“編譯原理與實(shí)踐”以Tiny語言編譯程序作為范例，結(jié)合各章內(nèi)容講解Tiny語言編譯程序中的相關(guān)部分的實(shí)現(xiàn)方法。

4 對(duì)課程發(fā)展的思考

為培養(yǎng)高素質(zhì)的計(jì)算機(jī)專業(yè)人才，重視軟件開發(fā)能力的培養(yǎng)至關(guān)重要。在編譯原理課程中強(qiáng)調(diào)理論知識(shí)的綜合應(yīng)用和編程實(shí)踐能力的訓(xùn)練，要求學(xué)生針對(duì)特定語言（如C語言的子集），從文法出發(fā)，設(shè)計(jì)一個(gè)編譯器構(gòu)造方案，并以此為基礎(chǔ)開發(fā)滿足要求的編譯器，將其看作軟件開發(fā)的綜合訓(xùn)練的重要一環(huán)。

編譯原理課程的實(shí)踐是在理論基礎(chǔ)知識(shí)的指導(dǎo)下進(jìn)行。學(xué)生在學(xué)習(xí)基本理論后進(jìn)行實(shí)驗(yàn)系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)；教師在掌握系統(tǒng)總體構(gòu)成和基本原理、方法的基礎(chǔ)上提出實(shí)驗(yàn)的基本要求。鼓勵(lì)學(xué)生選擇適當(dāng)?shù)姆椒ㄟM(jìn)行系統(tǒng)設(shè)計(jì)，包括選擇自動(dòng)化生成方法。為實(shí)現(xiàn)相應(yīng)效果，要求學(xué)生在每個(gè)實(shí)驗(yàn)之前應(yīng)完成設(shè)計(jì)、描述解決方法并給出算法、編寫出源程序、給出測(cè)試實(shí)例，實(shí)驗(yàn)完成后要求提交。學(xué)生對(duì)編譯課程內(nèi)容積極投入，絕大多數(shù)學(xué)生都能夠在有限時(shí)間內(nèi)獨(dú)立完成詞法分析和語法分析的實(shí)驗(yàn)，較優(yōu)秀的學(xué)生能夠獨(dú)立完成中間代碼生成的實(shí)驗(yàn)。

在教學(xué)過程中也發(fā)現(xiàn)了一些不足，編譯原理的教學(xué)和實(shí)驗(yàn)對(duì)后端工作不夠深入，尤其是實(shí)驗(yàn)，往往到中間代碼生成階段已經(jīng)接近學(xué)期末，目標(biāo)代碼（匯編代碼）生成、寄存器分配、優(yōu)化等沒有充分時(shí)間進(jìn)行，對(duì)綜合運(yùn)用C語言、計(jì)算機(jī)組成原理、匯編等知識(shí)鍛煉不夠。

5 結(jié)語

正所謂“教學(xué)相長(zhǎng)”，提高編譯原理課程教學(xué)質(zhì)量，需要教學(xué)雙方的共同努力，互相促進(jìn)。對(duì)學(xué)生而言，要提高自身學(xué)習(xí)積極性，敢于提出問題、解決問題；對(duì)教師而言，在講授知識(shí)的同時(shí)，要注重學(xué)生能力的培養(yǎng)，激發(fā)學(xué)生的學(xué)習(xí)興趣，充實(shí)教學(xué)內(nèi)容，提升教學(xué)質(zhì)量，在教學(xué)實(shí)踐中不斷思考、探索、實(shí)踐和總結(jié)。

參考文獻(xiàn)：

[1]Aho A，Sethi R'Ullman J D.編譯原理[M]，趙建華，譯，2版。北京：機(jī)械工業(yè)出版社，2009

[2]張昱，陳意云，鄭啟龍，編譯原理課程的教學(xué)方法和教材建設(shè)[J]，中國(guó)大學(xué)教育，2005（7）：61-62

[3]Aho A，Sethi R，Ullman J D.編譯原理[M]，趙建華，譯，本科教學(xué)版，北京：機(jī)械工業(yè)出版社，2009

[4]Louden K C.編譯原理與實(shí)踐[M]，馮博琴，馮嵐，譯，北京：機(jī)械工業(yè)出版社，2001：373-380

（編輯：趙廓）