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

徐艷群，張　斌

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

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

徐艷群，張斌

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

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

項目驅(qū)動；C編譯器；詞法分析；語法分析

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

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

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

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

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

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

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

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

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

3　具體實施

3.1詞法分析

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

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

圖2　詞法分析流程

3.2語法分析

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

3.2.1語法分析用到的文法

下面是識別表達式的文法G：

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

3.2.2求文法的First集

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

3.2.3“LR（1）”分析

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

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

struct node｛

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

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

｝eNode；

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

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

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

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

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

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

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

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

圖3　指令格式

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

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

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

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

OPR01棧頂元素取反。

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

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

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

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

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

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

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

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

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

圖4　指令解釋的流程

4　結(jié)語

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

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

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

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

［4］張龍祥.UML與系統(tǒng)分析設(shè)計［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— ），女，陜西韓城，碩士，講師；研究方向：計算機應(yīng)用。