FLEX

什么是FLEX？它是一個自動化工具，可以按照定義好的規(guī)則自動生成一個C函數(shù)yylex()，也成為掃描器（Scanner）。這個C函數(shù)把文本串作為輸入，按照定義好的規(guī)則分析文本串中的字符，找到符合規(guī)則的一些字符序列后，就執(zhí)行在規(guī)則中定義好的動作（Action）。例如在規(guī)則中可以這樣定義：如果遇到一個換行字符\n，那么就把行計(jì)數(shù)器的值加一。

Flex文件就是一個文本文件，內(nèi)容包括定義好的一系列詞法規(guī)則。文件的命名習(xí)慣上以小寫字母l(L)來作為文件后綴。如果為了清晰，也可以用.flx或者.flex作為文件的后綴名。Flex文件完成后，就執(zhí)行下列命令：

$ flex example.flex

這個命令執(zhí)行后將生成一個C文件，默認(rèn)文件名為lex.yy.c。這個C文件主要內(nèi)容就是函數(shù)yylex()的定義。

如果要直接將這個文件編譯成為一個可執(zhí)行程序，還有一些要注意的地方。如果在Flex文件中沒有提供main()函數(shù)的定義，那么這個C文件中不會有main()函數(shù)。此時單獨(dú)編譯這個C文件的時候，一定要加上-lfl的連接庫參數(shù)；若提供了main()函數(shù)，就不必要提供這個連接庫參數(shù)了。連接庫libfl提供了一個缺省的main函數(shù)。缺省的main()函數(shù)中只是簡單地調(diào)用yyflex()函數(shù)，而自己提供的main()函數(shù)則可以根據(jù)需要加入許多其他的處理代碼。

Flex文件

詞法規(guī)范定義文件給出了單詞構(gòu)成規(guī)則。詞法文件在習(xí)慣上用字母l(即L的小寫)來作為后綴。Flex文件由三個部分組成。或者說三個段。三個段之間用兩個%%分隔。

定義段(definitions)

%%

規(guī)則段(rules)

%%

用戶代碼段(user code)

定義段(definitions section)

定義段包含著一些簡單名字的定義(name definitions)，旨在簡化掃描器的規(guī)范。定義名字的方法如下:

name definition

名字可以由字母或下劃線開頭，后跟零個或多個字母、數(shù)字、下劃線、或短橫線。名字的定義則從其后的第一個非空白字符(non-white-space)開始直到行尾。下面是一個例子，定義了一個名字DIGIT，其定義就是指一個數(shù)字，如下所示：

DIGIT [0-9]

當(dāng)在后面引用這個名字時，用一對花括號({})括住該名字即可。它會被展開成一對圓括號括住的該名字的定義,即:

{name} 展開成 (definition)

例如：

{DIGIT}+"."{DIGIT}*

就等價(jià)于：

([0-9])+"."([0-9])*

定義段中還可以加入啟動條件(start conditions)的聲明。顧名思義，啟動條件就如同C語言中的條件編譯一樣，根據(jù)指定的啟動條件去激活一條規(guī)則，并用這條規(guī)則去匹配讀入的字符。關(guān)于啟動條件，后面還有更詳細(xì)的介紹。

規(guī)則段(rules section)

規(guī)則由模式(pattern)和動作(action)兩個部分組成。模式就是一個正則表達(dá)式，FLEX加入了一些自己的擴(kuò)展。而動作一般就是一些C語句。模式指出了一個單詞是如何構(gòu)成的，當(dāng)分析出一個符合該規(guī)則的單詞時，就執(zhí)行相應(yīng)的動作。

模式一定要位于一行的開頭處，不能有縮進(jìn)。而動作的開頭一定要與模式在同一行。當(dāng)動作是用一對花括號{}括起來時，可以將左花括號放在與規(guī)則相同的行，而其余部分則可以從下一行開始。

用戶代碼段(user code)

所有用戶代碼都被原樣拷貝到文件lex.yy.c中。在這里可以定義一些輔助函數(shù)或代碼，供掃描器yylex()調(diào)用，或者調(diào)用掃描器（一般來說就是main()了）。這一部分是可有可無的。如果沒有的話，Flex文件中第二個%%是可以省略的。

在定義段或者規(guī)則段中，任何一行有縮進(jìn)的文本或者包含在一對%{和%}之間的文本，都被原樣拷貝到最后生成的C代碼文件中（當(dāng)然%{和%}會被移走）。在書寫時%{和%}都必須在一行的開始處，不能縮進(jìn)。

在規(guī)則段中，第一條規(guī)則之前的任何未縮進(jìn)的文本或者在%{和%}之間的文本，可以用來為掃描器聲明一些本地變量和代碼。一旦進(jìn)入掃描器的代碼，這些代碼就會被執(zhí)行。規(guī)則段內(nèi)其他的縮進(jìn)的文本或者%{和%}之間的文本還是被原樣拷貝輸出，但是他們的含義是尚未有明確定義，很可能引起編譯時（compile-time）錯誤（這一特性是為了與POSIX兼容而提供的）。

在定義段中，沒有縮進(jìn)的注釋也會被原樣拷貝到最后生成的C代碼文件中，例如以/*開始的一行注釋，直到遇到*/，這中間的文本會被原樣拷貝輸出。

模式及其分類

模式采用正則表達(dá)式來書寫。正則表達(dá)式大致可以分為如下幾類（從上到下，優(yōu)先級依次遞減）：

（1）單字符匹配

* ‘x’ 匹配字符x。

* ‘.’ 匹配任意一個字符（字節(jié)），除了換行符。

* ‘[xyz]’ 匹配單個字符，這個字符是方括號中給出的字符類（character class）中的一個。

* ‘[abj-oZ]’ 匹配單個字符，這個字符是方括號中給出的字符類中的一個。與上一方式的區(qū)別是指定字符類時用到了一個范圍表示法：j-o，這表示按照26個英文字母的順序，從字母j開始一直到字母o共6個字母。這里減號（-）表示范圍。如果減號本身也要作為一個匹配字符時，最好用轉(zhuǎn)義字符（\）去除其特殊含義。由于花括號（{}）在模式中用來引用名字，以及作為模式定義之后的動作（Action）定義塊的首尾界定符，因此如果要在字符類中匹配花括號，必須用轉(zhuǎn)義字符（\）去除其特殊含義。下面這個例子定義了一個所有可打印字符的字符類：

[[:alnum:][:blank:]]\t+\-*/&!_'?@^`~$\\()%|.;[\]\{\}:,#<>=]

* ‘[^A-Z]’ 匹配單個字符，這個字符必須是方括號中給定字符類以外的字符。在方括號內(nèi)開始處的特殊符號（^）表示否定。當(dāng)字符^不在字符類的開始處時，并不具有特殊含義，而是一個普通字符。

* ‘[^A-Z\n]’ 匹配單個字符，這個字符不可以是方括號中給出的字符類中的字符。與上一方式的不同在于，這里多了一個換行符，也就是說所匹配的字符不能是26個大寫字母，也不能是換行符。

根據(jù)上面的描述，在表達(dá)字符分類時，除了直接用字符以及字符范圍來表達(dá)外，還有一種叫做字符類表達(dá)式的，也有同樣的作用，常見的一些表達(dá)式如下：

[:alnum:] [:alpha:] [:blank:] [:cntrl:] [:digit:] [:graph:]

[:lower:] [:print:] [:punct:] [:space:] [:upper:] [:xdigit:]

每一個表達(dá)式都指示了一個字符分類，而且其名稱與標(biāo)準(zhǔn)C函數(shù)isXXXX的名字對應(yīng)。例如，[:alnum:]就指示了那些經(jīng)由函數(shù)isalnum()檢查后返回true的字符，也就是任何的字母或者數(shù)字。注意，有些系統(tǒng)上沒有給出C函數(shù)isblank()的定義，所以flex自己定義了[:blank:]為一個空格或者一個tab。

下面所舉的幾個例子，都是等價(jià)的：

[[:alnum:]]

[[:alpha:][:digit:]]

[[:alpha:]0-9]

[a-zA-Z0-9]

應(yīng)該注意字符類表達(dá)式的寫法。一個字符類表達(dá)式是由一對[:和:]包住的，作為一個整體，在書寫時不可與外層的[]混淆。

（2）重復(fù)模式的匹配

* ‘r*’ r是一個正則表達(dá)式，特殊字符`*'表示0個或多個。因此這個模式表示匹配0個或多個r。

* ‘r+’ r是一個正則表達(dá)式，特殊字符`+'表示1個或多個。因此這個模式表示匹配1個或多個r。

* ‘r?’ r是一個正則表達(dá)式，特殊字符`?'表示0個或1個。因此這個模式表示匹配0個或1個r。（從另一個角度看，就是說模式r是可選的）

* ‘r{2,5}’ r是一個正則表達(dá)式，{2,5}表示2個到5個。因此這個模式表示匹配2個到5個r。也就是說可以匹配`rr'，`rrr'，`rrrr'，`rrrrr'四種重復(fù)的模式。

* ‘r{2,}’ r是一個正則表達(dá)式，{2,}省略了第二個數(shù)字，表示至少2個，不設(shè)上限。因此這個模式表示匹配2個及以上個r。也就是說至少可以匹配`rr'，還可以匹配`rrr'，`rrrr'等無限多種重復(fù)的模式。

* ‘r{4}’ r是一個正則表達(dá)式，{4}只有一個數(shù)字，表示4個。因此這個模式確切地匹配4個r，即`rrrr'。

（3）名字替換

* ‘{name}’ 這里name就是在前面的定義段給出的名字。這個模式將用這個名字的定義來匹配。

（4）平凡（plain）文本串的匹配

* ‘“[xyz]\″foo”’ 這個模式用來確切地匹配文本串：[xyz]\″foo。注意最外層的單引號所包含的是整個模式表達(dá)式，也就是說，當(dāng)希望匹配字串[xyz]\″foo時，在書寫規(guī)則時該字串必須用雙引號括住。

（5）特殊單字符的匹配

* ‘\x’ 當(dāng)x是一個`a'，`b'，`f'，`n'，`r'，`t'或`v'時，它就解釋為ANSI-C中的\x。否則就仍然作為一個普通字符x（一般用于諸如`*'字符的轉(zhuǎn)義字符）。

* ‘\0’ 匹配一個NUL字符（ASCII碼值為0）。

* ‘\123’ 匹配一個字符，其值用八進(jìn)制表示為123。

* ‘\x2a’ 匹配一個字符，其值用十六進(jìn)制表示為2a。

（6）組合模式的匹配

* ‘(r)’ 匹配規(guī)則表達(dá)式r，圓括號可以提高其優(yōu)先級。

* ‘rs’ 匹配規(guī)則表達(dá)式r，其后緊跟著表達(dá)式s。這稱為聯(lián)接(concatenation)。

* ‘r|s’ 或者匹配規(guī)則表達(dá)式r，或者匹配表達(dá)式s。

* ‘r/s’ 匹配模式r，但是要求其后緊跟著模式s。當(dāng)需要判斷本次匹配是否為“最長匹配（longest match）時，模式s匹配的文本也會被包括進(jìn)來，但完成判斷后開始執(zhí)行對應(yīng)的動作（action）之前，這些與模式s相配的文本會被返還給輸入。所以動作（action）只能看到模式r匹配到的文本。這種模式類型叫做尾部上下文（trailing context）。（有些‘r/s’組合是flex不能識別的；請參看后面deficiencies/bugs一節(jié)中的dangerous trailing context的內(nèi)容。）

* ‘^r’ 匹配模式r，但是這個模式只出現(xiàn)在一行的開始處。也就是說，剛開始掃描時遇到的，或者說在剛掃描完一個換行字符后緊接著遇到的。

* ‘r$’ 匹配模式r，但是這個模式只在一行的尾部。也就是說，該模式就出現(xiàn)在換行之前。這個模式等價(jià)于r/\n。注意，flex中的換行（newline）的概念，就是C編譯器中所使用的\n，flex也采用同樣的符號和解釋。在DOS系統(tǒng)中，可能必須由你自己濾除輸入中的\r，或者明確地在模式中寫成r/\r\n來代替r$。（在unix系統(tǒng)中換行是用一個字節(jié) \n 表示的，而DOS/Windows則采用兩個字節(jié) \r\n來表示換行。）

（7）有啟動條件（Start Condition）的模式匹配

* ‘<s>r’ 匹配模式r，但需要啟動條件s（后面后關(guān)于啟動條件的討論）。模式‘<s1,s2,s3>r’是類似的，匹配模式r，只要有三個啟動條件s1，s2，s3中的任一個即可。（啟動條件簡單來說，類似于C語言中的條件編譯，滿足了某個條件才啟動這個模式參與匹配，否則不會啟動該模式參與匹配。）

* ‘<*>r’ 匹配模式r，在任何啟動條件下都參與匹配，即使是排斥性的條件。

[上述還需要從實(shí)踐中體會其含義]

（8）文件尾匹配

* ‘<<EOF>>’ 匹配文件尾，即遇到了文件尾部。一般說來，都應(yīng)該在模式中加入文件尾模式。這樣可以有機(jī)會在文件掃描完成時增加一些額外的處理。

* ‘<s1,s2><<EOF>>’ 在有啟動條件s1或者s2的情況下，匹配文件尾部。

一些常見規(guī)則的編寫（待續(xù)）

（1）雙引號字符串。

[\"]({SAFECHAR}|{RESTCHAR}|[_])*[\"]

這里需要注意的地方是中間的重復(fù)模式的寫法：(r)*。r可以是一個組合模式。中間的兩個名稱SAFECHAR和RESTCHAR是在定義段給出的兩個字符類。

[此處應(yīng)在實(shí)用中不斷添加]

=========================================

創(chuàng)建一個簡單的掃描器

下列例子來自于Flex的手冊。并在Windows+Cygwin+bison+flex+gcc的環(huán)境下編譯運(yùn)行。

(1) 編輯Flex語法文件。

/* name: example.flex */

int num_lines = 0, num_chars = 0;

%%

\n ++num_lines; ++num_chars;

. ++num_chars;

%%

int main()

{

yylex();

printf("# of lines = %d, # of chars = %d\n", num_lines, num_chars);

return 0;

}

(2) 生成掃描器的C文件。

$ flex example.flex

The output is lex.yy.c

(3) 編譯生成的C文件。

編譯時失敗，出現(xiàn)了如下的問題：

# gcc -g -Wall -lfl -o scan lex.yy.c

lex.yy.c:959: warning: 'yyunput' defined but not used

/cygdrive/c/DOCUME~1/ADMINI~1.78B/LOCALS~1/Temp/ccHwCWNb.o: In function `main':

/cygdrive/c/home/sandbox/flex_exam_1/example.l:9: multiple definition of `_main'

/usr/lib/gcc/i686-pc-cygwin/3.4.4/../../../libfl.a(libmain.o):(.text+0x0): first defined here

/cygdrive/c/DOCUME~1/ADMINI~1.78B/LOCALS~1/Temp/ccHwCWNb.o: In function `yylex':

/cygdrive/c/home/sandbox/flex_exam_1/lex.yy.c:692: undefined reference to `_yywrap'

/cygdrive/c/DOCUME~1/ADMINI~1.78B/LOCALS~1/Temp/ccHwCWNb.o: In function `input':

/cygdrive/c/home/sandbox/flex_exam_1/lex.yy.c:1041: undefined reference to `_yywrap'

collect2: ld returned 1 exit status

上述消息指出兩個問題：

（1）函數(shù)yywrap沒有定義。

（2）自定義函數(shù)main與連接庫fl中的定義沖突了。

第一個問題的解決辦法是在第一段（定義段）中加上一個選項(xiàng)指令：

%option noyywrap

第二個問題的解決辦法就是用gcc編譯時不連接fl庫，如下所示：

# flex example.flex

# ls

example.flex lex.yy.c

# gcc -g -Wall -o scan lex.yy.c

lex.yy.c:977: warning: 'yyunput' defined but not used

# ls

example.flex lex.yy.c scan.exe

# ./scan.exe

789

234

345# of lines = 2, # of chars = 11

修改過的代碼如下：

%option noyywrap <==== 防止出現(xiàn)yywrap的問題

%{

int num_lines = 0, num_chars = 0;

%}

%%

\n ++num_lines; ++num_chars;

. ++num_chars;

%%

int main()

{

yylex();

printf("# of lines = %d, # of chars = %d\n",

num_lines, num_chars);

return 0;

}

更改掃描器yylex()的名字

我們還可以更改Flex自動生成的詞法分析函數(shù)yylex()的名字、參數(shù)以及返回值，也就是說yylex這個名字僅僅是一個默認(rèn)的名稱，是可以改成其他名稱的。方法很簡單，只需要對宏YY_DECL做一個重定義即可：

#define YY_DECL float lexscan (float a, float b)

上述的宏定義就表明：當(dāng)運(yùn)行Flex生成C代碼時，詞法分析函數(shù)的名字叫做lexscan（不再是yylex了），有兩個浮點(diǎn)型參數(shù)a和b，函數(shù)的返回值是浮點(diǎn)型。

如果與Bison聯(lián)用的話，還是不要更改的好，因?yàn)?font>Bison要求詞法分析函數(shù)的名稱是yylex。[應(yīng)該也是可以改的，但其實(shí)際的方法還需在實(shí)踐中得來。]

詞法分析函數(shù)yylex()會使用全局變量yyin讀取字符。

一些思考

（1）在H248協(xié)議的BNF文本中，需要分析很多的數(shù)字，有十六進(jìn)制的，有十進(jìn)制的，有長的數(shù)字也有短的數(shù)字。雖然在H248協(xié)議看來，各種不同的數(shù)字有著不同的意義，但是在Flex詞法掃描器看來，它們有什么不同呢？特別是同樣的一個0xab這樣的只有兩位數(shù)字的十六進(jìn)制數(shù)，在H248協(xié)議和BISON看來，其有不同的含義和類型，但是在Flex看來卻沒有什么不同。假設(shè)Bison分別將其定義為Token_A和Token_B，那么當(dāng)Flex分析出這么一個單詞時，返回給Bison的數(shù)字類型是A還是B？

（2）在H248協(xié)議中，有一種表達(dá)式是由多個參數(shù)組成的，其中每個參數(shù)至多出現(xiàn)一次，且參數(shù)間次序是任意的。此外其中有兩個參數(shù)是必須的。這種情況下如何給出Bison文法規(guī)則定義呢？

文法分析概覽

利用BNF寫出的文法規(guī)則，可以用來對輸入的文本進(jìn)行文法分析。一條BNF文法規(guī)則，左邊是一個非終結(jié)符（Symbol或者non-terminal），右邊則定義該非終結(jié)符是如何構(gòu)成的，也稱為產(chǎn)生式（Production），產(chǎn)生式中可能包含非終結(jié)符，也可能包含終結(jié)符（terminal），也可能二者都有。在所有文法規(guī)則中，必有一個開始的規(guī)則，該規(guī)則左邊的部分叫做開始符號（start symbol）。一個規(guī)則的寫法如下：

Symbol := Production

下面是一個BNF文法定義的例子。FN是fractional number的意思，DL是digit list的意思，S是start symbol。

S := '-' FN | FN

FN := DL | DL '.' DL

DL := D | D DL

D := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

一個非終結(jié)符可能有多個產(chǎn)生式，相互間用豎線（|）隔開。

每一條BNF產(chǎn)生式，都有自己的啟動集（start set）。啟動集里的元素就是每個Production中的第一個部分，比如上例S規(guī)則的啟動集就是{'-'}以及{FN}。

利用BNF文法來分析目標(biāo)文本，其分析方法比較流行的有幾種，下面作一概述[Garshol 03]。

LL(k)分析

LL分析又稱為自頂向下的分析（top-down parsing），也有叫遞歸下降分析（recursive-descent parsing）。也是最簡單的一種分析方式。它工作的方式類似于找出一個產(chǎn)生式可以從哪一個終結(jié)符開始。

當(dāng)分析時，從起始符號開始，比較輸入中的第一個終結(jié)符和啟動集，看哪一個產(chǎn)生式規(guī)則被使用了。當(dāng)然，兩個啟動集之間不能擁有同一個終結(jié)符。如果有的話，就沒有辦法決定選擇哪個產(chǎn)生式規(guī)則了。

Ll文法通常用數(shù)字來分類，比如LL(1)，LL(0)等。這個數(shù)字告訴你，在一個文法規(guī)則中的任何點(diǎn)可以允許一次察看的終結(jié)符的最大數(shù)量。LL(0)就不需要看任何終結(jié)符，分析器總是可以選擇正確的產(chǎn)生式規(guī)則。它只適用于所有的非終結(jié)符都只有一個產(chǎn)生規(guī)則。只有一個產(chǎn)生規(guī)則意味著只有一個字符串。[不用看當(dāng)前的終結(jié)符是什么就可以決定是哪一個產(chǎn)生規(guī)則，說明這個規(guī)則是為一個固定的字符串所寫的。]這種文法是沒有什么意義的。

最常見也是比較有用的事LL(1)文法。它只需要看一個終結(jié)符，然后就可以決定使用哪一個產(chǎn)生規(guī)則。而LL(2)則可以查看兩個終結(jié)符，還有LL(k)文法等等。對于某個固定的k值，也存在著根本不是LL(k)的文法，而且還很普遍。

下面來分析一下本章開頭給出的例子。首先看下面這條規(guī)則：

D := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

上述規(guī)則有十個產(chǎn)生式，每個產(chǎn)生式的啟動集是一個數(shù)字終結(jié)符構(gòu)成的集合{'0'}、{'1'}、……、{'9'}。這是一個很好的LL(1)文法，因?yàn)槲覀冎灰匆粋€終結(jié)符，就可以選擇一個正確的產(chǎn)生式。例如，如果看到一個終結(jié)符，其內(nèi)容是3，那么就采用上面第四個產(chǎn)生式，即D := '3'。

接下來分析DL規(guī)則。

DL := D | D DL

上述規(guī)則有兩個產(chǎn)生式，啟動集是{D}，{D}。很不幸，兩個產(chǎn)生式的啟動集相同。這就表示只看第一個輸入中的第一個終結(jié)符不能選擇正確的產(chǎn)生式。

然而可以通過欺騙來繞過這個問題：如果輸入中第二個終結(jié)符不是一個數(shù)字，那么就選擇第一個產(chǎn)生式，但如果兩者都是數(shù)字就必須選擇第二個產(chǎn)生式。換句話說，這意味著這是一條好的LL(2)文法規(guī)則。實(shí)際上這里有些東西被簡化了。

再分析下FN規(guī)則吧。它的情況更糟糕。

FN := DL | DL '.' DL

它有兩條產(chǎn)生式，而且啟動集相同，均為{DL}。然而這次不像DL規(guī)則那么幸運(yùn)了。咋一看，似乎通過LL(2)可以分辨應(yīng)該使用哪一個產(chǎn)生式。但是很不幸，我們無法確定在讀到終結(jié)符('.')之前，需要讀多少個數(shù)字才算是DL符號的最后一個數(shù)字。[想想吧，分析器這么工作著：讀入第一個終結(jié)符，一看是相同的DL符號，那么就讀第二個終結(jié)符吧；讀入第二個終結(jié)符，兩者合起來一看，還是一樣的DL符號；讀入第三個終結(jié)符，前三個終結(jié)符合起來看，仍然是相同的DL符號。但是DL符號表指示數(shù)字表示沒有長度限制的。] 沒有任何一個給定的k值，這都不符合LL(k)文法，因?yàn)閿?shù)字表總能突破這個k的長度。

最后看看啟動符號規(guī)則。有點(diǎn)意外，它產(chǎn)生規(guī)則的選擇很簡單。

S := '-' FN | FN

它有兩個產(chǎn)生規(guī)則，兩者的啟動集是{'-'}和{FN}。因此，如果輸入中第一個終結(jié)符是'-'，那么就選擇第一個產(chǎn)生式，否則選擇第二個產(chǎn)生式。所以這是一個LL(1)文法。

從上述的LL分析看，只有FN和DL規(guī)則引起了問題。但是不必絕望。大部分的非LL(k)文法都可以容易地轉(zhuǎn)換為LL(1)文法。下面以當(dāng)前的這個例子來看看如何轉(zhuǎn)換有問題的FN和DL。

對于FN符號來說，它的兩個產(chǎn)生式都開始于DL，但是第二個產(chǎn)生式其后續(xù)的是一個小數(shù)點(diǎn)終結(jié)符('.')，以及另外一個數(shù)字表。那么這很容易解決：可以將FN改變?yōu)橐粋€產(chǎn)生式，其以DL開始，后跟一個FP（fractional part）符號。而FP符號則定義成或者為空，或者為小數(shù)點(diǎn)后跟著一個數(shù)字表，如下所示：

FN := DL FP

FP := @ | '.' DL

上述@符號表示為空。現(xiàn)在FN文法沒有任何問題了，因?yàn)樗F(xiàn)在只有一個產(chǎn)生式。而FP也不會有問題，因?yàn)樗膬蓚€產(chǎn)生式的啟動集是不同的：前者是輸入的尾端，后者是小數(shù)點(diǎn)終結(jié)符。

DL符號就不是好啃的核桃了，原因在于其遞歸和至少需要一個D符號。解決方案就是，給DL一個產(chǎn)生式，由一個D后跟一個DR（digit rest）構(gòu)成；而DR則有兩個產(chǎn)生式，一個是D DR（表示更多的數(shù)字），一個是@（表示沒有更多的數(shù)字）。最后本章開頭的例子被轉(zhuǎn)換成下面的一個完全的LL(1)文法了：

S := '-' FN | FN

FN := DL FP

FP := @ | '.' DL

DL := D DR

DR := @ | D DR

D := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

LR分析

Lr分析也叫自底向上的分析（bottom-up parsing），或者叫移進(jìn)-歸約分析（shift-reduce parsing），相比LL分析難度更大些。它的基本原理是，首先收集輸入，直到它發(fā)現(xiàn)可以據(jù)此利用一個符號對收集到的輸入序列進(jìn)行歸約。可以與數(shù)學(xué)里面解方程式時的消元法進(jìn)行類比。這聽起來似乎很難。下面還是以一個例子來澄清。例子中將分析字符串3.14，看看是怎樣從文法產(chǎn)生出來的。

S := '-' FN | FN

FN := DL | DL '.' DL

DL := D | D DL

D := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

首先從輸入中讀入3。

3

然后看看是否可以將其歸約為一個符號（Symbol，即非終結(jié)符）。實(shí)際上可以歸約，就是說用D符號的產(chǎn)生式可以得到當(dāng)前讀入的字符串（這也是成為產(chǎn)生式的原因）。

很快發(fā)現(xiàn)，從DL符號可以產(chǎn)生符號D，于是又可以歸約成DL。（實(shí)際上還可以進(jìn)一步地歸約成FN，于是這里就產(chǎn)生了歧義，到底應(yīng)該歸約成哪一個呢？這表明這個文法定義是二義性的，我們在這里就忽略這個問題，直接選擇DL作為歸約結(jié)果吧。）接著從輸入中讀入一個小數(shù)點(diǎn)，并試圖進(jìn)行歸約：

D ==> 規(guī)約到DL

DL ==> 讀入下一個字符

DL . ==> 規(guī)約到？

但是這次的歸約嘗試失敗了，因?yàn)闆]有任何符號的定義可以產(chǎn)生這種形式的字符串。也就是說，這種形式不能規(guī)約到任何符號。

所以接著我們讀入下一個字符1。這次可以將數(shù)字1歸約到D符號。接著再讀入一個字符4。4可以歸約到D，繼續(xù)歸約到DL。這兩次的讀入和規(guī)約形成了D Dl這個序列，而這個序列可以歸約到DL。

DL . ==> 讀入下一個字符1

DL . 1 ==> 1歸約到D

DL . D ==> 讀入下一個字符4

DL . D 4 ==> 4歸約到D

DL . D D ==> 4繼續(xù)歸約到DL

DL . D DL ==> D DL 歸約到DL

察看文法我們可以很快地注意到，FN能產(chǎn)生DL . Dl這種形式的序列，所以可以做一個歸約。然后注意到FN可以從S符號產(chǎn)生，所以可以歸約到S，然后停止，整個分析結(jié)束。

DL . DL ==> 歸約到FN

FN ==> 規(guī)約到S

S ==> 分析結(jié)束

可能你已經(jīng)注意到，我們經(jīng)常可以選擇是否現(xiàn)在就做歸約，還是等到讀入更多的符號后再作不同的歸約。移進(jìn)-歸約分析算法有很多不同的變種，按照復(fù)雜度和能力遞增的順序是：LR(0)， SLR， LALR和LR(1)。LR(1)通常需要一個巨大的分析表，在實(shí)踐上不具有實(shí)用性，因此LALR是最常使用的算法。SLR和LR(0)對于大部分的程序語言來說還不夠強(qiáng)大。

Bison分析器的算法¹

Bison適合上下文無關(guān)文法（Context-free grammar），并采用LALR(1)算法[Donnelly 06]的文法。

當(dāng)bison讀入一個終結(jié)符（token），它會將該終結(jié)符及其語意值一起壓入堆棧。這個堆棧叫做分析器堆棧（parser stack）。把一個token壓入堆棧通常叫做移進(jìn)（shifting）。

例如，假設(shè)一個中綴計(jì)算器已經(jīng)讀入'1 + 5 * '，下一個準(zhǔn)備讀入的是'3'，那么這個棧里就有四個元素，每個元素都是移進(jìn)的一個終結(jié)符。

但堆棧并不是每讀入一個終結(jié)符就分配一個棧元素給它。當(dāng)已經(jīng)移進(jìn)的后n個終結(jié)符和組（groupings）與一個文法規(guī)則相匹配時，它們會被根據(jù)那個規(guī)則結(jié)合起來。這叫做歸約（reduction）。棧中的那些終結(jié)符和組會被單個的組（grouping）替換。那個組的符號就是那個規(guī)則的結(jié)果。執(zhí)行該規(guī)則的相應(yīng)的動作（Action）也是歸約處理的一部分，這個動作會計(jì)算這個組的語意值。

例如，如果中綴計(jì)算器的分析器堆棧包含：1 + 5 * 3，并且下一個輸入字符是換行符，那么上述后3個元素可以按照下面規(guī)則歸約到15：

expr: expr '*' expr;

于是堆棧中就只包含下面三個元素了：1 + 15。此刻，另一個規(guī)約也可以執(zhí)行，其結(jié)果是一個單值16。然后這個新行終結(jié)符就可以被移進(jìn)了。

分析器通過移進(jìn)和歸約嘗試著縮減整個輸入到單個的組。這個組的符號就是文法中的起始符號（start-symbol）。

終結(jié)符預(yù)讀

Bison分析器并不總是在后n個終結(jié)符與組匹配某一規(guī)則時立即就進(jìn)行歸約。這種策略對于大部分語言來說并不合適。相反，當(dāng)可以進(jìn)行歸約時，分析器有時會“預(yù)讀”（looks ahead）下一個終結(jié)符來決定做什么。

當(dāng)一個終結(jié)符被讀進(jìn)來后，并不會立即移進(jìn)堆棧，而是首先作為一個預(yù)讀終結(jié)符（look-ahead token）。此后，分析器開始對棧上的終結(jié)符和組執(zhí)行一個或多個歸約，而預(yù)讀終結(jié)符仍然放在一邊。當(dāng)沒有歸約可做時，這個預(yù)讀終結(jié)符才會被移進(jìn)堆棧。這并不表示所有可能的歸約都已經(jīng)做了，這要取決于預(yù)讀終結(jié)符的類型，一些規(guī)則可能選擇推遲它們的使用。

下面研究一個需要做預(yù)讀的案例。這里的三條規(guī)則定義了一個表達(dá)式，可以包含二元的加法運(yùn)算符和一元的后綴階乘運(yùn)算符('!')，并且允許用括號進(jìn)行分組。

expr: term '+' expr

| term

;

term: '(' expr ')'

| term '!'

| NUMBER

;

假定終結(jié)符'1' '+' '2'已經(jīng)讀入并移進(jìn)堆棧，那么接下來應(yīng)該做什么呢？如果接下來的終結(jié)符是')'，那么前三個終結(jié)符必須歸約成一個expr。這是唯一的合法情況，因?yàn)橐七M(jìn)')'將會產(chǎn)生一個序列term ')'，而沒有任何規(guī)則允許出現(xiàn)這種情況。[不做歸約移進(jìn)')'，堆棧上的元素序列是1 + 2 )，2可以歸約成NUMBER，進(jìn)而歸約成term，與其后的 ')'形成term ')'的序列，檢查所有規(guī)則發(fā)現(xiàn)沒有任何規(guī)則定義了這種序列。]

如果下一個終結(jié)符是'!'[記住此刻它還是預(yù)讀終結(jié)符]，那么該終結(jié)符必須立即移進(jìn)堆棧以便'2 !'可以歸約成一個term。如果相反地分析器在移進(jìn)這個階乘符號之前進(jìn)行歸約，那么'1 + 2'就會歸約成expr。這將導(dǎo)致不可能移進(jìn)'!'終結(jié)符，因?yàn)檫@樣的話將會產(chǎn)生一個expr '!'序列。同樣沒有任何規(guī)則定義了這種序列。

預(yù)讀終結(jié)符存儲在變量yychar中。它的語意值和位置，如果有的話，存儲在變量yylval和yylloc中。

移進(jìn)-歸約沖突

假定我們正在分析一個語言，其中有if-then和if-then-else語句，對應(yīng)的規(guī)則如下：

if_stmt: IF expr THEN stmt

| IF expr THEN stmt ELSE stmt

;

這里我們假設(shè)IF，THEN和ELSE是特別的關(guān)鍵字終結(jié)符。

當(dāng)ELSE終結(jié)符讀入后作為一個預(yù)讀終結(jié)符時，堆棧中的內(nèi)容（假設(shè)輸入是合法的）正好可以歸約到第一條規(guī)則上。但是把它移進(jìn)堆棧也是合理的，因?yàn)槟菢痈鶕?jù)第二條規(guī)則就會導(dǎo)致最后的歸約。

在這種情況下，移進(jìn)或者歸約都是合法的，稱為移進(jìn)-歸約沖突（shift-reduce conflict）。Bison的設(shè)計(jì)是，用移進(jìn)來解決沖突，除非有操作符優(yōu)先級聲明的指令。為了解釋如此選擇的理由，讓我們與其它可選辦法進(jìn)行一個比較。

既然分析器更傾向移進(jìn)ELSE，那么其結(jié)果是把else子句連接到最內(nèi)層的if語句，從而使得下面兩種輸入是等價(jià)的：

if x then if y then win (); else lose;

if x then do; if y then win (); else lose; end;

如果分析器選擇歸約而不是移進(jìn)，那么其結(jié)果將是把else子句連接到最外層的if語句，從而導(dǎo)致下面兩個輸入是等價(jià)的：

if x then if y then win (); else lose;

if x then do; if y then win (); end; else lose;

沖突的存在是因?yàn)槲姆ㄓ卸x性：簡單的嵌套的if語句的任一種解析都是合理的。已有的慣例是這種二義性的解決是通過把else子句連接到最內(nèi)層的if語句而獲得的；Bison是選擇移進(jìn)而不是歸約來實(shí)現(xiàn)的。（一種更清晰的做法是寫出無二義性的文法，但對于這種情況來說是非常困難的。）這種特殊的二義性首次出現(xiàn)在Algol 60的規(guī)范中，被稱作'dangling else ambiguity'。

對于可預(yù)見的合法的移進(jìn)-歸約沖突，為避免bison發(fā)出的警告，可以使用%expect n聲明。那么只要移進(jìn)-規(guī)約沖突的數(shù)量為n，就不會有警告產(chǎn)生。

操作符優(yōu)先級

可能出現(xiàn)移進(jìn)-歸約沖突的其它地方還有算術(shù)表達(dá)式。此時移進(jìn)就不總是更好的解決辦法了。Bison通過聲明操作符的優(yōu)先級來指定何時移進(jìn)何時歸約。

何時需要優(yōu)先級

考慮下面的二義文法片斷（其二義性體現(xiàn)在'1 – 2 * 3'可以用兩種不同的方式進(jìn)行分析）：

expr: expr '-' expr

| expr '*' expr

| expr '<' expr

| '(' expr ')'

...

;

假定分析器已經(jīng)看到了終結(jié)符'1'，'-'和'2'；那么應(yīng)該對它們歸約到減法運(yùn)算規(guī)則嗎？這取決于下一個終結(jié)符。當(dāng)然，若下一個終結(jié)符是')'，就必須歸約；此時移進(jìn)是非法的，因?yàn)闆]有任何規(guī)則可以對序列'- 2 )'進(jìn)行歸約，也沒有以這個序列開始的什么東西。但是如果下一個終結(jié)符是'*'或者'<'，那么就需要做一個選擇：移進(jìn)或者歸約，都可以讓分析得以完成，但是卻有不同的結(jié)果。

為了決定Bison應(yīng)該怎么做，必須考慮這兩個結(jié)果。若下一個終結(jié)符即操作符op被移進(jìn)，那么必然是op首先做歸約，然后才有機(jī)會讓前面的減法操作符做歸約。其結(jié)果就是（有效的）'1 – (2 op 3)'。另一方面，若在移進(jìn)op之前先對減法做歸約，那結(jié)果就是'(1 – 2) op 3'。很顯然，這里移進(jìn)或者規(guī)約的選擇取決于減法操作符'-'與下一個操作符op之間的優(yōu)先級：若op是乘法操作符'*'，那么就選擇移進(jìn)；若是關(guān)系運(yùn)算符'<'則應(yīng)該選擇規(guī)約。

那么諸如'1 – 2 – 5'這樣的輸入又如何呢？是應(yīng)該作為'(1 – 2) – 5' 還是應(yīng)該作為'1 – (2 – 5)' ？對于大多數(shù)的操作符，我們傾向于前一種形式，稱作左關(guān)聯(lián)（left association）。后一種形式稱作右關(guān)聯(lián)（right association），對于賦值操作符來說是比較理想的。當(dāng)堆棧中已經(jīng)有'1 – 2' 且預(yù)讀終結(jié)符是'-'，此時分析器選擇移進(jìn)還是歸約與選擇左關(guān)聯(lián)還是右關(guān)聯(lián)是一回事：移進(jìn)將會進(jìn)行右關(guān)聯(lián)。

指定操作符優(yōu)先級

Bison允許通過聲明%left和%right來指定操作符優(yōu)先級。每個這樣的聲明都包含一列終結(jié)符，這些終結(jié)符都是操作符，它們的優(yōu)先級和關(guān)聯(lián)性都被聲明了。%left聲明讓所有這些操作符左關(guān)聯(lián)，而%right聲明讓它們右關(guān)聯(lián)。第三種方案是%noassoc，它聲明了這是一個語法錯誤，表明“在一行中”找到了兩個同樣的操作符。

不同操作符的優(yōu)先級由它們的聲明次序來決定。先聲明的優(yōu)先級低，后聲明的優(yōu)先級高。[如果有同等優(yōu)先級的呢？應(yīng)該是按照其關(guān)聯(lián)性來決定了是移進(jìn)還是規(guī)約。]

優(yōu)先級例子

在本節(jié)給出的例子中，我們希望有如下的聲明：

%left '<'

%left '-'

%left '*'

在更復(fù)雜的例子中有更多的操作符，同等優(yōu)先級的操作符可以分成一組進(jìn)行聲明，如下所示：

%left '<' '>' '=' NE LE GE

%left '+' '-'

%left '*' '/'

這里NE代表not equal（不等于），LE表示小于等于，GE表示大于等于。

優(yōu)先級如何工作

優(yōu)先級聲明的第一個效果就是賦予了終結(jié)符不同的優(yōu)先級水平。第二個效果就是給某些規(guī)則賦予了優(yōu)先級水平：每個規(guī)則從它的最后的終結(jié)符得到其優(yōu)先級。[當(dāng)已讀入的終結(jié)符和組符合某個規(guī)則時，理論上講它可以進(jìn)行歸約。它最后的一個終結(jié)符可能被指定了優(yōu)先級，這個優(yōu)先級就成為該規(guī)則的優(yōu)先級。]

最終，沖突的解決是通過比較規(guī)則的優(yōu)先級與它的預(yù)讀終結(jié)符的優(yōu)先級實(shí)現(xiàn)的。若該終結(jié)符的優(yōu)先級高，那么就采用移進(jìn)。過規(guī)則的優(yōu)先級較高，那么就選擇歸約。若它們具有相同的優(yōu)先級，那么就基于該優(yōu)先級的關(guān)聯(lián)性來作出選擇。選項(xiàng)'-v'可以讓Bison產(chǎn)生詳細(xì)的輸出，其中有沖突是怎樣解決的信息。

并非所有的規(guī)則和終結(jié)符都具有優(yōu)先級。若規(guī)則或預(yù)讀終結(jié)符都沒有優(yōu)先級，那么缺省采用移進(jìn)[解決沖突]。

與上下文相關(guān)的優(yōu)先級

經(jīng)常有操作符的優(yōu)先級依靠上下文。起初這聽起來有些奇怪（outlandish），但這的確非常普通。例如，典型地一個減號作為一元操作符有非常高的優(yōu)先級，而作為二元操作符則具有較低的優(yōu)先級（比乘法低）。

對于給定的終結(jié)符，聲明%left，%right和%noassoc只能使用一次，所以這種方式下一個終結(jié)符只有一個優(yōu)先級。對于與上下文相關(guān)的優(yōu)先級，需要一個新增的機(jī)制：用于規(guī)則的%prec修飾符。

%prec修飾符聲明了某個規(guī)則的優(yōu)先級，通過指定某個終結(jié)符而該終結(jié)符的優(yōu)先級將用于該規(guī)則。沒有必要在該規(guī)則出現(xiàn)這個終結(jié)符。[就是說這個終結(jié)符可以是臆造的，在系統(tǒng)中可能并沒有實(shí)際的對應(yīng)體，只是為了用于指定該規(guī)則的優(yōu)先級]。下面是優(yōu)先級的語法：

%prec terminal-symbol

并且這個聲明必須寫在該規(guī)則的后面[看下面的例子]。這個聲明的效果就是把該終結(jié)符所具有的優(yōu)先級賦予該規(guī)則，而這個優(yōu)先級將會覆蓋在普通方式下推斷出來的該規(guī)則的優(yōu)先級。這個更改過的規(guī)則優(yōu)先級會影響規(guī)則如何解決沖突。

下面就是解決一元的負(fù)號的問題。首先，定義一個名為UMINUS的虛構(gòu)的終結(jié)符，并為之聲明一個優(yōu)先級。實(shí)際上并沒有這種類型的終結(jié)符，但是這個終結(jié)符僅僅為其的優(yōu)先級服務(wù)。

...

%left '+' '-'

%left '*'

%left UMINUS

現(xiàn)在UMINUS的優(yōu)先級可如此地用于規(guī)則：

exp: ...

| expr '-' exp

...

| '-' exp %prec UMINUS

分析器的狀態(tài)

函數(shù)yyparse用一個有限狀態(tài)機(jī)（finite-state）實(shí)現(xiàn)。壓入分析器堆棧的值并不是簡單地終結(jié)符類型碼。它們代表靠近堆棧頂部的整個的終結(jié)符和非終結(jié)符的序列。當(dāng)前狀態(tài)收集關(guān)于前一個輸入的所有信息，而這個輸入與決定下一步作什么有關(guān)。

每次預(yù)讀入一個終結(jié)符后，分析器當(dāng)前狀態(tài)與預(yù)讀終結(jié)符的類型一起，到表中查找。對應(yīng)的表項(xiàng)可能是：移進(jìn)這個預(yù)讀終結(jié)符。這種情況下，它也會指定新的分析器狀態(tài)，并被壓入到分析器棧的頂部。或者這個表項(xiàng)可能是：用規(guī)則n進(jìn)行歸約。這就意味著一定數(shù)量的終結(jié)符或組會被從堆棧頂部取走，并用一個組取代。換句話說，那些數(shù)量的狀態(tài)被從堆棧彈出，一個新的狀態(tài)被壓棧。

另外一個可能是：這個表項(xiàng)會告訴說，這個預(yù)讀終結(jié)符對當(dāng)前狀態(tài)來說是錯誤的。這將導(dǎo)致開始一個錯誤處理。

歸約-歸約沖突

歸約-歸約沖突（reduce-reduce conflict）發(fā)生在有兩個或以上的規(guī)則適用于同一個輸入序列時。這通常表明了一個嚴(yán)重的文法錯誤。

例如，這里有一個錯誤的嘗試，試圖定義一個具有0個或多個單詞（word）的組：

sequence: /* empty */ { printf (“empty sequence\n”); }

| maybeword

| sequence word { printf (“added word %s\n”, $2); }

;

maybeword: /* empty */ { printf (“empty maybeword\n”); }

| word { printf (“single word %s\n”, $1); }

;

[待續(xù)]

BISON

==Bison 語法文件內(nèi)容的布局==

Bison 工具將把 Bison 語法文件作為輸入。語法文件的擴(kuò)展名為.y。Bison 語法文件內(nèi)容的分布如下（四個部分）：

%{

序言

%}

Bison 聲明

%%

語法規(guī)則

%%

結(jié)尾

序言部分可定義 actions 中的C代碼要用到的類型和變量，定義宏，用 #include 包含頭文件等等。要在此處聲明詞法分析器 yylex 和錯誤輸出器 yyerror 。還在此處定義其他 actions 中使用到的全局標(biāo)識符。

Bison聲明部分可以聲明終結(jié)符和非終結(jié)符的名字，也可以描述操作符的優(yōu)先級，以及各種符號的值語義的數(shù)據(jù)類型。各種非單個字符的記號（節(jié)點(diǎn)）都必須在此聲明。

語法規(guī)則部分描述了如何用組件構(gòu)造出一個非終結(jié)符。（這里我們用術(shù)語組件來表示一條規(guī)則中的各個組成部分。）

結(jié)尾部分可以包含你希望使用的任何的代碼。通常在序言部分聲明的函數(shù)就在此處定義。在簡單程序中所有其余部分都可以在此處定義。

=例子一=

本例子完整實(shí)現(xiàn)一個采用逆波蘭式語法的計(jì)算器。

==語法文件==

語法文件rpcalc.y的內(nèi)容如下：

第一部分：序言和聲明

/* Reverse polish notation calculator. */

%{

#define YYSTYPE double

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

int yylex (void);

void yyerror (char const *);

%}

%token NUM

%% /* Grammar rules and actions follow. */

第二部分：語法規(guī)則部分

input: /* empty */

| input line

;

line: ’\n’

| exp ’\n’ { printf ("\t%.10g\n", $1); }

;

exp: NUM { $$ = $1; }

| exp exp ’+’ { $$ = $1 + $2; }

| exp exp ’-’ { $$ = $1 - $2; }

| exp exp ’*’ { $$ = $1 * $2; }

| exp exp ’/’ { $$ = $1 / $2; }

/* Exponentiation */

| exp exp ’^’ { $$ = pow ($1, $2); }

/* Unary minus */

| exp ’n’ { $$ = -$1; }

;

%%

可替換規(guī)則之間用豎線“|”連接，讀作“或”。在花括號內(nèi)部的是用于已經(jīng)識別出來的非終結(jié)符的動作（action），用C代碼寫成。在動作中偽變量$$代表即將被構(gòu)造的該分組的語義值。大部分動作的的主要工作就是向偽變量賦值。而各個部件的語義值則由$1、$2等來引用。

構(gòu)造同一個非終結(jié)符的多個可替換規(guī)則構(gòu)成了多個選擇，對每一個替換規(guī)則，在后文中用“選擇”來稱呼。

對 input 的解釋

input: /* empty */

| input line

;

上述讀作：一個完整的輸入或者是一個空串，或者是一個完整的輸入后跟著一個輸入行。“完整輸入”就是由其自身定義的。

在冒號與第一個豎線之間沒有任何字符，就表示為空。其含義表示input可以匹配一個空串的輸入（沒有記號）。這樣可以處理打開計(jì)算器后就輸入Ctrl-d結(jié)束輸入的情況。習(xí)慣上在為空的地方加上一個注釋/* empty */。

第二個選擇的含義是，在讀入了任意數(shù)量的行以后，可能的情況下再讀入一行。左邊的遞歸使本規(guī)則進(jìn)入到一個循環(huán)，由于第一個選擇是空，所以循環(huán)可以被執(zhí)行0次或多次。

對 line 的解釋

line: ’\n’

| exp ’\n’ { printf ("\t%.10g\n", $1); }

;

第一個選擇就是一個記號，表示一個換行字符。其含義是，rpcalc 接受一個空行（可以被忽略，因此沒有對應(yīng)的動作）。

第二個選擇就是一個表達(dá)式后跟著一個換行字符。這就使 rpcalc 變得有用起來。$1就是 exp 組的語義值，因?yàn)榇颂? exp 就是該選擇中的第一個符號。對應(yīng)的動作并不是普通的賦值給偽變量$$，這樣與 line 關(guān)聯(lián)的語義值就是未初始化的（因此其值是不可預(yù)測的）。倘若使用了這個值，拿這就是一個 bug。但本例中計(jì)算器并不使用這個值，

對 exp 的解釋

exp: NUM { $$ = $1; }

| exp exp ’+’ { $$ = $1 + $2; }

| exp exp ’-’ { $$ = $1 - $2; }

...

;

上述形式還有一種等價(jià)形式：

exp: NUM ;

exp: exp exp ’+’ { $$ = $1 + $2; } ;

exp: exp exp ’-’ { $$ = $1 - $2; } ;

...

并不需要為每個規(guī)則都指定動作，當(dāng)一條規(guī)則沒有動作時，Bison 默認(rèn)情況下把$1的值拷貝給$$。

==詞法分析器==

詞法分析器的工作是低級的分析：把字符或字符序列轉(zhuǎn)換成記號。Bison 調(diào)用詞法分析起來獲得記號。本例只需要一個簡單的詞法分析器。下面就是詞法分析器的代碼：

/* The lexical analyzer returns a double floating point

number on the stack and the token NUM, or the numeric code

of the character read if not a number. It skips all blanks

and tabs, and returns 0 for end-of-input. */

#include <ctype.h>

int

yylex (void)

{

int c;

/* Skip white space. */

while ((c = getchar ()) == ’ ’ || c == ’\t’)

;

/* Process numbers. */

if (c == ’.’ || isdigit (c))

{

ungetc (c, stdin);

scanf ("%lf", &yylval);

return NUM;

}

/* Return end-of-input. */

if (c == EOF)

return 0;

/* Return a single char. */

return c;

}

該分析器跳過空格和制表符，然后讀入數(shù)字作為雙精度數(shù)字，并將他們作為NUM記號返回。不屬于數(shù)字部分的任何其他字符都是一個單獨(dú)的記號。注意單字符記號的記號代碼就是該字符本身。

該記號的語義值被存儲到全局變量 yylval，被 Bison 的解析器使用。（yylval的C數(shù)據(jù)類型是YYSTYPE，定義在語法的開頭部分。）

一個為零的記號類型代碼被返回，表示輸入結(jié)束。（Bison 把任何的非正值識別為輸入結(jié)束。）

==控制函數(shù)==

int

main (void)

{

return yyparse ();

}

控制函數(shù)的唯一目的就是調(diào)用函數(shù) yyparse 來啟動解析處理。

==錯誤報(bào)告例程==

當(dāng) yyparse 檢測到一個錯誤時，將調(diào)用錯誤報(bào)告函數(shù) yyerror 打印出一條錯誤消息。下面是本例中使用的代碼。

#include <stdio.h>

/* Called by yyparse on error. */

void

yyerror (char const *s)

{

fprintf (stderr, "%s\n", s);

}

如果語法中包含有合適的錯誤規(guī)則，那么在 yyerror 返回后，Bison 解析器就可以從錯誤中恢復(fù)，并繼續(xù)解析。本例沒有提供錯誤規(guī)則，因此當(dāng)遇到非法輸入時，程序?qū)⑼顺觥?/p>

==運(yùn)行Bison制作解析器==

首先要考慮如何組織源代碼到一個或多個文件中。本例作為一個簡單程序，全部放到一個文件中是最簡單的。把 yylex、yyerror和main函數(shù)都放在語法文件的結(jié)尾部分就可以了。如果是一個大型工程，可能需要許多文件，并使用make工具來組織編譯工作。

對于單一文件的本程序來說，用如下指令來將其轉(zhuǎn)換為一個解析器：

bison rpcalc.y

Bison 將產(chǎn)生一個輸出文件，名為rpcalc.tab.c。該輸出文件中包含有供yyparse使用的代碼。一些額外的代碼（如yylex，yyerror，以及main）被原樣輸出到該文件中。最后用編譯器將生成的C文件編譯成可執(zhí)行文件，這樣計(jì)算器程序就可用了。編譯命令如下：

cc -lm -o rpcalc rpcalc.tab.c

下面是使用這個逆波蘭式計(jì)算器的例子，很顯然這種方式不符合人類自然的思維習(xí)慣。

4 9 +

13

3 7 + 3 4 5 *+-

-13

3 7 + 3 4 5 * + - n Note the unary minus, ‘n’

13

5 6 / 4 n +

-3.166666667

3 4 ^ Exponentiation

81

6 n

-6

^D End-of-file indicator

=例子二=

本例子將實(shí)現(xiàn)一個中綴式計(jì)算器。

對于中綴運(yùn)算符，存在優(yōu)先級的概念，并有任意深度的括號嵌套層次。下面是文件“calc.y”的內(nèi)容：

/* Infix notation calculator */

/* part1: prologue */

%{

#define YYSTYPE double

#include <math.h>

#include <stdio.h>

int yylex (void);

void yyerror (char const *);

%}

/* part2: bison decalarations */

%token NUM

%left '-' '+'

%left '*' '/'

%left NEG /* negation--unary minus */

%right '^' /* exponentiation */

/* part3: grammar rules */

%%

input: /* empty */

| input line

;

line: '\n'

| exp '\n' { printf("\t%.10g\n", $1); }

;

exp: NUM { $$ = $1; }

| exp '+' exp { $$ = $1 + $3; }

| exp '-' exp { $$ = $1 - $3; }

| exp '*' exp { $$ = $1 * $3; }

| exp '/' exp { $$ = $1 / $3; }

| '-' exp %prec NEG { $$ = -$2; }

| exp '^' exp { $$ = pow ($1, $3); }

| '(' exp ')' { $$ = $2; }

;

%%

/* part4: Epilogue same as the first example */

#include <ctype.h>

int

yylex (void)

{

int c;

/* Skip white space. */

while ((c = getchar ()) == ’ ’ || c == ’\t’)

;

/* Process numbers. */

if (c == ’.’ || isdigit (c))

{

ungetc (c, stdin);

scanf ("%lf", &yylval);

return NUM;

}

/* Return end-of-input. */

if (c == EOF)

return 0;

/* Return a single char. */

return c;

}

int

main (void)

{

return yyparse ();

}

#include <stdio.h>

/* Called by yyparse on error. */

void

yyerror (char const *s)

{

fprintf (stderr, "%s\n", s);

}

在語法段中引入兩個重要特性：

%left 聲明了記號類型，并指出他們是左關(guān)聯(lián)運(yùn)算符（left-associative operator）。

%right則表示是右關(guān)聯(lián)運(yùn)算符（right-associative operator）。

%token則聲明一個沒有關(guān)聯(lián)性的記號類型名稱。

本來單字符的記號一般不需要在這里聲明，但這里是為了指出他們的關(guān)聯(lián)性。

注意：運(yùn)算符的優(yōu)先級則由聲明的行順序決定，即越后聲明的優(yōu)先級越高，因此首先聲明的運(yùn)算符的優(yōu)先級最低，最后聲明的運(yùn)算符優(yōu)先級最高。本例中冪運(yùn)算優(yōu)先級最高，其次是一元取負(fù)運(yùn)算符，接著是乘除運(yùn)算，最低是加減運(yùn)算。

另一個特性是一元取負(fù)運(yùn)算符中用到的%prec。這個%prec指示bison本條規(guī)則“| '-' exp”具有與NEG相同的優(yōu)先級，本例中即是次高優(yōu)先級（next-to-highest）。

==簡單的錯誤恢復(fù)==

檢測到語法錯誤后，如何繼續(xù)進(jìn)行解析呢？目前已經(jīng)知道可以用 yyerror 報(bào)告錯誤。默認(rèn)情況下在調(diào)用了 yyerror 后， 函數(shù) yyparse 將返回。這樣當(dāng)遇到錯誤的輸入行時計(jì)算器程序?qū)⑼顺觥?/p>

bison 自己有一個保留關(guān)鍵字 error，可以用在語法規(guī)則部分。下面是一個例子：

line: '\n'

| exp '\n' { printf ("\t%.10g\n", $1); }

| error '\n' { yyerrok; }

;

當(dāng)不可計(jì)算的表達(dá)式被讀入后，上述第三條規(guī)則將識別出這個錯誤，解析將繼續(xù)。yyerror 仍將被調(diào)用以打印出一條消息。第三條規(guī)則對應(yīng)的動作是一個宏 yyerrok，由bison自動定義。此宏的含義是錯誤恢復(fù)已經(jīng)完成。要注意 yyerrok 和yyerror的區(qū)別，這不是打字錯誤。

本例中只處理了語法錯誤，實(shí)際還有很多如除零錯誤等需要處理。

==跟蹤定位計(jì)算器==

實(shí)現(xiàn)跟蹤定位將改善錯誤消息。為簡單起見，本例實(shí)現(xiàn)一個簡單的整數(shù)計(jì)算器。

/* Location tracking calculator */

/* part1: prologue */

%{

#define YYSTYPE int

#include <math.h>

int yylex (void);

void yyerror (char const *);

%}

/* part2: Bison declarations */

%token NUM

%left '-' '+'

%left '*' '/'

%left NEG

%right '^'

在聲明中并沒有用來存儲定位信息的數(shù)據(jù)類型，本例將使用默認(rèn)類型：一個含四個整型成員的結(jié)構(gòu)，即first_line, first_column, last_line, last_column。

是否處理位置信息，對你的語言的語法并沒有影響。在這里將用位置信息來報(bào)告被零除的錯誤，并定位錯誤表達(dá)式或子表達(dá)式。

/* part3: grammar rules */

%%

input : /* empty */

| input line

;

line : '\n'

| exp '\n' { printf ("%d\n", $1); }

;

exp : NUM { $$ = $1; }

| exp '+' exp { $$ = $1 + $3; }

| exp '-' exp { $$ = $1 - $3; }

| exp '*' exp { $$ = $1 - $3; }

| exp '/' exp /* 注意：與前面例子不同的地方 */

{

if ($3)

$$ = $1 / $3;

else

{

$$ = 1;

fprintf (stderr, "%d.%d-%d.%d: division by zero",

@3.first_line, @3.firt_column,

@3.last_line, @3.last_column);

}

}

| '-' exp %prec NEG { $$ = -$2; }

| exp '^' exp { $$ = pow ($1, $3); }

| '(' exp ')' { $$ = $2; }

;

%%

偽變量@n對應(yīng)規(guī)則中的部件，而偽變量@$則對應(yīng)于組別。并不需要手工對@$賦值，輸出解析器可以在執(zhí)行每個動作對應(yīng)的C代碼之前自動完成賦值。這個默認(rèn)行為是可以重定義的，對某些特殊規(guī)則，可以手工計(jì)算。[GNU的東西總是具有那么靈活的可配置性！]

那么詞法分析器應(yīng)該怎樣寫呢？在詞法分析器中一個重要的任務(wù)是告訴解析器各個記號的位置。

為此我們必須計(jì)算輸入文本中每個字符，以避免計(jì)算位置混淆或錯誤。

int yylex (void)

{

int c;

/* Skip white space */

while ((c = getchar ()) == ' ' || c == '\t')

++yylloc.last_column;

/* Step */

yylloc.first_line = yylloc.last_line;

yylloc.first_column = yylloc.last_column;

/* Process numbers */

if (isdigit (c))

{

yylval = c - '0';

++yylloc.last_cloumn;

while (isdigit (c = getchar ()))

{

++yyloc.last_column;

yylval = yylval * 10 + c - '0';

}

ungetc (c, stdin);

return NUM;

}

/* Return end-of-input */

if (c == EOF)

return 0;

/* Return a single char, and update location */

if (c == '\n')

{

++yyloc.last_line;

yyloc.last_column = 0;

}

else

++yylloc.last_column;

return c;

}

每次該函數(shù)返回一個記號時，解析器都知道它的數(shù)字，以及它的語義值，還有在文本中的位置。

[可以將這樣來看，四個值構(gòu)成成一個盒子，每一個合法的記號都應(yīng)該放到一個盒子里。當(dāng)讀入一個較長的記號時，顯然最后一列的值在增加，而開始讀新的一行時，最后一行的值也要增加。]

還需要初始化yylloc，這在控制函數(shù)中完成：

int main()

{

yylloc.first_line = yylloc.last_line = 1;

yylloc.first_column = yylloc.last_column = 0;

return yyparse();

}

注意：計(jì)算位置與語法無關(guān)，因此，每個字符都必須關(guān)聯(lián)一個位置，無論該字符在合法輸入中，還是在注釋中，或者字串中等。 yylloc是一個全局變量，類型是YYLTYPE，它包含著記號的位置信息。

用bison來做語法分析，首先要將分析對象做仔細(xì)的研究。分析工作的首要任務(wù)是分清楚什么是終結(jié)符，什么是非終結(jié)符。

終結(jié)符是一組原子性的單詞，表達(dá)了語法意義中不可分割的一個標(biāo)記。在具體的表現(xiàn)形式上，可能是一個字符串，也可能是一個整數(shù)，或者是一個空格，一個換行符等等。bison只給出每個終結(jié)符的名稱，并不給出其定義。Bison為每個終結(jié)符名稱分配一個唯一的數(shù)字代碼。

終結(jié)符的識別由專門定義的函數(shù)yylex()執(zhí)行。這個函數(shù)返回識別出來的終結(jié)符的編碼，且已識別的終結(jié)符可以通過全局變量yytext指針，而這個終結(jié)符的長度則存儲在全局變量yyleng中。來取得這種終結(jié)符的分析最好用flex工具通過對語法文件進(jìn)行掃描來識別。有些終結(jié)符有不同的具體表示。例如h248協(xié)議中的表示版本號的終結(jié)符VersionToken，既可能用字串Version表示，也可能用一個字符V表示。這種情況下，Bison中只給出終結(jié)符名稱，而由Flex給出終結(jié)符的具體定義。

非終結(jié)符是一個終結(jié)符序列所構(gòu)成的一個中間表達(dá)式的名字。實(shí)際上不存在這么一個原子性的標(biāo)記。這種非終結(jié)符的構(gòu)成方式則應(yīng)該由Bison來表達(dá)。語法規(guī)則就是由終結(jié)符和非終結(jié)符一起構(gòu)成的一種組成規(guī)則的表達(dá)。

Bison的文法規(guī)則中各個組成部分是有次序性的。如果在一個文法定義中，各個元素的次序是任意的，并且其中某些元素又是必須的，該怎么來編寫這樣的Bison文法規(guī)則呢？Bison的文法規(guī)則定義文件在命名習(xí)慣上以字母y作為后綴。

Bison實(shí)際上也是一個自動化的文法分析工具，其利用詞法分析函數(shù)yylex()返回的詞法標(biāo)記返回其ID，執(zhí)行每一條文法規(guī)則后定義的動作。Bison是不能自動地生成詞法分析函數(shù)的。一般簡單的程序里，一般在文法規(guī)則定義文件的末尾添加該函數(shù)的定義。但是在較復(fù)雜的大型程序里，則利用自動詞法生成工具flex生成yylex()的定義。

Bison與Flex聯(lián)用時，Bison只定義標(biāo)記的ID。Flex則需要知道這些詞法標(biāo)記的ID，才能在識別到一個詞法標(biāo)記時返回這個ID給Bison。Bison傳遞這些ID給Flex的方法，就是在調(diào)用bison命令時使用參數(shù)-d。使用這個參數(shù)后，Bison會生成一個獨(dú)立的頭文件，該文件的名稱形式為name.tab.h。在Flex的詞法規(guī)則文件中，在定義區(qū)段里包含這個頭文件即可。如下例所示：

%{

#include “name.tab.h”

%}

%%

[0-9]+ yylval = atoi(yytext); return TOK_NUMBER;

yylex()只需要每次識別出一個token就馬上返回這個token的ID即可。上例中返回的token的ID就是TOK_NUMBER。此外，一個token的語義值可以由yylex()計(jì)算出來后放在全局變量yylval中。下面是具有多種語義值類型的例子：

{DIGIT}+ { yylval.Number = new CNumberLiteralNode(yytext);

return T_NUMBER_LITERAL;

}

根據(jù)Bison文法定義文件自動生成的C代碼，給出了文法分析函數(shù)yyparse()的定義。然而該代碼還不是一個完整的C程序，還需要程序員提供幾個額外的函數(shù)。一個是詞法分析函數(shù)yylex()，另外一個就是報(bào)錯函數(shù)yyerror()。報(bào)錯函數(shù)被yyparse()調(diào)用，以便在遇到錯誤時匯報(bào)錯誤。此外，一個完整的C程序還需要程序員提供一個main()函數(shù)作為程序的入口。在這個main()函數(shù)中，一定要調(diào)用yyparse()，否則分析工作就不會啟動。

報(bào)錯函數(shù)yyerror()的編寫

這個函數(shù)的原型如下：

int yyerror (const char* msg);

yyparse()函數(shù)遇到了錯誤時，可能會把字串syntax error或者memory exhausted作為參數(shù)傳遞給yyerror()。一個簡單的例子如下：

int yyerror( const char* msg)

{

fprintf (stderr, “%s\n”, msg);

return 0;

}

Flex將識別到詞法標(biāo)記記錄到變量yytext中，長度記錄在yyleng中。函數(shù)yylex()的返回值是一個整型，就是詞法標(biāo)記的ID。但是yylex()識別出來的字符串也可能需要返回給Bison。那么怎么返回呢？

現(xiàn)在做一個練習(xí)：定義一個非常簡單的計(jì)算器，這個計(jì)算器只能做一個整數(shù)的加法。這個計(jì)算器不做任何的錯誤處理。

首先給出Bison的文法定義文件：

參考文獻(xiàn)