Flex & Bison 开始

GoCoding
• 阅读 370

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

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

例如,如下代码片段:

alpha = beta + gamma;

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

不过后来它们在其他应用领域被证明也非常有效。任何应用程序,尤其文本处理,只要在其输入中寻找特定的模式,或者它使用命令语言作为输入,都适合使用 Flex 与 Bison。

例如,SQL 分析:

在编译器结构中,词法分析器、语法分析器是编译器前端的主要组成部分。大多数编译器组织成三个主要的阶段:前端、优化器和后端。前端专注于理解源语言程序,将其转换为某种中间表示(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/start-ai-compiler/tree/main/books/flex_bison ,都来自结语给出的 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)的自动生成工具,应用了形式语言理论的结果。这些工具同样可用于文本搜索、网站过滤、文字处理和命令行语言解释器。

本文内容主要来源于以下书籍:

GoCoding 个人实践的经验分享,可关注公众号!

点赞
收藏
评论区
推荐文章
Alex799 Alex799
3年前
Vue进阶(幺柒幺):前端用户体验提升(五)Flex实现弹性布局
需求背景在实现组件拖拽设计过程中,发现组件样式中设置了display:flex属性信息,导致组件生成后无法实现拖拽效果,网上查阅资料后发现Flex布局大有天地。Flex来源
浩浩 浩浩
3年前
【Flutter实战】线性布局(Row、Column)
4.2线性布局(Row和Column)所谓线性布局,即指沿水平或垂直方向排布子组件。Flutter中通过Row和Column来实现线性布局,类似于Android中的LinearLayout控件。Row和Column都继承自Flex,我们将在弹性布局一节中详细介绍Flex。主轴和纵轴对于线性布局,有主轴和纵轴之分,如果
Wesley13 Wesley13
2年前
java做web项目比较多
WEB就是轻量级;如果要炫,FLEX或即将普及的html5.0都能做到像C/S那样。java做web项目比较多;如果是桌面程序,还是走C/S比较成熟。如果是B/S架构的,后台还是JAVA,前台可以用JSPJSCSS渲染;也可以把前台换成FLEX交互,效果也是很好的。1packageCom.MySwing;2impo
菜园前端 菜园前端
1年前
想学会flex布局,我强烈推荐你来看看这篇文章!!
原文链接:为什么要使用flex布局?flex布局是目前比较流行的一种布局,因为它十分简单灵活,区区简单几行代码就可以实现各种页面的的布局,以前我在学习页面布局的时候我深受其float、display、position这些属性的困扰。使用flex属性就可以写
Stella981 Stella981
2年前
OpenCASCADE Expression Interpreter by Flex & Bison
OpenCASCADEExpressionInterpreterbyFlex&Bisoneryar@163.com(https://www.oschina.net/action/GoToLink?urlmailto%3Aeryar%40163.com)Abstract.OpenCASCADEprovidedat
Wesley13 Wesley13
2年前
PHP扩展开发
首先需要确定系统中安装了gcc编译器,合适版本的bison等构建一个基本的扩展骨架在PHP扩展开发时,使用ext_skel完成扩展的结构骨架创建。$./ext_skel./ext_skelextnamemoduleprotofilestubsfilexmlfile
Stella981 Stella981
2年前
Grid布局和Flex布局
Flex布局(弹性布局)Flex是弹性布局,用来为盒状模型提供最大的灵活性,任何一个容器都可以指定为Flex布局。行内元素也可以使用Flex布局。采用Flex布局的元素,称为Flex容器。flexitem项目是Flex布局的元素,简称项目。容器:水平的主轴(mainaxis)和垂直的交叉轴(crossaxis),单个项目占据的主轴空间叫做m
Stella981 Stella981
2年前
Elasticsearch学习(七):Elasticsearch分析
一、分析1\.分析(analysis)首先,标记化一个文本块为适用于倒排索引单独的词(term)然后标准化这些词为标准形式,提高它们的“可搜索性”或“查全率”分析是由分析器(analyzer)完成的。2\.分析器(analyzer)
Wesley13 Wesley13
2年前
C语言词法分析器
概述词法分析是编译阶段的第一步。这个阶段的任务是从左到右一个字符一个字符地读入源程序,即对构成源程序的字符流进行扫描然后根据构词规则识别单词(也称单词符号或符号)。词法分析程序实现这个任务。词法分析程序可以使用Lex等工具自动生成。本项目实现了一个简单C语言词法分析器。软件首页:http://www.oschina.net/p/l
达里尔 达里尔
5个月前
Flex布局:flex-grow:1失效
工作中遇到一些flexgrow:1的容器失效,一堆文字乱码溢出,最后看了一下flex布局的原理解决了cssdivflexgrow:1;wisth:0;如果遇到另一边的div设了宽但是被flexgrow:1的内容挤压了,可以给设了宽的div加flexshri
GoCoding
GoCoding
Lv1
Go coding in my way :)
文章
32
粉丝
5
获赞
10