編譯原理中處理語法錯誤問題的研究

摘要：本文分析了編譯系統以及其錯誤處理能力對于程序設計語言的重要性，對其中處理語法錯誤問題進行了深入研究，并從語法錯誤的診察與報告，到利用遞歸下降分析法對錯誤進行恢復和糾正處理，直至最后的限制重復報告錯誤信息及其中涉及的關鍵技術進行了介紹，從而幫助學習者和開發者牢固掌握相關的理論和技術。

關鍵詞：編譯系統；語法錯誤處理；遞歸下降分析法

中圖分類號：G642.41 文獻標識碼：B

文章編號：1672-5913（2007）06-0040-03

1 前言

在計算機應用領域，目前多數用戶都是通過高級語言實現所需要的計算。而對于任何高級語言來說，其編譯系統內容豐富，具有嚴密的邏輯性，對提高學習者和開發者的計算機軟件素質具有很大作用，使其不但能認識計算機信息處理的實質，還可以綜合運用所學的軟件設計技術來分析解決問題[1]。因此，編譯系統是計算機系統軟件最重要的組成部分之一，也是用戶最直接關心的工具之一，它不但要接受程序語言的所有標準定義，以便源代碼實現跨平臺的可移植性，還必須生成高效、正確的目標代碼。因此編譯系統本身是一個大而復雜的程序，值得我們深入分析研究。

我們知道，在編譯原理的學習和編譯系統的構建過程中，語法分析是其中最為重要的一個組成部分。而在實際的編譯系統中，語法分析器的錯誤處理能力與其構造原理和技術一樣重要，這通常是編譯原理教學環節中容易忽視的地方，不利于學習者進行實際的編譯系統的開發工作。因此，本文對C++編譯系統中遞歸下降的語法分析過程進行了研究，找到了發現并糾正語法錯誤問題的有效方法。

2 語法錯誤

編程人員在編寫程序時，很難一次就將程序寫的完美無誤，尤其是一些比較復雜的程序，往往會存在程序錯誤。程序錯誤的種類有很多，比如違反語言的語法和語義規定的錯誤，源程序超出了計算機系統的某種限制而引發的錯誤，等等。其中語法錯誤是指源程序中含有不符合語法規則的成分時所產生的錯誤，一般是有關語言結構上的錯誤，如單詞拼寫錯、表達式中缺少操作數、begin和end不匹配等。

語法分析結果的質量將直接影響到編譯系統后期各階段的工作，因此，為了幫助編程人員發現并糾正這一階段可能出現的錯誤，編譯系統的語法分析器應該具有錯誤處理的能力，其不但可以對語法上正確的源程序進行正確的編譯，同時還能夠對有錯誤的源程序報錯，甚至在一定程度上對錯誤進行改正[2]。當然，進行出錯處理是件很麻煩的事，想象一個設計良好的編譯調試環境，比如Visual Studio，我們在用它開發編譯程序時，不光可以知道哪一句錯了，而且可以獲得出錯的原因。

3 語法錯誤處理技術

3.1 錯誤的診察與報告

語法錯誤可以采用系統的方式解決，不依賴于出現的上下文。這些錯誤比較容易發現，通常出現在表1所示的翻譯代碼error中。

表1分析函數翻譯代碼

這里，編譯系統使用EBNF文法描述語言，為每個非終結符計算FIRST集合和FOLLOW集合，編寫分析函數將非終結符的每個產生式翻譯成可執行代碼。翻譯的規則可由文法產生式的可能形式導出。對每一種產生式形式α，用T(α)表示α的翻譯代碼，全局變量t表示從詞法分析器讀入的當前單詞，調用函數gettok可以獲取下一個輸入單詞，此外，

當然，表1的代碼也可用其他代碼序列表示，以解決有時會出現的代碼冗長問題。

編譯系統在查找到源程序中的語法錯誤后，要對這些錯誤進行報告，報告的主要內容是錯誤發生的位置以及錯誤的性質。有了這兩點內容，編程人員就可以比較方便地確定錯誤的性質并對其進行改正。文本所采用的錯誤報告方式為：每發現一處錯誤，就把該錯誤信息打印出來，包括源程序的名字、錯誤所在行、錯誤的具體內容等，同時用箭頭指向出錯的位置。例如，對于程序段：

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

cout>>i

其中的錯誤，編譯系統將報告如下錯誤信息：

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”是錯誤所在的行的號碼，“missing ';' before ')'”表示具體的錯誤信息，下面的“location”指錯誤在PrintTest類中，接下來該信息還顯示了源程序中含有錯誤的代碼行，并用箭頭“^”指向出錯位置，最后指出錯誤的總數，這里是2個。

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

語法錯誤不難發現，但要修正錯誤并非易事。當然，不能說一發現錯誤就停止分析，這樣做顯然不合理，錯誤處理的大部分工作用于對錯誤進行適當的處理——錯誤恢復，以便系統分析過程可以繼續下去。

語法錯誤的恢復方法是通過對輸入程序添加遺漏的單詞或忽略某些單詞，從而將錯誤的輸入轉換為合法的句子。遺憾的是，找到合適的恢復方法非常困難，因為編程人員的意圖有時候是很難推斷出來的，這種推測在一定程度上增加了編譯系統的復雜程度，如果選擇錯誤將導致分析程序混亂，甚至導致后面本來文法上正確的輸入也產生大量的語法錯誤。

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

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

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

該函數檢查下一個單詞是否等于tok，如果不等，則發出提示信息，并跳過當前單詞，反復執行直至遇到一個屬于{tok}∪set的單詞。set集合包含了所有不能忽略的元素，保證輸入不會無限地忽略。

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

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

ｉｆ（ｔ＝＝ｔｏｋ）

ｔ＝ｇｅｔｔｏｋ（）；

ｅｌｓｅ｛

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

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

ｉｆ（ｔ＝＝ｔｏｋ）

ｔ＝ｇｅｔｔｏｋ（）；

｝

｝

函數test調用函數expect報錯，調用函數skipto跳過錯誤的單詞。skipto定義如下：

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

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

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

對于表中未提及的單詞，kind[t]就等于t。總之，如果t與tok相等，或者t屬于kind[t]，那么skipto將不會跳過任何單詞。

表2數組kind的值

3.3 限制重復報告錯誤信息

當我們在編寫程序時，有些錯誤會不止一次地出現，比如語句的最后忘記寫“；”，實際上這種錯誤沒有必要重復報告，這就要求語法分析具有制止重復報告錯誤信息的功能。我們設計了一張出錯名字表，一旦發現一個出錯名字后，先查出錯名字表，查找有無同名且同性質的出錯名字，如果有，則不再報告此錯誤，否則將此出錯名字添加進名字表并顯示出錯信息。

4 總結

錯誤處理能力是衡量編譯器性能的重要方面，本文列舉了一些編譯系統在實際應用中的案例，說明了系統的錯誤處理能力體現在編譯過程的各個環節，不可忽視。系統的錯誤處理能力在幫助編程人員盡快修改程序方面起到了非常重要的作用，是編譯系統的一個重要組成部分。因此，我們應盡量地把它設計完善，方便用戶的使用。

參考文獻：

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

103-105.

[2] 王雷，劉志成，等. 編譯原理課程設計[M]. 北京：機械工業出版社，2005.

收稿日期：2006-09-01

作者簡介：劉慧(1978-)，女，講師，博士研究生，主講課程為編譯原理、信息檢索，主要研究方向為Web信息挖掘與檢索、知識發現。