轉載自：https://zhuanlan.zhihu.com/p/89479111

Bison是一種通用解析器生成器，它將帶注釋的上下文無關文法轉換為使用LALR（1）解析器表的確定性LR或廣義LR（GLR）解析器 。作為一項實驗性功能，Bison還可以生成IELR（1）或規范的LR（1）解析器表。一旦您精通Bison，就可以使用它來開發各種語言解析器，從用于簡單臺式計算器的語言解析器到復雜的編程語言。 Bison與Yacc向上兼容：所有正確編寫的Yacc語法都應與Bison一起使用，而無需進行任何更改。熟悉Yacc的任何人都應該可以輕松使用Bison。您需要精通C或C ++編程才能使用Bison。還支持將Java作為實驗功能。

Bison由三部分組成

• 定義部分
• %%
• 規則部分
• %%
• 用戶附加的C語言部分

定義部分

代碼部分

%{ ... %}，或%code { ... }的內容都是C代碼，并將代碼照搬到生成的C文件中，可以定義一些函數聲明，結構體，類型等，還可以重定義一些Bison的宏，從而改變程序的規則。

聲明%name

與flex %option類似，提供一定機制來控制bison默認規則。

%pure-parser，指定希望解析器是可重入的。

%expect 0，希望沖突數量為0

%name-prefix="base_yy"，代表生成的函數和變量名從yy改成base_yy

%locations，生成處理位置的代碼。 語法使用特殊的'@n'標記后便會啟用此模式，但是如果您的語法不使用它，則使用'％locations'可以獲取更準確的語法錯誤消息。

%parse-param {core_yyscan_t yyscanner}，聲明一個或多個參數聲明是其他yyparse參數。 在聲明函數或原型時使用參數聲明。 參數聲明中的最后一個標識符必須是參數名稱。

%lex-param {core_yyscan_t yyscanner}，指定參數聲明是其他yylex參數聲明。 您可以傳遞一個或多個這樣的聲明，等效于重復％lex-param。

%union，嵌入動作返回值類型，一般為非終結符的類型定義。如：

%union {core_YYSTYPE core_yystype;/* these fields must match core_YYSTYPE: */int ival;char *str;const char *keyword;char chr;bool boolean;JoinType jtype;DropBehavior dbehavior;OnCommitAction oncommit;………………InsertStmt *istmt;VariableSetStmt *vsetstmt;PartitionElem *partelem;PartitionSpec *partspec;PartitionBoundSpec *partboundspec;RoleSpec *rolespec; }

8. %type<>，Bison構造％type用于聲明非終結符。 以前我們以前沒有使用％type，因為非終結符通常由定義它們的規則隱式聲明。 但是必須顯式聲明exp，以便我們可以指定其值類型。

9. %token<>，token類型定義。在PostgreSQL中為關鍵字定義。

10. 優先級定義，為了避免過多的語法沖突，在這里定義一些語法優先級，從上到下優先級依次遞增

%nonassoc SET /* see relation_expr_opt_alias */ %left UNION EXCEPT %left INTERSECT %left OR %left AND %right NOT %nonassoc IS ISNULL NOTNULL /* IS sets precedence for IS NULL, etc */ %nonassoc '<' '>' '=' LESS_EQUALS GREATER_EQUALS NOT_EQUALS %nonassoc BETWEEN IN_P LIKE ILIKE SIMILAR NOT_LA %nonassoc ESCAPE /* ESCAPE must be just above LIKE/ILIKE/SIMILAR */ %left POSTFIXOP /* dummy for postfix Op rules */

規則部分

規則分為規則/行為行和C代碼行。

規則/行為

bison語法是由一系列的規則組成。每個規則由非終結符開始，然后是“:”和可能為空的符號、文字記號和動作的列表。 例如：

simple_select:SELECT opt_all_clause opt_target_listinto_clause from_clause where_clausegroup_clause having_clause window_clause{SelectStmt *n = makeNode(SelectStmt);n->targetList = $3;n->intoClause = $4;n->fromClause = $5;n->whereClause = $6;n->groupClause = $7;n->havingClause = $8;n->windowClause = $9;$$ = (Node *)n;}|………………;

“:”左邊為非終結符。

“:”右邊為規則，由一系列的終結符或非終結符構成。

“$$”，表示simple_select。

“$number”，表示“:”右邊符號，數字為幾，則表示第幾個符號。

“|”，表示或，“simple_select”其他規則。

代碼段

此段落，postgresql, 定義了一些在規則段中使用的工具函數。

移進/歸約

移進：bison語法分析器通過查找能夠匹配當前token的規則來運作。當bison處理一個語法分析器時，他創建一組狀態，每個狀態都反應出一個或者多個部分分析過的規則中可能的位置。當語法分析器讀取記號時，每當它讀到的記號無法結束一條規則時，它將把這個記號壓入一個內部堆棧，然后切換到一個新狀態，這個狀態能夠反映出剛剛讀取的記號。這種行為被稱為移進。

歸約：當它發現壓入的所有語法符號已經可一以組成規則的右部時，他將把右部符號全部從堆棧中彈出，然后把左部語法符號壓入堆棧。這種行為被稱為歸約。因為它通常消減了堆棧中一定數量的符號。每當bison歸約一條規則時，它會執行該規則關聯的用戶代碼。

二義性

只要是對于語言的解析，往往都會伴隨二義性的問題。bison把語法翻譯為成語法分析器時有可能會報告沖突。一些情況下，語法確實有歧義；也就是說。對于一個輸入的字符串，存在兩種可能的語法分析器，而bison無法處理這種情況。（當然也有可能是bison對于某些規則不支持的緣故）。 bison的二義性沖突分為移進/歸約沖突和歸約/歸約沖突。 移進/歸約沖突：

%% e: 'X'| e '+' e;

在這里，當我們輸入X+X+X時，存在兩種可能，（X+X）+X和X+（X+X）。移進會按照第二條規則進行，而歸約會按照第一條規則進行，這時就會存在矛盾。 移進/歸約沖突：

%% prog: proga | progb ;proga: 'X'; progb 'X';

移進不會產生歧義，但當歸約時，X既是proga又是progb，這就會造成歸約/歸約沖突。

工作流程

圖片來自于同事，bret.shao

flex&bison協作方式

官方文檔

https://www.gnu.org/software/bison/

總結

以上是生活随笔為你收集整理的Bison介绍[转]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。