乐趣区

关于flex:Flex-Bison-开始

jiezi

Flex 与 Bison 是为编译器和解释器的编程人员特地设计的工具：

  • Flex 用于词法剖析（lexical analysis，或称 scanning），把输出宰割成一个个有意义的词块，称为记号（token）。
  • Bison 用于语法分析（syntax analysis，或称 parsing），确定这些记号是如何彼此关联的。

例如，如下代码片段：

alpha = beta + gamma;

词法剖析把这段代码合成为这样一些记号：alpha, =, beta, +, gamma, ;。接着语法分析确定了 beta + gamma 是一个表达式，而这个表达式被赋给了 alpha。

不过起初它们在其余应用领域被证实也十分无效。任何应用程序，尤其文本处理，只有在其输出中寻找特定的模式，或者它应用命令语言作为输出，都适宜应用 Flex 与 Bison。

例如，SQL 剖析：

  • MySQL: C++ 词法剖析, Bison 语法分析

    • sql/sql_yacc.yy

  • PostgreSQL: Flex 词法剖析, Bison 语法分析

    • parser/scan.l
    • parser/gram.y

在编译器构造中，词法分析器、语法分析器是编译器前端的次要组成部分。大多数编译器组织成三个次要的阶段：前端、优化器和后端。前端专一于了解源语言程序，将其转换为某种两头示意（IR）。而 Flex 与 Bison 就是给编译器前端设计出的工具。

起源

bison 来源于 yacc，一个由 Stephen C. Johnson 于 1975 年到 1978 年期间在贝尔实验室实现的语法分析器生成程序。正如它的名字（yacc 是 yet another compiler compiler 的缩写）所暗示的那样，那时很多人都在编写语法分析器生成程序。Johnson 的工具基于 D. E. Knuth 所钻研的语法分析实践（因而 yacc 非常牢靠）和不便的输出语法。这使得 yacc 在 Unix 用户中十分风行，只管过后 Unix 所遵循的受限版权使它只可能被应用在学术界和贝尔零碎里。大概在 1985 年，Bob Corbett，一个加州伯克利大学的研究生，应用改良的外部算法再次实现了 yacc 并演变成为伯克利 yacc。因为这个版本比贝尔实验室的 yacc 更快并且应用了灵便的伯克利许可证，它很快成为最风行的 yacc。来自自由软件基金会（Free Software Foundation）的 Richard Stallman 改写了 Corbett 的版本并把它用于 GNU 我的项目中，在那里，它被增加了大量的新个性并演变成为以后的 bison。bison 当初作为 FSF 的一个我的项目而被保护，且它基于 GNU 公共许可证进行公布。

在 1975 年，Mike Lesk 和暑期实习生 Eric Schmidt 编写了 lex，一个词法分析器生成程序，大部分编程工作由 Schmidt 实现。他们发现 lex 既能够作为一个独立的工具，也能够作为 Johnson 的 yacc 的协同程序。lex 因而变得非常风行，只管它运行起来有一点慢并且有很多谬误。（不过 Schmidt 起初在计算机行业里领有一份十分胜利的事业，他当初，2009 年，是 Google 的 CEO。2010 年 CEO 移交了，持续负责 Google 董事长。）

大略在 1987 年，Lawrence Berkeley 实验室的 Vern Paxson 把一种用 ratfor（过后风行的一种扩大的 Fortran 语言）写成的 lex 版本改写为 C 语言的，被称为 flex，意思是“疾速词法分析器生成程序”（Fast Lexical Analyzer Generator）。因为它比 AT&T 的 lex 更疾速和牢靠，并且就像伯克利的 yacc 那样基于伯克利许可证，它最终也超过了原来的 lex。flex 当初是 SourceForge 的一个我的项目，仍然基于伯克利许可证。

装置

大多数 Linux 和 BSD 零碎自带 flex 和 bison 作为零碎的根底局部。如果你的零碎没有蕴含它们，装置它们也很容易。

例如在 Ubuntu/Debian 零碎，能够间接 apt 装置：

# Ubuntu 20
$ sudo apt install flex bison -y

$ flex -V
flex 2.6.4
$ bison -V
bison (GNU Bison) 3.5.1

范例

范例请见 https://github.com/ikuokuo/st…，都来自结语给出的 Flex & Bison 一书。

范例领导了咱们如何应用 Flex & Bison 开发一个计算器，并能反对变量、过程、循环和条件表达式，有内置函数，也反对用户自定义函数。

如下编译所有范例：

cd books/flex_bison/

# 编译 release
make
# 编译 debug
make debug

# 清理
make clean

范例程序会输入进 _build 目录，如下执行：

$ ./_build/linux-x86_64/release/1-5_calc/bin/1-5_calc
> (1+2)*3 + 4/2
= 11

$ ./_build/linux-x86_64/release/3-5_calc/bin/3-5_calc
> let sq(n)=e=1; while |((t=n/e)-e)>.001 do e=avg(e,t);;
Defined sq
> let avg(a,b)=(a+b)/2;
Defined avg
> sq(10)
= 3.162
> sqrt(10)
= 3.162
> sq(10)-sqrt(10)
= 0.000178

如果只编译某一范例：

cd ch01/1-1_wc/

# 编译 release
make -j8
# 编译 debug
make -j8 args="debug"

# 清理
make clean

程序

Flex 与 Bison 程序都是由三局部形成：定义局部、规定局部和用户子例程。

... definition section ...
%%
... rules section ...
%%
... user subroutines section ...

Flex 规定局部基于正则表达式，Bison 则基于 BNF (Backus-Naur Form) 文法。具体用法，请按照结语给出的 Flex & Bison 一书，及范例。

这里不做过多论述，本文旨在让大家理解有 Flex 与 Bison 这样工具，以及它们能帮忙咱们实现什么样的工作。

结语

Flex 与 Bison 是词法分析器（Scanner）与语法分析器（Parser）的主动生成工具，利用了形式语言实践的后果。这些工具同样可用于文本搜寻、网站过滤、文字处理和命令行语言解释器。

本文内容次要来源于以下书籍：

  • 2011-03 / flex 与 bison（中文版）/ 浏览
  • 2009 / flex & bison – Text Processing Tools / 浏览

GoCoding 集体实际的教训分享，可关注公众号！

退出移动版