Lex和Yacc从入门到精通 熊春雷
Lex 和 Yacc 从入门到精通 熊春雷
Abstract 在开发程序的过程中经常会遇到文本解析的问题，例如：解析C语言源程序 编写脚本引擎等等 ，解决这种文本解析的方》 有很多， 方法就是自己手动 用C或者C+直接编写解析程序，这对于简单格式的文本信息来说，不会是什么 问题，但是对于稍微复杂一点的文本信息的解析来说，手工编写解析器将会是 一件漫长痛苦而容易出错的事情。本系列文档就是专门用来由浅入深的介绍两 个有名的Inix T且1ex知Vacc,并会一步一步的详细解强加何用这两个T且 来实现我们想要的任何功能的解析程序，为了方便理解和应用，我会在该系列 的文章中尽可能的采用具体可行的实例来加以阐释，而且这种实例都是尽可能 的和具体的系统平台无关的，因此我采用命令行程序作为我们的解析程序的最 终结果
Abstract 在开发程序的过程中经常会遇到文本解析的问题，例如：解析 C 语言源程序， 编写 脚本引擎等等，解决这种文本解析的方法有很多，一种方法就是自己手动 用 C 或者 C++直接编写解析程序，这对于简单格式的文本信息来说，不会是什么 问题，但是 对于稍微复杂一点的文本信息的解析来说，手工编写解析器将会是 一件漫长痛苦 而容易出错的事情。本系列文档就是专门用来由浅入深的介绍两 个有名的 Unix 工 具 Lex 和 Yacc，并会一步一步的详细解释如何用这两个工具 来实现我们想要的任何 功能的解析程序，为了方便理解和应用，我会在该系列 的文章中尽可能的采用具 体可行的实例来加以阐释，而且这种实例都是尽可能 的和具体的系统平台无关的 ，因此我采用命令行程序作为我们的解析程序的最 终结果
1、环境配置篇 开发Lex和Yacc程序最需要的程序就是lex和yacc了，如果你是Unix或 者Liux系统，则系统自带了这两个工具，无需安装，不过值得说明的是 GNU/Linux下面的Lex是flex,而Yacc则是bison。另外需要的就是一个C/C+ 语言编译器，由于我们采用的是GW的lex和yacc,所以，理所当然的我们就 使用GNU的编译器了，如果是Unix或者Linux系统，那么编译器应该已经安装 了。在这里我重点讨论的是Windows系统环境下的Lex和Yacc程序的开发，至 于为什么选择Windows系统作为开发平台，则是为了尽可能的让初学者容易入 门。 1.1.必备工具 言归正传，首先列举Windows平台下面Lex和Yacc开发环境所需要安装的程 序： L.Lex(flex.exe)和Yacc(bison.exe)环境 2.C/C+编译器 1.2.f1ex和bison 值得说明的是，flex.exe和bison.exe是UnxUtils包中的文件，已经将许多 Unix/Linu x平台的程序都移植到了Wi s平台，可以直接到UnxUtilsl网站下载 下载解压缩之后在系统 PATH 境变量中增加UnxUtils/所有的exe文件所在的 录，使得D0S命令行可以直接搜索到flex.exe和bison..exe,除此之外还需要 网络上下载bison需要的bison..simple和bison.hairy两个文件，并且还要分别 设置环境变量BISON HAIRY:指向bison.hairy,BISON SIMPLE指向bison.simple。 Tip 如果觉得麻烦也可以直接使用我做好的flex和bison环境，点击这里下载。 解压缩lexyacc.rar之后运行里面的lexyacc.bat文件就会得到一个lex利 yacc环境，下图是简单的运行结果： 1.3.C/C+编译器 由于我们使用的f1ex和bison都是GNU的工具，所以为了方便，采用的C/C+ 编译器也采用GU的编译器CCC,当然我们需要的也是indows版本的GCC了。目 前Windows平台的GCC主要是MinGW编译器，可以到MinGW的主页下载安装
1、环境配置篇 开发 Lex 和 Yacc 程序最需要的程序就是 lex 和 yacc 了，如果你是 Unix 或 者 Linux 系统，则 系统自带了这两个工具，无需安装，不过值得说明的是 GNU/Linux 下面的 Lex 是 flex， 而 Yacc 则是 bison。另外需要的就是一个 C/C++ 语言编译器，由于我们采用的是 GNU 的 lex 和 yacc，所以，理所当然的我们就 使用 GNU 的编译器了，如果是 Unix 或者 Linux 系统 ，那么编译器应该已经安装 了。在这里我重点讨论的是 Windows 系统环境下的 Lex 和 Yacc 程序的开发，至 于为什么选择 Windows 系统作为开发平台，则是为了尽可能的让初 学者容易入 门。 1.1．必备工具 言归正传，首先列举 Windows 平台下面 Lex 和 Yacc 开发环境所需要安装的程 序： 1. Lex(flex.exe)和 Yacc(bison.exe)环境 2. C/C++编译器 1.2．flex 和 bison 值得说明的是，flex.exe和bison.exe是UnxUtils包中的文件，已经将许多 Unix/Linux平台的程序都移植到了Windows平台，可以直接到UnxUtils网站下载， 下载解压缩之后在系统的PATH环境变量中增加UnxUtils所有的exe文件所在的目 录，使 得DOS命令行可以直接搜索到flex.exe和bison.exe，除此之外还需要从 网络上下载 bison需要的bison.simple和bison.hairy两个文件，并且还要分别 设置环境变量 BISON_HAIRY指向bison.hairy，BISON_SIMPLE指向bison.simple。 Tip 如果觉得麻烦也可以直接使用我做好的flex和bison环境，点击这里下载。 解压缩 lexyacc.rar 之后运行里面的 lexyacc.bat 文件就会得到一个 lex 和 yacc 环境， 下图是简单的运行结果： 1.3．C/C++编译器 由于我们使用的flex和bison都是GNU的工具，所以为了方便，采用的C/C++ 编译器也 采用GNU的编译器GCC，当然我们需要的也是Windows版本的GCC了。目 前Windows平台 的GCC主要是MinGW编译器，可以到 MinGW的主页下载安装
Important 注意安装了MinGW.之后一定要将安装后的MinGW的bin路径设置到环境变量 PATH中。 我们在下一章里面将会真正的接触到Lex和Yacc的具体内容，敏请关注：)
Important 注意安装了 MinGW 之后一定要将安装后的 MinGW 的 bin 路径设置到环境变量 PATH 中。 我们在下一章里面将会真正的接触到 Lex 和 Yacc 的具体内容，敬请关注:)
2、正则表达式篇 正则表达式在Unix/Liunx系统中起着非常重要的作用，在很大一部分的程 序中都使用了正则表达式，可以这么说： 在Unix/Linux系统中，如果不懂正 则表达式就不算会使用该系统”。本文中使用的Lex和Yacc都是基于正则表达 式的应用，因此有必要用一篇文档的形式详细说明在Lex和Yacc中使用的正则 表达式为何物！ 其实正则表达式非常简单，用过DOS的人都知道通配符吧，说得简单一点， 正则表达式就是稍微复杂 点的通配符。这里的正则表达式非常简单，规则非常 少，只需要花上几分钟就可以记住。正则表达式的元字符列表如下： 元字符 匹配内容 除了换行符之外的任意字符 换行符 米 0次或者多次匹配 1次或者多次匹配 0次或者1次匹配 行首 文 行尾 a或者b (ab)+ ab的一次或者多次匹配 “a+b” a+b(字面意思) 一类字符 有了上面的元字符之后，就可以用上面的元字符表达出非常复杂的匹配内容 出来，就像DOS名令中的通配符可以匹配多个指定规则的文件名一样。现在让我 们看看上面的元字符的一些应用例子，列表如下： 表达式 匹配内容 abc abc ahc常 abc abcc abccc abcccc… abc+ abcc abccc abcccc..... a(bc)+ abcbc abcbcbc abcbcbcbc..... a(bc)? abc abchc [abc abc其中之 [a-z] a b c d e f g……z其中之日 「a1-21 a-z三个字符其中之二 [-az] az三个字符其中之 [A-Za-20-9]± 大小写字符和10个数字的一个或多个 [1t\n] 空格，跳格，换行三者之一（空白符）
2、正则表达式篇 正则表达式在 Unix/Liunx 系统中起着非常重要的作用，在很大一部分的程 序中都使用了正则表达式，可以这么说：“在 Unix/Linux 系统中，如果不懂正 则表达式就不算会使用该系统”。本文中使用的 Lex 和 Yacc 都是基于正则表达 式的应用，因此有必要用一篇文档的形式详细说明在 Lex 和 Yacc 中使用的正则 表达式为何物！ 其实正则表达式非常简单，用过 DOS 的人都知道通配符吧，说得简单一点， 正则表达式就是稍微复杂一点的通配符。这里的正则表达式非常简单，规则非常 少，只需要花上几分钟就可以记住。正则表达式的元字符列表如下： 元字符 匹配内容 . 除了换行符之外的任意字符 \n 换行符 * 0 次或者多次匹配 + 1 次或者多次匹配 ? 0 次或者 1 次匹配 ^ 行首 $ 行尾 a|b a 或者 b (ab)+ ab 的一次或者多次匹配 “a+b” a+b（字面意思） [] 一类字符 有了上面的元字符之后，就可以用上面的元字符表达出非常复杂的匹配内容 出来，就像 DOS 名令中的通配符可以匹配多个指定规则的文件名一样。现在让我 们看看上面的元字符的一些应用例子，列表如下： 表达式 匹配内容 abc abc abc* abc abcc abccc abcccc …… abc+ abcc abccc abcccc …… a(bc)+ abcbc abcbcbc abcbcbcbc …… a(bc)? abc abcbc [abc] a b c 其中之一 [a-z] a b c d e f g… … z 其中之一 [a\-z] a – z 三个字符其中之一 [-az] – a z 三个字符其中之一 [A-Za-z0-9]+ 大小写字符和 10 个数字的一个或多个 [ \t\n] 空格，跳格，换行三者之一（空白符）
['ab] 除了ab之外的任意字符 [a'b] a“b三者之 a b ab三者之 a b ab两者之二 abcs 只有abc的一行 注意*和+的区别，通配符只是匹配之前最近的元素，可以用小括号将多个元 素括起来，整个括号括起来的整体可以看作是一个元素。那么通配符就可以匹配 整个括号的内容了。 方括号表示的是一类字符，[abc]就是定义了只有abc三个字符的一类字符。 这一点和bc不同，如果跟上通配符(*+？)的话，那么方括号就可以表示前面 的任意的字符 个字符的多个匹配，但是 bc的话就只能是c的多个匹配 了。说的更明白点就是D0S里面的通配符*表示的是任意字符的零个或者多个， 而这里的方括号就是把DOS里面的任意字符类缩小为只有方括号表示的类了。另 外还要注意连字符-在方括号中的意思，在方括号的中间表示“范围”的意思， 而在首部则仅仅表示自己而己。 转义用\，这和C语言类似，另外还需要注意三个特殊的元字符(|$)的意 不在济搭肉苹装的素不，除装示健他地方设有特别意文。 通过上面的注释可以看出：使用正则表达式可以表示非常复杂的匹配内容
[^ab] 除了 ab 之外的任意字符 [a^b] a ^ b 三者之一 [a|b] a | b 三者之一 a|b a b 两者之一 ^abc$ 只有 abc 的一行 注意*和+的区别，通配符只是匹配之前最近的元素，可以用小括号将多个元 素括起来，整个括号括起来的整体可以看作是一个元素。那么通配符就可以匹配 整个括号的内容了。 方括号表示的是一类字符，[abc]就是定义了只有 abc 三个字符的一类字符。 这一点和 abc 不同，如果跟上通配符（*+?）的话，那么方括号就可以表示前面 的任意的字符之一的一个字符的多个匹配，但是 abc 的话就只能是 c 的多个匹配 了。说的更明白点就是 DOS 里面的通配符*表示的是任意字符的零个或者多个， 而这里的方括号就是把 DOS 里面的任意字符类缩小为只有方括号表示的类了。另 外还要注意连字符-在方括号中的意思，在方括号的中间表示“范围”的意思， 而在首部则仅仅表示自己而已。 转义用\，这和 C 语言类似，另外还需要注意三个特殊的元字符(^ | $)的意 义。‘^’放在方括号的首部表示“除了”的意思，在其他地方没有特别意义。 ‘|’不在方括号中表示“或者”，‘$’通常表示行尾。 通过上面的注释可以看出：使用正则表达式可以表示非常复杂的匹配内容
3、一个极其简单的lex和yacc程序 摘要 在本章中，将会首先给出一个最基本的1ex和yacc联合使用的框架，这个基本 框架最主要的特点就是能够正确的被编译。在我学习lex和yacc的过程中经历 了无数次的痛苦折磨，我发现一个一开始足够简单而且能够被正确编译的例了 往往能够使学习者增加学习的兴趣和信心。因此我的所有的文章都尽可能的采 用这种方式进行描述。我写这些文档的最大的愿望就是希望能够减少新手学习 的痛苦。希望自己能够做到这一点！ 1.基本的1ex文件 例3.1.frame.1 int yywrap(void): 制 8 8 int yywrap(void) return 1: lex文件和yacc文件都是被%分成了上中下三个部分，在这个程序中的yywrap 函数需要说明一下： yywrap lex源文件中的yyra即函数是必须的！具体的原因就是因为给了这个函 数实现之后就可以不需要依赖flex库了。具体yywrap的作用会在后面
3、一个极其简单的 lex 和 yacc 程序 摘要 在 本章中，将会首先给出一个最基本的 lex 和 yacc 联合使用的框架，这个基本 框架 最主要的特点就是能够正确的被编译。在我学习 lex 和 yacc 的过程中经历 了无数次 的痛苦折磨，我发现一个一开始足够简单而且能够被正确编译的例子 往往能够使 学习者增加学习的兴趣和信心。因此我的所有的文章都尽可能的采 用这种方式进 行描述。我写这些文档的最大的愿望就是希望能够减少新手学习 的痛苦。希望自 己能够做到这一点！ 1. 基本的 lex 文件 例 3.1. frame.l %{ int yywrap(void); %} %% %% int yywrap(void) { return 1; } lex 文件和 yacc 文件都是被%%分成了上中下三个部分，在这个程序中的 yywrap 函数 需要说明一下： yywrap lex 源文件中的 yywrap 函数是必须的！具体的原因就是因为给了这个函 数实 现之后就可以不需要依赖 flex 库了。具体 yywrap 的作用会在后面
的章节应用的时候进行解释。通常的做法就是直接返回1，表示输入己 经结束了。 2.基本的yacc文件 例3.2.frame.y 0 void yyerror(const char *s); 的 program: 都 void yyerror(const char *s) int main( yyparse(); return 0: 如前所述，yacc文件被%分成了上中下三个部分，在这个程序中有几个需要说 明的地方： program
的章节应 用的时候进行解释。通常的做法就是直接返回 1，表示输入已 经结束了。 2. 基本的 yacc 文件 例 3.2. frame.y %{ void yyerror(const char *s); %} %% program: ; %% void yyerror(const char *s) { } int main() { yyparse(); return 0; } 如前所述，yacc 文件被%%分成了上中下三个部分，在这个程序中有几个需要说 明 的地方： program
这是语法规则里面的第一个非终结符，注意上面的格式哦：“prog肛am” 后面紧跟若一个冒号“：”，然后换行之后有一个分号“： ,这表明这 人 是由空串组成的。至 什么是非终结符以及什么是终结符， 还有什么是语法规则都会在后面的章节中进行详细介绍。 yyerror 从字面上就可以看出是一个处理错误的函数，在这里为空的原因是为了保 证代码尽可能的简洁！实际上这个函数里面的代码通常只有一句输出语 句，当然如果你喜欢还可以加入纠错代码，使你的解析器具备纠错能力：) yyparse 其实这个函数是yacc生成的，所以你在代码里面可以直接使用。这个时 候你可能会问：“yacc生成了yyparse函数，那么lex是不是也生成了 什么函数呢？”，是的，lex生成的函数为yylex函数。实际上yyparse 还间接调用了yylex函数，可以在生成的C源文件中去核实。 main 每一个C/C+程序都必须的装备啊 少了怎么能行呢：)所以这个main函 数你可以放到任何的地方，当然要保证能够调用yyparse就可以了。但 是通常的做法就是将main函数放到yacc文件中。 从上面的ycc文件中还可以看出被%分割成为的三个部分，第一部分中要写入 C/C++代码必须用%和%}括起来：但是第三个部分就可以直接写入C/C++代码 ，不需要任何的修饰：中间的那一部分就是】 cc语法规则了。为了能够让这 个最最简单 源程序能够通过bison的编译必须要提供 个语法 则，这 里给出了一 最简单的规则：一个program就是由空字符串构成的。实际上等于 什么也没有做。呵呵，对啊，本章的目的就是为了能够编译通过lex和yacc源 程序，并且也能够被C/C+编译器编译通过啊。现在是不是己经真的编译通过 了呢，可以按照下面的编译步骤一步一步的来编译核实。 提示 对yacc的描述同样也适用于lex。 lex就是词法扫描器，yacc就是语法分析器，这是通用的说法：具体的实现有所 不同GNW的lex就是flex,GNWU的yacc就是bison。为了统一，所以在后面的 文章中就只会用lex来表达词法扫描器，用yacc来表达语法分析器啦！ 3.用C语言编译器编译
这 是语法规则里面的第一个非终结符，注意上面的格式哦：“program” 后 面紧跟着一个冒号“:”，然后换行之后有一个分号“;”，这表明这 个 program 是由空串组成的。至于什么是非终结符以及什么是终结符， 还有什 么是语法规则都会在后面的章节中进行详细介 绍。 yyerror 从字面上就可以看出是一个处理错误的函数，在这里为空的原因是为了保 证代码尽可能的简洁! 实际上这个函数里面的代码通常只有一句输出语 句 ，当然如果你喜欢还可以加入纠错代码，使你的解析器具备纠错能力:) yyparse 其 实这个函数是 yacc 生成的，所以你在代码里面可以直接使用。这个时 候 你可能会问：“yacc 生成了 yyparse 函数，那么 lex 是不是也生成了 什么函 数呢？”，是的，lex 生成的函数为 yylex 函数。实际上 yyparse 还间接调用 了 yylex 函数，可以在生成的 C 源文件中去核实。 main 每一个 C/C++程序都必须的装备啊，少了怎么能行呢:)所以这个 main 函 数你 可以放到任何的地方，当然要保证能够调用 yyparse 就可以了。但 是通常的 做法就是将 main 函数放到 yacc 文件中。 从 上面的 yacc 文件中还可以看出被%%分割成为的三个部分，第一部分中要写入 C/C++代码必须用%{和%}括起来；但是第三个部分就可以直接写入 C/C++代码 了 ，不需要任何的修饰；中间的那一部分就是 yacc 语法规则了。为了能够让这 个 最最简单的 yacc 源程序能够通过 bison 的编译必须要提供一个语法规则，这 里给出了一个最简单的规则：一个 program 就是由空字符串构成的。实际上等于 什么也没有做。呵呵，对啊，本章的目的就是为了能够编译通过 lex 和 yacc 源 程 序，并且也能够被 C/C++编译器编译通过啊。现在是不是已经真的编译通过 了呢 ，可以按照下面的编译步骤一步一步的来编译核实。 提示 对 yacc 的描述同样也适用于 lex。 lex 就是词法扫描器，yacc 就是语法分析器，这是通用的说法；具体的实现有所 不同 GNU 的 lex 就是 flex，GNU 的 yacc 就是 bison。为了统一，所以在后面的 文章 中就只会用 lex 来表达词法扫描器，用 yacc 来表达语法分析器啦! 3. 用 C 语言编译器编译
下面是编译全过程记录，采用了我在第一章中所制作的lex和yacc转换环境： D:\work\lex_yacc\chapter03>dir 驱动器D中的卷是工作区 卷的序列号是54D0-5FC0 D:\work\lex_yacc\chapter03的目录 2006-09-2520:27 2006-09-2520:27 2006-092520:07 71 frame.1 2006-09-2520:20 144 frame.y 2个文件 215字节 2个目录7,785,578,496可用字节 D:\work\lex_yacc\chapter03>flex frame.1 D:\work\lex_yacc\chapter03>dir 驱动器D中的卷是工作区 卷的序列号是54D0-5FC0 D:\work\lex_yacc\chapter0(3的目录
下面是编译全过程记录，采用了我在第一章中所制作的 lex 和 yacc 转换环境： D:\work\lex_yacc\chapter03>dir 驱动器 D 中的卷是 工作区 卷的序列号是 54D0-5FC0 D:\work\lex_yacc\chapter03 的目录 2006-09-25 20:27 . 2006-09-25 20:27 .. 2006-09-25 20:07 71 frame.l 2006-09-25 20:20 144 frame.y 2 个文件 215 字节 2 个目录 7,785,578,496 可用字节 D:\work\lex_yacc\chapter03>flex frame.l D:\work\lex_yacc\chapter03>dir 驱动器 D 中的卷是 工作区 卷的序列号是 54D0-5FC0 D:\work\lex_yacc\chapter03 的目录