模式及其分類(lèi)

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

（1）單字符匹配

• ‘x’ 匹配字符x。

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

• ‘[xyz]’ 匹配單個(gè)字符，這個(gè)字符是方括號(hào)中給出的字符類(lèi)（character class）中的一個(gè)。

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

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

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

• ‘[^A-Z\n]’ 匹配單個(gè)字符，這個(gè)字符不可以是方括號(hào)中給出的字符類(lèi)中的字符。與上一方式的不同在于，這里多了一個(gè)換行符，也就是說(shuō)所匹配的字符不能是26個(gè)大寫(xiě)字母，也不能是換行符。

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

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

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

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

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

[[:alnum:]]

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

[[:alpha:]0-9]

[a-zA-Z0-9]

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

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

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

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

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

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

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

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

（3）名字替換

• ‘{name}’ 這里name就是在前面的定義段給出的名字。這個(gè)模式將用這個(gè)名字的定義來(lái)匹配。

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

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

（5）特殊單字符的匹配

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

• ‘\0’ 匹配一個(gè)NUL字符（ASCII碼值為0）。

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

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

（6）組合模式的匹配

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

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

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

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

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

• ‘r。（在unix系統(tǒng)中換行是用一個(gè)字節(jié) \n 表示的，而DOS/Windows則采用兩個(gè)字節(jié) \r\n來(lái)表示換行。）

（7）有啟動(dòng)條件（Start Condition）的模式匹配

• ‘<s>r’ 匹配模式r，但需要啟動(dòng)條件s（后面后關(guān)于啟動(dòng)條件的討論）。模式‘<s1,s2,s3>r’是類(lèi)似的，匹配模式r，只要有三個(gè)啟動(dòng)條件s1，s2，s3中的任一個(gè)即可。（啟動(dòng)條件簡(jiǎn)單來(lái)說(shuō)，類(lèi)似于C語(yǔ)言中的條件編譯，滿(mǎn)足了某個(gè)條件才啟動(dòng)這個(gè)模式參與匹配，否則不會(huì)啟動(dòng)該模式參與匹配。）

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

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

（8）文件尾匹配

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

• ‘<s1,s2><<EOF>>’ 在有啟動(dòng)條件s1或者s2的情況下，匹配文件尾部。

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

創(chuàng)建一個(gè)簡(jiǎn)單的掃描器
下列例子來(lái)自于Flex的手冊(cè)。并在Windows+Cygwin+bison+flex+gcc的環(huán)境下編譯運(yùn)行。

(1) 編輯Flex語(yǔ)法文件。

/* 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文件

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

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

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

/cygdrive/c/DOCUME_1/ADMINI1.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/ADMINI1.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/ADMINI1.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

上述消息指出兩個(gè)問(wèn)題：

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

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

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

%option noyywrap

第二個(gè)問(wèn)題的解決辦法就是用gcc編譯時(shí)不連接fl庫(kù)，如下所示：

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

修改過(guò)的代碼如下：

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

%{

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自動(dòng)生成的詞法分析函數(shù)yylex()的名字、參數(shù)以及返回值，也就是說(shuō)yylex這個(gè)名字僅僅是一個(gè)默認(rèn)的名稱(chēng)，是可以改成其他名稱(chēng)的。方法很簡(jiǎn)單，只需要對(duì)宏YY_DECL做一個(gè)重定義即可：

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

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

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

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

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

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

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

Symbol := Production

下面是一個(gè)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'

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

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

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

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

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

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

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

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

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

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

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

DL := D | D DL

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

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

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

FN := DL | DL '.' DL

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

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

S := '-' FN | FN

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

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

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

FN := DL FP

FP := @ | '.' DL

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

DL符號(hào)就不是好啃的核桃了，原因在于其遞歸和至少需要一個(gè)D符號(hào)。解決方案就是，給DL一個(gè)產(chǎn)生式，由一個(gè)D后跟一個(gè)DR（digit rest）構(gòu)成；而DR則有兩個(gè)產(chǎn)生式，一個(gè)是D DR（表示更多的數(shù)字），一個(gè)是@（表示沒(méi)有更多的數(shù)字）。最后本章開(kāi)頭的例子被轉(zhuǎn)換成下面的一個(gè)完全的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ù)此利用一個(gè)符號(hào)對(duì)收集到的輸入序列進(jìn)行歸約。可以與數(shù)學(xué)里面解方程式時(shí)的消元法進(jìn)行類(lèi)比。這聽(tīng)起來(lái)似乎很難。下面還是以一個(gè)例子來(lái)澄清。例子中將分析字符串3.14，看看是怎樣從文法產(chǎn)生出來(lái)的。

S := '-' FN | FN

FN := DL | DL '.' DL

DL := D | D DL

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

首先從輸入中讀入3。

3

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

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

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

DL ==> 讀入下一個(gè)字符

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

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

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

DL . ==> 讀入下一個(gè)字符1

DL . 1 ==> 1歸約到D

DL . D ==> 讀入下一個(gè)字符4

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

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

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

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

DL . DL ==> 歸約到FN

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

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

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

Bison分析器的算法¹

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

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

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

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

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

expr: expr '*' expr;

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

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

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

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

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

expr: term '+' expr

| term

;

term: '(' expr ')'

| term '!'

| NUMBER

;

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

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

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

移進(jìn)-歸約沖突
假定我們正在分析一個(gè)語(yǔ)言，其中有if-then和if-then-else語(yǔ)句，對(duì)應(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é)符讀入后作為一個(gè)預(yù)讀終結(jié)符時(shí)，堆棧中的內(nèi)容（假設(shè)輸入是合法的）正好可以歸約到第一條規(guī)則上。但是把它移進(jìn)堆棧也是合理的，因?yàn)槟菢痈鶕?jù)第二條規(guī)則就會(huì)導(dǎo)致最后的歸約。

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

既然分析器更傾向移進(jìn)ELSE，那么其結(jié)果是把else子句連接到最內(nèi)層的if語(yǔ)句，從而使得下面兩種輸入是等價(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語(yǔ)句，從而導(dǎo)致下面兩個(gè)輸入是等價(jià)的：

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

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

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

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

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

何時(shí)需要優(yōu)先級(jí)
考慮下面的二義文法片斷（其二義性體現(xiàn)在'1 – 2 * 3'可以用兩種不同的方式進(jìn)行分析）：

expr: expr '-' expr

| expr '*' expr

| expr '<' expr

| '(' expr ')'

...

;

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

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

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

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

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

優(yōu)先級(jí)例子
在本節(jié)給出的例子中，我們希望有如下的聲明：

%left '<'

%left '-'

%left '*'

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

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

%left '+' '-'

%left '*' '/'

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

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

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

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

與上下文相關(guān)的優(yōu)先級(jí)
經(jīng)常有操作符的優(yōu)先級(jí)依靠上下文。起初這聽(tīng)起來(lái)有些奇怪（outlandish），但這的確非常普通。例如，典型地一個(gè)減號(hào)作為一元操作符有非常高的優(yōu)先級(jí)，而作為二元操作符則具有較低的優(yōu)先級(jí)（比乘法低）。

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

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

%prec terminal-symbol

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

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

...

%left '+' '-'

%left '*'

%left UMINUS

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

exp: ...

| expr '-' exp

...

| '-' exp %prec UMINUS

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

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

另外一個(gè)可能是：這個(gè)表項(xiàng)會(huì)告訴說(shuō)，這個(gè)預(yù)讀終結(jié)符對(duì)當(dāng)前狀態(tài)來(lái)說(shuō)是錯(cuò)誤的。這將導(dǎo)致開(kāi)始一個(gè)錯(cuò)誤處理。
基礎(chǔ)的關(guān)鍵詞概念：

image.png

image.png

image.png

image.png

image.png

image.png

yacc如何取到 lex詞法解析出來(lái)的值呢：

當(dāng)Lex匹配到一個(gè)目標(biāo)時(shí)，它就會(huì)將匹配到的文字放到y(tǒng)ytext中。YACC從變量yylval中取值。以yytext作為參數(shù)調(diào)用atoi函數(shù)，并將其返回值賦給yylval變量，這樣YACC就可以使用它

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

例如：
為了取到規(guī)則中的第三個(gè)部分的值，（例如，NUMBER）,我們需要使用$3，只要yylex返回，yylval的值就會(huì)被顯示在終端中，其值經(jīng)由$取得。

target_set:
    TOKTARGET TOKTEMPERATURE NUMBER
    {
        printf("\tTemperature set to %d\n",$3);
    }
    ;

嵌入式動(dòng)作
對(duì)于語(yǔ)法分析程序中的每一個(gè)語(yǔ)法規(guī)則，都有相應(yīng)的C/C++語(yǔ)句來(lái)做一些額外的處理，這個(gè)額外的處理就是語(yǔ)法動(dòng)作。不過(guò)語(yǔ)法動(dòng)作和詞法動(dòng)作的不同之處在于，語(yǔ)法動(dòng)作允許嵌入式的語(yǔ)法動(dòng)作，而詞法動(dòng)作不行。
盡管yacc的語(yǔ)法分析技術(shù)只允許動(dòng)作在規(guī)則的末端，但yacc可以自動(dòng)模擬嵌入在規(guī)則內(nèi)部的動(dòng)作。如果在規(guī)則內(nèi)部寫(xiě)入一個(gè)動(dòng)作，yacc就會(huì)創(chuàng)造一個(gè)右側(cè)為空并且左邊是自動(dòng)生成的名字規(guī)則，使得嵌入的動(dòng)作進(jìn)高規(guī)則的動(dòng)作里去，用自動(dòng)成成的名字代替最初的規(guī)則內(nèi)的動(dòng)作。
例如： 下面的句子是等價(jià)的
thing : A {printf("I am A") ;} B
thing : A fakename B;
fakename : {printf("I am A");}

歸約-歸約沖突

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

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

%{

序言

%}

Bison 聲明

%%

語(yǔ)法規(guī)則

%%

結(jié)尾

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

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

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

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

=例子一=

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

==語(yǔ)法文件==

語(yǔ)法文件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. */

第二部分：語(yǔ)法規(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ī)則之間用豎線“|”連接，讀作“或”。在花括號(hào)內(nèi)部的是用于已經(jīng)識(shí)別出來(lái)的非終結(jié)符的動(dòng)作（action），用C代碼寫(xiě)成。在動(dòng)作中偽變量$$代表即將被構(gòu)造的該分組的語(yǔ)義值。大部分動(dòng)作的的主要工作就是向偽變量賦值。而各個(gè)部件的語(yǔ)義值則由2等來(lái)引用。

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

對(duì) input 的解釋

input: /* empty */

| input line

;

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

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

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

對(duì) line 的解釋

line: ’\n’

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

;

第一個(gè)選擇就是一個(gè)記號(hào)，表示一個(gè)換行字符。其含義是，rpcalc 接受一個(gè)空行（可以被忽略，因此沒(méi)有對(duì)應(yīng)的動(dòng)作）。

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

對(duì) 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; } ;

...

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

==詞法分析器==

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

/* 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;

}

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

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

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

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

int main (void)

{

return yyparse ();

}

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

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

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

#include <stdio.h>

/* Called by yyparse on error. */

void

yyerror (char const *s)

{

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

}

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

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

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

對(duì)于單一文件的本程序來(lái)說(shuō)，用如下指令來(lái)將其轉(zhuǎn)換為一個(gè)解析器：

bison rpcalc.y

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

cc -lm -o rpcalc rpcalc.tab.c

下面是使用這個(gè)逆波蘭式計(jì)算器的例子，很顯然這種方式不符合人類(lèi)自然的思維習(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)一個(gè)中綴式計(jì)算器。

對(duì)于中綴運(yùn)算符，存在優(yōu)先級(jí)的概念，并有任意深度的括號(hào)嵌套層次。下面是文件“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);

}

在語(yǔ)法段中引入兩個(gè)重要特性：

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

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

%token則聲明一個(gè)沒(méi)有關(guān)聯(lián)性的記號(hào)類(lèi)型名稱(chēng)。

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

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

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

==簡(jiǎn)單的錯(cuò)誤恢復(fù)==

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

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

line: '\n'

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

| error '\n' { yyerrok; }

;

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

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

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

實(shí)現(xiàn)跟蹤定位將改善錯(cuò)誤消息。為簡(jiǎn)單起見(jiàn)，本例實(shí)現(xiàn)一個(gè)簡(jiǎ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 '^'

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

是否處理位置信息，對(duì)你的語(yǔ)言的語(yǔ)法并沒(méi)有影響。在這里將用位置信息來(lái)報(bào)告被零除的錯(cuò)誤，并定位錯(cuò)誤表達(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對(duì)應(yīng)規(guī)則中的部件，而偽變量@賦值，輸出解析器可以在執(zhí)行每個(gè)動(dòng)作對(duì)應(yīng)的C代碼之前自動(dòng)完成賦值。這個(gè)默認(rèn)行為是可以重定義的，對(duì)某些特殊規(guī)則，可以手工計(jì)算。[GNU的東西總是具有那么靈活的可配置性！]

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

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

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ù)返回一個(gè)記號(hào)時(shí)，解析器都知道它的數(shù)字，以及它的語(yǔ)義值，還有在文本中的位置。

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

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

int main()

{

yylloc.first_line = yylloc.last_line = 1;

yylloc.first_column = yylloc.last_column = 0;

return yyparse();

}

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

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

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

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

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

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

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

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

%{

#include “name.tab.h”

%}

%%

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

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

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

return T_NUMBER_LITERAL;

}

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

報(bào)錯(cuò)函數(shù)yyerror()的編寫(xiě)

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

int yyerror (const char* msg);

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

int yyerror( const char* msg)

{

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

return 0;

}

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

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

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

出自：http://blog.chinaunix.net/u/5929/showart_602272.html