Bison 的构成与使用_bison转bnf_MrYuTing的博客

Bison 的使用说明

一、使用 Bison 的流程

1. 创建语言描述文件 (.y 文件)
2. 编写词法分析器函数 yylex()
3. 编写错误报告函数 yyerror()
4. 在 main() 中调用分析器函数 yyparse()
5. 执行 bison -d，由 .y 文件产生 .tab.c 和 .tab.h 文件
6. 执行 gcc，把 .tab.c 文件编译和链接成可执行程序

例. 计算器项目 calc。
calc.y
| bison -d calc.y
calc.tab.c
calc.tab.h
| gcc calc.tab.c -o calc
calc

二、语言描述文件的组成

%{
1. 序言 (Prologue)
声明全局标识符，定义数据类型、变量和宏，包含头文件，等。
%}

2. 声明 (declarations)
声明终结符，非终结符，运算符的优先级，符号语义值的各种类型。

3. 文法 (Grammar rules)
定义每一非终结符的文法规则。

4. 结言 (Epilogue)
定义序言中声明的函数，以及剩余的所有程序。如 yylex(), yyerror(), main(), 等。

三、语言描述文件中的声明

1. 语素类型的结合性
%left 声明左结合操作符
%right 声明右结合操作符
%token 声明无结合性的语素类型
单字符语素原本不用声明，声明它们是指出其结合性。

2. token 的语义值
若有，存储在全局变量 yylval (类型 YYSTYPE) 中。

四、词法分析器函数 yylex()

该函数实现功能：读入下一 token，返回它的编号。

例. 对于简化的 C语言。

1. 对于各种各样的数，编号 NUM。

2. 对于各种各样的字符串，编号 STR。

3. 对于各种各样的名称, 编号 ID。

4. 每一关键字有唯一的编号。
例.
关键字编号
int INT
double DOUBLE
if IF
while WHILE
return RETURN
说明：这里把编号取为相应的大写，是为了方便记忆，并非必须。

5. 单字符 token 包括运算符和分隔符，如 '+', '-', ';', ',', 等。它们的编号为其自身，直接返回即可。

6. 输入结束，编号为 0。

如果把 token 的编号视作符号的分类，那么每个单字符自成一类。
编号是一个整数，定义在 .tab.h 文件中，形如
#define NUM 257
#define ID 258
...

五、基本概念

1. BNF (Backus-Naur Form, 或 Backus Normal Form)
John Backus 提出的描述上下文无关文法的范式。在 Peter Naur 的 Algol60 报告中做了少许改进。

2. 上下文无关文法 (Context-free grammars)
描述不考虑上下文的规则的文法。如某规则说整数是表达式，那么，整数在任何地方都是一个允许的表达式。

3. 左递归 (Left recursion)
规则中，右端的第一个符号与左端相同。如
exprs: exprs ',' expr
;

4. 右递归 (Right recursion)
规则中，右端的最后一个符号与左端相同。如
exprs: expr ',' exprs
;

辨析：左递归比右递归更为自然，分析时占用内存也更少些。

5. 符号表 (Symbol table)
用来存储和查询已存在符号的名称和相关数据的数据结构。

6. 终结符 (Terminal symbol)
不可再分的文法符号。也称 token，中文称作语素、词法记号、记号、单词、符号等。

7. 非终结符 (Nonterminal symbol)
可以表达为更小结构的文法结构。每一非终结符用一条规则来定义。

8. 开始符号 (Start symbol)
一个特殊的非终结符，代表语言的开始。通常作为文法中的第一个规则。

9. LR(1)
一种用于自底向上分析的上下文无关文法，大多数时侯需要一个预读语素来消除任何输入片段的歧义。

10. LALR(1)
LR(1)的子集。Bison 采用的文法。

11. parser stack 分析栈
自底向上分析算法用到的栈。

12. shift 移进
把输入流中的下一个 token 移入分析栈。

13. reduce 归约
归约分析栈顶中已识别的规则。当分析栈顶的符号序列匹配某规则右端时，用该规则的左端替换之。

14. look-ahead token 预读语素
已读取、尚未移进的 token。

五、Bison 分析器算法

bison 采用自底向上 (bottom-up) 的分析方法。它用到一个分析栈 (parser stack)，关键有两个动作：

1. 移进 (shift)
读取的 token 移进到分析栈中。

2. 归约 (reduce)
当分析栈顶的 n 个符号匹配某规则的右端时，用该规则的左端取代之。

自底向上算法要做的事情是，对于一个接一个读入的 token，何时移进，何时归约。LR(1) 中的 1表示，只需预读 1个语素，就可以确定是移进，还是归约。

在移进和归约的过程中，可能出现两类冲突。

1. 移进/归约冲突 (shift/reduce conflicts)
在某一时刻，可以移进，也可以归约。是选择移进，还是归约？这就是移进/归约冲突。这种冲突可以接受。
在出现移进/归约冲突时，bison 选择移进。

例. if 语句的文法。
stmt_if: IF expr THEN stmt
| IF expr THEN stmt ELSE stmt
;
分析栈顶的符号序列是 IF expr THEN stmt，而当前符号是 ELSE。是移进？还是归约？bison 选择移进。

2. 归约/归约冲突 (Reduce/Reduce Conflicts)
当分析栈顶的符号序列可归约到多于一个规则时，选择哪一个规则？这就是归约/归约冲突。这种冲突不可接受。这是文法中的严重错误，必须修改文法。
在出现归约/归约冲突时，bison 选择归约到第一个匹配的规则。这十分冒险。

例. 定义包含 word 或 redirect 的序列。
sequence: /* empty */
| sequence words
| sequence redirects
;

words: /* empty */
| words word
;

redirects: /* empty */
| redirects redirect
;

sequence, words 和 redirects 的定义单独来看没问题，但放在一起产生了歧义：一个空输入可以归约到这三个规则中的任何一个。

Bison 采用自底向上（ bottom-up）的分析方法。 bottom-up 算法是 LR(1)，最先由knuth 1965年提出，以 BNF 文法为指引，比 top-down 算法更为强大。算法构造用到有限状态机 (Finite State Machine)，占用内存多，很复杂，实际中编译程序难以用纯手工构造，而是采用自动工具如 yacc/bison 辅助构造。 biso...

YACC（Yet AnotherCompile-Compiler）是语法分析器生成工具，它生成的是LALR分析器。Yacc于上世纪70年代产生，是美国贝尔实验室的产品，已经用于帮助实现了几百个编译器。 Yacc是linux下的工具，本实验使用的编译工具是cygwin（cygwin在windows下模拟一个linux环境）下的 bison ，它与Yacc的使用方法基本相同，只有...

一、 Bison 对输入的匹配 bison 是基于你所给定的语法来生成一个可以识别这个语法中有效“语句”的语法分析器。例如下面的这个例子: statement:NAME ‘=’ expression expression:NUMBER ‘+’ NUMBER | NUMBER ‘?’ NUMBER 其中statement是递归的开始语句,N

3. 编写错误报告函数 yyerror() 4. 在 main() 中调用分析器函数 yyparse() 5. 执行 bison -d，由 .y 文件产生 .tab.c 和 .tab.h 文件 6. 执... 1.文章诞生的契机在计算机学习中，我们有时可能会想到自制一门属于自己的编程语言，此时选择lex与yacc来生成词法分析器与语法分析器是非常不错的选择。然而，这两个工具虽然用起来简单，但对于新手来说，入门还有着些许的难度。入门的难度通常不是因为工具的复杂，而是因为教程有些难懂。在大多数教程作者眼里，想要自制一个语言的必然不会是初学者，毕竟新手们还在被C和JAVA等语言搞得晕头转向。这导致大多数lex与yacc教程都是面向进阶选手，内容“点到为止”，并心照不宣地省略了一些“常识”。导致内容在我等这般新

flex是windows下词法分析工具，lex是linux下词法分析工具， bison 是windows下的语法分析工具，而yacc对应为linux下的语法分析工具，flex和 bison 如何配置网上教程一搜一大把。先定义了一个二义性文法 exp:n|exp '+' exp; n:'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9'|'0'; int main() yyparse(); return 0; 经过命令行编译后，发现了移进归约冲突，于是报错

你也可以通过我的独立博客 —— www.huliujia.com 获取本篇文章简易编译器实现（一）使用 Flex创建词法分析器一文介绍了编译器的概念和七个阶段，并说明了如何使用 Flex创建词法分析器。本篇文章介绍如何使用 Bison 创建语法分析器，并实现基本的运算能力。本文继续使用简易编译器实现（一）使用 Flex创建词法分析器中提出的集合运算语言AlphaGun作为演示的例子。语法分析器使用词法分析器输出的token流作为输入，把token流转换成树状的中间表示，通常会转换成语法树，本文中使用 .

当我们的文法设计的有问题的时候，就需要开启 bison 的调试方式来检测文法错在哪里，那么如何开启 bison 的调试方式呢？ bison 调式需要做的事情如下： 1 ）在语法文件*.y定义段开启yydebug，最终如下： #include <string.h> #include <stdlib.h> #include <stdio.h> int yydebug=1...

Bison 适合上下文无关文法（Context-free grammar），并采用LALR(1)算法[Donnelly 06]的文法。当 bison 读入一个终结符（token），它会将该终结符及其语意值一起压入堆栈。这个堆栈叫做分析器堆栈（parser stack）。把一个token压入堆栈通常叫做移进（shifting）。例如，假设一个中缀计算器已经读入'1...