層次化精準編譯原理實踐教學

王中卿　朱培培

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

關鍵詞：編譯原理;實踐教學;詞法分析;語法分析;語法制導翻譯

中圖分類號：C642 文獻標識碼：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引言

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

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

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

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

2.1詞法分析的實驗設計

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

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

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

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

2.2語法分析的實驗設計

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

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

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

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

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

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

3.1簡單的語法處理器的實驗設計

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

1）化學表達式的解析

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

2）SQL語言的解析

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

3）LaTex源文件的解析

LaTex源文件的解析主要是考察學生對于多行語句的解析。該實驗需要學生定義LaTex中各個標簽的語法規(guī)則，輸出相應的語法樹，并轉(zhuǎn)化為PDF格式。語法分析中會運用到遞歸思想，能鍛煉學生的邏輯思維能力，且該實驗能加強學生對La-Tex文本的認識。

3.2基于Python--的編譯器的實驗設計

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

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

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

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

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

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

4結(jié)束語

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

參考文獻：

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

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

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

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

[5]萬新燕，時招軍.編譯原理實驗教學設計[J].教育教學論壇，2019（8）：261-262.

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

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

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

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

收稿日期：2020-01-19

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

作者簡介：王中卿（1987-），男，江蘇蘇州人，講師，博士，主要研究方向為自然語言處理;朱培培（1995-），女，江蘇省徐州人，碩士研究生，主要研究方向為自然語言處理，