本节书摘来自华章计算机《编译原理实践与指导教程》一书中的第1章，第1.2节,作者：许畅 陈嘉 朱晓瑞著， 更多章节内容可以访问云栖社区“华章计算机”公众号查看。
词法分析和语法分析这两块，可以说是在整个编译器当中被自动化得最好的部分。也就是说即使没有任何的理论基础，在掌握了工具的用法之后，也可以在短时间内做出功能很全很棒的词法分析程序和语法分析程序。当然这并不意味着，词法分析和语法分析部分的理论基础并不重要。恰恰相反，这一部分被认为是计算机理论在工程实践中最成功的应用之一，对它的介绍也是编译理论课中的重点。但本节指导内容的重点不在于理论而在于工具的使用。本节指导内容将分别介绍词法分析工具GNU Flex和语法分析工具GNU Bison。如前所述，完成实验一并不需要太多的理论基础，只要看完并掌握了本节的大部分内容即可完成实验一。1.2.1 词法分析概述词法分析程序的主要任务是将输入文件中的字符流组织成为词法单元流，在某些字符不符合程序设计语言词法规范时要有能力报告相应的错误。词法分析程序是编译器所有模块中唯一读入并处理输入文件中每一个字符的模块，它使得后面的语法分析阶段能在更高抽象层次上运作，而不必纠结于字符串处理这样的细节问题。高级程序设计语言大多采用英文作为输入方式，而英文有个非常好的性质，就是它比较容易断词：相邻的英文字母一定属于同一个词，而字母与字母之间插入任何非字母的字符（如空格、运算符等）就可以将一个词断成两个词。判断一个词是否符合语言本身的词法规范也相对简单，一个直接的办法是我们可以事先列一张搜索表，将所有符合词法规范的字符串都存放在表中，每次我们从输入文件中断出一个词后，通过查找这张表就可以判断该词究竟合法还是不合法。正因为词法分析任务的难度不高，所以在实用的编译器中它常常是手工写成，而非使用工具生成。例如，我们下面要介绍的这个工具GNU Flex原先就是为了帮助GCC进行词法分析而被开发出来的，但在版本4.0之后，GCC的词法分析器已经一律改为手写了。不过，实验一要求使用工具来做，而词法分析程序生成工具所基于的理论基础，是计算理论中最入门的内容：正则表达式（Regular Expression）和有限状态自动机（Finite State Automata）。一个正则表达式由特定字符串构成，或者由其他正则表达式通过以下三种运算得到：1）并运算（Union）：两个正则表达式r和s的并记作r | s，意为r或s都可以被接受。2）连接运算（Concatenation）：两个正则表达式r和s的连接记作rs，意为r之后紧跟s才可以被接受。3）Kleene闭包（Kleene Closure）：一个正则表达式r的Kleene闭包记作r*，它表示：e | r | rr | rrr | …。有关正则表达式的内容在课本的理论部分已讨论过。正则表达式之所以被人们广泛应用，一方面是因为它表达能力足够强（基本上可以表示所有的词法规则），同时还易于书写和理解；另一方面是因为判断一个字符串是否被一个特定的正则表达式接受可以做到非常高效（在线性时间内即可完成）。比如，我们可以将一个正则表达式转化为一个NFA（即不确定的有限状态自动机），然后将这个NFA转化为一个DFA（即确定的有限状态自动机），再将转化好的DFA进行化简，之后我们就可以通过模拟这个DFA的运行对输入串进行识别了。具体的NFA和DFA的含义以及如何进行正则表达式、NFA及DFA之间的转化等，请参考课本的理论部分。这里我们仅需要知道，前面所述的所有转化和识别工作，都可以由工具自动完成。而我们所需要做的仅仅是为工具提供作为词法规范的正则表达式。1.2.2 GNU Flex介绍Flex的前身是Lex。Lex是1975年由Mike Lesk和当时还在AT&T做暑期实习的Eric Schmidt共同完成的一款基于Unix环境的词法分析程序生成工具。虽然Lex很出名并被广泛使用，但它的低效和诸多问题也使其颇受诟病。后来伯克利实验室的Vern Paxson使用C语言重写了Lex，并将这个新的程序命名为Flex（意为Fast Lexical Analyzer Generator）。无论在效率上还是在稳定性上，Flex都远远好于它的前身Lex。我们在Linux下使用的是Flex在GNU License下的版本，称作GNU Flex。GNU Flex在Linux下的安装非常简单。可以去它的官方网站下载安装包自行安装，不过在基于Debian的Linux系统下，更简单的安装方法是直接在命令行输入如下命令：
sudo apt-get install flex虽然版本不一样，但GNU Flex的使用方法与课本上介绍的Lex基本相同。首先，需要自行完成包括词法规则等在内的Flex代码。至于如何编写这部分代码我们在后面会提到，现在先假设这部分写好的代码名为lexical.l。随后，我们使用Flex对该代码进行编译：
flex lexical.l编译好的结果会保存在当前目录下的lex.yy.c文件中。打开这个文件你会发现，该文件本质上就是一份C语言的源代码。这份源代码里目前对我们有用的函数只有一个，叫做yylex()，该函数的作用就是读取输入文件中的一个词法单元。我们可以再为它编写一个main函数：
1 int main(int argc, char** argv) { 2 if (argc > 1) { 3 if (!(yyin = fopen(argv[1], "r"))) { 4 perror(argv[1]); 5 return 1; 6 } 7 } 8 while (yylex() != 0); 9 return 0; 10 }这个main函数通过命令行读入若干个参数，取第一个参数为其输入文件名并尝试打开该输入文件。如果文件打开失败则退出，如果成功则调用yylex()进行词法分析。其中，变量yyin是Flex内部使用的一个变量，表示输入文件的文件指针，如果不设置它，那么Flex会将它自动设置为stdin（即标准输入，通常连接到键盘）。注意，如果将main函数独立设为一个文件，则需要声明yyin为外部变量：
extern FILE* yyin将这个main函数单独放到一个文件main.c中（也可以直接放入lexical.l中的用户自定义代码部分，这样就可以不必声明yyin；甚至可以不写main函数，因为Flex会自动给你配一个，但不推荐这么做），然后编译这两个C源文件。我们将输出程序命名为scanner：
gcc main.c lex.yy.c -lfl -o scanner注意编译命令中的“-lfl”参数不可缺少，否则GCC会由于缺少库函数而报错。之后我们就可以使用这个scanner程序进行词法分析了。例如，想要对一个测试文件test.cmm进行词法分析，只需要在命令行输入：
./scanner test.cmm就可以得到你想要的结果了。1.2.3 Flex：编写源代码以上介绍的是使用Flex创建词法分析程序的基本步骤。在整个创建过程中，最重要的文件无疑是你所编写的Flex源代码，它决定了你的词法分析程序的一切行为。接下来我们介绍如何编写Flex源代码。Flex源代码文件包括三个部分，由“%%”隔开，如下所示：
1 {definitions} 2 %% 3 {rules} 4 %% 5 {user subroutines}第一部分为定义部分，实际上就是给后面某些可能经常用到的正则表达式取一个别名，从而简化词法规则的书写。定义部分的格式一般为：
name definition其中name是名字，definition是任意的正则表达式（正则表达式该如何书写后面会介绍）。例如，下面的这段代码定义了两个名字：digit和letter，前者代表0到9中的任意一个数字字符，后者则代表任意一个小写字母、大写字母或下划线：
1 … 2 digit [0-9] 3 letter [_a-zA-Z] 4 %% 5 … 6 %% 7 …Flex源代码文件的第二部分为规则部分，它由正则表达式和相应的响应函数组成，其格式为：
pattern {action}其中pattern为正则表达式，其书写规则与前面部分的正则表达式的定义相同。而action则为将要进行的具体操作，这些操作可以用一段C代码表示。Flex将按照这部分给出的内容依次尝试每一个规则，尽可能匹配最长的输入串。如果有些内容不匹配任何规则，Flex默认只将其拷贝到标准输出，想要修改这个默认行为只需要在所有规则的最后加上一条“.”（即匹配任何输入）规则，然后在其对应的action部分书写你想要的行为即可。例如，下面这段Flex代码在遇到输入文件中包含一串数字时，会将该数字串转化为整数值并打印到屏幕上：
1 … 2 digit [0-9] 3 %% 4 {digit}+ { printf("Integer value %d\n", atoi(yytext)); } 5 … 6 %% 7 …其中变量yytext的类型为char*，它是Flex为我们提供的一个变量，里面保存了当前词法单元所对应的词素。函数atoi()的作用是把一个字符串表示的整数转化为int类型。Flex源代码文件的第三部分为用户自定义代码部分。这部分代码会被原封不动地拷贝到lex.yy.c中，以方便用户自定义所需要执行的函数（之前我们提到过的main函数也可以写在这里）。值得一提的是，如果用户想要对这部分用到的变量、函数或者头文件进行声明，可以在前面的定义部分（即Flex源代码文件的第一部分）之前使用“%{”和“%}”符号将要声明的内容添加进去。被“%{”和“%}”所包围的内容也会被一并拷贝到lex.yy.c的最前面。下面通过一个简单的例子来说明Flex源代码该如何书写。我们知道Unix/Linux下有一个常用的文字统计工具wc，它可以统计一个或者多个文件中的（英文）字符数、单词数和行数。利用Flex我们可以快速地写出一个类似的文字统计程序：
1 %{ 2 /* 此处省略#include部分 */ 3 int chars = 0; 4 int words = 0; 5 int lines = 0; 6 %} 7 letter [a-zA-Z] 8 %% 9 {letter}+ { words++; chars+= yyleng; } 10 \n { chars++; lines++; } 11 . { chars++; } 12 %% 13 int main(int argc, char** argv) { 14 if (argc > 1) { 15 if (!(yyin = fopen(argv[1], "r"))) { 16 perror(argv[1]); 17 return 1; 18 } 19 } 20 yylex(); 21 printf("