徐艷群，張　斌

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

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

徐艷群，張斌

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

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

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

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

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

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

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

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

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

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

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

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

3　具體實(shí)施

3.1詞法分析

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

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

圖2　詞法分析流程

3.2語(yǔ)法分析

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

3.2.1語(yǔ)法分析用到的文法

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

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

3.2.2求文法的First集

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

3.2.3“LR（1）”分析

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

（1）“LR（1）”項(xiàng)目集族的構(gòu)造。由于構(gòu)造的過(guò)程中同一個(gè)產(chǎn)生式的超前搜索字符不同或者原點(diǎn)位置不同，就說(shuō)明不在同一種狀態(tài)，所以對(duì)每個(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)造?！癓R（1）”分析表包括兩個(gè)部分，GOTO表和ACCTION表?！癓R（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，說(shuō)明此項(xiàng)目有規(guī)約動(dòng)作。更新Action［Ji_pos］［Pk的每一個(gè)超前搜索字符索引］為產(chǎn)生式Pk索引。

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

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

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

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

圖3　指令格式

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

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

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

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

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

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

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

數(shù)據(jù)棧用一個(gè)vector來(lái)模擬，每當(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)的位置保存，從而可以在訪問(wèn)函數(shù)結(jié)束的時(shí)候返回上一次的執(zhí)行點(diǎn)。從而實(shí)現(xiàn)函數(shù)的嵌套、遞歸調(diào)用。

圖4　指令解釋的流程

4　結(jié)語(yǔ)

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