Bison是一種通用目的的分析器生成器。它將LALR(1)上下文無關文法的描述轉化成分析該文法的C程序。使用它可以生成解釋器，編譯器，協議實現等多種程序。Bison向上兼容Yacc，所有書寫正確的Yacc語法都應該可以不加修改地在Bison下工作。它不但與Yacc兼容還具有許多Yacc不具備的特性。 Bison分析器文件是定義了名為yyparse并且實現了某個語法的函數的C代碼。這個函數并不是一個可以完成所有的語法分析任務的C程序。除此這外我們還必須提供額外的一些函數：如詞法分析器、分析器報告錯誤時調用的錯誤報告函數等等。我們知道一個完整的C程序必須以名為main的函數開頭，如果我們要生成一個可執行文件，并且要運行語法解析器，那么我們就需要有main函數，并且在某個地方直接或間接調用yyparse，否則語法分析器永遠都不會運行。 先看下bison的示例：[逆波蘭記號計算器](#) %{ #define YYSTYPE double #include <stdio.h> #include <math.h> #include <ctype.h> int yylex (void); void yyerror (char const *); %} ? %token NUM ? %% 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; } ; %% ? #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; } ? void yyerror (char const *s) { fprintf (stderr, "%s\n", s); } ? int main (void) { return yyparse (); } 我們先看下運行的效果： bison demo.y gcc -o test -lm test.tab.c chmod +x test ./test > gcc命令需要添加-lm參數。因為頭文件僅對接口進行描述，但頭文件不是負責進行符號解析的實體。此時需要告訴編譯器應該使用哪個函數庫來完成對符號的解析。 　GCC的命令參數中，-l參數就是用來指定程序要鏈接的庫，-l參數緊接著就是庫名，這里我們在-l后面接的是m，即數學庫，他的庫名是m，他的庫文件名是libm.so。 這是一個逆波蘭記號計算器的示例，在命令行中輸入 3 7 + 回車，輸出10 一般來說，使用Bison設計語言的流程，從語法描述到編寫一個編譯器或者解釋器,有三個步驟: - 以Bison可識別的格式正式地描述語法。對每一個語法規則，描述當這個規則被識別時相應的執行動作，動作由C語句序列。即我們在示例中看到的%%和%%這間的內容。 - 描述編寫一個詞法分析器處理輸入并將記號傳遞給語法分析器（即yylex函數一定要存在）。詞法分析器既可是手工編寫的C代碼, 也可以由lex產生，后面我們會討論如何將re2c與bison結合使用。上面的示例中是直接手工編寫C代碼實現一個命令行讀取內容的詞法分析器。 - 編寫一個調用Bison產生的分析器的控制函數，在示例中是main函數直接調用。編寫錯誤報告函數（即yyerror函數）。 將這些源代碼轉換成可執行程序，需要按以下步驟進行： - 按語法運行Bison產生分析器。對應示例中的命令，bison demo.y - 同其它源代碼一樣編譯Bison輸出的代碼，鏈接目標文件以產生最終的產品。即對應示例中的命令　gcc -o test -lm test.tab.c 我們可以將整個Ｂison語法文件劃分為四個部分。這三個部分的劃分通過`%%',`%{' 和`%}'符號實現。一般來說，Bison語法文件結構如下： %{ 這里可以用來定義在動作中使用類型和變量，或者使用預處理器命令在那里來定義宏, 或者使用#include包含需要的文件。 如在示例中我們聲明了YYSTYPE，包含了頭文件math.h等，還聲明了詞法分析器yylex和錯誤打印程序yyerror。 %} ? Bison 的一些聲明 在這里聲明終結符和非終結符以及操作符的優先級和各種符號語義值的各種類型 如示例中的%token　NUM。我們在PHP的源碼中可以看到更多的類型和符號聲明，如%left，%right的使用 ? %% 在這里定義如何從每一個非終結符的部分構建其整體的語法規則。 %% ? 這里存放附加的內容 這里就比較自由了，你可以放任何你想放的代碼。 在開始聲明的函數，如yylex等，經常是在這里實現的，我們的示例就是這么搞的。 我們在前面介紹了PHP是使用re2c作為詞法分析器，那么PHP是如何將re2c與bison集成在一起的呢？我們以一個從PHP源碼中剝離出來的示例來說明整個過程。這個示例的功能與上一小節的示例類似，作用都是識別輸入參數中的字符串類型。本示例是在其基礎上添加了語法解析過程。首先我們看這個示例的語法文件：demo.y %{ #include <stdio.h> #include "demo_scanner.h" extern int yylex(znode *zendlval); void yyerror(char const *); ? #define YYSTYPE znode //關鍵點一，znode定義在demo_scanner.h %} ? %pure_parser // 關鍵點二 ? %token T_BEGIN %token T_NUMBER %token T_LOWER_CHAR %token T_UPPER_CHAR %token T_EXIT %token T_UNKNOWN %token T_INPUT_ERROR %token T_END %token T_WHITESPACE ? %% ? begin: T_BEGIN {printf("begin:\ntoken=%d\n", $1.op_type);} | begin variable { printf("token=%d ", $2.op_type); if ($2.constant.value.str.len > 0) { printf("text=%s", $2.constant.value.str.val); } printf("\n"); } ? variable: T_NUMBER {$$ = $1;} |T_LOWER_CHAR {$$ = $1;} |T_UPPER_CHAR {$$ = $1;} |T_EXIT {$$ = $1;} |T_UNKNOWN {$$ = $1;} |T_INPUT_ERROR {$$ = $1;} |T_END {$$ = $1;} |T_WHITESPACE {$$ = $1;} ? %% ? void yyerror(char const *s) { printf("%s\n", s); } 這個語法文件有兩個關鍵點： 1、znode是復制PHP源碼中的znode，只是這里我們只保留了兩個字段，其結構如下： typedef union _zvalue_value { long lval; /* long value */ double dval; /* double value */ struct { char *val; int len; } str; } zvalue_value; ? typedef struct _zval_struct { /* Variable information */ zvalue_value value; /* value */ int type; /* active type */ }zval; ? typedef struct _znode { int op_type; zval constant; }znode; 這里我們同樣也復制了PHP的zval結構，但是我們也只取了關于整型，浮點型和字符串型的結構。op_type用于記錄操作的類型，constant記錄分析過程獲取的數據。一般來說，在一個簡單的程序中，對所有的語言結構的語義值使用同一個數據類型就足夠用了。比如在前一小節的逆波蘭記號計算器示例就只有double類型。而且Bison默認是對于所有語義值使用int類型。如果要指明其它的類型，可以像我們示例一樣將YYSTYPE定義成一個宏: #define YYSTYPE znode 2、%pure_parser在Bison中聲明%pure_parse表明你要產生一個可重入(reentrant)的分析器。默認情況下Bison調用的詞法分析函數名為yylex，并且其參數為void，如果定義了YYLEX_PARAM，則使用YYLEX_PARAM為參數，這種情況我們可以在Bison生成的.c文件中發現其是使用#ifdef實現。 如果聲明了%pure_parser，通信變量yylval和yylloc則變為yyparse函數中的局部變量，變量yynerrs也變為在yyparse中的局部變量，而yyparse自己的調用方式并沒有改變。比如在我們的示例中我們聲明了可重入，并且使用zval類型的變更作為yylex函數的第一個參數，則在生成的.c文件中，我們可以看到yylval的類型變成 > 一個可重入(reentrant)程序是在執行過程中不變更的程序；換句話說,它全部由純(pure)(只讀)代碼構成。 當可異步執行的時候，可重入特性非常重要。例如，從一個句柄調用不可重入程序可能是不安全的。 在帶有多線程控制的系統中，一個非可重入程序必須只能被互鎖(interlocks)調用。 通過聲明可重入函數和使用znode參數，我們可以記錄分析過程中獲取的值和詞法分析過程產生的token。在yyparse調用過程中會調用yylex函數，在本示例中的yylex函數是借助re2c生成的。在demo_scanner.l文件中定義了詞法的規則。大部分規則是借用了上一小節的示例，在此基礎上我們增加了新的yylex函數，并且將zendlval作為通信變量，把詞法分析過程中的字符串和token傳遞回來。而與此相關的增加的操作為： SCNG(yy_text) = YYCURSOR; // 記錄當前字符串所在位置 /*!re2c <!*> {yyleng = YYCURSOR - SCNG(yy_text);} // 記錄字符串長度　 main函數發生了一些改變： int main(int argc, char* argv[]) { BEGIN(INITIAL); // 全局初始化，需要放在scan調用之前 scanner_globals.yy_cursor = argv[1]; //將輸入的第一個參數作為要解析的字符串 ? yyparse(); return 0; } 在新的main函數中，我們新增加了yyparse函數的調用，此函數在執行過程中會自動調用yylex函數。 如果需要運行這個程序，則需要執行下面的命令： re2c -o demo_scanner.c -c -t demo_scanner_def.h demo_scanner.l bison -d demo.y gcc -o t demo.tab.c demo_scanner.c chmod +x t ./t "<?php tipi2011" 在前面我們以一個小的示例和從PHP源碼中剝離出來的示例簡單說明了bison的入門和bison與re2c的結合。當我們用gdb工具Debug PHP的執行流程中編譯PHP代碼過程如下： #0 lex_scan (zendlval=0xbfffccbc) at Zend/zend_language_scanner.c:841 #1 0x082bab51 in zendlex (zendlval=0xbfffccb8) at /home/martin/project/c/phpsrc/Zend/zend_compile.c:4930 #2 0x082a43be in zendparse () at /home/martin/project/c/phpsrc/Zend/zend_language_parser.c:3280 #3 0x082b040f in compile_file (file_handle=0xbffff2b0, type=8) at Zend/zend_language_scanner.l:343 #4 0x08186d15 in phar_compile_file (file_handle=0xbffff2b0, type=8) at /home/martin/project/c/phpsrc/ext/phar/phar.c:3390 #5 0x082d234f in zend_execute_scripts (type=8, retval=0x0, file_count=3) at /home/martin/project/c/phpsrc/Zend/zend.c:1186 #6 0x08281b70 in php_execute_script (primary_file=0xbffff2b0) at /home/martin/project/c/phpsrc/main/main.c:2225 #7 0x08351b97 in main (argc=4, argv=0xbffff424) at /home/martin/project/c/phpsrc/sapi/cli/php_cli.c:1190 在PHP源碼中，詞法分析器的最終是調用re2c規則定義的lex_scan函數，而提供給Bison的函數則為zendlex。而yyparse被zendparse代替。