qu'est-ce que le bison Linux

Sous Linux, bison est un outil utilisé pour générer un programme d'analyse de grammaire. Il peut convertir les règles de grammaire fournies par l'utilisateur en un analyseur de grammaire ; bison doit être utilisé en conjonction avec flex (analyseur lexical) pour gérer l'analyse de fichiers complexes ; Travail. À partir de la production d'une grammaire donnée, le bison va parcourir l'algorithme et enfin construire une table d'actions, puis utiliser cette table d'actions pour analyser la phrase.

L'environnement d'exploitation de ce tutoriel : système linux7.3, ordinateur Dell G3.

Unix Lex/YACC développé en Linux FLex/Bison

Lex a été achevé en 1975 par Mike Lesk et Eric Schmidt, qui était alors stagiaire chez AT&T (Schmidt a fait plus). programme d'analyseur, qui peut être utilisé seul ou en conjonction avec le yacc de Johnson. Lex est très célèbre, mais son efficacité est trop faible et il présente des bugs. Vers 1987, Vern Paxson du Lawrence Berkeley Laboratory a réécrit Lex en C et l'a nommé FLex (Fast Lexical Analyser Generator), basé sur la licence de Berkeley. Flex est maintenant un projet de SourceForge, toujours basé sur la licence Berkeley
[Flex](https://github.com/westes/flex "Flex") est l'implémentation gratuite (mais non GNU) de la version Unix originale. de lex, utilisé pour le générateur d'analyse lexicale pour c/c++.

(Remarque : Schmidt était le PDG de Google)

Le prédécesseur du bison est yacc. Yacc a été écrit par S.C. Johnson des Bell Labs de 1975 à 1978 sur la base de la théorie de l'analyse syntaxique LR de Knuth. Vers 1985, Bob Corbett, étudiant diplômé de l'UC Berkeley, a implémenté Berkeley yacc en utilisant des algorithmes internes améliorés. Richard Stallman de la FSF a réécrit Berkeley yacc et l'a utilisé pour le projet GNU, ajoutant de nombreuses fonctionnalités pour former le GNU Bison actuel. Bison est maintenant maintenu en tant que projet FSF et publié sous la licence publique GNU. [Bison](http://www.gnu.org/software/bison/manual/) est un générateur de grammaire gratuit compatible avec yacc.

Le premier Unix Lex/YACC s'est développé en FLex/Bison. La nouvelle version du programme est compatible vers le haut (c'est-à-dire compatible avec l'ancienne version Flex et Bison).

Comment fonctionne flex/bison

Du point de vue de l'utilisation, Flex et Bison sont des outils utilisés pour générer deux programmes, un analyseur lexical et un analyseur de syntaxe sous Linux. Ils peuvent traiter des entrées structurées et sont généralement utilisés en combinaison pour traiter des processus complexes. Travail d'analyse de fichiers.

bison peut convertir les règles de grammaire fournies par l'utilisateur en un analyseur de grammaire. Pour faire simple, à partir de la production d'une grammaire donnée, le bison va parcourir l'algorithme et enfin construire une table d'actions, puis utiliser cette table d'actions pour analyser la phrase. Plus précisément, bison lit la production de la grammaire fournie par l'utilisateur, génère une table d'actions LALR(1) au format langage C et l'inclut dans une fonction C nommée yyparse. La fonction de cette fonction est d'utiliser cette table d'actions pour analyser. le flux de jetons, ce flux de jetons est obtenu en scannant le programme source avec l'analyseur lexical généré par flex.

Le fichier flex définit le motif (qui est le soja, qui est le haricot mungo...), et divise la sortie en segments de jetons grâce au traitement flex (analyse lexicale) (en sélectionnant les haricots d'entrée un par un), exécutant ainsi différentes actions (broyer les graines de soja en lait de soja (action), préparer des gâteaux de haricots mungo à partir de haricots mungo (action))...
Les jetons générés par flex peuvent être transmis à Bison pour être traités (de plus en plus faciles à déboguer). Bien sûr, vous pouvez également les traiter directement vous-même sans les donner à manger aux bisons. Compris (comme dans l'exemple suivant). Cependant, l'utilisation de bison peut gérer plus facilement une logique complexe, ce qui la rend simple à écrire et facile à déboguer.

Pratique d'encodage : compteur de caractères

//本例中仅仅使用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 Structure du contenu du fichier flexible (lex rapide, scanner) (*.l, divisé en 3 parties)

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

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

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

Section de définition comprend des blocs de texte, des définitions et des informations internes les déclarations attendent.
Les fichiers d'en-tête du langage C, les déclarations de fonctions et de variables sont généralement placés entre %{...%}, et le contenu de cette partie sera directement copié au début du fichier .c généré.

Contient l'option %option

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

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

le segment de règle La partie entre %%...%%, qui est une série de modèles correspondants (expression régulière) et d'actions (code C).

Lorsque le scanner flex s'exécute, il fait correspondre l'entrée au modèle du segment de règle, et chaque fois qu'il trouve une correspondance (l'entrée correspondante est appelée un jeton), il exécute le code C associé à ce modèle.

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

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

Segment de programme auxiliaire utilisateur est du code C et sera copié dans le fichier c tel quel. Généralement, certaines fonctions auxiliaires sont définies ici.

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

2 structure du contenu du fichier bison (yacc, parser) (*.y, divisé en 3 parties, séparées par %%)

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

section de définition peut être divisée en deux parties :

1. et %} Les parties intermédiaires sont écrites en langage C, y compris l'inclusion du fichier d'en-tête, la définition de macro, la définition de variable globale, la déclaration de fonction, etc.

2 Faites quelques déclarations pertinentes sur les symboles terminaux et les symboles non terminaux du. grammaire.

Les déclarations de balises Bison couramment utilisées incluent : %token %union %start %type %left %right %nonassoc, etc.

%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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!