编译原理-第三章 词法分析[xiwang].ppt

1、1,编 译 原 理Compiler Principles,徐小龙 南京邮电大学.计算机学院,第三章 词 法 分 析,教材：编译技术原理及其实现方法王汝传 编著,2,经过第一章的学习，我们已经初步了解了编译过程及各阶段的功能，从本章开始我门将详细叙述各阶段是如何工作的。首先来看一下词法分析，这是编译的第一步，也是编译的重点，下面我们将将详细介绍词法分析的方法。,源程序,词法 分析 程序,语法 分析 程序,语义 分析 程序,中间 代码 生成,代码 优化 程序,目标 代码 生成,目标程序,信 息 表 管 理 程 序,错 误 检 查 和 处 理 程 序,3,第三章 词 法 分 析,3.1 引言 一、词

2、法分析基本思想 二、词法分析任务 三、词法分析方式 四、词法分析方法 3.2 单词的内部编码 一、单词 二、内部编码 3.3 正规文法和状态转换图 一、正规文法 二、状态转换图 三、正规文法与状态转换图 3.4 词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理 三、超前搜索 四、由词法语法规则画状态转换图 五、词法分析程序的设计与实现,3.5 正规文法和有穷自动机 一、用正规文法描述单词 二、由正规文法构造状态转换图 三、有穷自动机FA 四、有穷自动机和正规文法的关系 五、DFA与NFA的关系 3.6 正规表达式和有穷自动机 一、正规表达式和正规集的定义 二、正规表达式的性质 三、

3、正规文法、正规表达式与有穷自动机 四、由正规表达式构造确定有穷自动机 五、确定有穷自动机的化简 3.7 词法分析程序的自动生成 一、问题的提出 二、语言LEX一般描述 三、LEX编译程序的实现 四、LEX目标程序,4,第三章 词 法 分 析,3.1 引言 一、词法分析基本思想 二、词法分析任务 三、词法分析方式 四、词法分析方法 3.2 单词的内部编码 一、单词 二、内部编码 3.3 正规文法和状态转换图 一、正规文法 二、状态转换图 三、正规文法与状态转换图 3.4 词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理 三、超前搜索 四、由词法语法规则画状态转换图 五、词法分析程序的

4、设计与实现,3.5 正规文法和有穷自动机 一、用正规文法描述单词 二、由正规文法构造状态转换图 三、有穷自动机FA 四、有穷自动机和正规文法的关系 五、DFA与NFA的关系 3.6 正规表达式和有穷自动机 一、正规表达式和正规集的定义 二、正规表达式的性质 三、正规文法、正规表达式与有穷自动机 四、由正规表达式构造确定有穷自动机 五、确定有穷自动机的化简 3.7 词法分析程序的自动生成 一、问题的提出 二、语言LEX一般描述 三、LEX编译程序的实现 四、LEX目标程序,5,第三章 词 法 分 析,3.1 引言 一、词法分析基本思想 二、词法分析任务 1. 识别单词 2. 消除无用字符 3.

5、变成内部编码 4. 建立各种表格 5. 分配存贮单元（静态变量） 6. 进行词法检查 三、词法分析方式 1. 将词法分析和语法分析程序分开 2. 将词法分析程序编写成一个独立子程序 四、词法分析方法 1. 直接分析方法 2. 状态矩阵法,6,第三章 词 法 分 析,3.1 引言 一、词法分析基本思想 二、词法分析任务 1. 识别单词 2. 消除无用字符 3. 变成内部编码 4. 建立各种表格 5. 分配存贮单元（静态变量） 6. 进行词法检查 三、词法分析方式 1. 将词法分析和语法分析程序分开 2. 将词法分析程序编写成一个独立子程序 四、词法分析方法 1. 直接分析方法 2. 状态矩阵法,

6、7,3.1 引言 一、词法分析基本思想 扫描源程序 识别单词 变成中间程序L1（内部编码）。 即从左到右逐个字符地扫描源程序，产生一个个独立的单词， 并将其改变成等价的中间程序，记为：L1。实际上是机器的 内部编码,符号序列,单词序列,词 法 分 析,8,第三章 词 法 分 析,3.1 引言 一、词法分析基本思想 二、词法分析任务 1. 识别单词 2. 消除无用字符 3. 变成内部编码 4. 建立各种表格 5. 分配存贮单元（静态变量） 6. 进行词法检查 三、词法分析方式 1. 将词法分析和语法分析程序分开 2. 将词法分析程序编写成一个独立子程序 四、词法分析方法 1. 直接分析方法 2.

7、 状态矩阵法,9,3.1 引言 二、词法分析任务 1. 识别单词 扫描源程序的一个个字符，按照语言的词法规则，识别出各类有独立意义的单词。 如：begin ， procedure ， + ， 5.43 ， abc等。,10,第三章 词 法 分 析,3.1 引言 一、词法分析基本思想 二、词法分析任务 1. 识别单词 2. 消除无用字符 3. 变成内部编码 4. 建立各种表格 5. 分配存贮单元（静态变量） 6. 进行词法检查 三、词法分析方式 1. 将词法分析和语法分析程序分开 2. 将词法分析程序编写成一个独立子程序 四、词法分析方法 1. 直接分析方法 2. 状态矩阵法,11,3.1 引言

8、 二、词法分析任务 2. 消除无用字符 对源程序文本进行处理，消除源程序文本中的注释、空格、换行符以及其他一切对语法分析和代码生成均无关的信息。,12,第三章 词 法 分 析,3.1 引言 一、词法分析基本思想 二、词法分析任务 1. 识别单词 2. 消除无用字符 3. 变成内部编码 4. 建立各种表格 5. 分配存贮单元（静态变量） 6. 进行词法检查 三、词法分析方式 1. 将词法分析和语法分析程序分开 2. 将词法分析程序编写成一个独立子程序 四、词法分析方法 1. 直接分析方法 2. 状态矩阵法,13,3.1 引言 二、词法分析任务 3. 变成内部编码 将长度不一、种类不同的单词变成长

9、度统一、格式规整、分类清晰的一种内部机器码表示。,14,第三章 词 法 分 析,3.1 引言 一、词法分析基本思想 二、词法分析任务 1. 识别单词 2. 消除无用字符 3. 变成内部编码 4. 建立各种表格 5. 分配存贮单元（静态变量） 6. 进行词法检查 三、词法分析方式 1. 将词法分析和语法分析程序分开 2. 将词法分析程序编写成一个独立子程序 四、词法分析方法 1. 直接分析方法 2. 状态矩阵法,15,3.1 引言 二、词法分析任务 4. 建立各种表格 在词法分析时，可以根据单词特点建立不同表格，如： 名字表（标识符表）：源程序中的标识符集中在表中 常数表 数组向量表、过程表等

10、界限表：包含了保留字、运算符等,16,第三章 词 法 分 析,3.1 引言 一、词法分析基本思想 二、词法分析任务 1. 识别单词 2. 消除无用字符 3. 变成内部编码 4. 建立各种表格 5. 分配存贮单元（静态变量） 6. 进行词法检查 三、词法分析方式 1. 将词法分析和语法分析程序分开 2. 将词法分析程序编写成一个独立子程序 四、词法分析方法 1. 直接分析方法 2. 状态矩阵法,17,3.1 引言 二、词法分析任务 5. 分配存贮单元（静态变量） 对简单变量、常量及数组进行静态存贮分配 静态存贮分配：在编译时就可以决定应分配内存的大小。 动态存贮分配：到运行时才进行的存贮分配。

11、如：变界数组、动态变量。 静态存贮分配可以在词法分析阶段进行，也可以在语法分析阶段进行，随具体编译系统而定。,18,第三章 词 法 分 析,3.1 引言 一、词法分析基本思想 二、词法分析任务 1. 识别单词 2. 消除无用字符 3. 变成内部编码 4. 建立各种表格 5. 分配存贮单元（静态变量） 6. 进行词法检查 三、词法分析方式 1. 将词法分析和语法分析程序分开 2. 将词法分析程序编写成一个独立子程序 四、词法分析方法 1. 直接分析方法 2. 状态矩阵法,19,3.1 引言 二、词法分析任务 6. 进行词法检查 将一些单词错误检查出来， 如保留字PROGRAM、 VAR； 又例如

12、变量是否有说明或是否重复说明等。,20,第三章 词 法 分 析,3.1 引言 一、词法分析基本思想 二、词法分析任务 1. 识别单词 2. 消除无用字符 3. 变成内部编码 4. 建立各种表格 5. 分配存贮单元（静态变量） 6. 进行词法检查 三、词法分析方式 1. 将词法分析和语法分析程序分开 2. 将词法分析程序编写成一个独立子程序 四、词法分析方法 1. 直接分析方法 2. 状态矩阵法,21,第三章 词 法 分 析,3.1 引言 一、词法分析基本思想 二、词法分析任务 1. 识别单词 2. 消除无用字符 3. 变成内部编码 4. 建立各种表格 5. 分配存贮单元（静态变量） 6. 进行

13、词法检查 三、词法分析方式 1. 将词法分析和语法分析程序分开 2. 将词法分析程序编写成一个独立子程序 四、词法分析方法 1. 直接分析方法 2. 状态矩阵法,22,3.1 引言 三、词法分析方式 1. 将词法分析和语法分析程序分开 在多遍扫描的编译程序中，词法分析可以单独作为一遍扫描来完成，此时可将词法分析程序的输出放在一个中间文件上，语法分析程序可以从该文件上取得它的输入。 词法分析从语法分析独立出来的原因： （1）便于集中进行语法分析 （2）便于建立有效词法分析技术 （3）将给语法分析提供更多更详细信息,字符串表示 的源程序,词法分析程序,符号串表示的源程序,字符,单词,23,第三章

14、词 法 分 析,3.1 引言 一、词法分析基本思想 二、词法分析任务 1. 识别单词 2. 消除无用字符 3. 变成内部编码 4. 建立各种表格 5. 分配存贮单元（静态变量） 6. 进行词法检查 三、词法分析方式 1. 将词法分析和语法分析程序分开 2. 将词法分析程序编写成一个独立子程序 四、词法分析方法 1. 直接分析方法 2. 状态矩阵法,24,3.1 引言 三、词法分析方式 2. 将词法分析程序编写成一个独立子程序 在一遍扫描的编译程序中，往往将词法分析编成语法分析的一个子程序，供语法分析时随时调用，每调用一次，则从源程序字符串中读出一个具有独立意义的单词。,优点：不需要在内存中构造

15、和保留中间文件所以节省内存容量,字符串表示 的源程序,词法分析程序,语法分析程序,字符,取一符号,符 号,25,第三章 词 法 分 析,3.1 引言 一、词法分析基本思想 二、词法分析任务 1.识别单词 2. 消除无用字符 3. 变成内部编码 4. 建立各种表格 5. 分配存贮单元（静态变量） 6. 进行词法检查 三、词法分析方式 1. 将词法分析和语法分析程序分开 2. 将词法分析程序编写成一个独立子程序 四、词法分析方法 1. 直接分析方法 2. 状态矩阵法,26,第三章 词 法 分 析,3.1 引言 一、词法分析基本思想 二、词法分析任务 1.识别单词 2. 消除无用字符 3. 变成内部

16、编码 4. 建立各种表格 5. 分配存贮单元（静态变量） 6. 进行词法检查 三、词法分析方式 1. 将词法分析和语法分析程序分开 2. 将词法分析程序编写成一个独立子程序 四、词法分析方法 1. 直接分析方法 2. 状态矩阵法,27,3.1 引言 三、词法分析方法 1. 直接分析方法 根据词法分析任务编成多个不同独立子程序（如：读符号子 程序、取单词子程序、拼标识符子程序、处理无符号数子程 序），对源程序进行分析加工处理。,28,第三章 词 法 分 析,3.1 引言 一、词法分析基本思想 二、词法分析任务 1.识别单词 2. 消除无用字符 3. 变成内部编码 4. 建立各种表格 5. 分配存

17、贮单元（静态变量） 6. 进行词法检查 三、词法分析方式 1. 将词法分析和语法分析程序分开 2. 将词法分析程序编写成一个独立子程序 四、词法分析方法 1. 直接分析方法 2. 状态矩阵法,29,3.1 引言 三、词法分析方法 2. 状态矩阵法 根据一张二维状态矩阵表对源程序进行控制分析。这部分内容将在语法分析时介绍。,30,第三章 词 法 分 析,3.1 引言 一、词法分析基本思想 二、词法分析任务 三、词法分析方式 四、词法分析方法 3.2 单词的内部编码 一、单词 二、内部编码 3.3 正规文法和状态转换图 一、正规文法 二、状态转换图 三、正规文法与状态转换图 3.4 词法分析程序设

18、计与实现 一、源程序的输入 二、缓冲区及预处理 三、超前搜索 四、由词法语法规则画状态转换图 五、词法分析程序的设计与实现,3.5 正规文法和有穷自动机 一、用正规文法描述单词 二、由正规文法构造状态转换图 三、有穷自动机FA 四、有穷自动机和正规文法的关系 五、DFA与NFA的关系 3.6 正规表达式和有穷自动机 一、正规表达式和正规集的定义 二、正规表达式的性质 三、正规文法、正规表达式与有穷自动机 四、由正规表达式构造确定有穷自动机 五、确定有穷自动机的化简 3.7 词法分析程序的自动生成 一、问题的提出 二、语言LEX一般描述 三、LEX编译程序的实现 四、LEX目标程序,31,第三章

19、 词 法 分 析,3.1 引言 一、词法分析基本思想 二、词法分析任务 三、词法分析方式 四、词法分析方法 3.2 单词的内部编码 一、单词 二、内部编码 3.3 正规文法和状态转换图 一、正规文法 二、状态转换图 三、正规文法与状态转换图 3.4 词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理 三、超前搜索 四、由词法语法规则画状态转换图 五、词法分析程序的设计与实现,3.5 正规文法和有穷自动机 一、用正规文法描述单词 二、由正规文法构造状态转换图 三、有穷自动机FA 四、有穷自动机和正规文法的关系 五、DFA与NFA的关系 3.6 正规表达式和有穷自动机 一、正规表达式和正

20、规集的定义 二、正规表达式的性质 三、正规文法、正规表达式与有穷自动机 四、由正规表达式构造确定有穷自动机 五、确定有穷自动机的化简 3.7 词法分析程序的自动生成 一、问题的提出 二、语言LEX一般描述 三、LEX编译程序的实现 四、LEX目标程序,32,第三章 词 法 分 析,3.2 单词的内部编码 一、单词 二、内部编码 1 . 单词类别 2. 单词自身值,33,第三章 词 法 分 析,3.2 单词的内部编码 一、单词 二、内部编码 1 . 单词类别 2. 单词自身值,34,3.2 单词的内部编码 一、单词 这部分内容在第一章中已介绍，在此简单回顾一下。 所谓单词，是指那些具有独立含义的

21、最小语法单位 。单词可分为以下 几种类型： （）保留字：PROGRAM, VAR, IF, FOR, AND等 。 （）标识符：是用户选来表示常量、变量、类型、过程等名字。 （ 3 ）常数：分为整型、实型、布尔型、字符型等，如2，3.1416等。 （）运算符：分为算术运算符（，*，等），逻辑运算符 （，），关系运算符（=）等。 （）界限符：如逗号、分号、括号等。,35,第三章 词 法 分 析,3.2 单词的内部编码 一、单词 二、内部编码 1 . 单词类别 2. 单词自身值,36,对于单词类别可以用整数表示，用来指示单词的种类 。例如上面的例子，我们可以用个不同的整数作为它们单词类别的编码 。

22、单词的内部编码是词法分析的输出形式,3.2 单词的内部编码 二、内部编码 1 . 单词类别,单词类型,单词自身值,37,3.2 单词的内部编码 二、内部编码 2. 单词自身值 可以是单词某种形式内部编码，也可以是该单词在某些表格中地址码。如第一章所讲，保留字、运算符和界限符用内部固定编码值作为单词值；标识符取其在标识符表中的地址码 ；常量取其在常数表中的地址码。 例如：有下列单词： 单词 内部编码 单词 内部编码 IF 2 + 25 THEN 3 * 26 ELSE 4 34,38,单词 内部编码 （ 35 ） 36 ：= 37 单词 地址码 a1 200 b1 201 c1 202 d1 2

23、03 b 204 0 100 3 101,语句：if a10 then b1:=(c1+3) else b:=0 经词法分析变成如下的内部编码形式： If a1 0 1 2 2 200 4 34 3 100 then b1 := ( 1 3 2 201 5 37 5 35 C1 + 3 ) 2 202 4 24 3 101 5 36 else b := 0 1 4 2 204 5 37 3 102,39,第三章 词 法 分 析,3.1 引言 一、词法分析基本思想 二、词法分析任务 三、词法分析方式 四、词法分析方法 3.2 单词的内部编码 一、单词 二、内部编码 3.3 正规文法和状态转换图

24、一、正规文法 二、状态转换图 三、正规文法与状态转换图 3.4 词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理 三、超前搜索 四、由词法语法规则画状态转换图 五、词法分析程序的设计与实现,3.5 正规文法和有穷自动机 一、用正规文法描述单词 二、由正规文法构造状态转换图 三、有穷自动机FA 四、有穷自动机和正规文法的关系 五、DFA与NFA的关系 3.6 正规表达式和有穷自动机 一、正规表达式和正规集的定义 二、正规表达式的性质 三、正规文法、正规表达式与有穷自动机 四、由正规表达式构造确定有穷自动机 五、确定有穷自动机的化简 3.7 词法分析程序的自动生成 一、问题的提出 二、

25、语言LEX一般描述 三、LEX编译程序的实现 四、LEX目标程序,40,第三章 词 法 分 析,3.1 引言 一、词法分析基本思想 二、词法分析任务 三、词法分析方式 四、词法分析方法 3.2 单词的内部编码 一、单词 二、内部编码 3.3 正规文法和状态转换图 一、正规文法 二、状态转换图 三、正规文法与状态转换图 3.4 词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理 三、超前搜索 四、由词法语法规则画状态转换图 五、词法分析程序的设计与实现,3.5 正规文法和有穷自动机 一、用正规文法描述单词 二、由正规文法构造状态转换图 三、有穷自动机FA 四、有穷自动机和正规文法的关系

26、 五、DFA与NFA的关系 3.6 正规表达式和有穷自动机 一、正规表达式和正规集的定义 二、正规表达式的性质 三、正规文法、正规表达式与有穷自动机 四、由正规表达式构造确定有穷自动机 五、确定有穷自动机的化简 3.7 词法分析程序的自动生成 一、问题的提出 二、语言LEX一般描述 三、LEX编译程序的实现 四、LEX目标程序,41,第三章 词 法 分 析,3.3 正规文法和状态转换图 一、正规文法 二、状态转换图 1. 定义 2. 功能 三、正规文法与状态转换图 1. 由正规文法构造状态转换图 2. 由正规文法状态转换图识别句子（单词）,42,第三章 词 法 分 析,3.3 正规文法和状态转

27、换图 一、正规文法 二、状态转换图 1. 定义 2. 功能 三、正规文法与状态转换图 1. 由正规文法构造状态转换图 2. 由正规文法状态转换图识别句子（单词）,43,3.3 正规文法和状态转换图 一、正规文法 在介绍词法分析程序的设计之前，先来看一下正规文法和状态转换图 它们是词法分析的理论基础。 一、正规文法 正规文法就是乔姆斯基(Chomsky)文法分类中的3型文法，如果P中 规则形式为 ： A=a B 或 A=a 其中A,BVN，aVT，则称文法G为右线性文法。如P中规则形式为: A=B a 或 A=a，则称文法G为左线性文法 。 3型文法与词法分析密切相关 如： =字母|字母|数字

28、左线性文法 又如：=+|-|*|/ 正规文法,44,第三章 词 法 分 析,3.3 正规文法和状态转换图 一、正规文法 二、状态转换图 1. 定义 2. 功能 三、正规文法与状态转换图 1. 由正规文法构造状态转换图 2. 由正规文法状态转换图识别句子（单词）,45,第三章 词 法 分 析,3.3 正规文法和状态转换图 一、正规文法 二、状态转换图 1. 定义 2. 功能 三、正规文法与状态转换图 1. 由正规文法构造状态转换图 2. 由正规文法状态转换图识别句子（单词）,46,3.3 正规文法和状态转换图 二、状态转换图 1. 定义 转换图实际上是一个有限方向图，图中结点代表状态，用圆圈表示

29、。 状态之间用箭弧连接，箭弧上标记（字符如x，y）代表射出结（即箭 弧始结）状态下可能出现的输入字符 . 如：,该状态转换图表示在状态1下读入x转到状态2，若在状态1下读入字符y，则转到状态3。,1,X,2,3,Y,47,3.3 正规文法和状态转换图 二、状态转换图 2. 功能 一个状态转换图可以用于识别（或接受）一 定的字符串 。例如：识别标识符的转换图如 下图所示,0,字母,字母或数字,其他,*,1,48,其中为初态，为终态（双圆圈表示）。 这个转换图识别（接受）标识符过程是： （1）从初态开始，若在状态之下输入字符是一个字母则转入状态。 （2）在状态之下，若下一个输入字符为字母或数字，则

30、读进它，并重新 进入状态1。 （3） 重复（2），直到状态发现输入字符不再是字母或数字时就进入 状态。状是终态，它意味着到此已识别出一个标识符，识别 过程宣告终止。 终态结上打个星号，表示多读进一个不属于标识符的字符， 应把它退还给输入串。 （4） 如果在开始状态0下，输入字符不是字母，则意味着识别不出标识符 按同样的方法，同学们可以考虑一下整数的识别状态转换图及识别过程,49,第三章 词 法 分 析,3.3 正规文法和状态转换图 一、正规文法 二、状态转换图 1. 定义 2. 功能 三、正规文法与状态转换图 1. 由正规文法构造状态转换图 2. 由正规文法状态转换图识别句子（单词）,50,第

31、三章 词 法 分 析,3.3 正规文法和状态转换图 一、正规文法 二、状态转换图 1. 定义 2. 功能 三、正规文法与状态转换图 1. 由正规文法构造状态转换图 2. 由正规文法状态转换图识别句子（单词）,51,对于一个左线性文法GE ： U =a 或 U=Ba U,BVN ，aVT （1）设一个开始状态S， SVN （2）对于每一条规则U =a ，从状态S向状态U画一条箭弧，标记为a a S U (3)对于每一条规则U =Ba ，从状态B向状态U画一条箭弧，标记为a a B U (4) 识别符E为状态转换图的终态 由以上规则，我们就可以构造一个左线性文法状态转换图。,3.3 正规文法和状态

32、转换图 三、正规文法与状态转换图 1.由正规文法(左线性文法)构造状态转换图,52,例如：设有左线性文法（，）， 其中： ，U， ， U U 由该文法所确定的语言为 ， 根据上述构造状态转换图的规则，该文法状态转换图如下图所示。,53,3.3 正规文法和状态转换图 三、正规文法与状态转换图 2. 由正规文法状态转换图识别句子（单词） 如：符号串0110是上述文法的句子，因为： 从开始状态S出发，读入0转入V，再读入1转入Z，再读入1转入U，最后读 入0转入Z，且Z是终态。 又如：符号串101001也是该文法的一个句子。实 际上这是一个自底向上分析方法进行分析。,由此可以看出正规文法的状态转换图

33、有助于识别正规文法产生的句子。,步骤 当前状态 x的余留部分 1 S 101001 2 U 01001 3 Z 1001 4 U 001 5 Z 01 6 V 1 7 Z,识别字符串x=101001,句子101001语法树,Z,V,1,Z,U,Z,U,0,0,1,0,1,54,第三章 词 法 分 析,3.1 引言 一、词法分析基本思想 二、词法分析任务 三、词法分析方式 四、词法分析方法 3.2 单词的内部编码 一、单词 二、内部编码 3.3 正规文法和状态转换图 一、正规文法 二、状态转换图 三、正规文法与状态转换图 3.4 词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理 三、

34、超前搜索 四、由词法语法规则画状态转换图 五、词法分析程序的设计与实现,3.5 正规文法和有穷自动机 一、用正规文法描述单词 二、由正规文法构造状态转换图 三、有穷自动机FA 四、有穷自动机和正规文法的关系 五、DFA与NFA的关系 3.6 正规表达式和有穷自动机 一、正规表达式和正规集的定义 二、正规表达式的性质 三、正规文法、正规表达式与有穷自动机 四、由正规表达式构造确定有穷自动机 五、确定有穷自动机的化简 3.7 词法分析程序的自动生成 一、问题的提出 二、语言LEX一般描述 三、LEX编译程序的实现 四、LEX目标程序,55,第三章 词 法 分 析,3.1 引言 一、词法分析基本思想

35、 二、词法分析任务 三、词法分析方式 四、词法分析方法 3.2 单词的内部编码 一、单词 二、内部编码 3.3 正规文法和状态转换图 一、正规文法 二、状态转换图 三、正规文法与状态转换图 3.4 词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理 三、超前搜索 四、由词法语法规则画状态转换图 五、词法分析程序的设计与实现,3.5 正规文法和有穷自动机 一、用正规文法描述单词 二、由正规文法构造状态转换图 三、有穷自动机FA 四、有穷自动机和正规文法的关系 五、DFA与NFA的关系 3.6 正规表达式和有穷自动机 一、正规表达式和正规集的定义 二、正规表达式的性质 三、正规文法、正规

36、表达式与有穷自动机 四、由正规表达式构造确定有穷自动机 五、确定有穷自动机的化简 3.7 词法分析程序的自动生成 一、问题的提出 二、语言LEX一般描述 三、LEX编译程序的实现 四、LEX目标程序,56,第三章 词 法 分 析,3.4 词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理 1、扫描缓冲区 2、预处理 三、超前搜索 1、问题的提出 2、工作原理 四、由词法语法规则画状态转换图 1、语言子集单词符号 2、单词的正规文法规则 3、构造状态转换图 五、词法分析程序的设计与实现,57,第三章 词 法 分 析,3.4 词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理

37、1、扫描缓冲区 2、预处理 三、超前搜索 1、问题的提出 2、工作原理 四、由词法语法规则画状态转换图 1、语言子集单词符号 2、单词的正规文法规则 3、构造状态转换图 五、词法分析程序的设计与实现,58,3.4 词法分析程序设计与实现 一、源程序的输入 1. 内存比较大的情况下,直接输入到内存的一个源程序区 (1)一个字符占一个字节 (2)词法分析程序从源程序区读入字符 2. 内存不足的情况下，将源程序以文件的形式存贮在外部 介质上，如磁盘、磁带等 。可以先在内存中开辟一个 大小适宜的缓冲区，这个缓冲区称为 输入缓冲区。词法 分析程序工作时，先从外部介质上将输入 符号串分批读 入缓冲区，单词

38、符号的识别可在这个缓冲区中进行. 具 体处理时还要开辟一个扫描缓冲区。,59,第三章 词 法 分 析,3.4 词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理 1、扫描缓冲区 2、预处理 三、超前搜索 1、问题的提出 2、工作原理 四、由词法语法规则画状态转换图 1、语言子集单词符号 2、单词的正规文法规则 3、构造状态转换图 五、词法分析程序的设计与实现,60,第三章 词 法 分 析,3.4 词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理 1、扫描缓冲区 2、预处理 三、超前搜索 1、问题的提出 2、工作原理 四、由词法语法规则画状态转换图 1、语言子集单词符号 2

39、、单词的正规文法规则 3、构造状态转换图 五、词法分析程序的设计与实现,61,3.4 词法分析程序设计与实现 二、扫描缓冲区及预处理 1. 扫描缓冲区 （1）定义：扫描缓冲区就是在内存中开辟一部分单元，供识别 单词用。 注意：扫描缓冲区和缓冲区是不同的，缓冲区是从 外存上读入部分字符，而扫描缓冲区仅是为识别单词用。 （2）工作原理 在扫描缓冲区中一般设两个指示器，一个指向当前正在识别 单词开始位置，另一个用于向前搜索寻找单词的终点。不论 扫描缓冲区定为多大都不能保证单词符号不会被它的边界所打断， 因此，扫描缓冲区最好使用如下所示的一分为二的区域（每半区 可容120个字符 ）： 扫描缓冲区1 扫

40、描缓冲区2 起始指示器 搜索指示器,62,1) 开始时扫描缓冲区皆为空 。 2) 调用预处理子程序，将120个字符填满扫描缓冲区 。并将两个指示器指向扫描缓冲区的第个字符 。 3) 将搜索指示器向后移动,当识别出一个单词之后，搜索指示器已指向 下一个单词的第一个字符,然后再将起始指示器移到搜索指示器指向 字符,接着搜索指示器又开始扫描第二个单词。 当搜索指示器越界时，说明缓冲区中的字符不足一个单词，这时 再调用预处理子程序，再将120个字符填满扫描缓冲区，再将 搜索指示器扫描缓冲区第个字符。这样，两个扫描缓冲区交替 工作 。 4) 一般描缓冲区长度可以存放最长一个单词，即可正常工作 ；否则，

41、就不能保证单词符号不会被缓冲区边界所打断。 ,63,3.4 词法分析程序设计与实现 二、扫描缓冲区及预处理 2、预处理 预处理目的是将一些无用的空白符、跳格符、回车换行符等编辑性字符剔除掉 。 其工作原理是每次从缓冲区读入一个字符后，便进行判断，如属于无用字符则将其删除不用，再读下一个字符，直至读出一个有用字符为止。 ,64,第三章 词 法 分 析,3.4 词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理 1、扫描缓冲区 2、预处理 三、超前搜索 1、问题的提出 2、工作原理 四、由词法语法规则画状态转换图 1、语言子集单词符号 2、单词的正规文法规则 3、构造状态转换图 五、词法

42、分析程序的设计与实现,65,第三章 词 法 分 析,3.4 词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理 1、扫描缓冲区 2、预处理 三、超前搜索 1、问题的提出 2、工作原理 四、由词法语法规则画状态转换图 1、语言子集单词符号 2、单词的正规文法规则 3、构造状态转换图 五、词法分析程序的设计与实现,66,3.4 词法分析程序设计与实现 三、超前搜索 1、问题的提出,所谓超前读字符（也称超前搜索或向前扫描），是指仅向前读取字符，判别该字符是什么，不做别的处理工作。当判明情况以后,再回过头来处理已读过的字符 。 如：某语句 ABCDE := 2,从A开始依次读字符，直到E还不

43、能判断出标识符ABCDE已结束，还需继续读下面的字符，当发现E后字符既不是字母又不是数字时，才确定ABCDE为标识符。 又如：如FORTRAN语言，只设关键字（如DO，IF，GOTO等），而无保留字。在语句中，关键字、标号和标识符之间，并无明显的分界符，为了识别这些单词，就要采用超前搜索的方法。 ,67,（）DO99K=1,10 （）DO99K=1.10 这两个语句都是正确的语句。语句（）是语句，它是 以关键字开头。语句（）是赋值语句，它是以用户自己定义的标识符 K开头的。 语句（）和（）区别在于等号之后第一个界限符，语句（）是逗号， 语句（）是句末号。对于语句（）和（）来说，尽管都以“”两个

44、 字符开头，我们不能一见“”就认定是语句。我们必须超前搜索，看 看是否有等号，如果有，再向前搜索，若下个界限符是逗点，则是关键 字，否则为非关键字，它只是用户定义标识符头两个字母。,例如有以下两个语言的语句：,68,3.4 词法分析程序设计与实现 三、超前搜索 2. 工作原理 向前搜索由起始指示器和搜索指示器协同工作，搜索指示器一直向前搜索直到可以判断单词类别后再退回原来位置。 ,69,第三章 词 法 分 析,3.4 词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理 1、扫描缓冲区 2、预处理 三、超前搜索 1、问题的提出 2、工作原理 四、由词法语法规则画状态转换图 1、语言子集

45、单词符号 2、单词的正规文法规则 3、构造状态转换图 五、词法分析程序的设计与实现,70,第三章 词 法 分 析,3.4 词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理 1、扫描缓冲区 2、预处理 三、超前搜索 1、问题的提出 2、工作原理 四、由词法语法规则画状态转换图 1、语言子集单词符号 2、单词的正规文法规则 3、构造状态转换图 五、词法分析程序的设计与实现,71,3.4 词法分析程序设计与实现 四、由词法规则画状态转换图 .语言子集单词符号 下表列出了这个语言所有单词符号，以及它们种别编码和内部值。,基本符号 种别编码 助记符 内码值 BEGIN 1 $BEGIN EN

46、D 2 $END WHILE 3 $WHILE DO 4 $SEMI 标识符 5 $ID 内部字符串 整常数 6 $INT 标准二进制形式 ; 7 $SEMT + 8 $PLUS * 9 $STAR := 10 $ASSIGN = 11 $LE 12 $LT : 13 $COLON,72,3.4 词法分析程序设计与实现 四、由词法规则画状态转换图 2. 单词的正规文法规则 对于表.中的基本符号（单词）可用下述正规文法规则 (左线性）加以描述： 标识符字母标识符数字标识符字母 整常数数字整常数数字 单分界符； 双分界符冒号小于号 冒号 ： 小于号 ,73,3. 构造状态转换图 （1）先构造每一个

47、单词的状态转换图。 例如 := 字母| 字母| 数字 按照前面所述规则 U:=a U:=Ba :=数字|数字,S,U,a,B,U,a,S,标志符,字母,字母/数字,出口,其他符号,S,整常数,数字,数字,出口,非数字,3.4 词法分析程序设计与实现 四、由词法语法规则画状态转换图,74,（2）将所有单词的状态转换图合并成一张状态转换图。,0,字母,1,3,8,11,字母或数字,*,*,*,*,非字母或数字,非数字,非,非,数字,数字,;,+,*,:,其他,75,第三章 词 法 分 析,3.4 词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理 1、扫描缓冲区 2、预处理 三、超前搜索

48、 1、问题的提出 2、工作原理 四、由词法语法规则画状态转换图 1、语言子集单词符号 2、单词的正规文法规则 3、构造状态转换图 五、词法分析程序的设计与实现,76,第三章 词 法 分 析,3.4 词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理 1、扫描缓冲区 2、预处理 三、超前搜索 1、问题的提出 2、工作原理 四、由词法语法规则画状态转换图 1、语言子集单词符号 2、单词的正规文法规则 3、构造状态转换图 五、词法分析程序的设计与实现,77,3.4 词法分析程序设计与实现 五、词法分析程序的实现 有了状态转换图很容易写出词法分析程序，下面考虑把词法分析 程序作为一个子程序来

49、构造， 每当语法分析程序需要一个单词符号时 就调用这个子程序。在此对保留字不专设状态转换图，只作标识符处理 识别出标识符后，再去查保留字表，以确定是保留字还是普通标识符。 下面我们根据前述的状态转换图来构造由表3.2给出的PASCAL 子语言的词法分析程序。首先我们引入一些变量和过程： （）字符变量，它存放着新读入的源程序字符。 （）字符数组，它存放构成单词符号的字符串。 （）过程，读入下一个源程序字符至中， 并把字符指针后移一个位置。,78,（）过程GETNBC，先检查CHAR中是否为空白字符，若是则反复调 用GETCHAR直至CHAR中读入的是一个非空白字符。 （）过程CONCAT，将CH

50、AR字连接到TOKEN后面。例如，假定TOKEN 原来的值为STUDENT，而CHAR中存放着 ，则调用过程 CONCAT之后，TOKEN的新值为STUDENTS。 （）布尔函数LETTER，若CHAR中字符为字母则返回TRUE，否则返回 FALSE。 （）布尔函数DIGIT，若CHAR中字符为数字则返回TRUE， 否则返回 FALSE。 （）函数RESERVE，由TOKEN字符串查保留字表，若TOKEN中字符串 为保留字则返回其种别编码，否则返回值为。 （）过程RETRACT，将字符指针向前移一个位置，CHAR置空白字符。,79,现在我们可以写出前面所述的子语言的词法分析程序： Start

51、: token:= ; 置为空串 getchar; getnbc; CASE char OF AZ : BEGIN WHILE letter OR digit DO BEGIN Concat; getchar; END； retract； c := reserve IF c=0 THEN return ($ ID, token) ELSE return (c,) END；,80,0 9 : WHILE digit DO BEGIN Concat； getchar； END； retract； return （INT, DTB） END； ;: return ($SEMI，)； : return

52、（$PLUS，）； *: return ($STAR，）；,81,: BEGIN； getchar； IF char THEN return （ $ASSIGN,）； ELSE retract； return ($COLON,) END； : BEGIN getchar； charTHEN return ($LE,)； ELSE retract; return($LT,) END END OF CASE； ERROR；出错处理 GOTO start； 返回开始处，进行下一个单词的识别,82,第三章 词 法 分 析,3.1 引言 一、词法分析基本思想 二、词法分析任务 三、词法分析方式 四、词法

53、分析方法 3.2 单词的内部编码 一、单词 二、内部编码 3.3 正规文法和状态转换图 一、正规文法 二、状态转换图 三、正规文法与状态转换图 3.4 词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理 三、超前搜索 四、由词法语法规则画状态转换图 五、词法分析程序的设计与实现,3.5 正规文法和有穷自动机 一、用正规文法描述单词 二、由正规文法构造状态转换图 三、有穷自动机FA 四、有穷自动机和正规文法的关系 五、DFA与NFA的关系 3.6 正规表达式和有穷自动机 一、正规表达式和正规集的定义 二、正规表达式的性质 三、正规文法、正规表达式与有穷自动机 四、由正规表达式构造确定有

54、穷自动机 五、确定有穷自动机的化简 3.7 词法分析程序的自动生成 一、问题的提出 二、语言LEX一般描述 三、LEX编译程序的实现 四、LEX目标程序,83,第三章 词 法 分 析,3.1 引言 一、词法分析基本思想 二、词法分析任务 三、词法分析方式 四、词法分析方法 3.2 单词的内部编码 一、单词 二、内部编码 3.3 正规文法和状态转换图 一、正规文法 二、状态转换图 三、正规文法与状态转换图 3.4 词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理 三、超前搜索 四、由词法语法规则画状态转换图 五、词法分析程序的设计与实现,3.5 正规文法和有穷自动机 一、用正规文法描述单词 二、由正规文法构造状态转换图 三、有穷自动机FA 四、有穷自动机和正规文法的关系 五、DFA与NFA的关系