基于過程驅(qū)動(dòng)的“編譯原理”課程實(shí)踐教學(xué)研究

徐艷群，張　斌

（南陽理工學(xué)院 計(jì)算機(jī)與信息工程學(xué)院，河南　南陽　473004）

基于過程驅(qū)動(dòng)的“編譯原理”課程實(shí)踐教學(xué)研究

徐艷群，張斌

（南陽理工學(xué)院 計(jì)算機(jī)與信息工程學(xué)院，河南南陽473004）

“編譯原理”是計(jì)算機(jī)所有專業(yè)課程中最能鍛煉學(xué)生計(jì)算思維能力的一門課程，也是計(jì)算機(jī)專業(yè)較難的一門課程，很多高校忽視編譯原理的實(shí)踐環(huán)節(jié)，導(dǎo)致學(xué)生對編譯的學(xué)習(xí)斷章取義，學(xué)了“編譯原理”還是不明白編譯的實(shí)際過程。為了解決學(xué)生在“編譯原理”課程學(xué)習(xí)中存在的問題，筆者提出了基于過程驅(qū)動(dòng)的“編譯原理”實(shí)踐教學(xué)模式，教學(xué)過程貫穿小型C語言編譯器的詞法分析、語法分析、目標(biāo)代碼生成等階段，實(shí)現(xiàn)了對C語言部分語法的識(shí)別，課后組織學(xué)生進(jìn)行編程實(shí)踐，達(dá)到了教授該課程的預(yù)期效果。

項(xiàng)目驅(qū)動(dòng)；C編譯器；詞法分析；語法分析

1　“編譯原理”課程實(shí)踐教學(xué)現(xiàn)狀

“編譯原理”這門課程是計(jì)算機(jī)專業(yè)一門比較難的課程，課理論性很強(qiáng)，實(shí)踐性也很強(qiáng)，是一門很難出成果且很難上手實(shí)現(xiàn)編程的課程。很少有學(xué)生畢業(yè)后會(huì)從事編譯器開發(fā)這樣的工作。鑒于這種情況，目前很多應(yīng)用型本科院校對編譯原理這門課程不夠重視：有的高校只講理論不安排實(shí)踐；有的高校即使有實(shí)踐環(huán)節(jié)也只是對詞法分析、語法分析、中間代碼生成和代碼優(yōu)化等分別給一個(gè)簡單程序讓學(xué)生理解并實(shí)踐。這導(dǎo)致學(xué)生只是局部理解編譯，不能把握編譯的整個(gè)過程，實(shí)際上編譯的各個(gè)過程之間存在著緊密的聯(lián)系，前一個(gè)階段的輸出是后一個(gè)階段的輸入，因而必須注重編譯的過程。

高級(jí)語言的迅速發(fā)展對編譯器的要求越來越高，而C語言在高級(jí)語言中占據(jù)的重要地位使人們對C語言編譯器的發(fā)展格外關(guān)注。筆者在編譯理論教學(xué)中，通過一個(gè)簡單的C語言編譯器和一個(gè)類偽代碼（Pseudo-Code，PCODE）指令代碼的解釋器的設(shè)計(jì)與實(shí)現(xiàn)過程，幫助學(xué)生深入理解編譯的過程。教學(xué)過程中貫穿小型C語言編譯器的詞法分析、語法分析、目標(biāo)代碼生成等階段，實(shí)現(xiàn)了對C語言部分語法的識(shí)別，課后組織學(xué)生開展編程實(shí)踐，改變以往枯燥的理論講課過程，從而提高了學(xué)生的編程能力以及學(xué)生對多門課程的融會(huì)貫通能力等，學(xué)生的計(jì)算思維能力也得到了提升。具體環(huán)節(jié)按照先理論后實(shí)踐的過程展開。

2　基于C語言編譯器的課程實(shí)踐設(shè)計(jì)思想

本文的主要目的是設(shè)計(jì)和實(shí)現(xiàn)一個(gè)簡單的C語言的編譯器和一個(gè)類PCODE指令代碼的解釋器。C語言編譯器經(jīng)過詞法分析、語法分析后生成PCODE指令形式，調(diào)用類PCODE指令代碼的解釋器解釋運(yùn)行。具體設(shè)計(jì)過程如下。

（1）介紹如何設(shè)計(jì)和實(shí)現(xiàn)一個(gè)簡單的C語言編譯器時(shí)，文章提出了如何設(shè)計(jì)文法能夠方便地編程，將復(fù)雜的詞法、語法分析層次變得更加清晰。同時(shí)對文法采取動(dòng)態(tài)的方法讀入，只要寫出文法就可以實(shí)現(xiàn)對輸入串的分析、識(shí)別，而不必再去修改程序部分，使得此編譯器更加靈活。

（2）語法分析部分采用“LR（1）”分析法，可以識(shí)別絕大多數(shù)的文法，克服了遞歸下降和LL（0）分析法對文法的“嚴(yán)格要求”，雖然實(shí)現(xiàn)“LR（1）”分析器的算法相對復(fù)雜，但它帶來的方便是顯而易見的。

（3）為了方便調(diào)試和提高代碼的易讀性，此編譯器并沒有生成匯編語言，而是生成了類PCODE指令形式。接著文章討論了如何設(shè)計(jì)和實(shí)現(xiàn)一個(gè)部分功能的類PCODE指令代碼解釋器，從而可以執(zhí)行上一步生成的中間代碼。具體實(shí)現(xiàn)過程如圖1所示。

圖1　C語言編譯器的實(shí)現(xiàn)過程

3　具體實(shí)施

3.1詞法分析

詞法分析是編譯的第一個(gè)階段，它的主要任務(wù)根據(jù)單詞的構(gòu)詞規(guī)則是從左至右逐個(gè)字符地對源程序進(jìn)行掃描，產(chǎn)生一個(gè)個(gè)單詞序列，用以進(jìn)行語法分析。詞法分析其實(shí)也是語法分析的一部分，詞法分析的描述完全可以歸并到語法分析的描述中去，只不過詞法規(guī)則更加簡單一些。如果分離了可以使得編譯程序的結(jié)構(gòu)更加簡潔、清晰和條理化，還可增加編譯程序的可移植性等優(yōu)點(diǎn)。詞法分析程序的輸出一般為二元式單詞種別（單詞自身的值）。

程序每次讀出一個(gè)單詞，然后獲得對應(yīng)的類型作為語法分析的輸入部分，其流程如圖2所示。經(jīng)過詞法分析后所有的字符都被加入到words中，最后用#作為結(jié)束符號(hào)。

圖2　詞法分析流程

3.2語法分析

語法分析是編譯程序的核心部分。語法分析的作用是識(shí)別有詞法分析給出的單詞符號(hào)序列是否是給定的文法的正確句子。可以采用自頂向下的語法分析方法，也可以采用自底向上的語法分析方法。本文以自底向上的“LR（1）”分析方法為例。文法不僅可以精準(zhǔn)地表達(dá)出來可以識(shí)別的輸入串，同時(shí)還可以極大地方便編程的實(shí)現(xiàn)。

3.2.1語法分析用到的文法

下面是識(shí)別表達(dá)式的文法G：

為了簡化語義分析時(shí)的判斷，對表達(dá)式的文法而言，又引入了兩個(gè)非終結(jié)符：乘除法句柄（md_opr_express）和加減法句柄（ps_opr_express），從而前文的產(chǎn)生式可以被表示為：

3.2.2求文法的First集

求First集的過程中將每一個(gè)終結(jié)符的First集存入到set 類型中，這樣可以保證每一次插入不用進(jìn)行判斷了，最后只需要查看一下First集有沒有增加就能夠知道是否有新元素加入到集合之中。

3.2.3“LR（1）”分析

“LR（1）”針對不同產(chǎn)生式上的非終極符，分別定義其超前搜索字符（Reducelookup），減少了移入/歸約沖突。

（1）“LR（1）”項(xiàng)目集族的構(gòu)造。由于構(gòu)造的過程中同一個(gè)產(chǎn)生式的超前搜索字符不同或者原點(diǎn)位置不同，就說明不在同一種狀態(tài)，所以對每個(gè)產(chǎn)生式再構(gòu)造下面數(shù)據(jù)結(jié)構(gòu)，就可以達(dá)到唯一的表示一個(gè)產(chǎn)生式的狀態(tài)。

struct node｛

int key， //產(chǎn)生式的索引，可以唯一地表示出一個(gè)產(chǎn)生式int pos， //原點(diǎn)的位置

int First_index， //超前搜索字符的索引

｝eNode；

（2）“LR（1）”分析表的構(gòu)造。“LR（1）”分析表包括兩個(gè)部分，GOTO表和ACCTION表。“LR（1）”分析表的構(gòu)造一般是在構(gòu)造項(xiàng)目集簇的第（5）步生成的。

①Xi為終結(jié)符，獲取Ji在隊(duì)列中的位置，Ji_pos，則更新Action［pos］［ Xi］=Ji_pos 。

②Xi為非終結(jié)符，獲取Ji在隊(duì)列中的位置，則更新GOTO ［pos］［Xi］=Ji_pos。

③如果識(shí)別Xi后，發(fā)現(xiàn)Ji中有原點(diǎn)已經(jīng)移到產(chǎn)生式右部最后一個(gè)文法符號(hào)的后面的產(chǎn)生式Pk，說明此項(xiàng)目有規(guī)約動(dòng)作。更新Action［Ji_pos］［Pk的每一個(gè)超前搜索字符索引］為產(chǎn)生式Pk索引。

總的來說，每當(dāng)識(shí)別一個(gè)文法符號(hào)（無論是終結(jié)符還是非終結(jié)符）都需要更新Action表或GOTO表的一個(gè)位置。每當(dāng)有產(chǎn)生式的原點(diǎn)位置越過最后一個(gè)位置的時(shí)候，就可能要更新Action表的多個(gè)位置，根據(jù)“LR（1）”分析表就可以對C語言程序進(jìn)行語法分析。

3.2.4目標(biāo)代碼的生成

在進(jìn)行過語法分析后，多數(shù)編譯器根據(jù)代碼的語義將源程序生成另外一種內(nèi)部表示形式，例如三元式或四元式。本文所討論的方案并沒有這一步驟，而是直接生成了類PCODE指令代碼，然后通過類PCODE指令解釋器解釋類PCODE指令代碼。

（1）類PCODE指令代碼語言說明。類PCODE指令代碼是一種假想棧式計(jì)算機(jī)的匯編語言，它不依賴于實(shí)際的計(jì)算機(jī)，其指令非常簡單。指令格式如圖3所示。

圖3　指令格式

其中f代表功能碼，l表示層差，a的含義不同指令有所區(qū)別，主要指令解釋說明如下。

LIT0a將常數(shù)值取到棧頂，a為常數(shù)值。

LODla將變量值取到棧頂，a為偏移量，l為層差。

OPR00過程調(diào)用結(jié)束后，返回調(diào)用點(diǎn)并退棧。

OPR01棧頂元素取反。

OPR02次棧頂與棧頂相加，退兩個(gè)棧元素，結(jié)果值進(jìn)棧。

OPR03次棧頂減去棧頂，退兩個(gè)棧元素，結(jié)果值進(jìn)棧。

OPR04次棧頂乘以棧頂，退兩個(gè)棧元素，結(jié)果值進(jìn)棧。

OPR05次棧頂除以棧頂，退兩個(gè)棧元素，結(jié)果值進(jìn)棧。

（2）生成方法簡述。對改寫好的文法而言，每一個(gè)需要生成指令的規(guī)約動(dòng)作都可以在語法分析的過程中被捕獲到，根據(jù)規(guī)約的產(chǎn)生式不同，生成對應(yīng)指令即可。如表1所示。

表1　表達(dá)式中間代碼生成對應(yīng)表

3.2.5類PCODE指令代碼解釋程序的設(shè)計(jì)和實(shí)現(xiàn)

當(dāng)生成目標(biāo)代碼的過程中如果沒有發(fā)現(xiàn)錯(cuò)誤，就可以由編譯程序調(diào)用解釋程序?qū)ι傻念怭CODE指令代碼進(jìn)行解釋執(zhí)行。解釋執(zhí)行的過程中，其數(shù)據(jù)空間為棧式計(jì)算機(jī)存儲(chǔ)空間，遵循后進(jìn)先出的規(guī)則，對每個(gè)過程被調(diào)用時(shí)才分配數(shù)據(jù)空間，當(dāng)程序退出時(shí)，釋放所分配的空間。

數(shù)據(jù)棧用一個(gè)vector來模擬，每當(dāng)發(fā)現(xiàn)int指令的時(shí)候就開辟一個(gè)棧，每當(dāng)遇到opr 0 0的時(shí)候就銷毀一個(gè)棧。數(shù)據(jù)棧的數(shù)據(jù)類型為vector >。類PCODE指令代碼指令的解釋流程如圖4所示。在執(zhí)行指令的時(shí)候，執(zhí)行cal指令的時(shí)候需要將上一次跳轉(zhuǎn)的位置保存，從而可以在訪問函數(shù)結(jié)束的時(shí)候返回上一次的執(zhí)行點(diǎn)。從而實(shí)現(xiàn)函數(shù)的嵌套、遞歸調(diào)用。

圖4　指令解釋的流程

4　結(jié)語

經(jīng)過過程驅(qū)動(dòng)的“編譯原理”實(shí)踐教學(xué)過程的引入，學(xué)生對編譯器的理解有了新的認(rèn)識(shí)，學(xué)生能清楚編譯的整個(gè)過程及過程之間的銜接，理解編譯器的設(shè)計(jì)過程包括詞法分析、語法分析、目標(biāo)代碼生成等，了解每個(gè)過程都有相應(yīng)的算法，如詞法分析用到自動(dòng)機(jī)的確定化及最小化算法、語法分析的First集構(gòu)造算法等，在具體編程過程中如何實(shí)現(xiàn)。在課堂教學(xué)過程中把對應(yīng)的程序引入進(jìn)來，講完理論就接著講具體實(shí)踐，課下學(xué)生實(shí)際練習(xí)。通過近3年的統(tǒng)計(jì)，學(xué)校計(jì)算機(jī)專業(yè)學(xué)生期末成績從平均分60多分提高到80分左右，學(xué)生算法理解及編程能力也不同程度有了提高，很多學(xué)生加入了國際大學(xué)生程序設(shè)計(jì)競賽（Associationfor Computing Machinery International Collegiate Programming Contest，ACM）等計(jì)算機(jī)興趣小組。雖然實(shí)現(xiàn)了函數(shù)的調(diào)用，但是函數(shù)遞歸調(diào)用過程中不能使用全局變量，同時(shí)指針、函數(shù)返回值、結(jié)構(gòu)體等都沒有實(shí)現(xiàn)對其處理，因而還需教師帶領(lǐng)學(xué)生朝這些方面進(jìn)一步努力，實(shí)現(xiàn)一個(gè)對C語言程序都能進(jìn)行編譯的C語言編譯器，讓學(xué)生掌握編譯器的工作原理和編譯器的設(shè)計(jì)與實(shí)現(xiàn)過程，激發(fā)學(xué)生的學(xué)習(xí)興趣和動(dòng)手實(shí)踐的能力。

［1］王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析［M］.北京：電子工業(yè)出版社，2007.

［2］張素琴.編譯原理［M］.北京：清華大學(xué)出版社，2003.

［3］THOMAS H C.算法導(dǎo)論［M］.陳克忠，譯.北京：機(jī)械工業(yè)出版社，2006.

［4］張龍祥.UML與系統(tǒng)分析設(shè)計(jì)［M］.2版.北京：人民郵電出版社，2007.

Research on practice teaching of compiler principles course based on process driven

Xu Yanqun， Zhang Bin
（Computer and Information Engineering Department of Nanyang Institute of Technology， Nanyang 473004， China）

The course of compiler principles is very important in training computational thinking ability in all computer courses， it is also a kind of course more diffcult to learn. Many colleges ignore compiler principles practice process， which results in compile learning is not complete to students， who still don't fgure the actual process of compile. In order to solve the problem in studying “compiling principle”，the author puts forward practice teaching mode of “compiler principle”based on process driven， the teaching process applies a small C language compiler， including lexical analysis， syntax analysis， code generation phases， and achieved the recognition of C language partial syntax， organized student to take part in the practice of compiling， achieved the course effect by programming after class.

project driven； C compiler； lexical analysis； syntax analysis

徐艷群（1978— ），女，陜西韓城，碩士，講師；研究方向：計(jì)算機(jī)應(yīng)用。