一、Bison對輸入的匹配

??bison是基于你所給定的語法來生成一個可以識別這個語法中有效“語句”的語法分析器。例如下面的這個例子:
statement:NAME ‘=’ expression
expression:NUMBER ‘+’ NUMBER
| NUMBER ‘?’ NUMBER
;
其中statement是遞歸的開始語句,NAME為遞歸終止符號,expression為遞歸式，同樣的NUMBER也為遞歸終止符號,所以這句話可以理解為NAME=NUMBER+NUMBER/NUMBER?NUMBER,此處應注意終結符號和非終結符號是不同的.

二、移進/規約分析

1、移進

從一中的例子可以看出，bison在對語句進行分析時，會有一個遞歸的過程，當它分析到expression這個非終止符時，會遞歸到下一個語句，左值是expression開始的這個語句。此時bison會把expression先壓入內部堆棧，接著切換到一個新的狀態，這個狀態會對應著剛剛壓入內部堆棧的狀態，這種過程叫移進.

2、規約

那么同樣的，當expression匹配完成后，此時發現已經達到終態，可以完全匹配，所以要將棧中的expression狀態移出，這樣的過程叫規約.

3、二者的分析

現在舉一個具體的例子來對上面的概念進行說明。現在有一個表達式a=13+15，bison先對其進行移進匹配:
首先NAME=expression這個語句沒有組成規則，所以要先進行移進，
按照順序a(此時NAME本是是終結符，所以直接被消除)
a =
a = 13
a = 13 +
a = 13 + 15
13 + 15已經可以匹配expression了，所以消除expression，此時就可以規約statement,將NAME=expression替換成statement.

三、Bison的LALR(1)

bison使用的是LALR(1)，即自左向右一次只分析一個記號，看下面的例子
statement: a B C
| d B G
a: A | Z
d: Y|U
此處如果輸入A B C，bison是會報錯的，因為對于另一個輸入Y B G來看，bison必須要通過C,G來區別究竟是a還是b記號，但是可惜的是bison一次只能識別一個記號，所以這2個輸入bison識別到B時會出現二義性.

四、對bison和flex實現的一個計算器的代碼分析

extern int yylineno; void yyerror(char* s,...);struct ast{int nodetype;struct ast* l;struct ast* r; };struct numval{int nodetype;double number; };struct ast* newcast(int nodetype,struct ast* l,struct ast* r); struct ast* newnum(double d);double eval(struct ast*);void treefree(struct ast*);

先來看這里的代碼，這是對計算器的一個聲明，第一行的yylineno是來自于flex中，注意在flex中要使用%option yylineno來選擇使用這個變量,yyerror是一個對原有函數的簡單擴展，ast是定義即將生成的抽象語法樹的節點類型，newcast,newnum是分別用來創建抽象語法樹的節點的，
eval是遍歷整棵樹獲得表達式的結果，treefree自然是釋放整棵樹.

%{ #include <stdio.h> #include <stdlib.h> #include "calc.h" %} %union{struct ast* a;double d; } %token <d> NUMBER %token EOL %type <a> exp factor term

再看這里，是bison文件中的第一部分的聲明，union表明即將使用的終結符號的類型有struct ast*和double，也就是一中的NAME和NUMBER的類型。%token指定了使用的終結符的符號，< d >的作用是指定NUMBER的類型為double,在union中可以看到d的類型為double,而EOL沒有為其指定類型，故其類型默認為int.%type的作用是用來定義一個非終結字符，也就是一中的expression,同樣的< a >是指定這些字符的類型為struct ast*

%% calclist:| calclist exp EOL {printf("=%4.4g\n",eval($2));treefree($2);printf("> ");}| calclist EOL {printf("> ");}; exp:factor| exp '+' factor{ $$=newcast('+',$1,$3);}| exp '-' factor{ $$=newcast('-',$1,$3);}; factor:term | factor '*' term {$$=newcast('*',$1,$3);}| factor '/' term {$$=newcast('/',$1,$3);}; term: NUMBER {$$=newnum($1);}| '|' term{$$=newcast('|',$2,NULL);}| '(' exp ')' {$$=$2;}| '-' term {$$=newcast('M',$2,NULL);}; %%

??這是bison的第二部分，是用來定義各種動作的，首先來說第一句，它可以匹配2種結果，一種是規約了exp和EOL之后所得到的表達式的結果，一種是只規約EOL的結果，當然這個地方為了計算器能夠連續進行計算，所以將開始符號calclist進行了移進。接下來，來看第二個符號exp,因為表達式可能是嵌套式的，例如4-5+3這種，所以exp同樣在右式當中也要移進，這里注意一點，$$代替的是表達式的左式，即exp，$1、$2對應的是右式中的第一個符號和第二個符號.
??特別要注意的是這個地方通過factor,term的移進順序指定了一個優先級，可以看出，在第二句中，bison一定會先移進factor,接著到factor，會先移進term,之后在term中才會進行規約，這樣就實現了絕對值,(，負號的優先級高于乘除,乘除會高于加減

%option noyywrap nodefault yylineno %{#include "calc.tab.h"#include "calc.h" %} EXP ([Ee][-+]?[0-9]+) %% "+" | "-" | "*" | "/" | "(" | ")" | {return yytext[0];} [0-9]+"."[0-9]*{EXP}? | "."?[0-9]+{EXP}? {yylval.d=atof(yytext);return NUMBER;}\n {return EOL;} "//".* [ \t] {} . {yyerror("Mystery character %c\n",*yytext);} %%

接下來就是flex中的文件，首先為了保證flex能正常使用bison中定義的符號，當然要包含bison生成的頭文件 #include “calc.tab.h”。%option noyywrap是為了保證生成的文件在c中的可移植性.下面的就是對數的各種模式定義以及符號定義。當然有一點需要注意，yylval已經在bison中被定義為union類型了，因此浮點數的值應該賦給yylval.d

#include <stdio.h> #include <stdlib.h> #include <stdarg.h> #include "calc.h"struct ast* newcast(int nodetype,struct ast* l,struct ast* r){struct ast* a=malloc(sizeof(struct ast));if(!a){yyerror("out of space");exit(0);}a->nodetype=nodetype;a->l=l;a->r=r;return a; }struct ast* newnum(double d){struct numval* a=malloc(sizeof(struct numval));if(!a){yyerror("out of space");exit(0);}a->nodetype='K';a->number=d;return (struct ast*)a; }double eval(struct ast* a){double v;switch(a->nodetype){case 'K':v=((struct numval*)a)->number;break;case '+':v=eval(a->l)+eval(a->r);break;case '-':v=eval(a->l)-eval(a->r);break;case '*':v=eval(a->l)*eval(a->r);break;case '/':v=eval(a->l)/eval(a->r);break;case '|':v=eval(a->l);if(v<0)v=-v;break;case 'M':v=-eval(a->l);break;default:printf("internal error:bad node %c\n",a->nodetype);}return v; }void treefree(struct ast* a){switch(a->nodetype){case '+':case '-':case '*':case '/':treefree(a->r);case '|':case 'M':treefree(a->l);case 'K':free(a);break;default:printf("internal error:free bad node %c\n",a->nodetype);} }void yyerror(char* s,...){va_list ap;va_start(ap,s);fprintf(stderr,"%d: error: ",yylineno);vprintf(stderr,s,ap);fprintf(stderr,"\n"); }int main(){ printf("> ");return yyparse(); }

這是bison中的聲明的定義文件

總結

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

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