学过编译原理的朋友肯定都接触过
LEX
这个小型的词法扫描工具
.
但是却很少有人真正把
LEX
用在自己的程序里
.
在构造专业的编译器的时候
,
常常需要使用到
lex
和
yacc.
正是因为这两个工具
,
使得我们编写编译器
,
解释器等工具的时候工作变得非常简单
.
不过话说回来
,
会使用
lex
和
yacc
的人也确实不简单
. Lex
和
yacc
里面牵涉到一系列的编译原理的理论知识
,
不是简单地看看书就能搞懂的
.
本文只是简单地介绍一下
lex
和
yacc
的使用方法
.
相关编译理请查看本科教材
.
国内大学教材里面对于
lex
和
yacc
的介绍很少
,
有些根本就没有
,
不过在国外的编译原理教材介绍了很多
.
按照学科的分类
,
国内大学本科里面开的
<<
编译原理
>>
教程只是讲解编译的原理
,
并不讲解实践
.
而对于实践方面则是另外一门学科
<<
编译技术
>>.
关于编译技术的书籍在国内是少之又少
.
前不久
,
听说上海交大的计科内部出版过编译技术的教材
.
可惜我们这些人就无法得见了
.
还好
,
机械工业出版社引进了美国
Kenneth C.Louden
所著的经典著作
<<
编译原理及实践
>>
中
,
比较详细地介绍
lex
和
yacc
的使用
.
Lex
属于
GNU
内部的工具
,
它通常都是
gcc
的附带工具
.
如果你使用的
Linux
操作系统
,
那么肯定系统本身就有
lex
和
yacc,
不过
yacc
的名字变成了
bison.
如果你使用的
Windows
操作系统
,
那么可以到
cygwin
或者
GNUPro
里面找得到
.
网上也有
windows
版本
lex
和
yacc,
大家可以自己去找一找
.
本文一共有两篇
,
一篇是介绍
lex,
另一篇是介绍
yacc. Lex
和
yacc
搭配使用
,
我们构造自己的编译器或者解释器就如同儿戏
.
所以我把本文的名字叫做黄金组合
.
本文以
flex( Fase Lex)
为例
,
两讲解如何构造扫描程序
.
Flex
可以通过一个输入文件
,
然后生成扫描器的
C
源代码
.
其实扫描程序并不只用于编译器
.
比如编写游戏的脚本引擎的时候
,
我看到很多开发者都是自己写的扫描器
,
其算法相当落后
(
完全没有
DFA
的概念化
),
甚至很多脚本引擎开发者的词法扫描器都没有编写
,
而是在运行过程中寻找
token(
单词
).
在现代的计算机速度确实可以上小型的脚本引擎在运行中进行词法扫描
,
但是作为一个合格的程序员
,
或者说一个合格的计算机本科毕业生而来说
,
能够运用编译原理与技术实践
,
应该是个基本要求
.
如果要说到词法分析的扫描器源代码编写
,
其实也很简单
,
会
C
语言的人都会写
.
可是
Kenneth Louden
在
<<
编译原理及技术
>
里面
,
花了
50
多页
,
原因就是从理论角度
,
介绍标准的
,
可扩展的
,
高效的词法扫描器的编写
.
里面从正则表达式介绍到
DFA(
有穷自动机
),
再到
NFA(
非确定性有穷自动机
),
最后才到代码的编写
.
以自动机原理编译扫描器的方法基本上就是现在词法扫描器的标准方法
,
也就是
Lex
使用的方法
.
在
Lex
中
,
我们甚至不需要自己构造词法的
DFA,
我们只需要把相应的正则表达式输入
,
然后
lex
能够为我们自己生成
DFA,
然后生成源代码
,
可谓方便之极
.
本文不讲
DFA, lex
的输入是正则表达式
,
我们直接先看看正则表达式方面知识就可以了
.
1.
正则表达式
(regular expression):
对于学过编译原理的朋友来说
,
这一节完全可以不看
.
不过有些东西还是得注意一下
,
因为在
flex
中的正则表达式的使用有些具体的问题是在我们的课本上没有说明的
.
先看看例子
:
例
1.1
name Tangl_99
这就是定义了
name
这个正则表达式
,
它就等于字符串
Tangl_99.
所以
,
如果你的源程序中出现了
Tangl_99
这个字符传
,
那么它就等于出现一次
name
正则表达式
.
例
1.2
digit 0|1|2|3|4|5|6|7|8|9
这个表达式就是说
,
正则表达式
digit
就是
0,1,2,…,9
中的某一个字母
.
所以无论是
0,2,
或者是
9…
都是属于
digit
这个正则表达式的
.
“|”
符号表示
”
或者
”
的意思
.
那么定义正则表达式
name Tangl_99|Running,
同样的
,
如果你的源程序中出现了
Tangl_99
或者
Running,
那么就等于出现了一次
name
正则表达式
.
例
1.3
one 1*
“*”
符号表示
”
零到无限次重复
”
那么
one
所表示的字符串就可以是空串
(
什么字符都没有
), 1, 11, 111, 11111, 11111111111, 11111111…
等等
.
总之
,one
就是由
0
个或者
N
个
1
所组成
(N
可以为任意自然数
).
与
”*”
相同的有个
”+”
符号
.
请看下面的例子
1.4
例
1.4
realone 1+
“+”
符号表示
”1
到无限次重复
”
那么
realone
和
one
不同的唯一一点就是
,realone
不包含空串
,
因为
”+”
表示至少一次重复
,
那么
realone
至少有一个
1.
所以
realone
所表达的字符串就是
1,11,111, 1111, 11111…,
等等
.
例
1.5
digit [0-9]
letter [a-zA-Z]
这里的
digit
等于例
1.2
中的
digit,
也就是说
,a|b|c
就相当于
[a-c].
同理
,letter
也就是相当于
a|b|c|d|e|f|…|y|z|A|B|C|D…|Z
不过注意的一点就是
,
你不能把
letter
写成
[A-z],
而必须大写和小写都应该各自写出来
.
例
1.6
notA [^A]
“^”
表示非
,
也就是除了这个字符以外的所有字符
所以
notA
表示的就是除了