編譯原理實(shí)驗(yàn)教學(xué)設(shè)計(jì)

萬新燕 時(shí)招軍

摘要：《編譯原理》課程知識(shí)點(diǎn)多、概念復(fù)雜、理論性強(qiáng)、算法難理解，具有很強(qiáng)的復(fù)雜性與抽象性、與實(shí)際聯(lián)系不緊密等問題。為了探索編譯原理的實(shí)驗(yàn)教學(xué)方法，針對(duì)《編譯原理》課程中的實(shí)驗(yàn)教學(xué)設(shè)計(jì)和分析，通過對(duì)實(shí)驗(yàn)過程的創(chuàng)新性探索，尋找實(shí)驗(yàn)教學(xué)的更優(yōu)方案，加深學(xué)生對(duì)編譯原理的理解。

關(guān)鍵詞：編譯原理；前端；實(shí)驗(yàn)教學(xué)

中圖分類號(hào)：G642.0 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1674-9324（2019）08-0261-02

引言

《編譯原理》作為計(jì)算機(jī)專業(yè)的一門重要專業(yè)課程，是日后深入研究專業(yè)領(lǐng)域知識(shí)的基礎(chǔ)。這門課作為計(jì)算機(jī)科學(xué)與技術(shù)的專業(yè)課，融合了離散數(shù)學(xué)、數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、計(jì)算機(jī)組成原理等多個(gè)學(xué)科的知識(shí)，屬于綜合性與理論性較強(qiáng)的一門課[1]，由于編譯原理課程內(nèi)容的以上特點(diǎn)，目前在實(shí)驗(yàn)教學(xué)中仍存在一些問題。天津工業(yè)大學(xué)崔光宇[2]提出編譯原理課程教學(xué)所存在的問題主要有：學(xué)生對(duì)于課程的認(rèn)識(shí)模糊；編譯原理理論抽象，算法比較復(fù)雜；程序設(shè)計(jì)要求比較高。編譯原理實(shí)驗(yàn)部分若要設(shè)計(jì)制作完整的編譯器，實(shí)驗(yàn)周期長，涉及的模塊較多，各模塊間銜接較復(fù)雜，不易立即看到整體效果。若實(shí)驗(yàn)由各個(gè)同學(xué)獨(dú)自設(shè)計(jì)完成代碼，具有一定難度；若通過小組形式合作完成，一部分同學(xué)易產(chǎn)生依賴思想，寄希望于組內(nèi)其他同學(xué)，如此便達(dá)不到提升對(duì)編譯原理理解的目的[3]。

一、實(shí)驗(yàn)教學(xué)流程設(shè)計(jì)

實(shí)驗(yàn)教學(xué)以構(gòu)建一個(gè)編譯程序前端的過程，進(jìn)行流程設(shè)計(jì)，培養(yǎng)學(xué)生從部分到整體的程序設(shè)計(jì)概念。首先，需要對(duì)讀入的程序進(jìn)行預(yù)處理。去除程序中多余的空格，相繼的若干空格只留一個(gè)作為分界標(biāo)志，以便接下來的分析。

接下來，開始詞法分析。根據(jù)詞法分析規(guī)則設(shè)計(jì)自動(dòng)機(jī)，再將預(yù)處理好的程序運(yùn)用詞法分析的原理逐個(gè)掃描，按照關(guān)鍵字、標(biāo)識(shí)符、常數(shù)、運(yùn)算符、分隔符這五類單詞符號(hào)進(jìn)行分類，生成單詞符號(hào)屬性值與其對(duì)應(yīng)單詞種別碼的二元式。然后，根據(jù)所得到的單詞符號(hào)二元式進(jìn)一步進(jìn)行語法分析，參照表示語法規(guī)則的正則文法設(shè)計(jì)函數(shù)，并運(yùn)用遞歸下降法自上而下進(jìn)行語法分析，依次掃描由詞法分析得到的符號(hào)單元，獲得滿足文法規(guī)則的語法單元。最后，在運(yùn)用遞歸下降法進(jìn)行語法分析的同時(shí)也進(jìn)行語義分析及中間代碼生成。將符合語法規(guī)則的句子翻譯為四元式形式的中間代碼。以上，就是編譯原理實(shí)驗(yàn)設(shè)計(jì)的幾個(gè)關(guān)鍵部分。實(shí)驗(yàn)教學(xué)設(shè)計(jì)中應(yīng)將一個(gè)龐大完整的編譯系統(tǒng)拆分成這樣的模塊，對(duì)每個(gè)模塊進(jìn)行設(shè)計(jì)分析，研究現(xiàn)有源碼的實(shí)現(xiàn)方式，再根據(jù)各模塊具體功能設(shè)計(jì)接口實(shí)現(xiàn)要求，供學(xué)生思考及編程。

（一）詞法分析

編譯時(shí)要經(jīng)過詞法分析識(shí)別出單詞符號(hào)，語法分析生成語法樹，語法樹生成中間代碼，中間代碼才能最終生成目標(biāo)代碼。教學(xué)重點(diǎn)在于鍛煉學(xué)生從理論建模到代碼實(shí)現(xiàn)的能力，特別是從DFA到各個(gè)分支語句的建模與實(shí)現(xiàn)，實(shí)驗(yàn)中應(yīng)引導(dǎo)學(xué)生思考其中的對(duì)應(yīng)關(guān)系及轉(zhuǎn)化過程。首先，讀入源程序，并依次去除多余空格，做好預(yù)處理之后，可以開始詞法分析。該部分實(shí)驗(yàn)的理論教學(xué)路線從正則文法到NFA，再到狀態(tài)轉(zhuǎn)換矩陣，再到DFA及其化簡，將這些理論投入實(shí)驗(yàn)教學(xué)，重點(diǎn)在于讓學(xué)生理解如何繪制狀態(tài)轉(zhuǎn)換圖，以及借助設(shè)計(jì)好的符號(hào)表對(duì)單詞符號(hào)進(jìn)行逐個(gè)識(shí)別的思想，將狀態(tài)轉(zhuǎn)換圖的邏輯算法設(shè)計(jì)出程序，讓學(xué)生對(duì)程序中單詞符號(hào)分類方式有進(jìn)一步的理解。教學(xué)應(yīng)遵循從易到難、循序漸進(jìn)的原則，一開始的詞法分析階段可以先實(shí)現(xiàn)識(shí)別一個(gè)單詞，然后進(jìn)一步實(shí)現(xiàn)一類關(guān)鍵字，再按照關(guān)鍵字、標(biāo)識(shí)符、常數(shù)、運(yùn)算符、分隔符這五類單詞符號(hào)進(jìn)行分類識(shí)別并生成相應(yīng)的二元式。

（二）語法分析

語法分析的主要目的是利用詞法分析所得的單詞符號(hào)二元式進(jìn)一步分析，判斷程序的語法結(jié)構(gòu)是否符合語法規(guī)則。該實(shí)驗(yàn)的重點(diǎn)在于根據(jù)產(chǎn)生式規(guī)則將程序中所讀取的語句結(jié)構(gòu)進(jìn)行推導(dǎo)。教學(xué)中，對(duì)語法分析所使用的理論方法有自上而下分析與自下而上分析，前者需要預(yù)先消除產(chǎn)生式規(guī)則中的左遞歸以及回溯，從而使語法樹唯一，即算法的唯一確定性，例如有LL（1）分析法；而后者需要借助符號(hào)棧進(jìn)行歸約操作，重點(diǎn)在于判斷棧頂有無句柄以及句柄的長度，例如算符優(yōu)先分析法、LR分析法等。

其中LL（1）分析法根據(jù)語法規(guī)則構(gòu)造出預(yù)測分析表，并利用棧的數(shù)據(jù)結(jié)構(gòu)，通過將待識(shí)別的符號(hào)單元依次入棧，并結(jié)合預(yù)測分析表在合適的時(shí)機(jī)彈出棧，獲取語法分析所得的匹配結(jié)果。其重點(diǎn)在于深化學(xué)生對(duì)棧這種數(shù)據(jù)結(jié)構(gòu)的理解，以及將其靈活應(yīng)用于語法分析的匹配識(shí)別過程中。

其中遞歸下降法在實(shí)驗(yàn)教學(xué)設(shè)計(jì)中雖然從理論上需消除產(chǎn)生式規(guī)則的左遞歸及回溯，但在代碼實(shí)現(xiàn)的過程中利用遞歸的特點(diǎn)設(shè)計(jì)，可使用改寫文法的技巧，優(yōu)化算法進(jìn)行實(shí)現(xiàn)。在遞歸下降法過程中可根據(jù)不同語法規(guī)則設(shè)計(jì)出各個(gè)規(guī)則對(duì)應(yīng)的接口，即將上一步詞法分析程序作為語法分析的一個(gè)功能函數(shù)，所得出的各類單詞符號(hào)二元式又作為語法分析的最小單元按照語法規(guī)則進(jìn)一步分析，每一類語法規(guī)則又設(shè)計(jì)為一個(gè)函數(shù)單元，進(jìn)行函數(shù)調(diào)用。教學(xué)實(shí)驗(yàn)中，可以給出設(shè)計(jì)好的各函數(shù)接口所需實(shí)現(xiàn)的語法規(guī)則要求，主要包括總流程、Block程序塊、Stmts語句串、Bool邏輯判斷語句、Expr表達(dá)式、Term項(xiàng)、Stmt語句、Factor因子等。根據(jù)語法分析中的多種分析方法也可設(shè)計(jì)不同的功能接口，實(shí)驗(yàn)中讓學(xué)生對(duì)比分析不同接口實(shí)現(xiàn)所用的數(shù)據(jù)結(jié)構(gòu)。讓學(xué)生逐個(gè)進(jìn)行編寫，并替換代入原編譯器代碼中，分析其中原理。

（三）語義分析及中間代碼生成

語義分析及中間代碼生成穿插在語法分析的掃描過程中，對(duì)語法規(guī)則進(jìn)行判斷的同時(shí)生成四元式組。在實(shí)驗(yàn)教學(xué)中，此部分實(shí)驗(yàn)教學(xué)的重點(diǎn)在于對(duì)程序擴(kuò)充能力的培養(yǎng)，指導(dǎo)學(xué)生在上一步遞歸下降法所設(shè)計(jì)的代碼中穿插四元式的生成以及嵌入地址跳轉(zhuǎn)的拉鏈回填技術(shù)。由于對(duì)語法單元只能從前往后依次掃描，逐步生成四元式，所以此過程的實(shí)現(xiàn)在選擇、循環(huán)結(jié)構(gòu)中需根據(jù)實(shí)際情況，把部分跳轉(zhuǎn)地址暫時(shí)留空，直到向后掃描到相應(yīng)位置，再把所得地址回填。此模塊可將生成四元式的功能作為單獨(dú)接口，設(shè)計(jì)所需參數(shù)讓學(xué)生進(jìn)行實(shí)驗(yàn)分析，并引導(dǎo)學(xué)生思考應(yīng)在哪些位置對(duì)四元式生成的接口進(jìn)行調(diào)用。

二、實(shí)驗(yàn)教學(xué)改進(jìn)措施

1.實(shí)驗(yàn)前，應(yīng)督促學(xué)生做好預(yù)習(xí)，根據(jù)所學(xué)理論進(jìn)一步思考，結(jié)合實(shí)驗(yàn)所給的模塊接口要求，設(shè)計(jì)各個(gè)模塊的算法流程圖及所需的數(shù)據(jù)結(jié)構(gòu)。

2.根據(jù)學(xué)生水平情況，因材施教，無需所有學(xué)生都獨(dú)立構(gòu)造出一個(gè)具體完整的編譯器，而是剖析已有的編譯器源碼，分析各個(gè)部分的實(shí)現(xiàn)策略。

3.可將一個(gè)完整編譯器的各階段功能拆分成各個(gè)小接口，設(shè)計(jì)好對(duì)應(yīng)的輸入輸出參數(shù)及功能實(shí)現(xiàn)要求。通過由學(xué)生自行編寫各個(gè)小接口，嵌入編譯器代碼替換原模塊進(jìn)行測試，這樣無需一次實(shí)現(xiàn)編譯器的全部功能也能及時(shí)進(jìn)行功能實(shí)現(xiàn)的檢測，有利于增強(qiáng)學(xué)生信心，也能及時(shí)獲取實(shí)驗(yàn)情況反饋。

4.每場實(shí)驗(yàn)的代碼實(shí)現(xiàn)任務(wù)完成后，分配一部分時(shí)間供學(xué)生討論遇到的常見問題并分析原因，從而更好地發(fā)現(xiàn)問題、解決問題，收到及時(shí)的教學(xué)效果反饋，有利于為下一堂課的重難點(diǎn)講解和教學(xué)進(jìn)度進(jìn)行補(bǔ)充與調(diào)整。教師可以選取其中一些優(yōu)秀的例子進(jìn)行講解分享，不僅能讓優(yōu)秀的同學(xué)更加開闊思路，也能讓能力較弱的同學(xué)看到自己的不足，使全體學(xué)生都能對(duì)課程的各知識(shí)點(diǎn)有更深入的理解。

5.最重要的是可提升學(xué)生對(duì)編譯原理課程學(xué)習(xí)的興趣，從易到難，循序漸進(jìn)，讓學(xué)生吃透每一個(gè)部分的原理及編碼實(shí)現(xiàn)。

三、結(jié)論

本文主要通過設(shè)計(jì)編譯原理中詞法分析、語法分析、語義分析及中間代碼生成的實(shí)驗(yàn)教學(xué)步驟，將編譯原理課程的理論與實(shí)踐教學(xué)相結(jié)合，對(duì)編譯原理的教學(xué)方式進(jìn)一步探索，對(duì)編譯原理的知識(shí)點(diǎn)進(jìn)行充分實(shí)踐與運(yùn)用。本文所設(shè)計(jì)的教學(xué)實(shí)驗(yàn)，有助于提高學(xué)生對(duì)編譯原理理論知識(shí)的實(shí)踐轉(zhuǎn)化能力，提升學(xué)生對(duì)課程知識(shí)的理解，并進(jìn)一步提高動(dòng)手能力，培養(yǎng)學(xué)生的編程能力，從而達(dá)到提高教學(xué)質(zhì)量的目的。

參考文獻(xiàn)：

[1]丁志軍，周澤霞，衛(wèi)志華.過程可視化類C編譯器的教學(xué)輔助軟件[J].計(jì)算機(jī)與現(xiàn)代化，2017，（6）：34-39.

[2]崔光宇.編譯原理教學(xué)現(xiàn)狀與創(chuàng)新研究[J].無線互聯(lián)科技，2017，（24）：81-82.

[3]曹瓊.淺談編譯原理實(shí)驗(yàn)課程教學(xué)[J].計(jì)算機(jī)教育，2007，（18）：45-46.