Was ist Linux Bison?

Unter Linux ist Bison ein Tool zum Generieren eines Grammatikanalyseprogramms. Es kann die vom Benutzer bereitgestellten Grammatikregeln in einen Grammatikanalysator umwandeln, der in Verbindung mit Flex (lexikalischer Analysator) verwendet werden muss, um komplexe Dateianalysen durchzuführen Arbeiten. Ausgehend von der Produktion einer bestimmten Grammatik durchläuft Bison den Algorithmus, erstellt schließlich eine Aktionstabelle und verwendet diese Aktionstabelle dann zum Parsen des Satzes.

Die Betriebsumgebung dieses Tutorials: Linux7.3-System, Dell G3-Computer.

Unix Lex/YACC entwickelte sich zu Linux FLex/Bison

Lex wurde 1975 von Mike Lesk und Eric Schmidt fertiggestellt, der zu dieser Zeit Praktikant bei AT&T war (Schmidt war mehr als einer). Analyseprogramm, das allein oder in Verbindung mit Johnsons Yacc verwendet werden kann. Lex ist sehr berühmt, aber seine Effizienz ist zu gering und es weist Fehler auf. Um 1987 schrieb Vern Paxson vom Lawrence Berkeley Laboratory Lex in C um und nannte es FLex (Fast Lexical Analyzer Generator), basierend auf der Berkeley-Lizenz. Flex ist jetzt ein Projekt von SourceForge, das immer noch auf der Berkeley-Lizenz basiert.
[Flex](https://github.com/westes/flex „Flex“) ist die kostenlose (aber nicht GNU) Implementierung der ursprünglichen Unix-Version von lex, verwendet für den lexikalischen Scan-Generator für c/c++.

(Hinweis: Schmidt war der CEO von Google)

Der Vorgänger von Bison ist Yacc. Yacc wurde von 1975 bis 1978 von S.C. Johnson von Bell Labs auf der Grundlage der LR-Syntaxanalysetheorie von Knuth geschrieben. Um 1985 implementierte der Doktorand der UC Berkeley, Bob Corbett, Berkeley yacc mithilfe verbesserter interner Algorithmen. Richard Stallman von der FSF schrieb Berkeley yacc um und verwendete es für das GNU-Projekt, wodurch viele Funktionen hinzugefügt wurden, um das heutige GNU Bison zu bilden. Bison wird jetzt als FSF-Projekt verwaltet und unter der GNU Public License veröffentlicht. [Bison] (http://www.gnu.org/software/bison/manual/) ist ein kostenloser Grammatikgenerator, der mit yacc kompatibel ist.

Das frühe Unix Lex/YACC entwickelte sich zu FLex/Bison. Die neue Version des Programms ist aufwärtskompatibel (d. h. kompatibel mit der alten Version).

So funktioniert Flex/Bison

Aus Sicht der Verwendung sind Flex und Bison Tools zum Generieren von zwei Programmen, einem lexikalischen Analysator und einem Syntaxanalysator unter Linux. Sie können strukturierte Eingaben verarbeiten und werden im Allgemeinen in Kombination verwendet, um komplexe zu verarbeiten Datei-Parsing-Arbeit.

bison kann die vom Benutzer bereitgestellten Grammatikregeln in einen Grammatikanalysator umwandeln. Einfach ausgedrückt: Ausgehend von der Produktion einer bestimmten Grammatik durchläuft Bison den Algorithmus, erstellt schließlich eine Aktionstabelle und verwendet diese Aktionstabelle dann zum Parsen des Satzes. Konkret liest Bison die vom Benutzer bereitgestellte Grammatik, generiert eine LALR(1)-Aktionstabelle im C-Sprachformat und fügt sie in eine C-Funktion namens yyparse ein. Die Funktion dieser Funktion besteht darin, diese Aktionstabelle zu analysieren Der Token-Stream wird durch Scannen des Quellprogramms mit dem von Flex generierten lexikalischen Analysator erhalten.

Die Flex-Datei definiert das Muster (das ist die Sojabohne, das ist die Mungbohne ...) und unterteilt die Ausgabe durch Flex-Verarbeitung (lexikalische Analyse) (Auswahl der Eingabebohnen einzeln) in Token-Segmente. Dadurch werden verschiedene Aktionen ausgeführt (Sojabohnen zu Sojamilch mahlen (Aktion), Mungobohnenkuchen aus Mungobohnen herstellen (Aktion)) ...
Die von Flex generierten Token können zur Verarbeitung an Bison weitergeleitet werden (einfacher und einfacher zu debuggen). Natürlich können Sie sie auch direkt selbst verarbeiten, ohne sie an Bisons zu verfüttern (wie im folgenden Beispiel). Allerdings kann die Verwendung von Bison die komplexe Logik bequemer handhaben, was das Schreiben und Debuggen erleichtert.

Kodierungspraxis: Zeichenzähler

//本例中仅仅使用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) Dateiinhaltsstruktur (*.l, in 3 Teile unterteilt)

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

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

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

Definitionsabschnitt enthält Textblöcke, Definitionen und interne Erklärungen warten.
C-Sprach-Header-Dateien, Funktions- und Variablendeklarationen werden im Allgemeinen zwischen %{...%} platziert, und der Inhalt dieses Teils wird direkt an den Anfang der generierten .c-Datei kopiert.

Enthält die %option-Option

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

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

das Regelsegment Der Teil zwischen %%...%%, der eine Reihe übereinstimmender Muster (regulärer Ausdruck) und Aktionen (C-Code) darstellt.

Wenn der Flex-Scanner ausgeführt wird, gleicht er die Eingabe mit dem Muster des Regelsegments ab und führt jedes Mal, wenn er eine Übereinstimmung findet (die übereinstimmende Eingabe wird als Token bezeichnet), den diesem Muster zugeordneten C-Code aus.

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

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

Benutzer-Hilfsprogrammsegment ist C-Code und wird unverändert in die C-Datei kopiert. Im Allgemeinen werden hier einige Hilfsfunktionen definiert.

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

2 Bison (YACC, Parser) Dateiinhaltsstruktur (*.y, unterteilt in 3 Teile, getrennt durch %%)

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

Definitionsabschnitt kann in zwei Teile unterteilt werden:

1. und %} Die Teile dazwischen sind in C-Sprache geschrieben, einschließlich Header-Datei-Include, Makrodefinition, globale Variablendefinition, Funktionsdeklaration usw.

2 Machen Sie einige relevante Deklarationen zu den Terminalsymbolen und Nicht-Terminalsymbolen Grammatik.

Zu den häufig verwendeten Bison-Tag-Deklarationen gehören: %token %union %start %type %left %right %nonassoc usw.

%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

Das obige ist der detaillierte Inhalt vonWas ist Linux Bison?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!