摘要：本文分析了編譯系統(tǒng)以及其錯(cuò)誤處理能力對(duì)于程序設(shè)計(jì)語(yǔ)言的重要性，對(duì)其中處理語(yǔ)法錯(cuò)誤問(wèn)題進(jìn)行了深入研究，并從語(yǔ)法錯(cuò)誤的診察與報(bào)告，到利用遞歸下降分析法對(duì)錯(cuò)誤進(jìn)行恢復(fù)和糾正處理，直至最后的限制重復(fù)報(bào)告錯(cuò)誤信息及其中涉及的關(guān)鍵技術(shù)進(jìn)行了介紹，從而幫助學(xué)習(xí)者和開(kāi)發(fā)者牢固掌握相關(guān)的理論和技術(shù)。

關(guān)鍵詞：編譯系統(tǒng)；語(yǔ)法錯(cuò)誤處理；遞歸下降分析法

中圖分類(lèi)號(hào)：G642.41 文獻(xiàn)標(biāo)識(shí)碼：B

文章編號(hào)：1672-5913（2007）06-0040-03

1 前言

在計(jì)算機(jī)應(yīng)用領(lǐng)域，目前多數(shù)用戶(hù)都是通過(guò)高級(jí)語(yǔ)言實(shí)現(xiàn)所需要的計(jì)算。而對(duì)于任何高級(jí)語(yǔ)言來(lái)說(shuō)，其編譯系統(tǒng)內(nèi)容豐富，具有嚴(yán)密的邏輯性，對(duì)提高學(xué)習(xí)者和開(kāi)發(fā)者的計(jì)算機(jī)軟件素質(zhì)具有很大作用，使其不但能認(rèn)識(shí)計(jì)算機(jī)信息處理的實(shí)質(zhì)，還可以綜合運(yùn)用所學(xué)的軟件設(shè)計(jì)技術(shù)來(lái)分析解決問(wèn)題[1]。因此，編譯系統(tǒng)是計(jì)算機(jī)系統(tǒng)軟件最重要的組成部分之一，也是用戶(hù)最直接關(guān)心的工具之一，它不但要接受程序語(yǔ)言的所有標(biāo)準(zhǔn)定義，以便源代碼實(shí)現(xiàn)跨平臺(tái)的可移植性，還必須生成高效、正確的目標(biāo)代碼。因此編譯系統(tǒng)本身是一個(gè)大而復(fù)雜的程序，值得我們深入分析研究。

我們知道，在編譯原理的學(xué)習(xí)和編譯系統(tǒng)的構(gòu)建過(guò)程中，語(yǔ)法分析是其中最為重要的一個(gè)組成部分。而在實(shí)際的編譯系統(tǒng)中，語(yǔ)法分析器的錯(cuò)誤處理能力與其構(gòu)造原理和技術(shù)一樣重要，這通常是編譯原理教學(xué)環(huán)節(jié)中容易忽視的地方，不利于學(xué)習(xí)者進(jìn)行實(shí)際的編譯系統(tǒng)的開(kāi)發(fā)工作。因此，本文對(duì)C++編譯系統(tǒng)中遞歸下降的語(yǔ)法分析過(guò)程進(jìn)行了研究，找到了發(fā)現(xiàn)并糾正語(yǔ)法錯(cuò)誤問(wèn)題的有效方法。

2 語(yǔ)法錯(cuò)誤

編程人員在編寫(xiě)程序時(shí)，很難一次就將程序?qū)懙耐昝罒o(wú)誤，尤其是一些比較復(fù)雜的程序，往往會(huì)存在程序錯(cuò)誤。程序錯(cuò)誤的種類(lèi)有很多，比如違反語(yǔ)言的語(yǔ)法和語(yǔ)義規(guī)定的錯(cuò)誤，源程序超出了計(jì)算機(jī)系統(tǒng)的某種限制而引發(fā)的錯(cuò)誤，等等。其中語(yǔ)法錯(cuò)誤是指源程序中含有不符合語(yǔ)法規(guī)則的成分時(shí)所產(chǎn)生的錯(cuò)誤，一般是有關(guān)語(yǔ)言結(jié)構(gòu)上的錯(cuò)誤，如單詞拼寫(xiě)錯(cuò)、表達(dá)式中缺少操作數(shù)、begin和end不匹配等。

語(yǔ)法分析結(jié)果的質(zhì)量將直接影響到編譯系統(tǒng)后期各階段的工作，因此，為了幫助編程人員發(fā)現(xiàn)并糾正這一階段可能出現(xiàn)的錯(cuò)誤，編譯系統(tǒng)的語(yǔ)法分析器應(yīng)該具有錯(cuò)誤處理的能力，其不但可以對(duì)語(yǔ)法上正確的源程序進(jìn)行正確的編譯，同時(shí)還能夠?qū)τ绣e(cuò)誤的源程序報(bào)錯(cuò)，甚至在一定程度上對(duì)錯(cuò)誤進(jìn)行改正[2]。當(dāng)然，進(jìn)行出錯(cuò)處理是件很麻煩的事，想象一個(gè)設(shè)計(jì)良好的編譯調(diào)試環(huán)境，比如Visual Studio，我們?cè)谟盟_(kāi)發(fā)編譯程序時(shí)，不光可以知道哪一句錯(cuò)了，而且可以獲得出錯(cuò)的原因。

3 語(yǔ)法錯(cuò)誤處理技術(shù)

3.1 錯(cuò)誤的診察與報(bào)告

語(yǔ)法錯(cuò)誤可以采用系統(tǒng)的方式解決，不依賴(lài)于出現(xiàn)的上下文。這些錯(cuò)誤比較容易發(fā)現(xiàn)，通常出現(xiàn)在表1所示的翻譯代碼error中。

表1分析函數(shù)翻譯代碼

這里，編譯系統(tǒng)使用EBNF文法描述語(yǔ)言，為每個(gè)非終結(jié)符計(jì)算FIRST集合和FOLLOW集合，編寫(xiě)分析函數(shù)將非終結(jié)符的每個(gè)產(chǎn)生式翻譯成可執(zhí)行代碼。翻譯的規(guī)則可由文法產(chǎn)生式的可能形式導(dǎo)出。對(duì)每一種產(chǎn)生式形式α，用T(α)表示α的翻譯代碼，全局變量t表示從詞法分析器讀入的當(dāng)前單詞，調(diào)用函數(shù)gettok可以獲取下一個(gè)輸入單詞，此外，

當(dāng)然，表1的代碼也可用其他代碼序列表示，以解決有時(shí)會(huì)出現(xiàn)的代碼冗長(zhǎng)問(wèn)題。

編譯系統(tǒng)在查找到源程序中的語(yǔ)法錯(cuò)誤后，要對(duì)這些錯(cuò)誤進(jìn)行報(bào)告，報(bào)告的主要內(nèi)容是錯(cuò)誤發(fā)生的位置以及錯(cuò)誤的性質(zhì)。有了這兩點(diǎn)內(nèi)容，編程人員就可以比較方便地確定錯(cuò)誤的性質(zhì)并對(duì)其進(jìn)行改正。文本所采用的錯(cuò)誤報(bào)告方式為：每發(fā)現(xiàn)一處錯(cuò)誤，就把該錯(cuò)誤信息打印出來(lái)，包括源程序的名字、錯(cuò)誤所在行、錯(cuò)誤的具體內(nèi)容等，同時(shí)用箭頭指向出錯(cuò)的位置。例如，對(duì)于程序段：

for (i=0; i<100， i++)

cout>>i

其中的錯(cuò)誤，編譯系統(tǒng)將報(bào)告如下錯(cuò)誤信息：

Test.cpp: 15: missing ';' before ')'

location: class PrintTest

for (i=0; i<100， i++)

^

Test.cpp: 16: missing ';'

location: class PrintTest

cout>>i

^

2 errors

其中，“Test.cpp”是上述程序段所在的C++源程序的名字，后面的“15”是錯(cuò)誤所在的行的號(hào)碼，“missing ';' before ')'”表示具體的錯(cuò)誤信息，下面的“l(fā)ocation”指錯(cuò)誤在PrintTest類(lèi)中，接下來(lái)該信息還顯示了源程序中含有錯(cuò)誤的代碼行，并用箭頭“^”指向出錯(cuò)位置，最后指出錯(cuò)誤的總數(shù)，這里是2個(gè)。

3.2 遞歸下降分析法中的錯(cuò)誤糾正策略

語(yǔ)法錯(cuò)誤不難發(fā)現(xiàn)，但要修正錯(cuò)誤并非易事。當(dāng)然，不能說(shuō)一發(fā)現(xiàn)錯(cuò)誤就停止分析，這樣做顯然不合理，錯(cuò)誤處理的大部分工作用于對(duì)錯(cuò)誤進(jìn)行適當(dāng)?shù)奶幚怼e(cuò)誤恢復(fù)，以便系統(tǒng)分析過(guò)程可以繼續(xù)下去。

語(yǔ)法錯(cuò)誤的恢復(fù)方法是通過(guò)對(duì)輸入程序添加遺漏的單詞或忽略某些單詞，從而將錯(cuò)誤的輸入轉(zhuǎn)換為合法的句子。遺憾的是，找到合適的恢復(fù)方法非常困難，因?yàn)榫幊倘藛T的意圖有時(shí)候是很難推斷出來(lái)的，這種推測(cè)在一定程度上增加了編譯系統(tǒng)的復(fù)雜程度，如果選擇錯(cuò)誤將導(dǎo)致分析程序混亂，甚至導(dǎo)致后面本來(lái)文法上正確的輸入也產(chǎn)生大量的語(yǔ)法錯(cuò)誤。

而對(duì)于遞歸下降分析器的結(jié)構(gòu)而言，有助于選取合適的錯(cuò)誤恢復(fù)策略。分析器由許多函數(shù)組成，每個(gè)函數(shù)只完成分析任務(wù)的一小部分，因此，目標(biāo)被劃分成若干個(gè)子目標(biāo)，每個(gè)子目標(biāo)調(diào)用相關(guān)的分析函數(shù)。具體而言，假設(shè)構(gòu)造了一個(gè)非終結(jié)符X的分析函數(shù)X，如果下一個(gè)輸入單詞不屬于非終結(jié)符X的FOLLOW集合，函數(shù)就略過(guò)它，反復(fù)執(zhí)行直至遇到X的FOLLOW集合中的單詞，在處理完屬于FOLLOW(X)的單詞后，要將所有合法的部分返回給函數(shù)X的調(diào)用者。但這樣做也有不完善之處，它不能處理含有非終結(jié)符X的句型。例如，非終結(jié)符X出現(xiàn)在句型αXβ中，函數(shù)X會(huì)略過(guò)D(β)中的元素，由于D(β)通常比FOLLOW(X)小，當(dāng)分析識(shí)別出一個(gè)屬于FOLLOW(X)，但不屬于D(β)的輸入單詞時(shí)，程序丟棄該單詞，X停止繼續(xù)執(zhí)行。因此，如果D(β)已知，函數(shù)必須使用D(β)，否則使用FOLLOW(X)，實(shí)現(xiàn)方法如下面error.cpp中的輸出函數(shù)所示。比如，當(dāng)分析函數(shù)分析for語(yǔ)句的第三個(gè)表達(dá)式時(shí)，函數(shù)就利用了集合{ ; ) }恢復(fù)表達(dá)式存在的語(yǔ)法錯(cuò)誤。

＜ｅｒｒｏｒ．ｃｐｐ ｅｘｐｏｒｔｅｄ ｆｕｎｃｔｉｏｎｓ＞≡

ｅｘｔｅｒｎ ｖｏｉｄ ｔｅｓｔ ＡＲＧＳ（（ｉｎｔ ｔｏｋ，ｃｈａｒ ｓｅｔ［］））；

該函數(shù)檢查下一個(gè)單詞是否等于tok，如果不等，則發(fā)出提示信息，并跳過(guò)當(dāng)前單詞，反復(fù)執(zhí)行直至遇到一個(gè)屬于{tok}∪set的單詞。set集合包含了所有不能忽略的元素，保證輸入不會(huì)無(wú)限地忽略。

＜ｅｒｒｏｒ．ｃｐｐ ｆｕｎｃｔｉｏｎｓ＞≡

ｖｉｏｄ ｔｅｓｔ（ｔｏｋ，ｓｅｔ） ｉｎｔ ｔｏｋ；ｃｈａｒ ｓｅｔ［］；｛

ｉｆ（ｔ＝＝ｔｏｋ）

ｔ＝ｇｅｔｔｏｋ（）；

ｅｌｓｅ｛

ｅｘｐｅｃｔ（ｔｏｋ）；

ｓｋｉｐｔｏ（ｔｏｋ，ｓｅｔ）；

ｉｆ（ｔ＝＝ｔｏｋ）

ｔ＝ｇｅｔｔｏｋ（）；

｝

｝

函數(shù)test調(diào)用函數(shù)expect報(bào)錯(cuò)，調(diào)用函數(shù)skipto跳過(guò)錯(cuò)誤的單詞。skipto定義如下：

＜ｅｒｒｏｒ．ｃｐｐ ｅｘｐｏｒｔｅｄ ｆｕｎｃｔｉｏｎｓ＞＋≡

ｅｘｔｅｒｎ ｖｏｉｄ ｓｋｉｐｔｏ ＡＲＧＳ（（ｉｎｔ ｔｏｋ，ｃｈａｒ ｓｅｔ［］））；

skipto不斷跳過(guò)輸入單詞，直至遇到單詞t（t要么與tok相等，要么使得kind[t]包含在無(wú)效終結(jié)符數(shù)組set中）。kind[t]是一個(gè)單詞編碼，它意味著一個(gè)含有t的集合。例如，編碼ID表示集合FIRST(expression)，kind[t]與ID相等。利用數(shù)組{ID，0}作為函數(shù)skipto的第二個(gè)參數(shù)，指示函數(shù)跳過(guò)若干個(gè)無(wú)關(guān)的單詞直至找到一個(gè)屬于FIRST(expression)的元素。表2概括了所有的kind值。

對(duì)于表中未提及的單詞，kind[t]就等于t?？傊绻鹴與tok相等，或者t屬于kind[t]，那么skipto將不會(huì)跳過(guò)任何單詞。

表2數(shù)組kind的值

3.3 限制重復(fù)報(bào)告錯(cuò)誤信息

當(dāng)我們?cè)诰帉?xiě)程序時(shí)，有些錯(cuò)誤會(huì)不止一次地出現(xiàn)，比如語(yǔ)句的最后忘記寫(xiě)“；”，實(shí)際上這種錯(cuò)誤沒(méi)有必要重復(fù)報(bào)告，這就要求語(yǔ)法分析具有制止重復(fù)報(bào)告錯(cuò)誤信息的功能。我們?cè)O(shè)計(jì)了一張出錯(cuò)名字表，一旦發(fā)現(xiàn)一個(gè)出錯(cuò)名字后，先查出錯(cuò)名字表，查找有無(wú)同名且同性質(zhì)的出錯(cuò)名字，如果有，則不再報(bào)告此錯(cuò)誤，否則將此出錯(cuò)名字添加進(jìn)名字表并顯示出錯(cuò)信息。

4 總結(jié)

錯(cuò)誤處理能力是衡量編譯器性能的重要方面，本文列舉了一些編譯系統(tǒng)在實(shí)際應(yīng)用中的案例，說(shuō)明了系統(tǒng)的錯(cuò)誤處理能力體現(xiàn)在編譯過(guò)程的各個(gè)環(huán)節(jié)，不可忽視。系統(tǒng)的錯(cuò)誤處理能力在幫助編程人員盡快修改程序方面起到了非常重要的作用，是編譯系統(tǒng)的一個(gè)重要組成部分。因此，我們應(yīng)盡量地把它設(shè)計(jì)完善，方便用戶(hù)的使用。

參考文獻(xiàn)：

[1] 黃賢英，劉貞，劉全利. “編譯原理”課程的地位及教改思路[J].重慶科技學(xué)院學(xué)報(bào)(社會(huì)科學(xué)版)，2005，(3):

103-105.

[2] 王雷，劉志成，等. 編譯原理課程設(shè)計(jì)[M]. 北京：機(jī)械工業(yè)出版社，2005.

收稿日期：2006-09-01

作者簡(jiǎn)介：劉慧(1978-)，女，講師，博士研究生，主講課程為編譯原理、信息檢索，主要研究方向?yàn)閃eb信息挖掘與檢索、知識(shí)發(fā)現(xiàn)。