linux bison的作用是什么

87次阅读

共计 6283 个字符，预计需要花费 16 分钟才能阅读完成。

这篇文章主要讲解了“linux bison 的作用是什么”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着丸趣 TV 小编的思路慢慢深入，一起来研究和学习“linux bison 的作用是什么”吧！

在 linux 中，bison 是用来生成语法分析器程序的工具，它可以将用户提供的语法规则转化成一个语法分析器；bison 需要和 flex（词法分析器）配合使用来处理复杂的文件解析工作。通过给定语法的产生式开始，bison 会通过算法，最终构造得到动作表，然后利用这个动作表去解析句子。

Unix Lex/YACC 发展为 Linux FLex/Bison

Lex 是 1975 年由 Mike Lesk 和当时尚在 AT T 实习的 Eric Schmidt 共同完成的（Schmidt 做的更多），是一个词法分析器的生成程序，可以单独使用也可以与 Johnson 的 yacc 协同工作。lex 很有名气，但是无奈效率太低加上有 bug。大概在 1987 年，Lawrence Berkeley 实验室的 Vern Paxson 用 C 重新写了 Lex，并命名为 FLex（the Fast Lexical Analyzer Generator），基于伯克利许可证。flex 现在是 SourceForge 的一个项目，依然基于伯克利许可，
[Flex](https://github.com/westes/flex Flex) 是起初 unix 版 lex 的 free (but non-GNU) implementation，用于 c /c ++ 的词法扫描生成器。

（注意：Schmidt 曾是 google 的 CEO）

bison 的前身是 yacc。yacc 是由贝尔实验室的 S.C.Johnson 基于 Knuth 大神的 LR 语法分析理论，于 1975～1978 年写成。大约 1985 年，UC Berkeley 的研究生 Bob Corbett 使用改进的内部算法实现了伯克利 yacc，来自 FSF 的 Richard Stallman 改写了伯克利 yacc 并将其用于 GNU 项目，添加了很多特性，形成了今天的 GNU Bison。bison 现在作为 FSF 的项目被维护，基于 GNU 公共许可证发布，[Bison](http://www.gnu.org/software/bison/manual/)是兼容 yacc 的 free 的语法生成器。

早期 Unix 的 Lex/YACC，发展为 FLex/Bison，新版本的程序是向上兼容的(即兼容老版本)，现 chang 用 Flex 和 Bison。

flex/bison 工作原理

使用的角度，Flex 和 Bison 是 Linux 下用来生成词法分析器和语法分析器两个程序的工具，可以处理结构化输入，一般结合使用来处理复杂的文件解析工作。

bison 可以将用户提供的语法规则转化成一个语法分析器。简单来说，通过给定语法的产生式开始，bison 会通过算法，最终构造得到动作表，然后利用这个动作表去解析句子。具体来说，bison 读取用户提供的语法的产生式，生成一个 C 语言格式的 LALR(1) 动作表，并将其包含进一个名为 yyparse 的 C 函数，这个函数的作用就是利用这个动作表来解析 token 流，而这个 token 流是由 flex 生成的词法分析器扫描源程序得到的。

flex 文件是定义 pattern（哪是黄豆，哪是绿豆 …），通过 flex 处理（词法分析）将输出切分成一段一段的 token（将输入的豆子一个个摘出来），从而执行不同的 action（黄豆就磨豆浆（action），绿豆去做绿豆糕(action)）…
flex 生成的 tokens 可以喂给 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++; }

 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
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 代码)。

当 flex 扫描程序运行时，它把输入与规则段的模式进行匹配，每次发现一个匹配（被匹配的输入称为标记（token））时就执行与那种模式相关的 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 函数) */

定义段可以分为两部分：

1. %{和 %}之间的部分，C 语言编写的，包括头文件 include、宏定义、全局变量定义、函数声明等;

2. 对文法的终结符和非终结符做一些相关声明。

常用的 Bison 标记声明有：%token %union %start %type %left %right %nonassoc 等。

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

%left、%right、%nonassoc 也是定义文法中使用了哪些终结符。定义形式与 %token 类似。
先定义的优先级低，最后定义的优先级最高，同时定义的优先级想通过。
%left 表示左结合，%right 表示右结合；
%nonassoc 表示不可结合（即它定义的终结符不能连续出现。例如，如果文法中不允许出现形如 a b c 的句子，则就是不可结合的）

%left AA BB
%nonassoc CC
%right DD
表示优先级关系为：AA=BB CC DD，表示结核性为：AA\BB 左结合，DD 右结合，CC 不可结合。
注意：也可以于 %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 sindex 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;
}

4 Makefile 文件：

all: clean calc

 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.
3

感谢各位的阅读，以上就是“linux bison 的作用是什么”的内容了，经过本文的学习后，相信大家对 linux bison 的作用是什么这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是丸趣 TV，丸趣 TV 小编将为大家推送更多相关知识点的文章，欢迎关注！

正文完