[工学]《编译原理》第三章-修正版

编 译 原 理Compiler Principles,黄海平 密钥：compiling南京邮电大学.计算机学院,第三章 词法分析,教材：编译技术原理及其实现方法王汝传 编著,第三章 词法分析,本章内容,3.1 引言 一、词法分析基本思想 二、词法分析任务 三、词法分析方式 四、词法分析方法3.2 单词的内部编码 一、单词 二、内部编码3.3 正规文法和状态转换图 一、正规文法 二、状态转换图 三、正规文法与状态转换图3.4 词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理 三、超前搜索 四、由词法语法规则画状态转换图 五、词法分析程序的设计与实现,3.5 正规文法和有穷自动机 一、用正规文法描述单词 二、由正规文法构造状态转换图 三、有穷自动机FA 四、有穷自动机和正规文法的关系 五、DFA与NFA的关系 3.6 正规表达式和有穷自动机 一、正规表达式和正规集的定义 二、正规表达式的性质 三、正规文法、正规表达式与有穷自动机 四、由正规表达式构造确定有穷自动机 五、确定有穷自动机的化简 3.7 词法分析程序的自动生成 一、问题的提出 二、语言LEX一般描述 三、LEX编译程序的实现 四、LEX目标程序,本章内容,3.1 引言 一、词法分析基本思想 二、词法分析任务 三、词法分析方式 四、词法分析方法3.2 单词的内部编码 一、单词 二、内部编码3.3 正规文法和状态转换图 一、正规文法 二、状态转换图 三、正规文法与状态转换图3.4 词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理 三、超前搜索 四、由词法语法规则画状态转换图 五、词法分析程序的设计与实现,3.5 正规文法和有穷自动机 一、用正规文法描述单词 二、由正规文法构造状态转换图 三、有穷自动机FA 四、有穷自动机和正规文法的关系 五、DFA与NFA的关系 3.6 正规表达式和有穷自动机 一、正规表达式和正规集的定义 二、正规表达式的性质 三、正规文法、正规表达式与有穷自动机 四、由正规表达式构造确定有穷自动机 五、确定有穷自动机的化简 3.7 词法分析程序的自动生成 一、问题的提出 二、语言LEX一般描述 三、LEX编译程序的实现 四、LEX目标程序,第三章 词法分析,本节内容,3.1 引言 一、词法分析基本思想 二、词法分析任务 1. 识别单词 2. 消除无用字符 3. 变成内部编码 4. 建立各种表格 5. 分配存贮单元（静态变量） 6. 进行词法检查 三、词法分析方式 1. 将词法分析和语法分析程序分开 2. 将词法分析程序编写成一个独立子程序 四、词法分析方法 1. 直接分析方法 2. 状态矩阵法,第三章 词法分析,引言,经过第一章的学习，我们已经初步了解了编译过程及各阶段的功能，从本章开始我们将详细叙述各阶段是如何工作的。首先来看一下词法分析，这是编译的第一步，也是编译的重点，下面我们将将详细介绍词法分析的方法。,第三章 词法分析,本节内容,3.1 引言 一、词法分析基本思想 二、词法分析任务 1. 识别单词 2. 消除无用字符 3. 变成内部编码 4. 建立各种表格 5. 分配存贮单元（静态变量） 6. 进行词法检查 三、词法分析方式 1. 将词法分析和语法分析程序分开 2. 将词法分析程序编写成一个独立子程序 四、词法分析方法 1. 直接分析方法 2. 状态矩阵法,第三章 词法分析,词法分析基本思想,扫描源程序 识别单词 变成中间程序L1（内部编码）。 即从左到右逐个字符地扫描源程序，产生一个个独立的单词， 并将其改变成等价的中间程序，记为：L1。实际上是机器的 内部编码,第三章 词法分析,本节内容,1.1 引言 一、词法分析基本思想 二、词法分析任务 1. 识别单词 2. 消除无用字符 3. 变成内部编码 4. 建立各种表格 5. 分配存贮单元（静态变量） 6. 进行词法检查 三、词法分析方式 1. 将词法分析和语法分析程序分开 2. 将词法分析程序编写成一个独立子程序 四、词法分析方法 1. 直接分析方法 2. 状态矩阵法,第三章 词法分析,识别单词,扫描源程序的一个个字符，按照语言的词法规则，识别出各类有独立意义的单词。 如： begin ， procedure ， + ， 5.43 ， abc等。,第三章 词法分析,本节内容,1.1 引言 一、词法分析基本思想 二、词法分析任务 1. 识别单词 2. 消除无用字符 3. 变成内部编码 4. 建立各种表格 5. 分配存贮单元（静态变量） 6. 进行词法检查 三、词法分析方式 1. 将词法分析和语法分析程序分开 2. 将词法分析程序编写成一个独立子程序 四、词法分析方法 1. 直接分析方法 2. 状态矩阵法,第三章 词法分析,消除无用字符,对源程序文本进行处理，消除源程序文本中的注释、空格、换行符以及其他一切对语法分析和代码生成均无关的信息。,第三章 词法分析,本节内容,1.1 引言 一、词法分析基本思想 二、词法分析任务 1. 识别单词 2. 消除无用字符 3. 变成内部编码 4. 建立各种表格 5. 分配存贮单元（静态变量） 6. 进行词法检查 三、词法分析方式 1. 将词法分析和语法分析程序分开 2. 将词法分析程序编写成一个独立子程序 四、词法分析方法 1. 直接分析方法 2. 状态矩阵法,第三章 词法分析,变成内部编码,将长度不一、种类不同的单词变成长度统一、格式规整、分类清晰的一种内部机器码表示。,第三章 词法分析,本节内容,1.1 引言 一、词法分析基本思想 二、词法分析任务 1. 识别单词 2. 消除无用字符 3. 变成内部编码 4. 建立各种表格 5. 分配存贮单元（静态变量） 6. 进行词法检查 三、词法分析方式 1. 将词法分析和语法分析程序分开 2. 将词法分析程序编写成一个独立子程序 四、词法分析方法 1. 直接分析方法 2. 状态矩阵法,第三章 词法分析,建立各种表格,在词法分析时，可以根据单词特点建立不同表格如： 名字表（标识符表）：源程序中的标识符集中表 常数表 数组向量表、过程表等 界限表：包含了保留字、运算符等,第三章 词法分析,本节内容,1.1 引言 一、词法分析基本思想 二、词法分析任务 1. 识别单词 2. 消除无用字符 3. 变成内部编码 4. 建立各种表格 5. 分配存贮单元（静态变量） 6. 进行词法检查 三、词法分析方式 1. 将词法分析和语法分析程序分开 2. 将词法分析程序编写成一个独立子程序 四、词法分析方法 1. 直接分析方法 2. 状态矩阵法,第三章 词法分析,分配存储单元(静态变量),对简单变量、常量及数组进行静态存贮分配 静态存贮分配：在编译时就可以决定应分配 内存的大小。 动态存贮分配：到运行时才进行的存贮分配。 如：变界数组、动态变量。 静态存贮分配可以在词法分析阶段进行，也可以在语法分析阶段进行，随具体编译系统而定。,第三章 词法分析,本节内容,1.1 引言 一、词法分析基本思想 二、词法分析任务 1. 识别单词 2. 消除无用字符 3. 变成内部编码 4. 建立各种表格 5. 分配存贮单元（静态变量） 6. 进行词法检查 三、词法分析方式 1. 将词法分析和语法分析程序分开 2. 将词法分析程序编写成一个独立子程序 四、词法分析方法 1. 直接分析方法 2. 状态矩阵法,第三章 词法分析,进行词法检查,将一些单词错误检查出来， 如保留字PROGRAM、 VAR； 又例如变量是否有说明或是否重复说明等。,第三章 词法分析,本节内容,1.1 引言 一、词法分析基本思想 二、词法分析任务 1. 识别单词 2. 消除无用字符 3. 变成内部编码 4. 建立各种表格 5. 分配存贮单元（静态变量） 6. 进行词法检查 三、词法分析方式 1. 将词法分析和语法分析程序分开 2. 将词法分析程序编写成一个独立子程序 四、词法分析方法 1. 直接分析方法 2. 状态矩阵法,第三章 词法分析,本节内容,1.1 引言 一、词法分析基本思想 二、词法分析任务 1. 识别单词 2. 消除无用字符 3. 变成内部编码 4. 建立各种表格 5. 分配存贮单元（静态变量） 6. 进行词法检查 三、词法分析方式 1. 将词法分析和语法分析程序分开 2. 将词法分析程序编写成一个独立子程序 四、词法分析方法 1. 直接分析方法 2. 状态矩阵法,第三章 词法分析,将词法分析和语法分析程序分开,在多遍扫描的编译程序中，词法分析可以单独作为一遍扫描来完成，此时可将词法分析程序的输出放在一个中间文件上，语法分析程序可以从该文件上取得它的输入。 词法分析从语法分析独立出来的原因： （1）便于集中进行语法分析 （2）便于建立有效词法分析技术 （3）将给语法分析提供更多更详细信息,字符串表示的源程序,词法分析程序,符号串表示的源程序,字符,单词,第三章 词法分析,本节内容,1.1 引言 一、词法分析基本思想 二、词法分析任务 1. 识别单词 2. 消除无用字符 3. 变成内部编码 4. 建立各种表格 5. 分配存贮单元（静态变量） 6. 进行词法检查 三、词法分析方式 1. 将词法分析和语法分析程序分开 2. 将词法分析程序编写成一个独立子程序 四、词法分析方法 1. 直接分析方法 2. 状态矩阵法,第三章 词法分析,将词法分析程序编写成一个独立子程序,在一遍扫描的编译程序中，往往将词法分析编成语法分析的一个子程序，供语法分析时随时调用，每调用一次，则从源程序字符串中读出一个具有独立意义的单词。,字符串表示的源程序,词法分析程序,语法分析程序,字符,取一单词,返 回,优点：不需要在内存中构造和保留中间文件所以节省内存容量,第三章 词法分析,本节内容,1.1 引言 一、词法分析基本思想 二、词法分析任务 1. 识别单词 2. 消除无用字符 3. 变成内部编码 4. 建立各种表格 5. 分配存贮单元（静态变量） 6. 进行词法检查 三、词法分析方式 1. 将词法分析和语法分析程序分开 2. 将词法分析程序编写成一个独立子程序 四、词法分析方法 1. 直接分析方法 2. 状态矩阵法,第三章 词法分析,本节内容,1.1 引言 一、词法分析基本思想 二、词法分析任务 1. 识别单词 2. 消除无用字符 3. 变成内部编码 4. 建立各种表格 5. 分配存贮单元（静态变量） 6. 进行词法检查 三、词法分析方式 1. 将词法分析和语法分析程序分开 2. 将词法分析程序编写成一个独立子程序 四、词法分析方法 1. 直接分析方法 2. 状态矩阵法,第三章 词法分析,直接分析方法,根据词法分析任务编成多个不同独立子程序（如：读符号子程序、取单词子程序、拼标识符子程序、处理无符号数子程序），对源程序进行分析加工处理。,第三章 词法分析,本节内容,1.1 引言 一、词法分析基本思想 二、词法分析任务 1. 识别单词 2. 消除无用字符 3. 变成内部编码 4. 建立各种表格 5. 分配存贮单元（静态变量） 6. 进行词法检查 三、词法分析方式 1. 将词法分析和语法分析程序分开 2. 将词法分析程序编写成一个独立子程序 四、词法分析方法 1. 直接分析方法 2. 状态矩阵法,第三章 词法分析,状态矩阵法,根据一张二维状态矩阵表对源程序进行控制分析。这部分内容将在第四章讲语法分析时介绍。,第三章 词法分析,本章内容,3.1 引言 一、词法分析基本思想 二、词法分析任务 三、词法分析方式 四、词法分析方法3.2 单词的内部编码 一、单词 二、内部编码3.3 正规文法和状态转换图 一、正规文法 二、状态转换图 三、正规文法与状态转换图3.4 词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理 三、超前搜索 四、由词法语法规则画状态转换图 五、词法分析程序的设计与实现,3.5 正规文法和有穷自动机 一、用正规文法描述单词 二、由正规文法构造状态转换图 三、有穷自动机FA 四、有穷自动机和正规文法的关系 五、DFA与NFA的关系 3.6 正规表达式和有穷自动机 一、正规表达式和正规集的定义 二、正规表达式的性质 三、正规文法、正规表达式与有穷自动机 四、由正规表达式构造确定有穷自动机 五、确定有穷自动机的化简 3.7 词法分析程序的自动生成 一、问题的提出 二、语言LEX一般描述 三、LEX编译程序的实现 四、LEX目标程序,第三章 词法分析,本节内容,3.2 单词的内部编码 一、单词 二、内部编码 1. 单词类别 2. 单词自身值,第三章 词法分析,本节内容,3.2 单词的内部编码 一、单词 二、内部编码 1. 单词类别 2. 单词自身值,第三章 词法分析,单词,这部分内容在第一章中已介绍，在此简单回顾一下。 所谓单词，是指那些具有独立含义的最小语法单位 。单词可 分为以下几种类型： （）保留字：PROGRAM, VAR, IF, FOR, AND等 。 （）标识符：是用户选来表示常量、变量、类型、过程等名字。 （ 3 ）常数：分为整型、实型、布尔型、字符型等，如2, 3.1416等。 （）运算符：分为算术运算符（, , *, 等），逻辑运算符 （, , ），关系运算符（=）等。 （）界限符：如逗号、分号、括号等。,第三章 词法分析,本节内容,3.2 单词的内部编码 一、单词 二、内部编码 1. 单词类别 2. 单词自身值,第三章 词法分析,本节内容,3.2 单词的内部编码 一、单词 二、内部编码 1. 单词类别 2. 单词自身值,第三章 词法分析,单词类别,对于单词类别可以用整数表示，用来指示单词的种类 。例如上面的例子，我们可以用个不同的整数作为它们单词类别的编码 。单词的内部编码是词法分析的输出形式。,单词类型,单词自身值,第三章 词法分析,本节内容,3.2 单词的内部编码 一、单词 二、内部编码 1. 单词类别 2. 单词自身值,第三章 词法分析,单词自身值,可以是单词某种形式内部编码，也可以是该单词在某些表格中地址码。如第一章所讲，保留字、运算符和界限符用内部固定编码值作为单词值；标识符取其在标识符表中的地址码 ；常量取其在常数表中的地址码。 例如：有下列单词： 单词 内部编码 单词 内部编码 IF 2 + 25 THEN 3 * 26 ELSE 4 34,第三章 词法分析,单词自身值,第三章 词法分析,单词 内部编码 （ 35 ） 36 ：= 37单词 地址码 a1 200 b1 201 c1 202 d1 203 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,本章内容,3.1 引言 一、词法分析基本思想 二、词法分析任务 三、词法分析方式 四、词法分析方法3.2 单词的内部编码 一、单词 二、内部编码3.3 正规文法和状态转换图 一、正规文法 二、状态转换图 三、正规文法与状态转换图3.4 词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理 三、超前搜索 四、由词法语法规则画状态转换图 五、词法分析程序的设计与实现,3.5 正规文法和有穷自动机 一、用正规文法描述单词 二、由正规文法构造状态转换图 三、有穷自动机FA 四、有穷自动机和正规文法的关系 五、DFA与NFA的关系 3.6 正规表达式和有穷自动机 一、正规表达式和正规集的定义 二、正规表达式的性质 三、正规文法、正规表达式与有穷自动机 四、由正规表达式构造确定有穷自动机 五、确定有穷自动机的化简 3.7 词法分析程序的自动生成 一、问题的提出 二、语言LEX一般描述 三、LEX编译程序的实现 四、LEX目标程序,第三章 词法分析,本章内容,3.1 引言 一、词法分析基本思想 二、词法分析任务 三、词法分析方式 四、词法分析方法3.2 单词的内部编码 一、单词 二、内部编码3.3 正规文法和状态转换图 一、正规文法 二、状态转换图 三、正规文法与状态转换图3.4 词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理 三、超前搜索 四、由词法语法规则画状态转换图 五、词法分析程序的设计与实现,3.5 正规文法和有穷自动机 一、用正规文法描述单词 二、由正规文法构造状态转换图 三、有穷自动机FA 四、有穷自动机和正规文法的关系 五、DFA与NFA的关系 3.6 正规表达式和有穷自动机 一、正规表达式和正规集的定义 二、正规表达式的性质 三、正规文法、正规表达式与有穷自动机 四、由正规表达式构造确定有穷自动机 五、确定有穷自动机的化简 3.7 词法分析程序的自动生成 一、问题的提出 二、语言LEX一般描述 三、LEX编译程序的实现 四、LEX目标程序,第三章 词法分析,本节内容,3.3 正规文法和状态转换图 一、正规文法 二、状态转换图 1. 定义 2. 功能 三、正规文法与状态转换图 1. 由正规文法构造状态转换图 2. 由正规文法状态转换图识别句子（单词）,第三章 词法分析,本节内容,3.3 正规文法和状态转换图 一、正规文法 二、状态转换图 1. 定义 2. 功能 三、正规文法与状态转换图 1. 由正规文法构造状态转换图 2. 由正规文法状态转换图识别句子（单词）,第三章 词法分析,正规文法,在介绍词法分析程序的设计之前，先来看一下正规文法和状态转换图，它们是词法分析的理论基础。一、正规文法正规文法就是乔姆斯基(Chomsky)文法分类中的3型文法，如果P中规则形式为 ： A=aB 或 A=a其中A, BVN，aVT，则称文法G为右线性文法。如P中规则形式为: A=Ba 或 A=a，则称文法G为左线性文法 。3型文法与词法分析密切相关如： =字母|字母|数字 左线性文法又如：=+|-|*|/ 正规文法,第三章 词法分析,本节内容,3.3 正规文法和状态转换图 一、正规文法 二、状态转换图 1. 定义 2. 功能 三、正规文法与状态转换图 1. 由正规文法构造状态转换图 2. 由正规文法状态转换图识别句子（单词）,第三章 词法分析,本节内容,3.3 正规文法和状态转换图 一、正规文法 二、状态转换图 1. 定义 2. 功能 三、正规文法与状态转换图 1. 由正规文法构造状态转换图 2. 由正规文法状态转换图识别句子（单词）,第三章 词法分析,状态转化图 定义,转换图实际上是一个有限方向图，图中结点代表状态，用圆圈表示。状态之间用箭弧连接，箭弧上标记（字符如x，y）代表射出结（即箭弧始结）状态下可能出现的输入字符 . 如：,第三章 词法分析,该状态转换图表示在状态1下读入x转到状态2，若在状态1下读入字符y，则转到状态3。,1,X,2,3,Y,本节内容,3.3 正规文法和状态转换图 一、正规文法 二、状态转换图 1. 定义 2. 功能 三、正规文法与状态转换图 1. 由正规文法构造状态转换图 2. 由正规文法状态转换图识别句子（单词）,第三章 词法分析,状态转化图功能,一个状态转换图可以用于识别（或接受）一定的字符串。例如：识别标识符的转换图如下图所示:,第三章 词法分析,0,字母,字母或数字,其他,*,1,状态转化图功能,第三章 词法分析,其中为初态，为终态（双圆圈表示）。这个转换图识别（接受）标识符过程是： （1）从初态开始，若在状态之下输入字符是一个字母则转入状态。 （2）在状态之下，若下一个输入字符为字母或数字，则读进它，并重 新进入状态1。 （3）重复（2），直到状态发现输入字符不再是字母或数字时就进入 状态。状是终态，它意味着到此已识别出一个标识符，识别 过程宣告终止。 终态结上打个星号，表示多读进一个不属于标识符的字符， 应把它退还给输入串。 （4）如果在开始状态0下，输入字符不是字母，则意味着识别不出标识符 按同样的方法，同学们可以考虑一下整数的识别状态转换图及识别过程,本节内容,3.3 正规文法和状态转换图 一、正规文法 二、状态转换图 1. 定义 2. 功能 三、正规文法与状态转换图 1. 由正规文法构造状态转换图 2. 由正规文法状态转换图识别句子（单词）,第三章 词法分析,本节内容,3.3 正规文法和状态转换图 一、正规文法 二、状态转换图 1. 定义 2. 功能 三、正规文法与状态转换图 1. 由正规文法构造状态转换图 2. 由正规文法状态转换图识别句子（单词）,第三章 词法分析,对于一个左线性文法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为状态转换图的终态 由以上规则，我们就可以构造一个左线性文法状态转换图。,第三章 词法分析,由正规文法(左线性文法)构造状态转化图,例如：设有左线性文法（，），其中： ，U， ， U U 由该文法所确定的语言为，根据上述构造状态转换图的规则，该文法状态转换图如下图所示。,第三章 词法分析,由正规文法(左线性文法)构造状态转化图,本节内容,3.3 正规文法和状态转换图 一、正规文法 二、状态转换图 1. 定义 2. 功能 三、正规文法与状态转换图 1. 由正规文法构造状态转换图 2. 由正规文法状态转换图识别句子（单词）,第三章 词法分析,如：符号串0110是上述文法的句子，因为：从开始状态S出发，读入0转入V，再读入1转入Z，再读入1转入U，最后读入0转入Z，且Z是终态。又如：符号串101001也是该文法的一个句子。实际上这是一个自底向上分析方法进行分析。,第三章 词法分析,由正规文法状态转化图识别句子(单词),第三章 词法分析,由正规文法状态转化图识别句子(单词),识别字符串x=101001,步骤 当前状态 x的余留部分 1 S 101001 2 U 01001 3 Z 1001 4 U 001 5 Z 01 6 V 1 7 Z,句子101001语法树,Z,V,1,Z,U,Z,U,0,0,1,0,1,由此可以看出正规文法的状态转换图有助于识别正规文法产生的句子。,本章内容,3.1 引言 一、词法分析基本思想 二、词法分析任务 三、词法分析方式 四、词法分析方法3.2 单词的内部编码 一、单词 二、内部编码3.3 正规文法和状态转换图 一、正规文法 二、状态转换图 三、正规文法与状态转换图3.4 词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理 三、超前搜索 四、由词法语法规则画状态转换图 五、词法分析程序的设计与实现,3.5 正规文法和有穷自动机 一、用正规文法描述单词 二、由正规文法构造状态转换图 三、有穷自动机FA 四、有穷自动机和正规文法的关系 五、DFA与NFA的关系 3.6 正规表达式和有穷自动机 一、正规表达式和正规集的定义 二、正规表达式的性质 三、正规文法、正规表达式与有穷自动机 四、由正规表达式构造确定有穷自动机 五、确定有穷自动机的化简 3.7 词法分析程序的自动生成 一、问题的提出 二、语言LEX一般描述 三、LEX编译程序的实现 四、LEX目标程序,第三章 词法分析,本节内容,3.4 词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理 1、扫描缓冲区 2、预处理 三、超前搜索 1、问题的提出 2、工作原理 四、由词法语法规则画状态转换图 1、语言子集单词符号 2、单词的正规文法规则 3、构造状态转换图 五、词法分析程序的设计与实现,第三章 词法分析,本节内容,3.4 词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理 1、扫描缓冲区 2、预处理 三、超前搜索 1、问题的提出 2、工作原理 四、由词法语法规则画状态转换图 1、语言子集单词符号 2、单词的正规文法规则 3、构造状态转换图 五、词法分析程序的设计与实现,第三章 词法分析,1. 内存比较大的情况下，直接输入到内存的一个源程序区 (1) 一个字符占一个字节 (2) 词法分析程序从源程序区读入字符2. 内存不足的情况下，将源程序以文件的形式存贮在外部介质上，如磁盘、磁带等 。可以先在内存中开辟一个大小适宜的缓冲区，这个缓冲区称为输入缓冲区。词法分析程序工作时，先从外部介质上将输入符号串分批读入缓冲区，单词符号的识别可在这个缓冲区中进行。具体处理时还要开辟一个扫描缓冲区。,第三章 词法分析,源程序的输入,本节内容,3.4 词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理 1、扫描缓冲区 2、预处理 三、超前搜索 1、问题的提出 2、工作原理 四、由词法语法规则画状态转换图 1、语言子集单词符号 2、单词的正规文法规则 3、构造状态转换图 五、词法分析程序的设计与实现,第三章 词法分析,本节内容,3.4 词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理 1、扫描缓冲区 2、预处理 三、超前搜索 1、问题的提出 2、工作原理 四、由词法语法规则画状态转换图 1、语言子集单词符号 2、单词的正规文法规则 3、构造状态转换图 五、词法分析程序的设计与实现,第三章 词法分析,本节内容,3.4 词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理 1、扫描缓冲区 2、预处理 三、超前搜索 1、问题的提出 2、工作原理 四、由词法语法规则画状态转换图 1、语言子集单词符号 2、单词的正规文法规则 3、构造状态转换图 五、词法分析程序的设计与实现,第三章 词法分析,（1）定义：扫描缓冲区就是在内存中开辟一部分单元，供识别单词用。 注意：扫描缓冲区和缓冲区不同，缓冲区是从内/外存上读入部分字符， 而扫描缓冲区仅是为识别单词用。 （2）工作原理 在扫描缓冲区中一般设两个指示器，一个指向当前正在识别单词开始位 置，另一个用于向前搜索寻找单词的终点。不论扫描缓冲区定为多大都 不能保证单词符号不会被它的边界所打断,因此，扫描缓冲区最好使用如 下所示的一分为二的区域（每半区可容120个字符 ）： 扫描缓冲区1 扫描缓冲区2 起始指示器 搜索指示器,第三章 词法分析,扫描缓冲区,1) 开始时扫描缓冲区皆为空 。2) 调用预处理子程序，将120个字符填满扫描缓冲区 。并将两个指示 器指向扫描缓冲区的第个字符 。3) 将搜索指示器向后移动，当识别出一个单词之后，搜索指示器已指向 下一个单词的第一个字符，然后再将起始指示器移到搜索指示器指向字符，接着搜索指示器又开始扫描第二个单词。 当搜索指示器越界时，说明缓冲区中的字符不足一个单词，这时再调用预处理子程序，再将120个字符填满扫描缓冲区，再将搜索指示器扫描缓冲区第个字符。这样，两个扫描缓冲区交替工作 。4) 一般描缓冲区长度可以存放最长一个单词，即可正常工作 ；否则， 就不能保证单词符号不会被缓冲区边界所打断。,第三章 词法分析,扫描缓冲区,本节内容,3.4 词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理 1、扫描缓冲区 2、预处理 三、超前搜索 1、问题的提出 2、工作原理 四、由词法语法规则画状态转换图 1、语言子集单词符号 2、单词的正规文法规则 3、构造状态转换图 五、词法分析程序的设计与实现,第三章 词法分析,预处理目的是将一些无用的空白符、跳格符、回车换行符等编辑性字符剔除掉