編譯原理實驗教學設(shè)計

萬新燕 時招軍

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

關(guān)鍵詞：編譯原理；前端；實驗教學

中圖分類號：G642.0 文獻標志碼：A 文章編號：1674-9324（2019）08-0261-02

引言

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

一、實驗教學流程設(shè)計

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

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

（一）詞法分析

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

（二）語法分析

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

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

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

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

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

二、實驗教學改進措施

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

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

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

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

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

三、結(jié)論

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

參考文獻：

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

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

[3]曹瓊.淺談編譯原理實驗課程教學[J].計算機教育，2007，（18）：45-46.