你也可以通過我的獨立博客 —— www.huliujia.com 獲取本篇文章

簡易編譯器實現（一）使用Flex創建詞法分析器一文介紹了編譯器的概念和七個階段，并說明了如何使用Flex創建詞法分析器。本篇文章介紹如何使用Bison創建語法分析器，并實現基本的運算能力。本文繼續使用簡易編譯器實現（一）使用Flex創建詞法分析器中提出的集合運算語言AlphaGun作為演示的例子。

語法分析

語法分析器使用詞法分析器輸出的token流作為輸入，把token流轉換成樹狀的中間表示，通常會轉換成語法樹，本文中使用的例子比較簡單，所以會對結果進行直接計算。復雜的語言通常會先構建語法樹，然后在語法樹的基礎上做一系列的處理。如果輸入的token流不符合語法分析器的規定的語法，語法分析器還可以報語法錯誤。

和詞法分析器自動生成類似，我們可以利用Bison來自動生成語法分析器，提高開發速度，降低迭代成本和維護成本。本文主要介紹Bison的使用。

Bison的語法

Bison語法規則和Flex一樣分為3個部分，第一部分是C語言聲明、token聲明、類型聲明。由"%{“和”}%"圍住的C語言部分會被直接拷貝到生成的語法分析器代碼前面。第二部分是使用BNF語法編寫的語法規則，為了編寫方便，Bison對BNF做了一定的簡化。第三部分是要執行的main函數。

下面是為集合運算語言AlphaGun編寫的Bison規則，代碼量比較大，可以直接翻到下面看解釋

%{#include <stdio.h>#include <string.h>#include <stdlib.h>#include <stdarg.h>#define NAME_SIZE 100#define CHAR_SET_SIZE 26extern int yylineno; /* from lexer */int yylex();void yyerror(char *s, ...){va_list ap;va_start(ap, s);fprintf(stderr, "%d: error: ", yylineno);vfprintf(stderr, s, ap);fprintf(stderr, "\n");}struct Symbol{char name;char value[CHAR_SET_SIZE];};struct Symbol symbol_table[26];char temp_char_set[CHAR_SET_SIZE];char factor_char_set[CHAR_SET_SIZE];char expr_char_set[CHAR_SET_SIZE];struct Symbol* NewSymbol(){struct Symbol* symbol = (struct Symbol*)malloc(sizeof(struct Symbol));symbol->name = 0;memset(symbol->value, 0, sizeof(symbol->value));}void PrintCharSet(char name, const char* char_set){printf("%c: [", name);int need_comma = 0;for(int i=0; i< CHAR_SET_SIZE; i++){if(char_set[i] != 0){if(need_comma == 1){printf(",");}printf("%c", char_set[i]);need_comma = 1;}}printf("]\n");}void PrintSymbol(const struct Symbol* symbol){PrintCharSet(symbol->name, symbol->value);}void Union(char* result_char_set, const char* char_set_1, const char* char_set_2){memcpy(result_char_set, char_set_1, CHAR_SET_SIZE);for(int i=0; i<CHAR_SET_SIZE; i++){if(char_set_2[i] != 0){result_char_set[i] = char_set_2[i];}}}void Intersect(char* result_char_set, const char* char_set_1, const char* char_set_2){for(int i=0;i <CHAR_SET_SIZE; i++){if(char_set_1[i] != char_set_2[i] || char_set_1[i] == 0){result_char_set[i] = 0;}else{result_char_set[i] = char_set_1[i];}}}void Substract(char* result_char_set, const char* char_set_1, const char* char_set_2){for(int i=0;i <CHAR_SET_SIZE; i++){if(char_set_1[i] == 0 || char_set_1[i] == char_set_2[i]){result_char_set[i] = 0;}else{result_char_set[i] = char_set_1[i];}}} %}%union {char name;char element;char* char_set; }%token PRINT %token <name> IDENTIFIER %token <element> CHAR %token COMMA %token LEFT_BRACKET %token RIGHT_BRACKET %token ASSIGN %token UNION %token INTERSECT %token SUBSTRACT %token NEWLINE%type <char_set> char_list init_list factor expr%%language: /* nothing */| language statement NEWLINE| language NEWLINE /*允許空行出現*/statement: PRINT IDENTIFIER { PrintSymbol(&symbol_table[$2 - 'A']); }| IDENTIFIER ASSIGN init_list { symbol_table[$1-'A'].name = $1; memcpy(symbol_table[$1-'A'].value, $3, CHAR_SET_SIZE); }| IDENTIFIER ASSIGN expr { symbol_table[$1-'A'].name = $1; memcpy(symbol_table[$1-'A'].value, $3, CHAR_SET_SIZE); }expr: factor { $$ = expr_char_set; memcpy($$, $1, CHAR_SET_SIZE); }| expr SUBSTRACT factor { Substract($$, $1, $3); }factor: IDENTIFIER { $$ = factor_char_set; memcpy($$, symbol_table[$1-'A'].value, CHAR_SET_SIZE); }| factor UNION IDENTIFIER { Union($$, $1, symbol_table[$3-'A'].value); }| factor INTERSECT IDENTIFIER { Intersect($$, $1, symbol_table[$3-'A'].value); }init_list: LEFT_BRACKET char_list RIGHT_BRACKET { $$ = $2; }char_list: CHAR { $$ = temp_char_set; memset($$, 0, 26); $$[$1-'a'] = $1; }| char_list COMMA CHAR { $$[$3-'a'] = $3; }%%int main(int argc, char ** argv) {yyparse(); }

Bision規則第一部分

C語言部分，包含了需要的頭文件，聲明了幾個函數，這些函數將在BNF語法規則部分用到。實現了yyerror，使得生成的語法分析器可以打印語法錯誤的相關信息，另外為了避免編譯錯誤，前置聲明了yylex。

token聲明部分，首先定義了yylval的union類型。這里yylval由name、element、char_set三種變量聯合組成，%token<name> IDENTIFIER 聲明了IDENTIFIER token類型，并且告訴Bison，IDENTIFIER使用union類型的name變量存儲值，這樣在BNF語法規則部分，$N就會直接指代name變量。類似的CHAR使用element變量，$N指代element。

type聲明部分，聲明了char_list, init_list, facotr, expr這4種非終結符使用union類型的char_set變量。如果沒有這個聲明的話，在BNF語法規則部分，是不能給非終結符的值變量$$賦值的。

Bison規則第二部分

第二部分是BNF語法規則部分，BNF語法規則如果細說的話又是一篇長文，這里簡單介紹一下。每個規則的最左邊是非終結符，冒號右邊是非終結符的推導規則，一個非終結符如果有多個推到規則，使用豎線 | 分割。每個推導規則都可以對應一個動作，由 { } 包含，使用C語言代碼編寫。第一個規則的非終結符也被稱為起始符，最終語言的全部輸入都會最終匹配到起始符這里。Bison會自動對輸入的token流進行解析，對匹配到的推導規則，執行動作代碼，如果沒有動作代碼，會繼續往下匹配。Bison中的每個token和非終結符都可以有一個值變量，這個是在上面的%token和%type聲明中定義的。每個推導規則中，非終結符的值保存在$$中，推導規則中出現的符號的值分別保存在$1、$2、$3、… 中。$$、$1、$2等實際指向的就是前面提到的yylval的union類型的具體變量。比如：

init_list: LEFT_BRACKET char_list RIGHT_BRACKET

init_list的值變量是$$，而LEFT_BRACKET的值變量就是$1，但是顯然左括號不會有值，所以這里$1實際上是無用的，char_list的值變量是$2，在動作部分我們把$2賦值給了$1，從而實現了集合的初始化動作。

Bison規則第三部分

第三部分是main函數，直接調用了yyparse函數，yyparse是Bison生成的語法分析器入口，yyparse會不斷地調用yylex獲取token流去解析，和語法規則去做匹配，直到token流結束或者發現語法錯誤。

執行Bison

首先把簡易編譯器實現（一）使用Flex創建詞法分析器中的Flex規則文件做一點修改，修改結果如下：

%option noyywrap yylineno %{#include <stdio.h>#include "set_calc.tab.h"int fileno(FILE *stream); %}%%PRINT { return PRINT; } [A-Z] { yylval.name = yytext[0]; return IDENTIFIER; } [a-z] { yylval.element = yytext[0]; return CHAR; } "," { return COMMA; } "[" { return LEFT_BRACKET; } "]" { return RIGHT_BRACKET; } "=" { return ASSIGN; } "∪" { return UNION; } "∩" { return INTERSECT; } "-" { return SUBSTRACT; } \n { return NEWLINE; } "//".* { /* omit comment*/ } [ \t] { /*ignore white space*/ } . { printf("unexpected token: (%s)\n", yytext); }%%

刪除了手動定義的枚舉類型和yylva變量，包含了set_calc.tab.h頭文件，這個頭文件是由bison生成的，頭文件中定義了枚舉類型和yylval變量。為了避免編譯錯誤，聲明了fileno函數。

保存文件、聯合Flex編譯

把上面的Bison規則保存為set_calc.y，把flex規則保存為set_calc.l，編譯

bison -d set_calc.y # 生成語法分析器 flex set_calc.l # 生成詞法分析器 gcc -std=c99 -o set_calc set_calc.tab.c lex.yy.c # 編譯生成可執行文件

編寫AlphaGun語言代碼，保存為test.set

A=[a,b,c,d,z] B=[c,d,e, f ] // test comment C=[e,f,g,h,z] D=[x,y,z]E = A ∪ B ∩ C - A ∩ B ∪ DPRINT A PRINT E

執行AlphaGun代碼

./set_calc < test.set

運行結果

A: [a,b,c,d,z] E: [e,f]

語法樹

對于復雜的語言，直接根據推導規則進行計算時無法實現的，所以在動作部分中可以構建語法樹，最后集中處理、計算。

總結

以上是生活随笔為你收集整理的简易编译器实现（二）使用Bison创建语法分析器的全部內容，希望文章能夠幫你解決所遇到的問題。

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