从lex&yacc说到编译器（一）：正则表达式--我的博客

一、正则表达式

学过编译原理的朋友肯定都接触过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表示的就是除了A以外的所有字符.

下面让我们来看看一些一般高级程序语言中常用的综合例子.

digit        [0-9]

number     {digit}+

letter       [a-zA-Z_]

digit前面多次提起过,就是0-9的阿拉伯数字.number就是所有的数字组合,也就是整数.

Letter前面也提起过,唯一不同的就是多了一个下划线.因为一般我们的C语言中容许有下划线来表示定义的变量名,所以我也把下划线当成英语字母来处理了.

这里number中使用上面定义的digit正则表达式.在lex中,用{digit}就是表示正则表达式digit.

newline      [\n]

whitespace   [ \t]+

newline就是提行的意思.这里我们使用的是\n这个符号,它和C语言中表示提行号一致.问题是大家可能要问到为什么要使用[]符号.因为在lex中,如果你使用[],那么里面表示的肯定就是单个字符号,而不会被理解成”\”和”n”两个字符.

Whitespace就是空格符号的意思.一般的高级程序语言中有两种,一种就是简单的空格,还有一种就是\t制表符.使用了”+”符号,就表示了这些空白符号的无限组合.

- 作者： 流星 访问统计： 　2005年10月11日, 星期二 03:04 加入博采