層次化精準(zhǔn)編譯原理實(shí)踐教學(xué)

王中卿　朱培培

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2）SQL語言的解析

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

3）LaTex源文件的解析

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

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

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

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

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

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

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

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

4結(jié)束語

在編譯原理實(shí)踐教學(xué)過程中，文章針對現(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é)生的編程能力，為之后大型程序的開發(fā)奠定了基礎(chǔ)，還提高了教學(xué)的質(zhì)量。關(guān)于層次化實(shí)踐教學(xué)這個課題，還需要和更多相關(guān)課程的教師一起探討研究。

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

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

收稿日期：2020-01-19

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

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