编译原理及实践(二).pdf

下载 第2章 词 法 分 析 本章要点 • 扫描处理 • 从正则表达式到D FA • 正则表达式 • TINY扫描程序的实现 • 有穷自动机 • 利用L e x 自动生成扫描程序 编译器的扫描或词法分析（ lexical analysis ）阶段可将源程序读作字符文件并将其分为若 干个记号。记号与自然语言中的单词类似：每一个记号都是表示源程序中信息单元的字符序列。 典型的有：关键字（k e y w o r d ），例如i f和w h i l e，它们是字母的固定串；标识符（ i d e n t i f i e r ） 是由用户定义的串，它们通常由字母和数字组成并由一个字母开头；特殊符号（special symbol ） 如算术符号+和*、一些多字符符号，如 = 和 。在各种情况中，记号都表示由扫描程序从剩 余的输入字符的开头识别或匹配的某种字符格式。 由于扫描程序的任务是格式匹配的一种特殊情况，所以需要研究在扫描过程中的格式说明 和识别方法，其中最主要的是正则表达式（regular expression ）和有穷自动机（finite automata ）。 但是，扫描程序也是处理源代码输入的编译器部分，而且由于这个输入经常需要非常多的额 外时间，扫描程序的操作也就必须尽可能地高效了。因此还需十分注意扫描程序结构的实际 细节。 扫描程序问题的研究可分为以下几个部分：首先，给出扫描程序操作的一个概貌以及所涉 及到的结构和概念。其次是学习正则表达式，它是用于表示构成程序设计语言的词法结构的串 格式的标准表示法。接着是有穷状态机器或称有穷自动机，它是对由正则表达式给出的串格式 的识别算法。此外还研究用正则表达式构造有穷自动机的过程。之后再讨论当有穷自动机表示 识别过程时，如何实际编写执行该过程的程序。另外还有 T I N Y语言扫描程序的一个完整的实 现过程。最后再看到自动产生扫描器生成器的过程和方法，并使用 L e x再次实现T I N Y 的扫描程 序，它是适用于U n i x和其他系统的标准扫描生成器。 2.1 扫描处理 扫描程序的任务是从源代码中读取字符并形成由编译器的以后部分（通常是分析程序）处 理的逻辑单元。由扫描程序生成的逻辑单元称作记号（ t o k e n ），将字符组合成记号与在一个英 语句子中将字母构成单词并确定单词的含义很相像。此时它的任务很像拼写。 记号通常定义为枚举类型的逻辑项。例如，记号在 C 中可被定义为 ： L在一种没有列举类型的语言中，则只能将记号直接定义为符号数值。因此在老版本的 C 中有时可看到： #define IF 256 #define THEN 257 #define ELSE 258 . . . (这些数之所以是从2 5 6开始是为了避免与A S C I I 的数值混淆。) 2 2 编译原理及实践 下载 typedef enum { IF, THEN, ELSE，PLUS, MINUS, NUM, ID, ...} T o k e n T y p e ; 记号有若干种类型，这其中包括了保留字（ reserved word ），如I F和T H E N，它们表示字符 串“i f ”和“t h e n ”；第2 类是特殊符号（ special symbol ），如算术符号加（ P L U S ）和减 （M I N U S ），它们表示字符“+ ”和“- ”。第3类是表示多字符串的记号，如 N U M和I D，它们分 别表示数字和标识符。 作为逻辑项的记号必须与它们所表示的字符串完全区分开来。例如：保留字记号 I F须与 它表示的两个字符“i f ”的串相区别。为了使这个区别更明显，由记号表示的字符串有时称作 它的串值（string va