apa itu linux bison

Dalam Linux, bison ialah alat yang digunakan untuk menjana program penganalisis tatabahasa Ia boleh menukar peraturan tatabahasa yang disediakan oleh pengguna kepada penganalisis tatabahasa yang perlu digunakan bersama dengan flex (penganalisis leksikal) kepada proses kerja penghuraian fail yang kompleks. Bermula daripada penghasilan tatabahasa yang diberikan, bison akan melalui algoritma dan akhirnya membina jadual tindakan, dan kemudian menggunakan jadual tindakan ini untuk menghuraikan ayat.

Persekitaran pengendalian tutorial ini: sistem linux7.3, komputer Dell G3.

Unix Lex/YACC dibangunkan menjadi Linux FLex/Bison

Lex telah disiapkan pada tahun 1975 oleh Mike Lesk dan Eric Schmidt, yang masih menjadi pelatih di AT&T (Schmidt melakukannya (Lagi), ialah program penjanaan penganalisis leksikal yang boleh digunakan secara bersendirian atau bersama-sama dengan yacc Johnson. Lex sangat terkenal, tetapi kecekapannya terlalu rendah dan ia mempunyai pepijat. Sekitar tahun 1987, Vern Paxson dari Lawrence Berkeley Laboratory telah menulis semula Lex dalam C dan menamakannya FLex (Penjana Penganalisis Leksikal Pantas), berdasarkan lesen Berkeley. Flex kini merupakan projek SourceForge, masih berdasarkan lesen Berkeley
[Flex](https://github.com/westes/flex "Flex") ialah perlaksanaan unix yang percuma (tetapi bukan GNU). versi penjana imbasan leksikal untuk c/c++.

(Nota: Schmidt ialah Ketua Pegawai Eksekutif Google)

Pendahulu bison ialah yacc. Yacc telah ditulis oleh S.C. Johnson dari Bell Labs dari 1975 hingga 1978 berdasarkan teori analisis sintaks LR Knuth. Sekitar tahun 1985, pelajar siswazah UC Berkeley Bob Corbett melaksanakan yacc Berkeley menggunakan algoritma dalaman yang dipertingkatkan daripada FSF menulis semula yacc Berkeley dan menggunakannya untuk projek GNU, menambah banyak ciri untuk membentuk GNU Bison hari ini. Bison kini dikekalkan sebagai projek FSF dan dikeluarkan di bawah Lesen Awam GNU [Bison](http://www.gnu.org/software/bison/manual/) ialah penjana tatabahasa percuma yang serasi dengan yacc.

Unix Lex/YACC awal dibangunkan menjadi FLex/Bison Versi baharu program ini serasi ke atas (iaitu, serasi dengan versi lama Flex dan Bison kini digunakan).

Cara flex/bison berfungsi

Dari perspektif penggunaan, Flex dan Bison ialah alatan yang digunakan untuk menjana dua atur cara, penganalisis leksikal dan penganalisis sintaks di bawah Linux. Memproses input berstruktur, biasanya digunakan dalam kombinasi untuk mengendalikan kerja penghuraian fail yang kompleks.

bison boleh menukar peraturan tatabahasa yang disediakan oleh pengguna kepada penganalisis tatabahasa. Ringkasnya, bermula daripada penghasilan tatabahasa yang diberikan, bison akan melalui algoritma dan akhirnya membina jadual tindakan, dan kemudian menggunakan jadual tindakan ini untuk menghuraikan ayat. Khususnya, bison membaca pengeluaran tatabahasa yang disediakan oleh pengguna, menghasilkan jadual tindakan LALR(1) dalam format bahasa C dan memasukkannya ke dalam fungsi C bernama yyparse Fungsi fungsi ini adalah menggunakan jadual tindakan ini Untuk menghuraikan aliran token, aliran token ini diperoleh dengan mengimbas atur cara sumber dengan penganalisis leksikal yang dihasilkan oleh flex.

Fail flex mentakrifkan corak (iaitu kacang soya, iaitu kacang hijau...), dan output dibahagikan kepada segmen token melalui pemprosesan flex (analisis leksikal) (memilih kacang input satu demi satu), Dengan itu melaksanakan tindakan yang berbeza (mengisar kacang soya menjadi susu soya (tindakan), membuat kek kacang hijau daripada kacang hijau (tindakan))...
Token yang dihasilkan oleh flex boleh disalurkan kepada Bison untuk diproses (lebih mudah dan lebih mudah untuk nyahpepijat), atau sudah tentu tidak bison dan hanya mengendalikannya sendiri (seperti contoh di bawah). Walau bagaimanapun, menggunakan bison boleh mengendalikan logik kompleks dengan lebih mudah, menjadikannya mudah untuk ditulis dan mudah untuk nyahpepijat.

Amalan pengekodan: pembilang aksara

//本例中仅仅使用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 struktur kandungan fail flex (lex cepat, pengimbas) (*.l, mata Bahagian 3)

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

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

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

Bahagian definisi termasuk blok teks, takrifan, pengisytiharan dalaman, dsb.
Fail pengepala bahasa C, fungsi dan pengisytiharan pembolehubah, dsb. biasanya diletakkan di antara %{...%}, dan kandungan bahagian ini akan disalin terus ke permulaan fail .c yang dihasilkan.

Mengandungi %pilihan pilihan

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

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

Segmen peraturan Bahagian antara %%...%% ialah satu siri corak padanan (ungkapan biasa ) dan tindakan (kod C).

Apabila pengimbas fleksibel dijalankan, ia memadankan input kepada corak segmen peraturan dan setiap kali ia menemui padanan (input yang dipadankan dipanggil token), ia melaksanakan operasi yang dikaitkan dengan corak tersebut. kod C.

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

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

Bahagian program tambahan pengguna ialah kod C dan akan disalin ke fail c seperti sedia ada, beberapa fungsi tambahan ditakrifkan di sini.

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

2 struktur kandungan fail bison (yacc, parser) (*.y, dibahagikan kepada 3 bahagian, dipisahkan oleh %%)

/*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函数) */

Bahagian definisi boleh dibahagikan kepada dua bahagian:

1 Bahagian antara %{ dan %}, ditulis dalam bahasa C, termasuk fail pengepala termasuk, definisi makro, definisi pembolehubah global, fungsi. pengisytiharan, dsb.;

2. Buat beberapa pengisytiharan yang berkaitan tentang simbol terminal dan simbol bukan terminal tatabahasa.

Pengisytiharan teg Bison yang biasa digunakan termasuk: %token %union %start %type %left %right %nonassoc, dsb.

%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

Atas ialah kandungan terperinci apa itu linux bison. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!