FLEX
什么是FLEX回窘？它是一個自動化工具，可以按照定義好的規(guī)則自動生成一個C函數(shù)yylex()市袖，也成為掃描器（Scanner）啡直。這個C函數(shù)把文本串作為輸入，按照定義好的規(guī)則分析文本串中的字符苍碟，找到符合規(guī)則的一些字符序列后酒觅，就執(zhí)行在規(guī)則中定義好的動作（Action）。例如在規(guī)則中可以這樣定義：如果遇到一個換行字符\n微峰，那么就把行計數(shù)器的值加一舷丹。
Flex文件就是一個文本文件，內容包括定義好的一系列詞法規(guī)則蜓肆。文件的命名習慣上以小寫字母l(L)來作為文件后綴颜凯。如果為了清晰谋币，也可以用.flx或者.flex作為文件的后綴名。Flex文件完成后装获，就執(zhí)行下列命令：
$ flex example.flex
這個命令執(zhí)行后將生成一個C文件瑞信，默認文件名為lex.yy.c。這個C文件主要內容就是函數(shù)yylex()的定義穴豫。
如果要直接將這個文件編譯成為一個可執(zhí)行程序凡简，還有一些要注意的地方。如果在Flex文件中沒有提供main()函數(shù)的定義精肃，那么這個C文件中不會有main()函數(shù)秤涩。此時單獨編譯這個C文件的時候，一定要加上-lfl的連接庫參數(shù)司抱；若提供了main()函數(shù)筐眷，就不必要提供這個連接庫參數(shù)了。連接庫libfl提供了一個缺省的main函數(shù)习柠。缺省的main()函數(shù)中只是簡單地調用yyflex()函數(shù)匀谣，而自己提供的main()函數(shù)則可以根據(jù)需要加入許多其他的處理代碼。
Flex文件
詞法規(guī)范定義文件給出了單詞構成規(guī)則资溃。詞法文件在習慣上用字母l(即L的小寫)來作為后綴武翎。Flex文件由三個部分組成∪芏В或者說三個段宝恶。三個段之間用兩個%%分隔。
定義段(definitions)
%%
規(guī)則段(rules)
%%
用戶代碼段(user code)
定義段(definitions section)
定義段包含著一些簡單名字的定義(name definitions)趴捅，旨在簡化掃描器的規(guī)范垫毙。定義名字的方法如下:
name definition
名字可以由字母或下劃線開頭，后跟零個或多個字母拱绑、數(shù)字综芥、下劃線、或短橫線猎拨。名字的定義則從其后的第一個非空白字符(non-white-space)開始直到行尾毫痕。下面是一個例子，定義了一個名字DIGIT迟几，其定義就是指一個數(shù)字，如下所示：
DIGIT [0-9]
當在后面引用這個名字時栏笆，用一對花括號({})括住該名字即可类腮。它會被展開成一對圓括號括住的該名字的定義,即:
{name} 展開成 (definition)
例如：
{DIGIT}+"."{DIGIT}*
就等價于：
([0-9])+"."([0-9])*
定義段中還可以加入啟動條件(start conditions)的聲明。顧名思義蛉加，啟動條件就如同C語言中的條件編譯一樣蚜枢，根據(jù)指定的啟動條件去激活一條規(guī)則缸逃，并用這條規(guī)則去匹配讀入的字符。關于啟動條件厂抽，后面還有更詳細的介紹需频。
規(guī)則段(rules section)
規(guī)則由模式(pattern)和動作(action)兩個部分組成。模式就是一個正則表達式筷凤，F(xiàn)LEX加入了一些自己的擴展昭殉。而動作一般就是一些C語句。模式指出了一個單詞是如何構成的藐守，當分析出一個符合該規(guī)則的單詞時挪丢，就執(zhí)行相應的動作。
模式一定要位于一行的開頭處卢厂，不能有縮進乾蓬。而動作的開頭一定要與模式在同一行。當動作是用一對花括號{}括起來時慎恒，可以將左花括號放在與規(guī)則相同的行任内，而其余部分則可以從下一行開始。
用戶代碼段(user code)
所有用戶代碼都被原樣拷貝到文件lex.yy.c中融柬。在這里可以定義一些輔助函數(shù)或代碼死嗦，供掃描器yylex()調用，或者調用掃描器（一般來說就是main()了）丹鸿。這一部分是可有可無的越走。如果沒有的話，F(xiàn)lex文件中第二個%%是可以省略的靠欢。
在定義段或者規(guī)則段中廊敌，任何一行有縮進的文本或者包含在一對%{和%}之間的文本，都被原樣拷貝到最后生成的C代碼文件中（當然%{和%}會被移走）门怪。在書寫時%{和%}都必須在一行的開始處骡澈，不能縮進。
在規(guī)則段中掷空，第一條規(guī)則之前的任何未縮進的文本或者在%{和%}之間的文本肋殴，可以用來為掃描器聲明一些本地變量和代碼。一旦進入掃描器的代碼坦弟，這些代碼就會被執(zhí)行护锤。規(guī)則段內其他的縮進的文本或者%{和%}之間的文本還是被原樣拷貝輸出，但是他們的含義是尚未有明確定義酿傍，很可能引起編譯時（compile-time）錯誤（這一特性是為了與POSIX兼容而提供的）烙懦。
在定義段中，沒有縮進的注釋也會被原樣拷貝到最后生成的C代碼文件中赤炒，例如以/開始的一行注釋氯析，直到遇到/亏较，這中間的文本會被原樣拷貝輸出。
模式及其分類
模式采用正則表達式來書寫掩缓。正則表達式大致可以分為如下幾類（從上到下雪情，優(yōu)先級依次遞減）：
（1）單字符匹配
‘x’ 匹配字符x。
‘.’ 匹配任意一個字符（字節(jié)）你辣，除了換行符巡通。
‘[xyz]’ 匹配單個字符，這個字符是方括號中給出的字符類（character class）中的一個绢记。
‘[abj-oZ]’ 匹配單個字符扁达，這個字符是方括號中給出的字符類中的一個。與上一方式的區(qū)別是指定字符類時用到了一個范圍表示法：j-o蠢熄，這表示按照26個英文字母的順序跪解，從字母j開始一直到字母o共6個字母。這里減號（-）表示范圍签孔。如果減號本身也要作為一個匹配字符時叉讥，最好用轉義字符（\）去除其特殊含義。由于花括號（{}）在模式中用來引用名字饥追，以及作為模式定義之后的動作（Action）定義塊的首尾界定符图仓，因此如果要在字符類中匹配花括號，必須用轉義字符（\）去除其特殊含義但绕。下面這個例子定義了一個所有可打印字符的字符類：
[[:alnum:][:blank:]]\t+-*/&!_'?@^`~$\()%|.;[]{}:,#<>=]
‘[^A-Z]’ 匹配單個字符救崔，這個字符必須是方括號中給定字符類以外的字符。在方括號內開始處的特殊符號（）表示否定捏顺。當字符不在字符類的開始處時六孵，并不具有特殊含義，而是一個普通字符幅骄。
‘[^A-Z\n]’ 匹配單個字符劫窒，這個字符不可以是方括號中給出的字符類中的字符。與上一方式的不同在于拆座，這里多了一個換行符主巍，也就是說所匹配的字符不能是26個大寫字母，也不能是換行符挪凑。
根據(jù)上面的描述孕索，在表達字符分類時，除了直接用字符以及字符范圍來表達外躏碳，還有一種叫做字符類表達式的檬果，也有同樣的作用，常見的一些表達式如下：
[:alnum:] [:alpha:] [:blank:] [:cntrl:] [:digit:] [:graph:]
[:lower:] [:print:] [:punct:] [:space:] [:upper:] [:xdigit:]
每一個表達式都指示了一個字符分類，而且其名稱與標準C函數(shù)isXXXX的名字對應选脊。例如，[:alnum:]就指示了那些經由函數(shù)isalnum()檢查后返回true的字符脸甘，也就是任何的字母或者數(shù)字恳啥。注意，有些系統(tǒng)上沒有給出C函數(shù)isblank()的定義丹诀，所以flex自己定義了[:blank:]為一個空格或者一個tab。
下面所舉的幾個例子，都是等價的：
[[:alnum:]]
[[:alpha:][:digit:]]
[[:alpha:]0-9]
[a-zA-Z0-9]
應該注意字符類表達式的寫法绵跷。一個字符類表達式是由一對[:和:]包住的盒齿，作為一個整體，在書寫時不可與外層的[]混淆枚荣。
（2）重復模式的匹配
‘r’ r是一個正則表達式碗脊，特殊字符`'表示0個或多個。因此這個模式表示匹配0個或多個r橄妆。
‘r+’ r是一個正則表達式衙伶，特殊字符`+'表示1個或多個。因此這個模式表示匹配1個或多個r害碾。
‘r?’ r是一個正則表達式矢劲，特殊字符`?'表示0個或1個。因此這個模式表示匹配0個或1個r慌随。（從另一個角度看芬沉，就是說模式r是可選的）
‘r{2,5}’ r是一個正則表達式，{2,5}表示2個到5個阁猜。因此這個模式表示匹配2個到5個r丸逸。也就是說可以匹配
rr'，rrr'蹦漠，rrrr'椭员，rrrrr'四種重復的模式。‘r{2,}’ r是一個正則表達式笛园，{2,}省略了第二個數(shù)字隘击，表示至少2個，不設上限研铆。因此這個模式表示匹配2個及以上個r埋同。也就是說至少可以匹配
rr'，還可以匹配rrr'棵红，`rrrr'等無限多種重復的模式凶赁。‘r{4}’ r是一個正則表達式，{4}只有一個數(shù)字，表示4個虱肄。因此這個模式確切地匹配4個r致板，即`rrrr'。
（3）名字替換
- ‘{name}’ 這里name就是在前面的定義段給出的名字咏窿。這個模式將用這個名字的定義來匹配斟或。
（4）平凡（plain）文本串的匹配
- ‘“[xyz]\″foo”’ 這個模式用來確切地匹配文本串：[xyz]\″foo。注意最外層的單引號所包含的是整個模式表達式集嵌，也就是說萝挤，當希望匹配字串[xyz]\″foo時，在書寫規(guī)則時該字串必須用雙引號括住根欧。
（5）特殊單字符的匹配
‘\x’ 當x是一個
a'怜珍，b'，f'凤粗，n'酥泛，r'，t'或v'時侈沪，它就解釋為ANSI-C中的\x揭璃。否則就仍然作為一個普通字符x（一般用于諸如*'字符的轉義字符）。‘\0’ 匹配一個NUL字符（ASCII碼值為0）亭罪。
‘\123’ 匹配一個字符瘦馍，其值用八進制表示為123。
‘\x2a’ 匹配一個字符应役，其值用十六進制表示為2a情组。
（6）組合模式的匹配
‘(r)’ 匹配規(guī)則表達式r，圓括號可以提高其優(yōu)先級箩祥。
‘rs’ 匹配規(guī)則表達式r院崇，其后緊跟著表達式s。這稱為聯(lián)接(concatenation)袍祖。
‘r|s’ 或者匹配規(guī)則表達式r底瓣，或者匹配表達式s。
‘r/s’ 匹配模式r蕉陋，但是要求其后緊跟著模式s捐凭。當需要判斷本次匹配是否為“最長匹配（longest match）時，模式s匹配的文本也會被包括進來凳鬓，但完成判斷后開始執(zhí)行對應的動作（action）之前茁肠，這些與模式s相配的文本會被返還給輸入。所以動作（action）只能看到模式r匹配到的文本缩举。這種模式類型叫做尾部上下文（trailing context）垦梆。（有些‘r/s’組合是flex不能識別的匹颤；請參看后面deficiencies/bugs一節(jié)中的dangerous trailing context的內容。）
‘^r’ 匹配模式r托猩，但是這個模式只出現(xiàn)在一行的開始處印蓖。也就是說，剛開始掃描時遇到的京腥，或者說在剛掃描完一個換行字符后緊接著遇到的另伍。
‘r
。（在unix系統(tǒng)中換行是用一個字節(jié) \n 表示的围段，而DOS/Windows則采用兩個字節(jié) \r\n來表示換行顾翼。）
（7）有啟動條件（Start Condition）的模式匹配
‘<s>r’ 匹配模式r，但需要啟動條件s（后面后關于啟動條件的討論）奈泪。模式‘<s1,s2,s3>r’是類似的适贸，匹配模式r，只要有三個啟動條件s1涝桅，s2拜姿，s3中的任一個即可。（啟動條件簡單來說冯遂，類似于C語言中的條件編譯蕊肥，滿足了某個條件才啟動這個模式參與匹配，否則不會啟動該模式參與匹配蛤肌。）
‘<*>r’ 匹配模式r壁却，在任何啟動條件下都參與匹配，即使是排斥性的條件寻定。
[上述還需要從實踐中體會其含義]
（8）文件尾匹配
‘<<EOF>>’ 匹配文件尾儒洛，即遇到了文件尾部。一般說來狼速，都應該在模式中加入文件尾模式琅锻。這樣可以有機會在文件掃描完成時增加一些額外的處理。
‘<s1,s2><<EOF>>’ 在有啟動條件s1或者s2的情況下，匹配文件尾部恼蓬。
=========================================
創(chuàng)建一個簡單的掃描器
下列例子來自于Flex的手冊惊完。并在Windows+Cygwin+bison+flex+gcc的環(huá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/DOCUME1/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/DOCUME1/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/DOCUME1/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
上述消息指出兩個問題：
（1）函數(shù)yywrap沒有定義。
（2）自定義函數(shù)main與連接庫fl中的定義沖突了荷辕。
第一個問題的解決辦法是在第一段（定義段）中加上一個選項指令：
%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這個名字僅僅是一個默認的名稱控嗜，是可以改成其他名稱的。方法很簡單骡显，只需要對宏YY_DECL做一個重定義即可：
#define YY_DECL float lexscan (float a, float b)
上述的宏定義就表明：當運行Flex生成C代碼時疆栏，詞法分析函數(shù)的名字叫做lexscan（不再是yylex了），有兩個浮點型參數(shù)a和b惫谤，函數(shù)的返回值是浮點型壁顶。
如果與Bison聯(lián)用的話，還是不要更改的好溜歪，因為Bison要求詞法分析函數(shù)的名稱是yylex若专。[應該也是可以改的，但其實際的方法還需在實踐中得來痹愚。]
詞法分析函數(shù)yylex()會使用全局變量yyin讀取字符。
一些思考
（1）在H248協(xié)議的BNF文本中拯腮，需要分析很多的數(shù)字窖式，有十六進制的，有十進制的动壤，有長的數(shù)字也有短的數(shù)字萝喘。雖然在H248協(xié)議看來，各種不同的數(shù)字有著不同的意義琼懊，但是在Flex詞法掃描器看來阁簸，它們有什么不同呢？特別是同樣的一個0xab這樣的只有兩位數(shù)字的十六進制數(shù)哼丈，在H248協(xié)議和BISON看來启妹，其有不同的含義和類型，但是在Flex看來卻沒有什么不同醉旦。假設Bison分別將其定義為Token_A和Token_B饶米，那么當Flex分析出這么一個單詞時桨啃，返回給Bison的數(shù)字類型是A還是B？
（2）在H248協(xié)議中檬输，有一種表達式是由多個參數(shù)組成的照瘾，其中每個參數(shù)至多出現(xiàn)一次，且參數(shù)間次序是任意的丧慈。此外其中有兩個參數(shù)是必須的析命。這種情況下如何給出Bison文法規(guī)則定義呢？
文法分析概覽
利用BNF寫出的文法規(guī)則逃默，可以用來對輸入的文本進行文法分析鹃愤。一條BNF文法規(guī)則，左邊是一個非終結符（Symbol或者non-terminal）完域，右邊則定義該非終結符是如何構成的昼浦，也稱為產生式（Production），產生式中可能包含非終結符筒主，也可能包含終結符（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'
一個非終結符可能有多個產生式，相互間用豎線（|）隔開镐依。
每一條BNF產生式匹涮，都有自己的啟動集（start set）。啟動集里的元素就是每個Production中的第一個部分槐壳，比如上例S規(guī)則的啟動集就是{'-'}以及{FN}然低。
利用BNF文法來分析目標文本，其分析方法比較流行的有幾種务唐，下面作一概述[Garshol 03]雳攘。
LL(k)分析
LL分析又稱為自頂向下的分析（top-down parsing），也有叫遞歸下降分析（recursive-descent parsing）枫笛。也是最簡單的一種分析方式吨灭。它工作的方式類似于找出一個產生式可以從哪一個終結符開始。
當分析時刑巧，從起始符號開始喧兄，比較輸入中的第一個終結符和啟動集无畔，看哪一個產生式規(guī)則被使用了。當然繁莹，兩個啟動集之間不能擁有同一個終結符檩互。如果有的話，就沒有辦法決定選擇哪個產生式規(guī)則了咨演。
Ll文法通常用數(shù)字來分類闸昨，比如LL(1)，LL(0)等薄风。這個數(shù)字告訴你饵较，在一個文法規(guī)則中的任何點可以允許一次察看的終結符的最大數(shù)量。LL(0)就不需要看任何終結符遭赂，分析器總是可以選擇正確的產生式規(guī)則循诉。它只適用于所有的非終結符都只有一個產生規(guī)則。只有一個產生規(guī)則意味著只有一個字符串撇他。[不用看當前的終結符是什么就可以決定是哪一個產生規(guī)則茄猫，說明這個規(guī)則是為一個固定的字符串所寫的。]這種文法是沒有什么意義的困肩。
最常見也是比較有用的事LL(1)文法划纽。它只需要看一個終結符，然后就可以決定使用哪一個產生規(guī)則锌畸。而LL(2)則可以查看兩個終結符勇劣，還有LL(k)文法等等。對于某個固定的k值潭枣，也存在著根本不是LL(k)的文法比默，而且還很普遍。
下面來分析一下本章開頭給出的例子盆犁。首先看下面這條規(guī)則：
D := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
上述規(guī)則有十個產生式命咐，每個產生式的啟動集是一個數(shù)字終結符構成的集合{'0'}、{'1'}谐岁、……侈百、{'9'}。這是一個很好的LL(1)文法翰铡，因為我們只要看一個終結符钝域，就可以選擇一個正確的產生式。例如锭魔，如果看到一個終結符例证，其內容是3，那么就采用上面第四個產生式迷捧，即D := '3'织咧。
接下來分析DL規(guī)則胀葱。
DL := D | D DL
上述規(guī)則有兩個產生式，啟動集是{D}笙蒙，{D}抵屿。很不幸，兩個產生式的啟動集相同捅位。這就表示只看第一個輸入中的第一個終結符不能選擇正確的產生式轧葛。
然而可以通過欺騙來繞過這個問題：如果輸入中第二個終結符不是一個數(shù)字，那么就選擇第一個產生式艇搀，但如果兩者都是數(shù)字就必須選擇第二個產生式尿扯。換句話說，這意味著這是一條好的LL(2)文法規(guī)則焰雕。實際上這里有些東西被簡化了衷笋。
再分析下FN規(guī)則吧。它的情況更糟糕矩屁。
FN := DL | DL '.' DL
它有兩條產生式辟宗，而且啟動集相同，均為{DL}吝秕。然而這次不像DL規(guī)則那么幸運了慢蜓。咋一看，似乎通過LL(2)可以分辨應該使用哪一個產生式郭膛。但是很不幸，我們無法確定在讀到終結符('.')之前氛悬，需要讀多少個數(shù)字才算是DL符號的最后一個數(shù)字则剃。[想想吧，分析器這么工作著：讀入第一個終結符如捅，一看是相同的DL符號棍现，那么就讀第二個終結符吧；讀入第二個終結符镜遣，兩者合起來一看己肮，還是一樣的DL符號；讀入第三個終結符悲关，前三個終結符合起來看谎僻，仍然是相同的DL符號。但是DL符號表指示數(shù)字表示沒有長度限制的寓辱。]沒有任何一個給定的k值艘绍，這都不符合LL(k)文法，因為數(shù)字表總能突破這個k的長度秫筏。
最后看看啟動符號規(guī)則诱鞠。有點意外挎挖，它產生規(guī)則的選擇很簡單。
S := '-' FN | FN
它有兩個產生規(guī)則航夺，兩者的啟動集是{'-'}和{FN}蕉朵。因此，如果輸入中第一個終結符是'-'阳掐，那么就選擇第一個產生式始衅，否則選擇第二個產生式。所以這是一個LL(1)文法锚烦。
從上述的LL分析看觅闽，只有FN和DL規(guī)則引起了問題。但是不必絕望涮俄。大部分的非LL(k)文法都可以容易地轉換為LL(1)文法蛉拙。下面以當前的這個例子來看看如何轉換有問題的FN和DL。
對于FN符號來說彻亲，它的兩個產生式都開始于DL孕锄，但是第二個產生式其后續(xù)的是一個小數(shù)點終結符('.')，以及另外一個數(shù)字表苞尝。那么這很容易解決：可以將FN改變?yōu)橐粋€產生式畸肆，其以DL開始，后跟一個FP（fractional part）符號宙址。而FP符號則定義成或者為空轴脐，或者為小數(shù)點后跟著一個數(shù)字表，如下所示：
FN := DL FP
FP := @ | '.' DL
上述@符號表示為空÷丈埃現(xiàn)在FN文法沒有任何問題了房蝉，因為它現(xiàn)在只有一個產生式贾铝。而FP也不會有問題，因為它的兩個產生式的啟動集是不同的：前者是輸入的尾端，后者是小數(shù)點終結符贸桶。
DL符號就不是好啃的核桃了捶朵，原因在于其遞歸和至少需要一個D符號勾缭。解決方案就是高镐，給DL一個產生式，由一個D后跟一個DR（digit rest）構成啤月；而DR則有兩個產生式煮仇，一個是D DR（表示更多的數(shù)字），一個是@（表示沒有更多的數(shù)字）谎仲。最后本章開頭的例子被轉換成下面的一個完全的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）欺抗，或者叫移進-歸約分析（shift-reduce parsing），相比LL分析難度更大些强重。它的基本原理是绞呈，首先收集輸入贸人，直到它發(fā)現(xiàn)可以據(jù)此利用一個符號對收集到的輸入序列進行歸約〉枭可以與數(shù)學里面解方程式時的消元法進行類比艺智。這聽起來似乎很難。下面還是以一個例子來澄清圾亏。例子中將分析字符串3.14十拣，看看是怎樣從文法產生出來的。
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夭问，即非終結符）。實際上可以歸約曹铃，就是說用D符號的產生式可以得到當前讀入的字符串（這也是成為產生式的原因）缰趋。
很快發(fā)現(xiàn)，從DL符號可以產生符號D陕见，于是又可以歸約成DL秘血。（實際上還可以進一步地歸約成FN，于是這里就產生了歧義评甜，到底應該歸約成哪一個呢灰粮？這表明這個文法定義是二義性的，我們在這里就忽略這個問題忍坷，直接選擇DL作為歸約結果吧粘舟。）接著從輸入中讀入一個小數(shù)點，并試圖進行歸約：
D ==> 規(guī)約到DL
DL ==> 讀入下一個字符
DL . ==> 規(guī)約到佩研？
但是這次的歸約嘗試失敗了柑肴，因為沒有任何符號的定義可以產生這種形式的字符串。也就是說韧骗，這種形式不能規(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
察看文法我們可以很快地注意到淋样，F(xiàn)N能產生DL . Dl這種形式的序列，所以可以做一個歸約胁住。然后注意到FN可以從S符號產生趁猴，所以可以歸約到S刊咳，然后停止，整個分析結束儡司。
DL . DL ==> 歸約到FN
FN ==> 規(guī)約到S
S ==> 分析結束
可能你已經注意到娱挨，我們經常可以選擇是否現(xiàn)在就做歸約捕犬，還是等到讀入更多的符號后再作不同的歸約跷坝。移進-歸約分析算法有很多不同的變種，按照復雜度和能力遞增的順序是：LR(0)碉碉， SLR柴钻， LALR和LR(1)。LR(1)通常需要一個巨大的分析表垢粮，在實踐上不具有實用性贴届，因此LALR是最常使用的算法。SLR和LR(0)對于大部分的程序語言來說還不夠強大足丢。
Bison分析器的算法1
Bison適合上下文無關文法（Context-free grammar）粱腻，并采用LALR(1)算法[Donnelly 06]的文法。
當bison讀入一個終結符（token）斩跌，它會將該終結符及其語意值一起壓入堆棧绍些。這個堆棧叫做分析器堆棧（parser stack）。把一個token壓入堆棧通常叫做移進（shifting）耀鸦。
例如柬批，假設一個中綴計算器已經讀入'1 + 5 * '，下一個準備讀入的是'3'袖订，那么這個棧里就有四個元素氮帐，每個元素都是移進的一個終結符。
但堆棧并不是每讀入一個終結符就分配一個棧元素給它洛姑。當已經移進的后n個終結符和組（groupings）與一個文法規(guī)則相匹配時上沐，它們會被根據(jù)那個規(guī)則結合起來。這叫做歸約（reduction）楞艾。棧中的那些終結符和組會被單個的組（grouping）替換参咙。那個組的符號就是那個規(guī)則的結果。執(zhí)行該規(guī)則的相應的動作（Action）也是歸約處理的一部分硫眯，這個動作會計算這個組的語意值蕴侧。
例如，如果中綴計算器的分析器堆棧包含：1 + 5 * 3两入，并且下一個輸入字符是換行符净宵，那么上述后3個元素可以按照下面規(guī)則歸約到15：
expr: expr '*' expr;
于是堆棧中就只包含下面三個元素了：1 + 15。此刻，另一個規(guī)約也可以執(zhí)行择葡，其結果是一個單值16紧武。然后這個新行終結符就可以被移進了。
分析器通過移進和歸約嘗試著縮減整個輸入到單個的組刁岸。這個組的符號就是文法中的起始符號（start-symbol）脏里。
終結符預讀
Bison分析器并不總是在后n個終結符與組匹配某一規(guī)則時立即就進行歸約。這種策略對于大部分語言來說并不合適虹曙。相反迫横，當可以進行歸約時，分析器有時會“預讀”（looks ahead）下一個終結符來決定做什么酝碳。
當一個終結符被讀進來后矾踱，并不會立即移進堆棧，而是首先作為一個預讀終結符（look-ahead token）疏哗。此后呛讲，分析器開始對棧上的終結符和組執(zhí)行一個或多個歸約，而預讀終結符仍然放在一邊返奉。當沒有歸約可做時贝搁，這個預讀終結符才會被移進堆棧。這并不表示所有可能的歸約都已經做了芽偏，這要取決于預讀終結符的類型雷逆，一些規(guī)則可能選擇推遲它們的使用。
下面研究一個需要做預讀的案例污尉。這里的三條規(guī)則定義了一個表達式膀哲，可以包含二元的加法運算符和一元的后綴階乘運算符('!')，并且允許用括號進行分組被碗。
expr: term '+' expr
| term
;
term: '(' expr ')'
| term '!'
| NUMBER
;
假定終結符'1' '+' '2'已經讀入并移進堆棧某宪，那么接下來應該做什么呢？如果接下來的終結符是')'锐朴，那么前三個終結符必須歸約成一個expr兴喂。這是唯一的合法情況，因為移進')'將會產生一個序列term ')'焚志，而沒有任何規(guī)則允許出現(xiàn)這種情況衣迷。[不做歸約移進')'，堆棧上的元素序列是1 + 2 )娩嚼，2可以歸約成NUMBER蘑险，進而歸約成term滴肿，與其后的 ')'形成term ')'的序列岳悟，檢查所有規(guī)則發(fā)現(xiàn)沒有任何規(guī)則定義了這種序列。]
如果下一個終結符是'!'[記住此刻它還是預讀終結符]，那么該終結符必須立即移進堆棧以便'2 !'可以歸約成一個term贵少。如果相反地分析器在移進這個階乘符號之前進行歸約呵俏，那么'1 + 2'就會歸約成expr。這將導致不可能移進'!'終結符滔灶，因為這樣的話將會產生一個expr '!'序列普碎。同樣沒有任何規(guī)則定義了這種序列。
預讀終結符存儲在變量yychar中录平。它的語意值和位置麻车，如果有的話，存儲在變量yylval和yylloc中斗这。
移進-歸約沖突
假定我們正在分析一個語言动猬，其中有if-then和if-then-else語句，對應的規(guī)則如下：
if_stmt: IF expr THEN stmt
| IF expr THEN stmt ELSE stmt
;
這里我們假設IF表箭，THEN和ELSE是特別的關鍵字終結符赁咙。
當ELSE終結符讀入后作為一個預讀終結符時，堆棧中的內容（假設輸入是合法的）正好可以歸約到第一條規(guī)則上免钻。但是把它移進堆棧也是合理的彼水，因為那樣根據(jù)第二條規(guī)則就會導致最后的歸約。
在這種情況下凤覆，移進或者歸約都是合法的，稱為移進-歸約沖突（shift-reduce conflict）揪胃。Bison的設計是骚勘，用移進來解決沖突玲献，除非有操作符優(yōu)先級聲明的指令抹锄。為了解釋如此選擇的理由，讓我們與其它可選辦法進行一個比較砾层。
既然分析器更傾向移進ELSE瘩燥，那么其結果是把else子句連接到最內層的if語句菱魔，從而使得下面兩種輸入是等價的：
if x then if y then win (); else lose;
if x then do; if y then win (); else lose; end;
如果分析器選擇歸約而不是移進桩卵，那么其結果將是把else子句連接到最外層的if語句辞州，從而導致下面兩個輸入是等價的：
if x then if y then win (); else lose;
if x then do; if y then win (); end; else lose;
沖突的存在是因為文法有二義性：簡單的嵌套的if語句的任一種解析都是合理的。已有的慣例是這種二義性的解決是通過把else子句連接到最內層的if語句而獲得的寥粹；Bison是選擇移進而不是歸約來實現(xiàn)的变过。（一種更清晰的做法是寫出無二義性的文法，但對于這種情況來說是非常困難的涝涤。）這種特殊的二義性首次出現(xiàn)在Algol 60的規(guī)范中媚狰，被稱作'dangling else ambiguity'。
對于可預見的合法的移進-歸約沖突阔拳，為避免bison發(fā)出的警告哈雏，可以使用%expect n聲明。那么只要移進-規(guī)約沖突的數(shù)量為n衫生，就不會有警告產生裳瘪。
操作符優(yōu)先級
可能出現(xiàn)移進-歸約沖突的其它地方還有算術表達式。此時移進就不總是更好的解決辦法了罪针。Bison通過聲明操作符的優(yōu)先級來指定何時移進何時歸約彭羹。
何時需要優(yōu)先級
考慮下面的二義文法片斷（其二義性體現(xiàn)在'1 – 2 * 3'可以用兩種不同的方式進行分析）：
expr: expr '-' expr
| expr '*' expr
| expr '<' expr
| '(' expr ')'
...
;
假定分析器已經看到了終結符'1'，'-'和'2'泪酱；那么應該對它們歸約到減法運算規(guī)則嗎派殷？這取決于下一個終結符还最。當然，若下一個終結符是')'毡惜，就必須歸約拓轻；此時移進是非法的，因為沒有任何規(guī)則可以對序列'- 2 )'進行歸約经伙，也沒有以這個序列開始的什么東西扶叉。但是如果下一個終結符是'*'或者'<'，那么就需要做一個選擇：移進或者歸約帕膜，都可以讓分析得以完成枣氧，但是卻有不同的結果。
為了決定Bison應該怎么做垮刹，必須考慮這兩個結果达吞。若下一個終結符即操作符op被移進，那么必然是op首先做歸約荒典，然后才有機會讓前面的減法操作符做歸約酪劫。其結果就是（有效的）'1 – (2 op 3)'。另一方面寺董，若在移進op之前先對減法做歸約契耿，那結果就是'(1 – 2) op 3'。很顯然螃征，這里移進或者規(guī)約的選擇取決于減法操作符'-'與下一個操作符op之間的優(yōu)先級：若op是乘法操作符'*'搪桂，那么就選擇移進；若是關系運算符'<'則應該選擇規(guī)約盯滚。
那么諸如'1 – 2 – 5'這樣的輸入又如何呢踢械？是應該作為'(1 – 2) – 5' 還是應該作為'1 – (2 – 5)' ？對于大多數(shù)的操作符魄藕，我們傾向于前一種形式内列，稱作左關聯(lián)（left association）。后一種形式稱作右關聯(lián)（right association）背率，對于賦值操作符來說是比較理想的话瞧。當堆棧中已經有'1 – 2' 且預讀終結符是'-'，此時分析器選擇移進還是歸約與選擇左關聯(lián)還是右關聯(lián)是一回事：移進將會進行右關聯(lián)寝姿。
指定操作符優(yōu)先級
Bison允許通過聲明%left和%right來指定操作符優(yōu)先級交排。每個這樣的聲明都包含一列終結符，這些終結符都是操作符饵筑，它們的優(yōu)先級和關聯(lián)性都被聲明了埃篓。%left聲明讓所有這些操作符左關聯(lián)，而%right聲明讓它們右關聯(lián)根资。第三種方案是%noassoc架专，它聲明了這是一個語法錯誤同窘，表明“在一行中”找到了兩個同樣的操作符。
不同操作符的優(yōu)先級由它們的聲明次序來決定部脚。先聲明的優(yōu)先級低想邦，后聲明的優(yōu)先級高。[如果有同等優(yōu)先級的呢委刘？應該是按照其關聯(lián)性來決定了是移進還是規(guī)約丧没。]
優(yōu)先級例子
在本節(jié)給出的例子中，我們希望有如下的聲明：
%left '<'
%left '-'
%left '*'
在更復雜的例子中有更多的操作符钱雷，同等優(yōu)先級的操作符可以分成一組進行聲明，如下所示：
%left '<' '>' '=' NE LE GE
%left '+' '-'
%left '*' '/'
這里NE代表not equal（不等于）吹零，LE表示小于等于罩抗，GE表示大于等于。
優(yōu)先級如何工作
優(yōu)先級聲明的第一個效果就是賦予了終結符不同的優(yōu)先級水平灿椅。第二個效果就是給某些規(guī)則賦予了優(yōu)先級水平：每個規(guī)則從它的最后的終結符得到其優(yōu)先級套蒂。[當已讀入的終結符和組符合某個規(guī)則時茫蛹，理論上講它可以進行歸約操刀。它最后的一個終結符可能被指定了優(yōu)先級，這個優(yōu)先級就成為該規(guī)則的優(yōu)先級婴洼。]
最終骨坑，沖突的解決是通過比較規(guī)則的優(yōu)先級與它的預讀終結符的優(yōu)先級實現(xiàn)的。若該終結符的優(yōu)先級高柬采，那么就采用移進欢唾。過規(guī)則的優(yōu)先級較高，那么就選擇歸約粉捻。若它們具有相同的優(yōu)先級礁遣，那么就基于該優(yōu)先級的關聯(lián)性來作出選擇。選項'-v'可以讓Bison產生詳細的輸出肩刃，其中有沖突是怎樣解決的信息祟霍。
并非所有的規(guī)則和終結符都具有優(yōu)先級。若規(guī)則或預讀終結符都沒有優(yōu)先級盈包，那么缺省采用移進[解決沖突]沸呐。
與上下文相關的優(yōu)先級
經常有操作符的優(yōu)先級依靠上下文。起初這聽起來有些奇怪（outlandish）呢燥，但這的確非常普通垂谢。例如，典型地一個減號作為一元操作符有非常高的優(yōu)先級疮茄，而作為二元操作符則具有較低的優(yōu)先級（比乘法低）滥朱。
對于給定的終結符根暑，聲明%left，%right和%noassoc只能使用一次徙邻，所以這種方式下一個終結符只有一個優(yōu)先級排嫌。對于與上下文相關的優(yōu)先級，需要一個新增的機制：用于規(guī)則的%prec修飾符缰犁。
%prec修飾符聲明了某個規(guī)則的優(yōu)先級淳地，通過指定某個終結符而該終結符的優(yōu)先級將用于該規(guī)則。沒有必要在該規(guī)則出現(xiàn)這個終結符帅容。[就是說這個終結符可以是臆造的颇象，在系統(tǒng)中可能并沒有實際的對應體，只是為了用于指定該規(guī)則的優(yōu)先級]并徘。下面是優(yōu)先級的語法：
%prec terminal-symbol
并且這個聲明必須寫在該規(guī)則的后面[看下面的例子]遣钳。這個聲明的效果就是把該終結符所具有的優(yōu)先級賦予該規(guī)則，而這個優(yōu)先級將會覆蓋在普通方式下推斷出來的該規(guī)則的優(yōu)先級麦乞。這個更改過的規(guī)則優(yōu)先級會影響規(guī)則如何解決沖突蕴茴。
下面就是解決一元的負號的問題。首先姐直，定義一個名為UMINUS的虛構的終結符倦淀，并為之聲明一個優(yōu)先級。實際上并沒有這種類型的終結符声畏，但是這個終結符僅僅為其的優(yōu)先級服務撞叽。
...
%left '+' '-'
%left '*'
%left UMINUS
現(xiàn)在UMINUS的優(yōu)先級可如此地用于規(guī)則：
exp: ...
| expr '-' exp
...
| '-' exp %prec UMINUS
分析器的狀態(tài)
函數(shù)yyparse用一個有限狀態(tài)機（finite-state）實現(xiàn)。壓入分析器堆棧的值并不是簡單地終結符類型碼插龄。它們代表靠近堆棧頂部的整個的終結符和非終結符的序列能扒。當前狀態(tài)收集關于前一個輸入的所有信息，而這個輸入與決定下一步作什么有關辫狼。
每次預讀入一個終結符后初斑，分析器當前狀態(tài)與預讀終結符的類型一起甫菠，到表中查找蔫耽。對應的表項可能是：移進這個預讀終結符。這種情況下遂蛀，它也會指定新的分析器狀態(tài)真椿，并被壓入到分析器棧的頂部鹃答。或者這個表項可能是：用規(guī)則n進行歸約突硝。這就意味著一定數(shù)量的終結符或組會被從堆棧頂部取走测摔，并用一個組取代。換句話說，那些數(shù)量的狀態(tài)被從堆棧彈出锋八，一個新的狀態(tài)被壓棧浙于。
另外一個可能是：這個表項會告訴說，這個預讀終結符對當前狀態(tài)來說是錯誤的挟纱。這將導致開始一個錯誤處理羞酗。
基礎的關鍵詞概念：
yacc如何取到 lex詞法解析出來的值呢：
當Lex匹配到一個目標時，它就會將匹配到的文字放到y(tǒng)ytext中紊服。YACC從變量yylval中取值檀轨。以yytext作為參數(shù)調用atoi函數(shù)，并將其返回值賦給yylval變量欺嗤，這樣YACC就可以使用它
[0-9]+ yylval=atoi(yytext); return NUMBER;
例如：
為了取到規(guī)則中的第三個部分的值参萄，（例如，NUMBER）,我們需要使用$3煎饼，只要yylex返回讹挎，yylval的值就會被顯示在終端中，其值經由$取得腺占。
target_set:
TOKTARGET TOKTEMPERATURE NUMBER
{
printf("\tTemperature set to %d\n",$3);
}
;
嵌入式動作
對于語法分析程序中的每一個語法規(guī)則淤袜，都有相應的C/C++語句來做一些額外的處理痒谴，這個額外的處理就是語法動作衰伯。不過語法動作和詞法動作的不同之處在于，語法動作允許嵌入式的語法動作积蔚，而詞法動作不行意鲸。
盡管yacc的語法分析技術只允許動作在規(guī)則的末端，但yacc可以自動模擬嵌入在規(guī)則內部的動作尽爆。如果在規(guī)則內部寫入一個動作怎顾，yacc就會創(chuàng)造一個右側為空并且左邊是自動生成的名字規(guī)則，使得嵌入的動作進高規(guī)則的動作里去漱贱，用自動成成的名字代替最初的規(guī)則內的動作槐雾。
例如： 下面的句子是等價的
thing : A {printf("I am A") ;} B
thing : A fakename B;
fakename : {printf("I am A");}
歸約-歸約沖突
BISON
==Bison 語法文件內容的布局==
Bison 工具將把 Bison 語法文件作為輸入。語法文件的擴展名為.y幅狮。Bison 語法文件內容的分布如下（四個部分）：
%{
序言
%}
Bison 聲明
%%
語法規(guī)則
%%
結尾
序言部分可定義 actions 中的C代碼要用到的類型和變量募强，定義宏，用 #include 包含頭文件等等崇摄。要在此處聲明詞法分析器 yylex 和錯誤輸出器 yyerror 擎值。還在此處定義其他 actions 中使用到的全局標識符。
Bison聲明部分可以聲明終結符和非終結符的名字逐抑，也可以描述操作符的優(yōu)先級鸠儿，以及各種符號的值語義的數(shù)據(jù)類型。各種非單個字符的記號（節(jié)點）都必須在此聲明。
語法規(guī)則部分描述了如何用組件構造出一個非終結符进每。（這里我們用術語組件來表示一條規(guī)則中的各個組成部分汹粤。）
結尾部分可以包含你希望使用的任何的代碼。通常在序言部分聲明的函數(shù)就在此處定義品追。在簡單程序中所有其余部分都可以在此處定義玄括。
=例子一=
本例子完整實現(xiàn)一個采用逆波蘭式語法的計算器。
==語法文件==
語法文件rpcalc.y的內容如下：
第一部分：序言和聲明
/* 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ī)則之間用豎線“|”連接肉瓦，讀作“或”遭京。在花括號內部的是用于已經識別出來的非終結符的動作（action），用C代碼寫成泞莉。在動作中偽變量$$代表即將被構造的該分組的語義值哪雕。大部分動作的的主要工作就是向偽變量賦值。而各個部件的語義值則由2等來引用斯嚎。
構造同一個非終結符的多個可替換規(guī)則構成了多個選擇，對每一個替換規(guī)則挨厚，在后文中用“選擇”來稱呼堡僻。
對 input 的解釋
input: /* empty */
| input line
;
上述讀作：一個完整的輸入或者是一個空串，或者是一個完整的輸入后跟著一個輸入行疫剃《ひ撸“完整輸入”就是由其自身定義的。
在冒號與第一個豎線之間沒有任何字符巢价，就表示為空牲阁。其含義表示input可以匹配一個空串的輸入（沒有記號）。這樣可以處理打開計算器后就輸入Ctrl-d結束輸入的情況壤躲。習慣上在為空的地方加上一個注釋/* empty */城菊。
第二個選擇的含義是，在讀入了任意數(shù)量的行以后碉克，可能的情況下再讀入一行凌唬。左邊的遞歸使本規(guī)則進入到一個循環(huán)，由于第一個選擇是空漏麦，所以循環(huán)可以被執(zhí)行0次或多次客税。
對 line 的解釋
line: ’\n’
| exp ’\n’ { printf ("\t%.10g\n", $1); }
;
第一個選擇就是一個記號，表示一個換行字符唁奢。其含義是霎挟，rpcalc 接受一個空行（可以被忽略，因此沒有對應的動作）麻掸。
第二個選擇就是一個表達式后跟著一個換行字符酥夭。這就使 rpcalc 變得有用起來。$1就是 exp 組的語義值，因為此處 exp 就是該選擇中的第一個符號熬北。對應的動作并不是普通的賦值給偽變量$$疙描，這樣與 line 關聯(lián)的語義值就是未初始化的（因此其值是不可預測的）。倘若使用了這個值讶隐，拿這就是一個 bug起胰。但本例中計算器并不使用這個值，
對 exp 的解釋
exp: NUM { $$ = $1; }
| exp exp ’+’ { $$ = $1 + $2; }
| exp exp ’-’ { $$ = $1 - $2; }
...
;
上述形式還有一種等價形式：
exp: NUM ;
exp: exp exp ’+’ { $$ = $1 + $2; } ;
exp: exp exp ’-’ { $$ = $1 - $2; } ;
...
并不需要為每個規(guī)則都指定動作巫延，當一條規(guī)則沒有動作時效五，Bison 默認情況下把$1的值拷貝給$$。
==詞法分析器==
詞法分析器的工作是低級的分析：把字符或字符序列轉換成記號炉峰。Bison 調用詞法分析起來獲得記號畏妖。本例只需要一個簡單的詞法分析器。下面就是詞法分析器的代碼：
/* 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ù)字部分的任何其他字符都是一個單獨的記號婆廊。注意單字符記號的記號代碼就是該字符本身迅细。
該記號的語義值被存儲到全局變量 yylval，被 Bison 的解析器使用淘邻。（yylval的C數(shù)據(jù)類型是YYSTYPE茵典，定義在語法的開頭部分。）
一個為零的記號類型代碼被返回列荔，表示輸入結束敬尺。（Bison 把任何的非正值識別為輸入結束枚尼。）
==控制函數(shù)==
int main (void)
{
return yyparse ();
}
控制函數(shù)的唯一目的就是調用函數(shù) yyparse 來啟動解析處理贴浙。
==錯誤報告例程==
當 yyparse 檢測到一個錯誤時，將調用錯誤報告函數(shù) yyerror 打印出一條錯誤消息署恍。下面是本例中使用的代碼崎溃。
#include <stdio.h>
/* Called by yyparse on error. */
void
yyerror (char const *s)
{
fprintf (stderr, "%s\n", s);
}
如果語法中包含有合適的錯誤規(guī)則，那么在 yyerror 返回后盯质，Bison 解析器就可以從錯誤中恢復袁串，并繼續(xù)解析。本例沒有提供錯誤規(guī)則呼巷，因此當遇到非法輸入時囱修，程序將退出。
==運行Bison制作解析器==
首先要考慮如何組織源代碼到一個或多個文件中王悍。本例作為一個簡單程序破镰，全部放到一個文件中是最簡單的。把yylex、yyerror和main函數(shù)都放在語法文件的結尾部分就可以了鲜漩。如果是一個大型工程源譬，可能需要許多文件，并使用make工具來組織編譯工作孕似。
對于單一文件的本程序來說踩娘，用如下指令來將其轉換為一個解析器：
bison rpcalc.y
Bison 將產生一個輸出文件，名為rpcalc.tab.c喉祭。該輸出文件中包含有供yyparse使用的代碼养渴。一些額外的代碼（如yylex，yyerror泛烙，以及main）被原樣輸出到該文件中厚脉。最后用編譯器將生成的C文件編譯成可執(zhí)行文件，這樣計算器程序就可用了胶惰。編譯命令如下：
cc -lm -o rpcalc rpcalc.tab.c
下面是使用這個逆波蘭式計算器的例子傻工，很顯然這種方式不符合人類自然的思維習慣。
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
=例子二=
本例子將實現(xiàn)一個中綴式計算器孵滞。
對于中綴運算符中捆，存在優(yōu)先級的概念，并有任意深度的括號嵌套層次坊饶。下面是文件“calc.y”的內容：
/* 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 聲明了記號類型泄伪，并指出他們是左關聯(lián)運算符（left-associative operator）。
%right則表示是右關聯(lián)運算符（right-associative operator）匿级。
%token則聲明一個沒有關聯(lián)性的記號類型名稱蟋滴。
本來單字符的記號一般不需要在這里聲明，但這里是為了指出他們的關聯(lián)性痘绎。
注意：運算符的優(yōu)先級則由聲明的行順序決定津函，即越后聲明的優(yōu)先級越高，因此首先聲明的運算符的優(yōu)先級最低孤页，最后聲明的運算符優(yōu)先級最高尔苦。本例中冪運算優(yōu)先級最高，其次是一元取負運算符行施，接著是乘除運算允坚，最低是加減運算。
另一個特性是一元取負運算符中用到的%prec蛾号。這個%prec指示bison本條規(guī)則“| '-' exp”具有與NEG相同的優(yōu)先級稠项，本例中即是次高優(yōu)先級（next-to-highest）。
==簡單的錯誤恢復==
檢測到語法錯誤后鲜结，如何繼續(xù)進行解析呢展运？目前已經知道可以用 yyerror 報告錯誤斩芭。默認情況下在調用了 yyerror 后， 函數(shù) yyparse將返回乐疆。這樣當遇到錯誤的輸入行時計算器程序將退出划乖。
bison 自己有一個保留關鍵字 error，可以用在語法規(guī)則部分挤土。下面是一個例子：
line: '\n'
| exp '\n' { printf ("\t%.10g\n", $1); }
| error '\n' { yyerrok; }
;
當不可計算的表達式被讀入后琴庵，上述第三條規(guī)則將識別出這個錯誤，解析將繼續(xù)仰美。yyerror 仍將被調用以打印出一條消息迷殿。第三條規(guī)則對應的動作是一個宏 yyerrok，由bison自動定義咖杂。此宏的含義是錯誤恢復已經完成庆寺。要注意 yyerrok 和yyerror的區(qū)別，這不是打字錯誤诉字。
本例中只處理了語法錯誤懦尝，實際還有很多如除零錯誤等需要處理。
==跟蹤定位計算器==
實現(xiàn)跟蹤定位將改善錯誤消息壤圃。為簡單起見陵霉，本例實現(xiàn)一個簡單的整數(shù)計算器。
/* 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ù)類型伍绳，本例將使用默認類型：一個含四個整型成員的結構踊挠，即first_line, first_column, last_line, last_column。
是否處理位置信息冲杀，對你的語言的語法并沒有影響效床。在這里將用位置信息來報告被零除的錯誤，并定位錯誤表達式或子表達式权谁。
/* 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對應規(guī)則中的部件剩檀，而偽變量@賦值闯传，輸出解析器可以在執(zhí)行每個動作對應的C代碼之前自動完成賦值谨朝。這個默認行為是可以重定義的卤妒，對某些特殊規(guī)則甥绿，可以手工計算。[GNU的東西總是具有那么靈活的可配置性则披！]
那么詞法分析器應該怎樣寫呢共缕？在詞法分析器中一個重要的任務是告訴解析器各個記號的位置。
為此我們必須計算輸入文本中每個字符士复，以避免計算位置混淆或錯誤图谷。
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ù)字，以及它的語義值便贵，還有在文本中的位置菠镇。
[可以將這樣來看，四個值構成成一個盒子承璃，每一個合法的記號都應該放到一個盒子里利耍。當讀入一個較長的記號時，顯然最后一列的值在增加盔粹，而開始讀新的一行時隘梨，最后一行的值也要增加。]
還需要初始化yylloc舷嗡，這在控制函數(shù)中完成：
int main()
{
yylloc.first_line = yylloc.last_line = 1;
yylloc.first_column = yylloc.last_column = 0;
return yyparse();
}
注意：計算位置與語法無關轴猎，因此，每個字符都必須關聯(lián)一個位置进萄，無論該字符在合法輸入中捻脖，還是在注釋中，或者字串中等中鼠。yylloc是一個全局變量郎仆，類型是YYLTYPE，它包含著記號的位置信息兜蠕。
用bison來做語法分析扰肌，首先要將分析對象做仔細的研究。分析工作的首要任務是分清楚什么是終結符熊杨，什么是非終結符曙旭。
終結符是一組原子性的單詞，表達了語法意義中不可分割的一個標記晶府。在具體的表現(xiàn)形式上桂躏，可能是一個字符串，也可能是一個整數(shù)川陆，或者是一個空格剂习，一個換行符等等。bison只給出每個終結符的名稱较沪，并不給出其定義鳞绕。Bison為每個終結符名稱分配一個唯一的數(shù)字代碼。
終結符的識別由專門定義的函數(shù)yylex()執(zhí)行尸曼。這個函數(shù)返回識別出來的終結符的編碼们何，且已識別的終結符可以通過全局變量yytext指針，而這個終結符的長度則存儲在全局變量yyleng中控轿。來取得這種終結符的分析最好用flex工具通過對語法文件進行掃描來識別冤竹。有些終結符有不同的具體表示拂封。例如h248協(xié)議中的表示版本號的終結符VersionToken，既可能用字串Version表示鹦蠕，也可能用一個字符V表示冒签。這種情況下，Bison中只給出終結符名稱钟病，而由Flex給出終結符的具體定義镣衡。
非終結符是一個終結符序列所構成的一個中間表達式的名字。實際上不存在這么一個原子性的標記档悠。這種非終結符的構成方式則應該由Bison來表達廊鸥。語法規(guī)則就是由終結符和非終結符一起構成的一種組成規(guī)則的表達。
Bison的文法規(guī)則中各個組成部分是有次序性的辖所。如果在一個文法定義中惰说，各個元素的次序是任意的，并且其中某些元素又是必須的缘回，該怎么來編寫這樣的Bison文法規(guī)則呢吆视？Bison的文法規(guī)則定義文件在命名習慣上以字母y作為后綴。
Bison實際上也是一個自動化的文法分析工具酥宴，其利用詞法分析函數(shù)yylex()返回的詞法標記返回其ID啦吧，執(zhí)行每一條文法規(guī)則后定義的動作。Bison是不能自動地生成詞法分析函數(shù)的拙寡。一般簡單的程序里授滓，一般在文法規(guī)則定義文件的末尾添加該函數(shù)的定義。但是在較復雜的大型程序里肆糕，則利用自動詞法生成工具flex生成yylex()的定義般堆。
Bison與Flex聯(lián)用時，Bison只定義標記的ID诚啃。Flex則需要知道這些詞法標記的ID淮摔，才能在識別到一個詞法標記時返回這個ID給Bison。Bison傳遞這些ID給Flex的方法始赎，就是在調用bison命令時使用參數(shù)-d和橙。使用這個參數(shù)后，Bison會生成一個獨立的頭文件造垛，該文件的名稱形式為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()計算出來后放在全局變量yylval中俄周。下面是具有多種語義值類型的例子：
{DIGIT}+ { yylval.Number = new CNumberLiteralNode(yytext);
return T_NUMBER_LITERAL;
}
根據(jù)Bison文法定義文件自動生成的C代碼，給出了文法分析函數(shù)yyparse()的定義髓迎。然而該代碼還不是一個完整的C程序峦朗，還需要程序員提供幾個額外的函數(shù)。一個是詞法分析函數(shù)yylex()排龄，另外一個就是報錯函數(shù)yyerror()波势。報錯函數(shù)被yyparse()調用，以便在遇到錯誤時匯報錯誤橄维。此外尺铣，一個完整的C程序還需要程序員提供一個main()函數(shù)作為程序的入口。在這個main()函數(shù)中争舞，一定要調用yyparse()凛忿，否則分析工作就不會啟動。
報錯函數(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將識別到詞法標記記錄到變量yytext中床牧，長度記錄在yyleng中壕吹。函數(shù)yylex()的返回值是一個整型，就是詞法標記的ID。但是yylex()識別出來的字符串也可能需要返回給Bison。那么怎么返回呢？
現(xiàn)在做一個練習：定義一個非常簡單的計算器，這個計算器只能做一個整數(shù)的加法。這個計算器不做任何的錯誤處理。
首先給出Bison的文法定義文件：
