盡管使用 Flex 和 Bison 生成程序非常簡(jiǎn)單，但是要讓這些程序產(chǎn)生用戶友好的語(yǔ)法和語(yǔ)義錯(cuò)誤消息卻很困難。本文將介紹 Flex 和 Bison 的錯(cuò)誤處理特性，并展示如何使用它們，然后詳細(xì)介紹它們的一些缺陷。
簡(jiǎn)介
正如 UNIX? 開發(fā)人員所了解的那樣，Flex 和 Bison 的功能非常強(qiáng)大，非常適合開發(fā)詞法和語(yǔ)法解析器，尤其是語(yǔ)言編譯器和解釋器。如果我們不熟悉它們所實(shí)現(xiàn)的工具 —— 分別是 Lex 和 Yacc —— 可以參考一下本文 參考資料一節(jié)中有關(guān) Flex 和 Bison 文檔的鏈接，以及其他介紹這兩個(gè)程序的文章。
本文介紹了更高級(jí)的一些主題：用來在編譯器和解釋器中更好地實(shí)現(xiàn)錯(cuò)誤處理能力的特性和技術(shù)。為了展示這些技術(shù)，我使用了一個(gè)示例程序 ccalc，它基于 Bison 手冊(cè)中的計(jì)算機(jī)實(shí)現(xiàn)了一個(gè)增強(qiáng)的計(jì)算器。我們可以從本文后面下載 一節(jié)下載 ccalc 和相關(guān)文件。
增強(qiáng)包括使用了很多變量。在 ccalc 中，變量是通過在初始化中首次使用時(shí)定義的，例如 a = 3。如果變量是在初始化之前使用的，那就會(huì)產(chǎn)生語(yǔ)義錯(cuò)誤，使用值為 0 來創(chuàng)建這個(gè)變量，并打印一條消息。
示例源文件
示例源代碼中包括 7 個(gè)文件：
ccalc.c：主程序，以及一些進(jìn)行輸入、輸出和錯(cuò)誤處理的函數(shù)
ccalc.h：包括了對(duì)所有模塊的定義
cmath.c：數(shù)學(xué)函數(shù)
parse.y：Bison 使用的輸入文法
lex.l：Flex 的輸入
makefile：簡(jiǎn)單的 makefile
defs.txt：示例輸入文件
這個(gè)程序接收兩個(gè)參數(shù)：
-debug：產(chǎn)生調(diào)試輸出
filename：輸入文件名；默認(rèn)值為 defs.txt
Bison 使用的設(shè)置
為了處理變量名和實(shí)際值，Bison 的語(yǔ)義類型必須進(jìn)行增強(qiáng)：
清單 1. 更好的 Bison 語(yǔ)義類型
/* generate include-file with symbols and types */
%defines
/* a more advanced semantic type */
%union {
double value;
char *string;
}
有些文法規(guī)則可以產(chǎn)生特定的語(yǔ)義類型，這需要像清單 2 中一樣對(duì) Bison 進(jìn)行聲明。要獲得一個(gè)可移植性更好的 Bison 文法版本，我們需要重新定義 +-*/() 符號(hào)。下面這個(gè)例子沒有使用左括號(hào) (，而是使用了結(jié)束符符號(hào) LBRACE，這是由詞法分析提供的。另外，操作符的優(yōu)先順序也必須進(jìn)行聲明。
對(duì)于 Flex 來說，所生成的代碼通常都依賴于平臺(tái)所使用的代碼頁(yè)（codepage）。盡管我們可以使用其他代碼頁(yè)，但是必須要對(duì)輸入進(jìn)行轉(zhuǎn)換。因此與 Bison 代碼不同，Flex 代碼尚不能進(jìn)行移植。
清單 2. Bison 聲明
/* terminal symbols */
%token <string> IDENTIFIER
%token <value> VALUE
%type <value> expression
/* operator-precedence
* top-0: -
* 1: * /
* 2: + -
*/
%left ADD SUB
%left MULT DIV
%left NEG
%start program
這段文法與 Bison 手冊(cè)非常類似，不同之處在于它使用了名字作為終端符號(hào)和標(biāo)識(shí)符的簡(jiǎn)寫形式。標(biāo)識(shí)符是在賦值語(yǔ)句中進(jìn)行定義和初始化的，并且可以在任何允許使用的地方使用。清單 3 給出了一個(gè)示例文法：
清單 3. 示例 Bison 文法
program
: statement SEMICOLON program
| statement SEMICOLON
| statement error SEMICOLON program
;
statement
: IDENTIFIER ASSIGN expression
| expression
;
expression
: LBRACE expression RBRACE
| SUB expression %prec NEG
| expression ADD expression
| expression SUB expression
| expression MULT expression
| expression DIV expression
| VALUE
| IDENTIFIER
;
program 的第三個(gè)輸出讓這個(gè)分析程序可以獲得錯(cuò)誤，從中搜索分號(hào)，然后繼續(xù)執(zhí)行（通常錯(cuò)誤對(duì)于解析器來說都是非常嚴(yán)重的）。
為了讓這個(gè)例子更加有趣，規(guī)則體中的真正數(shù)學(xué)函數(shù)都是以單獨(dú)函數(shù)的形式實(shí)現(xiàn)的。在進(jìn)行高級(jí)文法分析時(shí)，我們要盡量保證規(guī)則簡(jiǎn)短，并使用函數(shù)來實(shí)現(xiàn)一些不會(huì)直接處理解析的過程：
清單 4. 使用單獨(dú)的函數(shù)來實(shí)現(xiàn)數(shù)學(xué)規(guī)則
| expression DIV expression
{
$$ = ReduceDiv($1, $3);
}
最后，函數(shù) yyerror() 必須要進(jìn)行定義。這個(gè)函數(shù)是在所生成的解析器檢測(cè)到語(yǔ)法錯(cuò)誤時(shí)調(diào)用的，它又會(huì)調(diào)用一個(gè)小函數(shù) PrintError()，后者會(huì)打印增強(qiáng)的錯(cuò)誤消息。詳細(xì)內(nèi)容請(qǐng)參看源代碼。
Flex 的設(shè)置
Flex 所生成的詞法分析器必須要根據(jù)語(yǔ)義類型提供終止符號(hào)。清單 5 定義了空格、實(shí)際值、標(biāo)識(shí)符和符號(hào)所使用的語(yǔ)法。
清單 5. 示例 Flex 規(guī)則
[
]+ {
/* eat up whitespace */
}
{DIGIT}+ {
yylval.value = atof(yytext);
return VALUE;
}
{DIGIT}+"."{DIGIT}* {
yylval.value = atof(yytext);
return VALUE;
}
{DIGIT}+[eE]["+""-"]?{DIGIT}* {
yylval.value = atof(yytext);
return VALUE;
}
{DIGIT}+"."{DIGIT}*[eE]["+""-"]?{DIGIT}* {
yylval.value = atof(yytext);
return VALUE;
}
{ID} {
yylval.string = malloc(strlen(yytext)+1);
strcpy(yylval.string, yytext);
return IDENTIFIER;
}
"+" { return ADD; }
"-" { return SUB; }
"*" { return MULT; }
"/" { return DIV; }
"(" { return LBRACE; }
")" { return RBRACE; }
";" { return SEMICOLON; }
"=" { return ASSIGN; }
為了幫助調(diào)試，我們?cè)诔绦蜻\(yùn)行的末尾把所有已知的變量及其當(dāng)前內(nèi)容都打印了出來。
使用普通錯(cuò)誤消息的例子
使用下面的輸入（其中稍微進(jìn)行了排版）來編譯并運(yùn)行這個(gè)示例解析器程序 ccalc：
清單 6. 數(shù)學(xué)解析器的示例輸入
a = 3;
3 aa = a * 4;
b = aa / ( a - 3 );
輸出結(jié)果如下所示：
清單 7. 數(shù)學(xué)解析器的示例輸出
Error 'syntax error'
Error: reference to unknown variable 'aa'
division by zero!
final content of variables
Name------------------ Value----------
'a ' 3
'b ' 3
'aa ' 0
這個(gè)輸出結(jié)果并非非常有用，因?yàn)樗]有顯示問題到底在什么地方。這在下一節(jié)中會(huì)進(jìn)行介紹。
擴(kuò)展 Bison 可以更好地處理錯(cuò)誤消息
Bison 的最主要的特性在 Bison 手冊(cè)中隱藏的很深，就是它可以通過使用 YYERROR_VERBOSE 宏在產(chǎn)生語(yǔ)法錯(cuò)誤的情況下生成更有意義的錯(cuò)誤消息。
普通的 'syntax error' 消息如下：
Error 'syntax error, unexpected IDENTIFIER, expecting SEMICOLON'
這條消息對(duì)于調(diào)試更為合適。
更好的輸入函數(shù)
使用原來的錯(cuò)誤消息，很難判斷語(yǔ)義的錯(cuò)誤。當(dāng)然，這個(gè)例子非常容易修復(fù)，因?yàn)槲覀兞⒓淳涂梢哉页鲇绣e(cuò)誤的那一行。在更加復(fù)雜的語(yǔ)法和對(duì)應(yīng)輸入中，這可能并不簡(jiǎn)單。讓我們編寫一個(gè)輸入函數(shù)來從文件中讀取相應(yīng)的行。
Flex 具有一個(gè)非常有用的宏 YY_INPUT，它負(fù)責(zé)為符號(hào)解釋讀入數(shù)據(jù)。我們可以在 YY_INPUT 宏中添加一個(gè)對(duì) GetNextChar() 函數(shù)的調(diào)用，后者從文件中讀取數(shù)據(jù)，并保留了下一個(gè)要讀取的字符的位置信息。GetNextChar() 使用了一個(gè)緩沖區(qū)來存放一行輸入。這兩個(gè)變量保存了當(dāng)前行號(hào)和該行中下一個(gè)字符的位置：
清單 8. 更好的 Flex YY_INPUT 宏
#define YY_INPUT(buf,result,max_size) {
result = GetNextChar(buf, max_size);
if ( result <= 0 )
result = YY_NULL;
}
使用這個(gè)增強(qiáng)的錯(cuò)誤打印函數(shù) PrintError()（在前面討論過，它可以很好地顯示有問題的輸入行，完整的 PrintError() 源代碼請(qǐng)參看 示例源代碼），我們就具有了一個(gè)用戶友好的消息，它顯示了下一個(gè)字符的位置：
清單 9. 更好的 Flex 錯(cuò)誤：字符位置
|....+....:....+....:....+....:....+....:....+....:....+
1 |a = 3;
2 |3 aa = a * 4;
...... !.....^
Error: syntax error, unexpected IDENTIFIER, expecting SEMICOLON
3 |b = aa / ( a - 3 );
...... !.......^
Error: reference to unknown variable 'aa'
...... !.................^
Error: division by zero!
這個(gè)示例函數(shù)可以從其他函數(shù)（例如 ReduceDiv()）中進(jìn)行調(diào)用，從而打印語(yǔ)義錯(cuò)誤，例如 division by zero 或 unknown identifiers。
如果我們希望標(biāo)記一下最后使用的符號(hào)，就可以對(duì) Flex 規(guī)則進(jìn)行擴(kuò)展，并修改錯(cuò)誤的打印。函數(shù) BeginToken() 和 PrintError()（二者都可以在示例源代碼中找到）是關(guān)鍵：BeginToken() 是由每條規(guī)則進(jìn)行調(diào)用的，這樣它就可以記住每個(gè)符號(hào)的開始和結(jié)束，每次打印錯(cuò)誤時(shí)都會(huì)調(diào)用 PrintError()。這樣，我們就可以生成一條有用的消息了，例如：
清單 10. 更好的 Flex 錯(cuò)誤：表示確切的符號(hào)位置
2 |3 aa = a * 4;
...... !..^^............
Error: syntax error, unexpected IDENTIFIER, expecting SEMICOLON
缺點(diǎn)
所生成的詞法解析器可能會(huì)在檢測(cè)到某個(gè)符號(hào)之前讀入多個(gè)字符。因此，這個(gè)過程不可能精確地顯示確切的位置。它最終取決于為 Flex 所提供的規(guī)則。規(guī)則越復(fù)雜，位置的精確程度就越低。這個(gè)例子中的規(guī)則可以由 Flex 通過提前查找一個(gè)字符來進(jìn)行處理，這會(huì)讓位置的預(yù)測(cè)更加精確。
Bison 的定位機(jī)制
下面讓我們來看一下 division by zero 這個(gè)錯(cuò)誤。最后一次符號(hào)讀?。ńY(jié)束括號(hào)）并不是這個(gè)錯(cuò)誤的根源。表達(dá)式 (a-3) 的值就是 0。對(duì)于更好的錯(cuò)誤消息來說，我們需要知道表達(dá)式的位置。要實(shí)現(xiàn)這種功能，我們可以在 YYLTYPE 類型的全局變量 yylloc 中提供這個(gè)符號(hào)的確切位置。使用宏 YYLLOC_DEFAULT（請(qǐng)參看 Bison 文檔 中默認(rèn)的定義），Bison 可以計(jì)算出某個(gè)表達(dá)式的位置。
記住，只有當(dāng)您在文法中使用位置時(shí)才會(huì)定義類型。這是一個(gè)常見的錯(cuò)誤。
默認(rèn)的位置類型 YYLTYPE 如清單 11 所示。我們可以對(duì)這個(gè)類型重新進(jìn)行定義，使其包括更多信息，例如 Flex 所讀取的文件名。
清單 11. 默認(rèn)位置類型 YYLTYPE
typedef struct YYLTYPE
{
int first_line;
int first_column;
int last_line;
int last_column;
} YYLTYPE;
在上一節(jié)中，我們看到了 BeginToken() 函數(shù)，它是在新符號(hào)開始時(shí)調(diào)用的。此時(shí)就應(yīng)該存儲(chǔ)這個(gè)位置了。在我們的例子中，一個(gè)符號(hào)不能跨越多行，因此 first_line 和 last_line 是相同的，它們都保存了當(dāng)前的行號(hào)。其他屬性有符號(hào)的起點(diǎn)（first_column）和終點(diǎn)（last_column），這是通過符號(hào)的起點(diǎn)和長(zhǎng)度計(jì)算出來的。
要使用這個(gè)位置，我們必須對(duì)規(guī)則處理函數(shù)進(jìn)行處理，如清單 12 所示。符號(hào) $3 的位置是通過 @3 進(jìn)行引用的。為了防止拷貝這個(gè)規(guī)則中的整個(gè)結(jié)構(gòu)，我們生成了一個(gè)指針 &@3。這看起來可能有點(diǎn)奇怪，但卻是正確的。
清單 12. 記住規(guī)則中的位置
| expression DIV expression
{
$$ = ReduceDiv($1, $3, &@3);
}
在處理函數(shù)中，我們獲得了一個(gè)指向保存了位置信息的 YYLTYPE 結(jié)構(gòu)的指針，這樣可以生成一條很好的錯(cuò)誤消息。
清單 13. 在 ReduceDiv 中使用保存的位置
extern
double ReduceDiv(double a, double b, YYLTYPE *bloc) {
if ( b == 0 ) {
PrintError("division by zero! Line %d:c%d to %d:c%d",
bloc->first_line, bloc->first_column,
bloc->last_line, bloc->last_column);
return MAXFLOAT;
}
return a / b;
}
現(xiàn)在錯(cuò)誤消息可以幫助我們來定位問題了。除零操作錯(cuò)誤在第 3 行的第 10 列到 18 列之間。
清單 14. 更好的 ReduceDiv() 錯(cuò)誤消息
|....+....:....+....:....+....:....+....:....+....:....+
1 |a = 3;
2 |3 aa = a * 4;
...... !..^^...........
Error: syntax error, unexpected IDENTIFIER, expecting SEMICOLON
3 |b = aa / ( a - 3 );
...... !....^^...............
Error: reference to unknown variable 'aa'
...... !.................^..
Error: division by zero! Line 3:10 to 3:18
final content of variables
Name------------------ Value----------
'a ' 3
'b ' 3.40282e+38
'aa ' 0
結(jié)束語(yǔ)
Flex 和 Bison 是用來解析文法的一對(duì)功能強(qiáng)大的組合。通過使用本文中介紹的技巧，我們可以構(gòu)建更好的解釋器，它們可以生成像您自己喜歡的編譯器中一樣的有用的、容易理解的錯(cuò)誤消息。