王中卿　朱培培

摘要：《編譯原理》作為計(jì)算機(jī)專業(yè)一門重要的專業(yè)課，理論性強(qiáng)且較為抽象。實(shí)踐教學(xué)可以輔助理論教學(xué)，訓(xùn)練學(xué)生思維，加強(qiáng)學(xué)生對(duì)理論知識(shí)的深度了解及設(shè)計(jì)編譯程序的能力。針對(duì)現(xiàn)有實(shí)踐教學(xué)體系的問(wèn)題，在編譯原理核心算法和編澤器的設(shè)計(jì)兩方面，分別對(duì)教學(xué)內(nèi)容及實(shí)踐難度進(jìn)行了層次化創(chuàng)新，從而對(duì)學(xué)生進(jìn)行步步引導(dǎo)，提高編譯原理的教學(xué)質(zhì)量。

關(guān)鍵詞：編譯原理;實(shí)踐教學(xué);詞法分析;語(yǔ)法分析;語(yǔ)法制導(dǎo)翻譯

中圖分類號(hào)：C642 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2020）20-0158-02

Hierarchical and Precise Experiment Teaching of Principle Practical

WANG Zhong-qing， ZHU Pei-pei

（School of Computer Science and 'l'echnology， Soochow U niversity， Suzhou 215006， China）

Abstract： As an important professional course for computer maj ors，¨ C ompilation Principle "is highly theoretical and abstract. Practi-cal teaching can assist theoretical teaching， train students' thinking， and strengthen students' deep understanding of theoreticalknowledge and the ability to design compilers. Aiming at the problems of the existing practical teaching system， this paper makesthe teaching content and practice difficulty hierarchical in two aspects： the compilation principle core algorithms and compiler de-sign， so as to guide students step hy step and improve the teaching quality of compilation principle.

Key words： compilation principle; practical teaching; lexical analysis; grammatical analysis; grammatical guidance translation

1引言

編譯原理課程是高校計(jì)算機(jī)及信息類相關(guān)專業(yè)的基礎(chǔ)及核心課程，該課程涵蓋數(shù)據(jù)結(jié)構(gòu)、算法等多方面的知識(shí)，有著很強(qiáng)的邏輯推理性和高度概括的抽象性，同時(shí)也將實(shí)踐和理論高度結(jié)合[1]，是計(jì)算機(jī)專業(yè)課中最具有挑戰(zhàn)力的課程之一，在語(yǔ)言處理、軟件工程、軟件自動(dòng)化等諸多領(lǐng)域有著廣泛的應(yīng)用[2]。在編譯原理理論教學(xué)中有限自動(dòng)機(jī)、語(yǔ)法制導(dǎo)等知識(shí)都比較抽象，理解難度較大，學(xué)生只能片面的了解編譯器的相關(guān)知識(shí)，且難以運(yùn)用。其次理論教學(xué)模式單一，很難激起學(xué)生的學(xué)習(xí)興趣，影響學(xué)生創(chuàng)新和創(chuàng)造思維的發(fā)展，因此衍生了一系列改革理論教學(xué)的方法[3-4]。本文認(rèn)為理論教學(xué)還需要借助實(shí)踐課程來(lái)幫助學(xué)生進(jìn)一步熟悉編譯原理技術(shù)，培養(yǎng)設(shè)計(jì)實(shí)現(xiàn)編譯程序等能力。

編譯原理的實(shí)踐教學(xué)可以分為兩個(gè)方面：一方面是編譯原理相關(guān)算法的實(shí)踐[5]，包括詞法分析部分的MYT算法和子集構(gòu)造法，語(yǔ)法分析部分的LL文法和LR文法等;另外一方面是編譯器的設(shè)計(jì)[6-7]，包括從詞法分析到語(yǔ)法制導(dǎo)翻譯的整個(gè)流程，以及每一個(gè)模塊的設(shè)計(jì)。兩部分是相輔相成的，編譯原理相關(guān)算法的實(shí)現(xiàn)是整個(gè)編譯器設(shè)計(jì)的基礎(chǔ)，而編譯器的設(shè)計(jì)又可以幫助理解編譯原理中的每個(gè)算法的思想。以往的相關(guān)實(shí)踐教學(xué)研究多偏重于其中一方面的教學(xué)，而這兩方面對(duì)于編譯原理實(shí)踐課都很重要[8]，本文將分別從這兩個(gè)方面介紹層次化編譯原理實(shí)踐課的具體設(shè)計(jì)方案。

2編譯原理核心算法的實(shí)現(xiàn)

本節(jié)著重介紹編譯原理核心算法的實(shí)現(xiàn)，相關(guān)算法主要集中于詞法分析與語(yǔ)法分析部分。

2.1詞法分析的實(shí)驗(yàn)設(shè)計(jì)

在詞法分析部分，著重于分析如何將正則表達(dá)式轉(zhuǎn)換為自動(dòng)機(jī)，具體包含三方面的內(nèi)容：正則表達(dá)式的應(yīng)用，從正則表達(dá)式到不確定的有限自動(dòng)機(jī)（NFA）的實(shí)現(xiàn)（MYT算法），從不確定的有限自動(dòng)機(jī)（NFA）到確定的有限自動(dòng)機(jī)（DFA）的實(shí)現(xiàn)（子集構(gòu)造法）。

首先設(shè)計(jì)簡(jiǎn)單實(shí)驗(yàn)讓學(xué)生熟悉編程語(yǔ)言的環(huán)境，了解正則表達(dá)式的基本用法，例如匹配日期，提取超鏈接，提取文檔標(biāo)題與正文等。進(jìn)一步的可設(shè)計(jì)實(shí)驗(yàn)利用正則表達(dá)式進(jìn)行LaTex源文件解析，從而提高學(xué)生的學(xué)習(xí)興趣，讓學(xué)生了解正則表達(dá)式如何與編譯原理結(jié)合。

熟悉正則表達(dá)式之后，可設(shè)計(jì)實(shí)驗(yàn)基于MYT算法將正則表達(dá)式轉(zhuǎn)換為對(duì)應(yīng)的NFA狀態(tài)轉(zhuǎn)換表。實(shí)驗(yàn)中可以給出識(shí)別字母表中一個(gè)字符、主運(yùn)算符為閉包正則式的NFA狀態(tài)轉(zhuǎn)換表的構(gòu)建，讓學(xué)生以此為例，實(shí)現(xiàn)主運(yùn)算符為選擇，連接等正則式的NFA狀態(tài)轉(zhuǎn)換表的構(gòu)建。

最后設(shè)計(jì)基于子集構(gòu)造法的實(shí)驗(yàn)將NFA狀態(tài)轉(zhuǎn)換表轉(zhuǎn)換成對(duì)應(yīng)的DFA狀態(tài)轉(zhuǎn)換表，其中主要讓學(xué)生實(shí)現(xiàn)ε-closure（S）、ε-closure（T）和move（T，a）函數(shù)，及驗(yàn)證一個(gè)字符串是否能夠被DFA接受，從而提高學(xué)生對(duì)于從NFA到DFA轉(zhuǎn)換的理解。

2.2語(yǔ)法分析的實(shí)驗(yàn)設(shè)計(jì)

在語(yǔ)法分析部分，由于計(jì)算機(jī)主要是基于自下而上的方式進(jìn)行語(yǔ)法分析，因此主要要求學(xué)生實(shí)現(xiàn)兩個(gè)自下而上的語(yǔ)法分析算法：CYK算法和SLR語(yǔ)法分析方法。該部分的實(shí)驗(yàn)有助于學(xué)生開(kāi)拓算法知識(shí)，提高運(yùn)用不同方法解決問(wèn)題的能力。

CYK算法是一個(gè)基于動(dòng)態(tài)規(guī)劃思想，用于測(cè)試串w對(duì)于一個(gè)上下文無(wú)關(guān)文法L的成員性的一個(gè)算法。該算法采用并行算法，用逐次推進(jìn)的辦法獲得最優(yōu)的結(jié)構(gòu)，學(xué)生要定義語(yǔ)法規(guī)則并計(jì)算相關(guān)概率推算最可能的句子結(jié)構(gòu)。

SLR語(yǔ)法分析方法由從左向右處理輸入字符串，遵循最右邊優(yōu)先派生的推導(dǎo)順序，并解決相關(guān)沖突，該實(shí)驗(yàn)要求學(xué)生構(gòu)建SLR文法的可行前綴的DFA。

3編譯器的設(shè)計(jì)與實(shí)現(xiàn)

本節(jié)著重介紹編譯器的設(shè)計(jì)與實(shí)現(xiàn)過(guò)程中涉及的相關(guān)模塊的實(shí)現(xiàn)。整個(gè)實(shí)現(xiàn)過(guò)程需要利用編譯器構(gòu)建工具PLY（Py-thon Lex-Yacc），該工具已經(jīng)封裝了基本的詞法分析與語(yǔ)法分析模塊，基于PLY能夠使學(xué)生很快的構(gòu)建相關(guān)的編譯器模塊。

為了能夠更好地進(jìn)行編譯器的設(shè)計(jì)與實(shí)現(xiàn)，本文將整個(gè)實(shí)現(xiàn)過(guò)程分為兩個(gè)部分：一是對(duì)于一些簡(jiǎn)單的語(yǔ)法處理器的實(shí)現(xiàn)，二是構(gòu)建一個(gè)完整的基于程序設(shè)計(jì)語(yǔ)言的編譯器。在下面的小節(jié)將分別進(jìn)行描述。

3.1簡(jiǎn)單的語(yǔ)法處理器的實(shí)驗(yàn)設(shè)計(jì)

為了讓學(xué)生能夠?qū)幾g器有一個(gè)形象的理解，首先讓學(xué)生構(gòu)建一些簡(jiǎn)單的語(yǔ)法處理器，包括：化學(xué)表達(dá)式的解析，SQL語(yǔ)言的解析和LaTex源文件的解析。這些實(shí)驗(yàn)循序漸進(jìn)，從簡(jiǎn)單到復(fù)雜，可以讓學(xué)生熟悉PLY工具，理解詞法分析模塊（lex）如何與語(yǔ)法分析模塊（yacc）聯(lián)系在一起、如何定義沒(méi)有二義性的語(yǔ)法規(guī)則以及如何處理移進(jìn)和歸約沖突。

1）化學(xué)表達(dá)式的解析

化學(xué)分子式的解析主要為了考察學(xué)生對(duì)于單個(gè)語(yǔ)法單元的解析?；瘜W(xué)分子式由元素符號(hào)和數(shù)字組成，本實(shí)驗(yàn)要求學(xué)生計(jì)算化學(xué)分子式中元素的數(shù)目，例如“H2S04”中元素的數(shù)目為7。

2）SQL語(yǔ)言的解析

SQL語(yǔ)言的解析主要考察學(xué)生對(duì)于單行語(yǔ)句的解析。首先讓學(xué)生熟悉示例程序中的解析SQL語(yǔ)言的程序，然后讓學(xué)生擴(kuò)展示例程序中的語(yǔ)法，使其能完全適應(yīng)SQL查詢語(yǔ)句，并完成相關(guān)SQL文件的查詢（包括，where、order by、group等）。該實(shí)驗(yàn)要求學(xué)生寫出相應(yīng)的正則式提取及語(yǔ)法規(guī)則的定義。

3）LaTex源文件的解析

LaTex源文件的解析主要是考察學(xué)生對(duì)于多行語(yǔ)句的解析。該實(shí)驗(yàn)需要學(xué)生定義LaTex中各個(gè)標(biāo)簽的語(yǔ)法規(guī)則，輸出相應(yīng)的語(yǔ)法樹(shù)，并轉(zhuǎn)化為PDF格式。語(yǔ)法分析中會(huì)運(yùn)用到遞歸思想，能鍛煉學(xué)生的邏輯思維能力，且該實(shí)驗(yàn)?zāi)芗訌?qiáng)學(xué)生對(duì)La-Tex文本的認(rèn)識(shí)。

3.2基于Python--的編譯器的實(shí)驗(yàn)設(shè)計(jì)

當(dāng)學(xué)生實(shí)現(xiàn)了上述簡(jiǎn)單的語(yǔ)法處理器之后，本節(jié)將繼續(xù)指導(dǎo)學(xué)生實(shí)現(xiàn)一個(gè)基于Python——語(yǔ)法的編譯器。所謂Python——是指一個(gè)比Python更簡(jiǎn)單的程序設(shè)計(jì)語(yǔ)言。整個(gè)編譯器的實(shí)現(xiàn)包括：賦值語(yǔ)句，輸出語(yǔ)句，條件與循環(huán)語(yǔ)句，函數(shù)，類的實(shí)現(xiàn)等。

首先需要實(shí)現(xiàn)的是簡(jiǎn)單四則運(yùn)算的程序，例如c=a+b，其中包括賦值語(yǔ)句和輸出語(yǔ)句，該實(shí)驗(yàn)要求學(xué)生先構(gòu)造語(yǔ)法樹(shù)，然后為每一條Python語(yǔ)句所對(duì)應(yīng)的語(yǔ)法樹(shù)結(jié)點(diǎn)沒(méi)置一個(gè)屬性并為每一個(gè)產(chǎn)生式實(shí)現(xiàn)語(yǔ)法制導(dǎo)翻譯。

其次是實(shí)現(xiàn)循環(huán)與條件語(yǔ)句的解析，包括while，for，if等語(yǔ)句。并基于這些語(yǔ)句實(shí)現(xiàn)復(fù)雜的算法的編譯，例如：二分查找和選擇排序，從而幫助學(xué)生不斷優(yōu)化細(xì)節(jié)，使程序具有更好的魯棒性。

然后是函數(shù)的解析，該實(shí)驗(yàn)需要通過(guò)一個(gè)函數(shù)表來(lái)保存每個(gè)函數(shù)的信息，然后通過(guò)函數(shù)表實(shí)現(xiàn)函數(shù)的調(diào)用。在該實(shí)驗(yàn)中，學(xué)生要考慮到函數(shù)定義、函數(shù)調(diào)用、返回語(yǔ)句等的解析與翻譯。

最后就是類的解析，該實(shí)驗(yàn)需要實(shí)現(xiàn)類中變量和函數(shù)的翻譯等，要注意類中成員函數(shù)、成員變量和一般函數(shù)、變量的區(qū)別以及構(gòu)造函數(shù)的解析。

整個(gè)基于Python-語(yǔ)法編譯器的實(shí)現(xiàn)過(guò)程從簡(jiǎn)單的語(yǔ)句到函數(shù)再到類，一步一步指導(dǎo)學(xué)生優(yōu)化Python——語(yǔ)法的體系，幫助學(xué)生熟悉從詞法分析到語(yǔ)法分析再到語(yǔ)法制導(dǎo)翻譯的過(guò)程，有利于培養(yǎng)學(xué)生將理論轉(zhuǎn)化為實(shí)踐的能力。

4結(jié)束語(yǔ)

在編譯原理實(shí)踐教學(xué)過(guò)程中，文章針對(duì)現(xiàn)有教學(xué)進(jìn)行了一些創(chuàng)新研究。實(shí)踐教學(xué)改變了傳統(tǒng)理論教學(xué)單一的模式，提高了學(xué)生的興趣，且實(shí)踐內(nèi)容由算法到編譯器的實(shí)現(xiàn)，實(shí)踐難度由淺入深，均具有層次性，循序漸進(jìn)，一步一步引導(dǎo)學(xué)生深入了解編譯程序，不僅鍛煉了學(xué)生的編程能力，為之后大型程序的開(kāi)發(fā)奠定了基礎(chǔ)，還提高了教學(xué)的質(zhì)量。關(guān)于層次化實(shí)踐教學(xué)這個(gè)課題，還需要和更多相關(guān)課程的教師一起探討研究。

參考文獻(xiàn)：

[1]余芳，王曉明，趙森.基于創(chuàng)新思維培養(yǎng)的編譯原理實(shí)驗(yàn)教學(xué)改革[J].大學(xué)教育，2019（12）：45-47.

[2]余月，李鳳霞，陳宇峰，計(jì)衛(wèi)星.計(jì)算機(jī)編譯原理課程虛擬實(shí)驗(yàn)設(shè)計(jì)與實(shí)踐[J].實(shí)驗(yàn)技術(shù)與理，2019，36（8）：123-126.

[3]楊旭.新工科背景下基于混合式教學(xué)的編譯原理課程教學(xué)改革探析[J].計(jì)算機(jī)產(chǎn)品與流通，2019（12）：225.

[4]于雙元，徐金安，丁丁，陳鈺楓.基于層次遞進(jìn)模式的“編譯原理”課程教學(xué)研究與實(shí)踐[J].工業(yè)和信息化教育，2019（3）：51-55.

[5]萬(wàn)新燕，時(shí)招軍.編譯原理實(shí)驗(yàn)教學(xué)設(shè)計(jì)[J].教育教學(xué)論壇，2019（8）：261-262.

[6]李春娥.編譯原理實(shí)驗(yàn)教學(xué)設(shè)計(jì)的改進(jìn)[J].計(jì)算機(jī)產(chǎn)品與流通，2018（11）：225.

[7]侯書東，常家琦，劉恒.編譯原理課程教學(xué)實(shí)踐探究[J].安徽工業(yè)大學(xué)學(xué)報(bào)（社會(huì)科學(xué)版），2018，35（04）：91-92.

[8]孫守卿.基于工程教育專業(yè)認(rèn)證的《編譯原理》課程改革[J].電腦知識(shí)與技術(shù)，2019，15（29）：104-106.

【通聯(lián)編輯：王力】

收稿日期：2020-01-19

基金項(xiàng)目：面向杜交網(wǎng)絡(luò)的中文事件抽取與預(yù)測(cè)研究，國(guó)家自然科學(xué)基金（ 61806137）;基于文本和社交網(wǎng)絡(luò)的突發(fā)事件發(fā)現(xiàn)研究，江蘇省高等學(xué)校自然科學(xué)研究面上項(xiàng)目（18KJB520043）

作者簡(jiǎn)介：王中卿（1987-），男，江蘇蘇州人，講師，博士，主要研究方向?yàn)樽匀徽Z(yǔ)言處理;朱培培（1995-），女，江蘇省徐州人，碩士研究生，主要研究方向?yàn)樽匀徽Z(yǔ)言處理，