Linux Bisonとは何ですか

Linux では、bison は文法アナライザー プログラムの生成に使用されるツールです。ユーザーが提供した文法ルールを文法アナライザーに変換できます。bison は、flex (字句解析) と組み合わせて使用​​する必要があります。 process 複雑なファイルの解析作業。 bison は、特定の文法の作成から開始してアルゴリズムを実行し、最終的にアクション テーブルを構築し、このアクション テーブルを使用して文を解析します。

#このチュートリアルの動作環境: linux7.3 システム、Dell G3 コンピューター。

Unix Lex/YACC は Linux FLex/Bison に開発されました

Lex は、Mike Lesk とまだ AT&T でインターンだった Eric Sc​​hmidt によって 1975 年に完成されました (Schmidt は(詳細) は、単独で使用することも、Johnson の yacc と組み合わせて使用​​することもできる字句解析生成プログラムです。 Lex は非常に有名ですが、効率が低すぎてバグがあります。 1987 年頃、ローレンス バークレー研究所の Vern Paxson は Lex を C で書き直し、バークレー ライセンスに基づいて FLex (Fast Lexical Analyzer Generator) と名付けました。 Flex は現在、SourceForge のプロジェクトですが、依然として Berkeley ライセンスに基づいています。
[Flex](https://github.com/westes/flex "Flex") は、オリジナルの無料 (ただし GNU ではない) 実装です。 lex の unix バージョン。c/c 用の字句スキャン ジェネレーター。

(注: シュミットは Google の CEO でした)

bison の前身は yacc です。 Yacc は、Knuth の LR 構文解析理論に基づいて、1975 年から 1978 年にかけてベル研究所の S.C. Johnson によって作成されました。 1985 年頃、カリフォルニア大学バークレー校の大学院生であるボブ コーベットは、改良された内部アルゴリズムを使用してバークレー yacc を実装しました。FSF のリチャード ストールマンはバークレー yacc を書き換えて GNU プロジェクトに使用し、多くの機能を追加して今日の GNU Bison を形成しました。 Bison は現在、FSF プロジェクトとして維持され、GNU Public License の下でリリースされています [Bison](http://www.gnu.org/software/bison/manual/) は、yacc と互換性のある無料の文法ジェネレーターです。

初期の Unix Lex/YACC は FLex/Bison に発展しました。プログラムの新しいバージョンには上位互換性 (つまり、古いバージョンとの互換性) があり、現在は Flex と Bison が使用されています。

flex/bison の動作原理

使用の観点から見ると、Flex と Bison は、Linux 上で字句アナライザーと構文アナライザーという 2 つのプログラムを生成するために使用されるツールです。 . 構造化入力の処理。通常、複雑なファイル解析作業を処理するために組み合わせて使用​​されます。

#bison は、ユーザーが提供した文法ルールを文法アナライザーに変換できます。簡単に言うと、bison は与えられた文法の生成から始まり、アルゴリズムを経て最終的にアクション テーブルを構築し、このアクション テーブルを使用して文を解析します。具体的には、bison はユーザーが提供した文法の生成を読み取り、C 言語形式で LALR(1) アクション テーブルを生成し、それを yyparse という名前の C 関数に組み込みます。この関数の機能は、このアクション テーブルを使用して解析することです。トークン ストリーム。このトークン ストリームは、flex によって生成された字句解析器でソース プログラムをスキャンすることによって取得されます。

フレックス ファイルはパターン (大豆、緑豆など) を定義し、フレックス処理 (字句解析) によって出力をトークンのセグメントに分割します (入力 Bean から 1 つを選択します)。 1 つずつ)、それによってさまざまなアクション (大豆を粉砕して豆乳にする (アクション)、緑豆から緑豆ケーキを作る (アクション)) を実行します...
flex によって生成されたトークンは、処理のために Bison に供給できます (より簡単で、デバッグが簡単です)、またはもちろんそうではなく、bison を使用して自分で処理するだけです (以下の例のように)。ただし、bison を使用すると、複雑なロジックをより簡単に処理できるため、記述が簡単になり、デバッグが容易になります。

エンコーディングの練習: 文字カウンター

//本例中仅仅使用flex以及少量手写代码（main中），来完成字符串统计功能。
Yolandas-MacBook-Pro:flex-bison liuyuanyuan$ cat fb1-1.l
/* 统计输入字符串*/
%{
  int chars = 0;
  int words = 0;
  int lines =0;

%}

%%
[a-zA-Z]+ {
		words++;
		chars += strlen(yytext);
          }

\n        {     chars++; lines++;}

.         {     chars++;     }

%%


int main(int args, char **argv)
{
	yylex();
	printf("lines=%6d words=%6d chars=%6d\n", lines, words, chars);
	return 0;
}

//Linux 系统上用 -lfl 选项编译, Mac 的编译选项是 -ll
Yolandas-MacBook-Pro:flex-bison liuyuanyuan$ gcc -ll lex.yy.c  -o fb1-1
Yolandas-MacBook-Pro:flex-bison liuyuanyuan$ ./fb1-1
hello 
this is yolanda
bye.
lines=     3 words=     5 chars=    28

1 flex(fast lex, scanner) ファイルの内容構造 (*.l, は 3 つに分かれています)パーツ )

/* P1: declarations(定义段) */
%{
  
%}

%%
  /* P2: translation rules(规则段) */
%%

/* P3: auxiliary functions(用户辅助程序段，c函数)*/

定義セクションには、テキスト ブロック、定義、内部宣言などが含まれます。
C 言語のヘッダー ファイル、関数および変数の宣言は通常、%{...%} の間に配置され、この部分の内容は生成された .c ファイルの先頭に直接コピーされます。

%option オプションを含む

%option noyywrap /* 定义段中包含了option选项*/

%{
#include "cal.tab.h"
extern int yylval;
%}

ルール セグメント %%...%% の間の部分は、一連の一致パターン (正規表現 ) とアクション (C コード)。

フレックス スキャナーを実行すると、入力がルール セグメントのパターンと照合され、一致が見つかるたびに (一致した入力はトークンと呼ばれます)、そのパターンに関連付けられた操作が実行されます。 Cコード。

pattern（正则表达式） { action(c代码) }

example:
[0-9]+ {yylval = atoi(yytest); return NUMBER;}

ユーザー補助プログラムセクションはCコードなので、そのままcファイルにコピーされますが、一般的にはここにいくつかの補助関数が定義されています。

int terror(chr *s)
{
    printf("%s\n", s);
    return 0;
}

2 bison(yacc, parser) ファイルの内容構造 (*.y, を 3 つの部分に分割し、%% で区切る)

/*P1: declarations 定义段*/
%{

%}
 
%%
/*P2: grammar rules 规则段(rule-action)*/
    
     A: a1  {  语义动作1 }
	  | a2  {  语义动作2 }
	  | …
	  | an  {  语义动作n }
	  | b  //没有{…},则使用缺省的语义动作       
	; //产生式结束标记
    //语义动作一般是在产生式右部分析完，归约动作进行前执行。
    A→ a1 | a2 |  … | an | b 
%%

/* P3: supporting C routines 用户辅助程序段(C函数) */

定義セクション 2 つの部分に分けることができます:

1. %{ と %} の間の部分は C 言語で記述され、ヘッダー ファイル インクルード、マクロ定義、グローバル変数定義、関数宣言などが含まれます。

2. 文法の終端記号と非終端記号について適切な宣言をいくつか行います。

一般的に使用される Bison タグ宣言には、%token %union %start %type %left %right %nonassoc などがあります。

%token 定义文法中使用了哪些终结符。定义形式： %token TOKEN1 TOKEN2  
终结符一般全大写；（如 TOKEN1 TOKEN2）  
一行可定义多个终结符，空格分隔；  

%left、%right、%nonassoc 也是定义文法中使用了哪些终结符。定义形式与%token类似。  
先定义的优先级低，最后定义的优先级最高，同时定义的优先级想通过。  
%left表示左结合，%right表示右结合；  
%nonassoc 表示不可结合（即它定义的终结符不能连续出现。例如
%left AA BB  
%nonassoc CC  
%right DD  
表示优先级关系为：AA=BB 注意：也可以于%prec来结合使用来改变token的优先级和结合性 例如： :'-' expr %prec NEG { $$ = -$2; };  

%union 声明语法符号的语义值类型的集合，  
bison中每个符号包括记号和非终结符都有一个不同数据类型的语义值，并使用yylval变量在移进和归约中传递这些值，YYSTYPE（宏定义）为yylval的类型，默认为int；  
我们使用%union来重新定义符号的类型  
%union  
{  
int iValue; /* integer value */  
char sIndex; /* symbol table index */  
nodeType *nPtr; /* node pointer */  
};  

%type 定义非终结符其属性值的类型。  
%type sym1 sym2  
%type sym3  

%start 指定文法的开始的文法符号（非终结符），是最终需要规约而成的符号。  
定义形式为：%start startsym ， 其中startsym为文法的开始符号。  
如果不使用%start定义文法开始符号，则默认在第二部分规则段中定义的第一条生产式规则的左部非终结符为开始符号。

规则段 由rule(语法规则)和action(包括C代码)组成。

bison规则基本是BNF，做了一点简化以易于输入。

规则中目标或非终端符放在左边，后跟一个冒号：然后是产生式的右边，之后是对应的动作（用{}包含）。

%%
  program: program expr '\n' { printf("%d\n", $2); }
  ;

  expr: INTEGER {$$ = $1; }
           | expr '+' expr { $$ = $1 + $3; }
           | expr '-' expr { $$ = $1 - $3}
  ;
%%

注意：$1表示右边的第一个标记的值，$2表示右边的第二个标记的值，依次类推。$$表示归约后的值。

用户辅助程序段 为C代码，会被原样复制到c文件中，这里一般自定义一些函数。

3 flex-bison 代码协作方式

flex/bison编码实践：编写简单计算器

1 macOS下flex/bison安装

brew install flex
brew install bison
# macos下flex/bison安装简单方便，另需安装gcc用于编译c语言程序。
brew install gcc

2 flex词法文件：calc.l

%option noyywrap

%{
    /*
     *  一个简单计算器的Lex词法文件
     */
	void yyerror(char*);
	#include "calc.tab.h"
%}

%%

     /* a-z为变量 */   
[a-z]	{
            yylval = *yytext - 'a';
            return VARIABLE;
    	}

    /* 整数 */
[0-9]+	{
            yylval = atoi(yytext);
            return INTEGER;
    	}

    /* 运算符 */
[-+()=/*\n]	{return *yytext;}

    /* 空白被忽略 */
[ \t]    ;

    /* 其他字符都是非法的 */
.    yyerror("invalid input");

%%

3 bison语法文件：calc.y

%token    INTEGER VARIABLE
%left    '+' '-'
%left    '*' '/'

%{
	#include <stdio.h>   
    void yyerror(char*);
    int yylex(void);
	
    int sym[26];
%}

%%
program:
    program statement '\n'
    |
    ;
statement:
     expr    {printf("%d\n", $1);}
     |VARIABLE '=' expr    {sym[$1] = $3;}
     ;
expr:
    INTEGER
    |VARIABLE{$$ = sym[$1];}
    |expr '+' expr    {$$ = $1 + $3;}
    |expr '-' expr    {$$ = $1 - $3;}
    |expr '*' expr    {$$ = $1 * $3;}
    |expr '/' expr    {$$ = $1 / $3;}
    |'('expr')'    {$$ = $2;}
    ;
%%

void yyerror(char* s)
{
    fprintf(stderr, "%s\n", s);
}

int main(void)
{
    printf("A simple calculator.\n");
    yyparse();
    return 0;
}</stdio.h>

4 Makefile 文件：

all: clean calc


calc: calc.l calc.y
	bison -d calc.y
	flex calc.l
	cc -o $@ calc.tab.c lex.yy.c -lm

clean:
	rm -f calc \
	lex.yy.c calc.tab.c calc.tab.h

5 执行

(可以直接执行make也就是执行Makefile中定义的内容，也可以单步执行)

Yolandas-MBP:calcSimple liuyuanyuan$ ls -l
total 32
-rw-r--r--@ 1 liuyuanyuan  staff  157  8 13 09:53 Makefile
-rw-r--r--@ 1 liuyuanyuan  staff  507  8 13 10:01 calc.l
-rw-r--r--@ 1 liuyuanyuan  staff  731  8 13 23:04 calc.y

Yolandas-MBP:calcSimple liuyuanyuan$ make
rm -f calc \
	lex.yy.c calc.tab.c calc.tab.h
bison -d calc.y
flex calc.l
cc -o calc calc.tab.c lex.yy.c -lm

Yolandas-MBP:calcSimple liuyuanyuan$ ls -l
total 272
-rw-r--r--@ 1 liuyuanyuan  staff    157  8 13 09:53 Makefile
-rwxr-xr-x  1 liuyuanyuan  staff  24600  8 14 12:00 calc
-rw-r--r--@ 1 liuyuanyuan  staff    507  8 13 10:01 calc.l
-rw-r--r--  1 liuyuanyuan  staff  42011  8 14 12:00 calc.tab.c
-rw-r--r--  1 liuyuanyuan  staff   2143  8 14 12:00 calc.tab.h
-rw-r--r--@ 1 liuyuanyuan  staff    731  8 13 23:04 calc.y
-rw-r--r--  1 liuyuanyuan  staff  44590  8 14 12:00 lex.yy.c

Yolandas-MBP:calcSimple liuyuanyuan$ ./calc
A simple calculator.
1+2
3

以上がLinux Bisonとは何ですかの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。