打开APP
未登录
开通VIP,畅享免费电子书等14项超值服
开通VIP
首页
好书
留言交流
下载APP
联系客服
flex and bison :做个计算器
guitarhua
>《理学》
2014.10.24
关注
最近看PostgreSQL源码,看到了flex。我预计后面解析sql的时候,这两个兄弟还会出来相见,
所以这两天看了flex and bison的资料。
科班出身学过编译原理的人对flex 和bison这两个兄弟一定不会陌生,对于flex 和bison兄弟俩,天生就是和编译器打交道的。
flex的前身是lex,lex是1975年由Mike Lesk和当时尚在AT&T实习的Eric Schmidt
共同完成的基于UNIX环境的词法分析器的生成工具。这个lex很有名气,但是无奈效率太低加上有bug,让人用的很不爽。后来伯克利实验室的Vern Paxson用C重新写了lex,并命名为flex(Fast Lexical Analyzer Generator
)。Linux下我们用的是这个flex的GNU版本。对于我们Ubuntu来讲安装是一如既往的方便:
sudo apt
-
get install flex
flex到底是干啥的呢?咱就喜欢大白话,在我看来,flex就是将输入文件按照规则,切分成一段一段的。在白一点,一个文件,就好像黄豆绿豆黑豆混在一起。flex的作用就是定义好那是黄豆,哪是绿豆,黑豆,(就是专业术语中的pattern),将这些一个个摘出来,黄豆就磨豆浆(action),绿豆去做绿豆糕(action)...
flex 处理分词,将输出切分成一段一段的token,这些tokens可以喂给Bison处理,当然了,我们完全也可以不喂给bison,直接自己处理就得了。最简单的例子就是上篇博文提到了统计字符数,单词数和行数。
请看下面最简单的分词:
/
*
just like Unix wc
*
/
%{
int
chars
=
0
;
int
words
=
0
;
int
lines
=
0
;
%}
%%
[
a
-
zA
-
Z
]
+
{ words
+
+
;
chars
+
=
strlen
(
yytext
)
;
}
\n { chars
+
+
;
lines
+
+
;
}
.
{ chars
+
+
;
}
%%
int
main
(
int
argc
,
char
*
argv
[
]
)
{
yylex
(
)
;
printf
(
"%8d%8d%8d\n"
,
lines
,
words
,
chars
)
;
return 0
;
}
上面的内容分成三个部分,第一部分声明,第二部分是规则部分,简单地说就是
pattern action
匹配什么模式,匹配到后做什么动作。说到pattern,我仿佛看到正则表达式笑而不语。不过这不是我们这篇文章的主题。
第三部分是用户自定义部分,这部分代码会原封不动地拷贝到生成的.c文件中去。
我们用flex处理下这个wc.l文件,可以看到生成了lex.yy.c文件。
root@manu
:
~
/
code/flex_bison# flex wc
.
l
root@manu
:
~
/
code/flex_bison# ll
.
.
.
-
rw
-
r
-
-
r
-
-
1 root root 44407 4月 6 11
:
38 lex
.
yy
.
c
-
rw
-
r
-
-
r
-
-
1 root root 313 4月 5 13
:
21 wc
.
l
当然了我们可以制定输出C文件的名字,使用-o选项。Whatever,我们有了C文件,用gcc及可以编译出可执行文件了,记住加上-lfl选项。
root@manu
:
~
/
code/flex_bison# gcc
-
o wc lex
.
yy
.
c
-
lfl
root@manu
:
~
/
code/flex_bison# ll
.
.
.
-
rw
-
r
-
-
r
-
-
1 root root 44407 4月 6 11
:
38 lex
.
yy
.
c
-
rwxr
-
xr
-
x 1 root root 18482 4月 6 11
:
42 wc
*
-
rw
-
r
-
-
r
-
-
1 root root 313 4月 5 13
:
21 wc
.
l
root@manu
:
~
/
code/flex_bison#
使用下我们的wc程序:
root@manu
:
~
/
code/flex_bison# cat /var/log/kern
.
log
|
.
/
wc
13731 136454 1322344
root@manu
:
~
/
code/flex_bison# cat /var/log/kern
.
log
|
wc
13731 189620 1322344
可以看出我们的程序行数和字符数都是对的,但是单词数和标准的wc程序不同,这是因为我们对word的定义和标准的wc不同。
我们将第二部分添上:
[
^
\t\n\r\f\v
]
+
{ words
+
+
;
chars
+
=
strlen
(
yytext
)
;
}
结果就和标准的wc一样了。
root@manu
:
~
/
code/flex_bison# cat /var/log/kern
.
log
|
/
usr/bin/wc
13731 189620 1322344
root@manu
:
~
/
code/flex_bison# cat /var/log/kern
.
log
|
.
/
wc
13731 189620 1322344
不知道大家有没有激动,反正我是很激动,统计单词个数,这个函数看起来很复杂的函数,短短几行代码就搞定了。另外,不知道为什么,这个流程总让我想起Lisp的mapcar。
我毕业那年,参加了公司的TDD的培训,培训的思想是测试驱动开发(TDD)。其中第一道题目就是编写一个基本的四则运算的计算器,输入字符串,如
(1
+
2×4/6)
+
3/4
+
|
2
-
4
|
正确的返回结果。当时我们的scope比较小,基本是10以内个位数的加减乘除,带括号,带不带绝对值我都记不的了。当时写了一个近400行的C代码,当时很有成就感。我记得波哥对我微微一笑给我说了两个词 yacc lex。当时波哥给我写bison的资料,我当时不会的东西太多,没有顾上深入的学习flex 和 bison。昨天我就想起了这个事情,一边学习flex and bison这本书,一边照着课本写了一个计算器。
先介绍下Bison,bison的前身是传说中的yacc,yacc是由贝尔实验室的S.C.Johnson基于Knuth大神的LR分析技术,于1975~1978年写成。1987年 UC Berkeley 的Bob Corbett在BSD下重写了yacc。在后来GNU project接管了项目,添加了很多特性,形成了今天的GNU Bison。在Ubuntu下安装:
sudo apt
-
get install bison
Bison的.y文件也是分成三个部分:
三个部分也是用%%隔开
1 声明部分:所有词法单元的定义可以放在此处
2 规则部分:具体的语法和相应的动作。
3 用户自定义部分。第三部分会被bison原封不动的拷贝进生成的.C文件。
下面看下计算器的.y文件:
root@manu
:
~
/
code/flex_bison/calc# cat calc
.
y
/
*
simplest version
of
calculator
*
/
%{
#
include
<
stdio
.
h
>
#define YYSTYPE double
%}
/
*
declare tokens
*
/
%token NUMBER
%token
ADD
SUB
MUL
DIV
ABS OP CP
%token EOL
%%
calclist
:
/
*
nothing
*
/
|
calclist exp EOL { printf
(
"= %f\n"
,
$2
)
;
}
;
exp
:
factor
|
exp
ADD
factor { $$
=
$1
+
$3
;
}
|
exp
SUB
factor { $$
=
$1
-
$3
;
}
;
factor
:
term
|
factor
MUL
term { $$
=
$1
*
$3
;
}
|
factor
DIV
term { $$
=
$1 / $3
;
}
;
term
:
NUMBER
|
ABS exp ABS { $$
=
$2
>
=
0
?
$2
:
-
$2
;
}
|
OP exp CP { $$
=
$2
;
}
;
%%
main
(
int
argc
,
char
*
*
argv
)
{
yyparse
(
)
;
}
yyerror
(
char
*
s
)
{
fprintf
(
stderr
,
"error: %s\n"
,
s
)
;
}
bison和flex如果协同工作,应然怎么办呢:
首先bison -d选项,将calc.y文件处理生成两个文件calc.tab.c和calc.tab.h。其中H文件包含所有词法单元的定义:
root@manu
:
~
/
code/flex_bison/calc# cat calc
.
tab
.
h
.
.
.
.
enum yytokentype {
NUMBER
=
258
,
ADD
=
259
,
SUB
=
260
,
MUL
=
261
,
DIV
=
262
,
ABS
=
263
,
OP
=
264
,
CP
=
265
,
EOL
=
266
}
;
.
.
.
.
.
.
我们需要在flex的l文件中添加bison生成的.h文件。我们直接看下calc.l文件
root@manu
:
~
/
code
/
flex_bison
/
calc# cat calc
.
l
%{
#define YYSTYPE double
#include "calc.tab.h"
#ifdef CALC_LEX
YYSTYPE yylval;
#endif
%}
%%
"+" { return ADD; }
"-" { return SUB; }
"*" { return MUL; }
"/" { return DIV; }
"(" { return OP; }
")" { return CP; }
"|" { return ABS; }
\n { return EOL; }
[ t] { /* ignore */ }
([0-9]*\.?[0-9]+|[0-9]+\.[0-9]*) { yylval = atof(yytext); return NUMBER; }
%%
#ifdef CALC_LEX
int main (int argc, char** argv) {
int token;
while (token = yylex()) {
printf("%d", token);
if (token == NUMBER) {
printf(" = %f\n", yylval);
} else {
printf("\n");
}
}
return 0;
}
#endif
其中ifdef CALC_LEX部分属于单元测试部分代码,熟悉python的筒子,应该不陌生。OK,我们可以看下makefile看下如何使用flex和bison合作,生成一个计算器calc:
root@manu
:
~
/
code/flex_bison/calc# cat Makefile
cc
=
gcc
calc
:
calc
.
y calc
.
l
bison
-
d calc
.
y
flex
-
o calc
.
lex
.
c calc
.
l
cc
-
o $@ calc
.
tab
.
c calc
.
lex
.
c
-
lfl
calc
.
lex
:
calc
.
y calc
.
l
bison
-
d calc
.
y
flex
-
o calc
.
lex
.
c calc
.
l
cc
-
D CALC_LEX
-
o $@ calc
.
lex
.
c
-
lfl
clean
:
rm calc
.
lex
.
c
rm calc
.
tab
.
h
rm calc
.
tab
.
c
rm calc
执行一下make,可以看到生成了calc可执行程序。我们验证calc好不好用:
root@manu
:
~
/
code/flex_bison/calc# ll
总用量 156
drwxr
-
xr
-
x 2 root root 4096 4月 6 13
:
46
.
/
drwxr
-
xr
-
x 3 root root 4096 4月 6 11
:
51
.
.
/
-
rwxr
-
xr
-
x 1 root root 36459 4月 6 12
:
38 calc
*
-
rw
-
r
-
-
r
-
-
1 root root 979 4月 6 12
:
19 calc
.
l
-
rw
-
r
-
-
r
-
-
1 root root 45726 4月 6 12
:
38 calc
.
lex
.
c
-
rw
-
r
-
-
r
-
-
1 root root 45991 4月 6 12
:
38 calc
.
tab
.
c
-
rw
-
r
-
-
r
-
-
1 root root 2104 4月 6 12
:
38 calc
.
tab
.
h
-
rw
-
r
-
-
r
-
-
1 root root 690 4月 6 12
:
37 calc
.
y
-
rw
-
r
-
-
r
-
-
1 root root 282 4月 6 12
:
38 Makefile
root@manu
:
~
/
code/flex_bison/calc#
.
/
calc
1
+
2
=
3
.
000000
3/4
+
2
=
2
.
750000
|
2
-
4
|
*
3
-
2/
(
1
+
3
)
=
5
.
500000
2.4*5/48
= 0.250000
加上makefile,一共有91行代码。 这个例子本身没有什么什么,而且计算器本身还不完善。但是这个例子给我自己的启示是,计算机发展到现在,我们的前辈创造出了大量的有价值的东西,比如这个flex 和bison,如果我们不利用,我们自己去写一个四则运算的计算器,感兴趣的筒子可以实验下,考虑括号,考虑绝对值,考虑算法优先级,代码写的会特别的蛋疼,而且扩展性不好。我们伟大的前辈帮我们抽象这个事情,很多类似的工作就变的非常的easy。我们应该站在前辈的肩上去解决问题,而不应该人人都从0开始,这样浪费了太多的时间。对于某些领域,我们需要利用前人的成果,我们首先要通过大量的学习,至少了解前人的成果。
光荣属于前辈,光荣属于那些无数有分享精神 探索精神的前辈。
参考文献:
1 flex and bison
2 Flex/Bison Tutorial, by Aaron Myles Landwehr
3
用flex和bison做一个命令行计算器-第一次尝试
4 词法分析&语法分析 实习指导 原著:陈嘉 许畅 改编:朱晓瑞 许畅
本站仅提供存储服务,所有内容均由用户发布,如发现有害或侵权内容,请
点击举报
。
打开APP,阅读全文并永久保存
查看更多类似文章
猜你喜欢
类似文章
【热】
打开小程序,算一算2024你的财运
基于MSYS的 Flex & Bison
Bison解析器生成器概览
Lex和Yacc从入门到精通(1)--环境配置篇
编译器编译原理
lex & Yacc
Linux环境报错原因、解决方法记录(逐步总结)
更多类似文章 >>
生活服务
热点新闻
留言交流
回顶部
联系我们
分享
收藏
点击这里,查看已保存的文章
导长图
关注
一键复制
下载文章
绑定账号成功
后续可登录账号畅享VIP特权!
如果VIP功能使用有故障,
可点击这里联系客服!
联系客服
微信登录中...
请勿关闭此页面
先别划走!
送你5元优惠券,购买VIP限时立减!
5
元
优惠券
优惠券还有
10:00
过期
马上使用
×