獨(dú)立學(xué)院編譯原理課程教學(xué)改革

沈嵐嵐

（桂林電子科技大學(xué) 信息科技學(xué)院，廣西 桂林 541004）

0 引 言

編譯原理是計算機(jī)專業(yè)的一門重要基礎(chǔ)課，通過介紹和學(xué)習(xí)編譯程序構(gòu)造的一般原理和基本方法，培養(yǎng)學(xué)生的系統(tǒng)能力、程序設(shè)計和分析能力。獨(dú)立學(xué)院是高校內(nèi)部系院改造的二級單位，專業(yè)設(shè)置大多以工程應(yīng)用為主，目的是使畢業(yè)生可以直接服務(wù)社會，同時比高職高專畢業(yè)生具有更深厚的專業(yè)理論基礎(chǔ)，兼具學(xué)術(shù)性特色。獨(dú)立學(xué)院的培養(yǎng)目標(biāo)、教學(xué)對象、教學(xué)環(huán)境等都和傳統(tǒng)高校有所區(qū)別，因此在教學(xué)上也應(yīng)有自己的特色。

1 存在問題及分析

當(dāng)前獨(dú)立學(xué)院的編譯原理課程教學(xué)大多照搬傳統(tǒng)高校的形式，按照編譯器的構(gòu)造分成詞法、語法、語義分析，中間代碼生成、優(yōu)化，目標(biāo)代碼的生成等幾個章節(jié)，每個章節(jié)講授相關(guān)方面的知識，從而進(jìn)行理論和實(shí)踐教學(xué)。編譯系統(tǒng)是一個相當(dāng)復(fù)雜的系統(tǒng)，編譯原理課程的各個環(huán)節(jié)都包含了豐富的理論、大量的算法和實(shí)現(xiàn)的方法。獨(dú)立學(xué)院受限于課時、學(xué)生基礎(chǔ)等情況，在現(xiàn)有的教學(xué)體系之下，很難取得良好的教學(xué)效果，學(xué)生往往覺得這門課程理論繁多、算法抽象、實(shí)踐困難，各個知識點(diǎn)也難以貫通。

從本質(zhì)上說，編譯器的構(gòu)造是一個規(guī)模相當(dāng)大的復(fù)雜算法問題，導(dǎo)致講授其原理和技術(shù)的編譯原理課程也具有復(fù)雜性，并造成了教學(xué)上的困難。復(fù)雜問題的求解往往采用“分治”的方法，即將復(fù)雜問題分解成規(guī)模較小的子問題，通過求解一個個子問題降低復(fù)雜度，并根據(jù)子問題之間的聯(lián)系最終解決原本復(fù)雜的問題。編譯原理的教學(xué)雖然也進(jìn)行了一定的分解，但是這種分解是基于編譯器的構(gòu)造，而不是基于教學(xué)，子問題的規(guī)模仍然偏大，有必要根據(jù)教學(xué)規(guī)律進(jìn)行進(jìn)一步分解。

對問題進(jìn)行有效分解的前提是對其有一個清晰的定義，編譯原理課程教學(xué)并不是編譯器的構(gòu)造，其問題的表現(xiàn)形式是各個知識點(diǎn)。應(yīng)該將教學(xué)內(nèi)容分解成各個知識點(diǎn)，針對這些知識點(diǎn)進(jìn)行教學(xué)方法的設(shè)計，以實(shí)現(xiàn)“各個擊破、分而治之”。對于學(xué)科知識的定義，Denning提出了一種二維矩陣的方式，其“縱向”關(guān)系為各分支學(xué)科，“橫向”關(guān)系反映的是學(xué)科所研究的基本內(nèi)容[1]。董榮勝從認(rèn)知規(guī)律出發(fā)，認(rèn)為計算學(xué)科的所有知識點(diǎn)可以歸入抽象、理論和設(shè)計3種形態(tài)中，提出將這3種形態(tài)作為二維表的“橫向”關(guān)系[2]。認(rèn)知規(guī)律是教學(xué)的基本規(guī)律之一，我們采用這種定義方式將編譯原理課程各章節(jié)內(nèi)容進(jìn)行定義和教學(xué)設(shè)計，并以詞法分析為例進(jìn)行詳細(xì)闡述。

2 基于抽象、理論和設(shè)計的知識定義和分解

抽象指的是對現(xiàn)實(shí)世界的認(rèn)識，最初可能是感性而粗糙的，但能夠通過理論的指導(dǎo)進(jìn)行進(jìn)化而不斷趨于完美；理論是系統(tǒng)而完備的，其表現(xiàn)形式是定義、定理和證明等；設(shè)計是對知識的運(yùn)用，是一個有效的裝置或系統(tǒng)[2]。這三者之間的聯(lián)系符合對事物從感性認(rèn)識到理性認(rèn)識，并用認(rèn)識來指導(dǎo)實(shí)踐的認(rèn)知規(guī)律。

詞法分析的任務(wù)是將待編譯的源程序進(jìn)行分解，使之成為如屬性、值等的單詞二元組，然后用計算機(jī)表示這樣一個過程并自動執(zhí)行，使它變成可計算的。在數(shù)學(xué)家哥德爾的研究中，可以給每個對象配上1個數(shù)，接下來的證明或計算過程就是對這些具有某種確定性質(zhì)的符號的有窮序列所做的變換。根據(jù)這個理論，可以將單詞的每一屬性指定一個唯一的自然數(shù)進(jìn)行表示，即使用哥德爾配數(shù)法來進(jìn)行表示，后面的分析過程也就是將源程序的字符序列變成哥德爾數(shù)的序列。一般來說， 1個高級語言的源程序至少有5類單詞（見表1）。

表1　單詞屬性和哥德爾數(shù)

進(jìn)一步研究發(fā)現(xiàn)，關(guān)鍵字、運(yùn)算符和界符是預(yù)先定義好的，其數(shù)量有限；此時可以省略單詞的值，而為每一種符號定義1個哥德爾數(shù)，建立1個數(shù)據(jù)字典，以提高分析效率，由此產(chǎn)生了詞法分析結(jié)果的最終表現(xiàn)形式。這個過程體現(xiàn)了經(jīng)典理論和現(xiàn)實(shí)技術(shù)的結(jié)合，這樣的例子在編譯原理課程教學(xué)中還有許多，按照抽象、理論和設(shè)計來進(jìn)行教學(xué)內(nèi)容的分解能夠降低問題的復(fù)雜度，可以更好地進(jìn)行教學(xué)。基于這3種形態(tài)對詞法分析教學(xué)內(nèi)容的分解見表2。

Backus-Naur范式、正規(guī)式等是對詞法組成和規(guī)則的形式化描述，狀態(tài)轉(zhuǎn)換圖是按照規(guī)則識別字符串的工具。形式語言和自動機(jī)的相關(guān)理論可以指導(dǎo)詞法規(guī)則和狀態(tài)轉(zhuǎn)換圖的構(gòu)造，并對它們進(jìn)行優(yōu)化，以便更有效的應(yīng)用，并產(chǎn)生自動識別的算法。通過這些算法，可以編寫出詞法分析程序以及構(gòu)造詞法分析程序的自動工具。

通過表2的分解以及3種形態(tài)之間的聯(lián)系，可以知道為什么學(xué)習(xí)這些知識、這些知識起什么作用，從而將各知識點(diǎn)貫穿起來。此外，不同形態(tài)有著各自的思維特點(diǎn)和認(rèn)知方法，講授抽象形態(tài)的知識時應(yīng)盡可能使其形象化、具體化；理論形態(tài)的知識常用到推導(dǎo)、證明等方法，可以類比數(shù)學(xué)的教學(xué)方法；設(shè)計形態(tài)主要是針對實(shí)踐能力的培養(yǎng)，可以通過工程訓(xùn)練的方法進(jìn)行。通過這些原則可以對各個知識點(diǎn)進(jìn)行針對性的教學(xué)，以實(shí)現(xiàn)“各個擊破、分而治之”的教學(xué)目的。

表2　詞法分析的知識分解

3 “詞法分析”的教學(xué)設(shè)計與實(shí)現(xiàn)

在編譯原理課程的教學(xué)中，算法理解能力和實(shí)踐能力的培養(yǎng)往往是教學(xué)的重點(diǎn)和難點(diǎn)，它們分別屬于抽象和設(shè)計形態(tài)的內(nèi)容。針對2種形態(tài)的特點(diǎn)，我們給出了具體的教學(xué)設(shè)計和實(shí)現(xiàn)方式。

3.1 詞法分析中算法的講授

詞法分析在實(shí)現(xiàn)過程中產(chǎn)生了很多算法，這些算法具有抽象化和自動化的特點(diǎn)。傳統(tǒng)教學(xué)方式中，對算法的表示常使用偽代碼的形式，文本化的表示方式較難引起學(xué)習(xí)者的興趣，而且學(xué)生需要自行想象運(yùn)行結(jié)果，不夠直觀；直接給出源代碼雖然能夠直觀地看到算法的運(yùn)行，但涉及眾多語法知識和實(shí)現(xiàn)技術(shù)，分散了對算法本身的關(guān)注，實(shí)現(xiàn)起來也比較困難，所以這些教學(xué)方式往往以教授為主，配合板書、PPT，很少使用其他教學(xué)工具。

可視化編程工具Raptor[3]提供了一種基于流程圖的程序開發(fā)環(huán)境，使用Raptor編寫的NFA確定化算法的主要程序如圖1所示。在圖1中，定義二維矩陣nfa和dfa分別表示輸入和輸出，基于哥德爾數(shù)的理論，有限自動機(jī)的狀態(tài)以及輸入的符號都可以轉(zhuǎn)化成自然數(shù)，因此，使用二維矩陣的行下標(biāo)表示狀態(tài)，列下標(biāo)表示輸入字符，將有限自動機(jī)由圖形轉(zhuǎn)化成了鄰接矩陣。

Raptor提供了一種直觀的算法表達(dá)框架，使用了類似流程圖的語言來進(jìn)行程序編寫，這種可視化的算法表示形式更能引起學(xué)生的注意，執(zhí)行過程又可以使學(xué)生直觀地感受算法的所有運(yùn)行步驟，觀察到所有變量當(dāng)前的內(nèi)容，運(yùn)行結(jié)果也能夠直接驗(yàn)證算法的有效性。

3.2 詞法分析器的編寫

詞法分析器的編寫屬于設(shè)計形態(tài)的知識，運(yùn)用對現(xiàn)實(shí)世界的認(rèn)識來進(jìn)行實(shí)踐，開發(fā)一個系統(tǒng)或裝置。在詞法分析中，就是進(jìn)行詞法分析器的編寫，編寫的前提是要具備一定的先期知識，手工構(gòu)造詞法分析器需要先畫出最簡DFA，而用自動工具進(jìn)行生成只需寫出正規(guī)式即可。

實(shí)踐能力可以通過反復(fù)訓(xùn)練進(jìn)行培養(yǎng)并逐步提高，分任務(wù)的詞法分析器實(shí)踐方案見表3。

表3　詞法分析實(shí)驗(yàn)任務(wù)要求

圖1　NFA確定化的Raptor程序

從任務(wù)①到任務(wù)④難度逐級遞增，并給出每級任務(wù)所需的思維能力。在教學(xué)中，教師可以詳細(xì)講解任務(wù)①的實(shí)現(xiàn)方法，甚至可以視情況給出部分或全部源代碼供學(xué)生進(jìn)行仿寫；任務(wù)②是對任務(wù)①的改進(jìn)，首先需要學(xué)生自己進(jìn)行浮點(diǎn)數(shù)的表示，再參照任務(wù)①的方法進(jìn)行浮點(diǎn)數(shù)的識別，還可以增加一些新的運(yùn)算；任務(wù)③則需要識別出標(biāo)識符和關(guān)鍵字，讓學(xué)生自己設(shè)計標(biāo)識符規(guī)則和所用到的關(guān)鍵字，其中標(biāo)識符的識別方法類似于浮點(diǎn)數(shù)的識別，關(guān)鍵字的識別方法類似于運(yùn)算符的識別。這3個任務(wù)已基本包括高級語言中所有種類的單詞符號的識別方式，以此為基礎(chǔ)，可以嘗試選擇一種高級語言讓學(xué)生進(jìn)行詞法分析。任務(wù)④是補(bǔ)充知識，旨在開闊視野，可作為課后作業(yè)，要求學(xué)生翻閱資料，進(jìn)行需求分析并予以實(shí)現(xiàn)。讓學(xué)生在實(shí)踐中體會到編譯器構(gòu)造時產(chǎn)生理論技術(shù)的寶貴性，該技術(shù)不只應(yīng)用于產(chǎn)生一個編譯器，還可應(yīng)用于許多領(lǐng)域。

通過不斷深入迭代的任務(wù)體系，使學(xué)生在完成每級任務(wù)時產(chǎn)生“過關(guān)”的成就感，而下一任務(wù)的出現(xiàn)又對其提出了新挑戰(zhàn)，促使學(xué)生不斷地去學(xué)習(xí)、探索，使學(xué)生針對同一問題能夠得到反復(fù)的、大量的訓(xùn)練，從而實(shí)現(xiàn)思維能力的鍛煉和實(shí)踐能力的提高。

4 結(jié) 論

隨著科學(xué)技術(shù)的發(fā)展，并行編譯、動態(tài)編譯等在多核系統(tǒng)、單片機(jī)、信息安全領(lǐng)域等方面的作用越來越大，編譯原理課程的作用也越來越重要。不同于傳統(tǒng)高校教學(xué)，獨(dú)立學(xué)院的編譯原理課程教學(xué)應(yīng)有自己的特點(diǎn)。我們將編譯原理課程教學(xué)視為一個對復(fù)雜問題的求解過程，運(yùn)用“分治”法將其分解并各個擊破，可以實(shí)現(xiàn)較好的教學(xué)效果。

參考文獻(xiàn)：

[1]Denning P J, Comer D E, Gries D, et al. Computing as a discipline[J]. Commuications of the ACM, 1989, 32(1): 63-70.

[2]董榮勝. 計算機(jī)科學(xué)導(dǎo)論: 思想與方法[M]. 3版. 北京: 高等教育出版社, 2015: 53-62.

[3]董榮勝. 計算機(jī)思維結(jié)構(gòu)[M]. 北京: 人民郵電出版社, 2017: 34-56.

[4]程向前, 周夢遠(yuǎn). 基于RAPTOR的可視化計算案例教程[M]. 北京: 清華大學(xué)出版社, 2014: 1-27.

[5]前橋和彌. 自制編程語言[M]. 北京: 人民郵電出版社. 2013: 17-41.

[6]王峰, 張浩軍. 編譯原理課程教學(xué)中的詞法分析及其應(yīng)用[J]. 計算機(jī)教育, 2013(9): 19-23.