版权所有南京大学计算机科学与技术系许畅等2022春季版 2.2 实验指导 词法分析和语法分析这两块，可以说是在整个编译器当中被自动化得最好的部分。也就是 说，即使没有任何的理论基础，在掌握了工具的用法之后，也可以在短时间内做出功能很全很 棒的词法分析程序和语法分析程序。当然这并不意味着，词法分析和语法分析部分的理论基础 并不重要。恰恰相反，这一部分被认为是计算机理论在工程实践中最成功的应用之一，对它的 介绍也是编译理论课中的重点。但本节指导内容的重点不在于理论而在于工具的使用。 本节指导内容将分别介绍词法分析工具GNU Flex和语法分析工具GNU Bison。如前所 述，完成实验一并不需要太多的理论基础，只要看完并掌握了本节的大部分内容即可完成实验 一。 2.2.1词法分析概述 词法分析程序的主要任务是将输入文件中的字符流组织成为词法单元流，在某些字符不符 合程序设计语言词法规范时它也要有能力报告相应的错误。词法分析程序是编译器所有模块中 唯一读入并处理输入文件中每一个字符的模块，它使得后面的语法分析阶段能在更高抽象层次 上运作，而不必纠结于字符串处理这样的细节问题。 高级程序设计语言大多采用英文作为输入方式，而英文有个非常好的性质，就是它比较容 易断词：相邻的英文字母一定属于同一个词，而字母与字母之间插入任何非字母的字符（如空 格、运算符等)就可以将一个词断成两个词。判断一个词是否符合语言本身的词法规范也相对 简单，一个直接的办法是：我们可以事先开一张搜索表，将所有符合词法规范的字符串都存放 在表中，每次我们从输入文件中断出一个词之后，通过查找这张表就可以判断该词究竟合法还 是不合法。 正因为词法分析任务的难度不高，在实用的编译器中它常常是手工写成，而并非使用工具 生成。例如，我们下面要介绍的这个工具GNU Flex原先就是为了帮助GCC进行词法分析而被 开发出来的，但在4.0版本之后，GCC的词法分析器已经一律改为手写了。不过，实验一要求 使用工具来做，而词法分析程序生成工具所基于的理论基础，是计算理论中最入门的内容：正 则表达式(Regular Expression)和有限状态自s动机(Finite State Automata)。 一个正则表达式由特定字符串构成，或者由其它正则表达式通过以下三种运算得到： I)并运算(Union):两个正则表达式r和s的并记作rIs,意为r或s都可以被接受。 2)连接运算(Concatenation)：两个正则表达式r和s的连接记作rs,意为r之后紧跟s才 20
版权所有 南京大学计算机科学与技术系 许畅等 2022春季版 20 2.2 实验指导 词法分析和语法分析这两块，可以说是在整个编译器当中被自动化得最好的部分。也就是 说，即使没有任何的理论基础，在掌握了工具的用法之后，也可以在短时间内做出功能很全很 棒的词法分析程序和语法分析程序。当然这并不意味着，词法分析和语法分析部分的理论基础 并不重要。恰恰相反，这一部分被认为是计算机理论在工程实践中最成功的应用之一，对它的 介绍也是编译理论课中的重点。但本节指导内容的重点不在于理论而在于工具的使用。 本节指导内容将分别介绍词法分析工具GNU Flex和语法分析工具GNU Bison。如前所 述，完成实验一并不需要太多的理论基础，只要看完并掌握了本节的大部分内容即可完成实验 一。 2.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才
版权所有南京大学计算机科学与技术系许畅等2022春季版 可以被接受。 3)Kleene闭包(Kleene Closure):一个正则表达式r的Kleene闭包记作r*,它表示：eI r I rr I rrr I.... 有关正则表达式的内容在课本的理论部分讨论过。正则表达式之所以被人们所广泛应用， 一方面是因为它在表达能力足够强（基本上可以表示所有的词法规则）的同时还易于书写和理 解；另一方面也是因为判断一个字符串是否被一个特定的正则表达式接受可以做到非常高效 (在线性时间内即可完成)。比如，我们可以将一个正则表达式转化为一个NFA（即不确定 的有限状态自动机)，然后将这个NFA转化为一个DFA(即确定的有限状态自动机)，再将 转化好的DFA进行化简，之后我们就可以通过模拟这个DFA的运行来对输入串进行识别了。 具体的NFA和DFA的含义，以及如何进行正则表达式、NFA及DFA之间的转化等，请参考课 本的理论部分。这里我们仅需要知道，前面所述的所有转化和识别工作，都可以由工具自动完 成。而我们所需要做的，仅仅是为工具提供作为词法规范的正则表达式。 2.2.2GNUF1ex介绍 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基本相同。首先，我们需 要自行完成包括词法规则等在内的Flx代码。至于如何编写这部分代码我们在后面会提到，现 在先假设这部分写好的代码名为lexical.l。随后，我们使用Flex对该代码进行编译： flex lexical.1 编译好的结果会保存在当前目录下的lex.yy.c文件中。打开这个文件你就会发现，该文件 本质上就是一份C语言的源代码。这份源代码里目前对我们有用的函数只有一个，叫做 yylex(0,该函数的作用就是读取输入文件中的一个词法单元。我们可以再为它编写一个main 21
版权所有 南京大学计算机科学与技术系 许畅等 2022春季版 21 可以被接受。 3) Kleene闭包（Kleene Closure）：一个正则表达式r的Kleene闭包记作r*，它表示： | r | rr | rrr | …。 有关正则表达式的内容在课本的理论部分讨论过。正则表达式之所以被人们所广泛应用， 一方面是因为它在表达能力足够强（基本上可以表示所有的词法规则）的同时还易于书写和理 解；另一方面也是因为判断一个字符串是否被一个特定的正则表达式接受可以做到非常高效 （在线性时间内即可完成）。比如，我们可以将一个正则表达式转化为一个NFA（即不确定 的有限状态自动机），然后将这个NFA转化为一个DFA（即确定的有限状态自动机），再将 转化好的DFA进行化简，之后我们就可以通过模拟这个DFA的运行来对输入串进行识别了。 具体的NFA和DFA的含义，以及如何进行正则表达式、NFA及DFA之间的转化等，请参考课 本的理论部分。这里我们仅需要知道，前面所述的所有转化和识别工作，都可以由工具自动完 成。而我们所需要做的，仅仅是为工具提供作为词法规范的正则表达式。 2.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