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

1,编译原理CompilerPrinciples,徐小龙xuxl南京邮电大学.计算机学院,第三章词法分析,教材：编译技术原理及其实现方法王汝传编著,2,经过第一章的学习，我们已经初步了解了编译过程及各阶段的功能，从本章开始我门将详细叙述各阶段是如何工作的。首先来看一下词法分析，这是编译的第一步，也是编译的重点，下面我们将将详细介绍词法分析的方法。,源程序,词法分析程序,语法分析程序,语义分析程序,中间代码生成,代码优化程序,目标代码生成,目标程序,信息表管理程序,错误检查和处理程序,3,第三章词法分析,3.1引言一、词法分析基本思想二、词法分析任务三、词法分析方式四、词法分析方法3.2单词的内部编码一、单词二、内部编码3.3正规文法和状态转换图一、正规文法二、状态转换图三、正规文法与状态转换图3.4词法分析程序设计与实现一、源程序的输入二、缓冲区及预处理三、超前搜索四、由词法语法规则画状态转换图五、词法分析程序的设计与实现,3.5正规文法和有穷自动机一、用正规文法描述单词二、由正规文法构造状态转换图三、有穷自动机FA四、有穷自动机和正规文法的关系五、DFA与NFA的关系3.6正规表达式和有穷自动机一、正规表达式和正规集的定义二、正规表达式的性质三、正规文法、正规表达式与有穷自动机四、由正规表达式构造确定有穷自动机五、确定有穷自动机的化简3.7词法分析程序的自动生成一、问题的提出二、语言LEX一般描述三、LEX编译程序的实现四、LEX目标程序,4,第三章词法分析,3.1引言一、词法分析基本思想二、词法分析任务三、词法分析方式四、词法分析方法3.2单词的内部编码一、单词二、内部编码3.3正规文法和状态转换图一、正规文法二、状态转换图三、正规文法与状态转换图3.4词法分析程序设计与实现一、源程序的输入二、缓冲区及预处理三、超前搜索四、由词法语法规则画状态转换图五、词法分析程序的设计与实现,3.5正规文法和有穷自动机一、用正规文法描述单词二、由正规文法构造状态转换图三、有穷自动机FA四、有穷自动机和正规文法的关系五、DFA与NFA的关系3.6正规表达式和有穷自动机一、正规表达式和正规集的定义二、正规表达式的性质三、正规文法、正规表达式与有穷自动机四、由正规表达式构造确定有穷自动机五、确定有穷自动机的化简3.7词法分析程序的自动生成一、问题的提出二、语言LEX一般描述三、LEX编译程序的实现四、LEX目标程序,5,第三章词法分析,3.1引言一、词法分析基本思想二、词法分析任务1.识别单词2.消除无用字符3.变成内部编码4.建立各种表格5.分配存贮单元（静态变量）6.进行词法检查三、词法分析方式1.将词法分析和语法分析程序分开2.将词法分析程序编写成一个独立子程序四、词法分析方法1.直接分析方法2.状态矩阵法,6,第三章词法分析,3.1引言一、词法分析基本思想二、词法分析任务1.识别单词2.消除无用字符3.变成内部编码4.建立各种表格5.分配存贮单元（静态变量）6.进行词法检查三、词法分析方式1.将词法分析和语法分析程序分开2.将词法分析程序编写成一个独立子程序四、词法分析方法1.直接分析方法2.状态矩阵法,7,3.1引言一、词法分析基本思想扫描源程序识别单词变成中间程序L1（内部编码）。即从左到右逐个字符地扫描源程序，产生一个个独立的单词，并将其改变成等价的中间程序，记为：L1。实际上是机器的内部编码,符号序列,单词序列,词法分析,8,第三章词法分析,3.1引言一、词法分析基本思想二、词法分析任务1.识别单词2.消除无用字符3.变成内部编码4.建立各种表格5.分配存贮单元（静态变量）6.进行词法检查三、词法分析方式1.将词法分析和语法分析程序分开2.将词法分析程序编写成一个独立子程序四、词法分析方法1.直接分析方法2.状态矩阵法,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引言二、词法分析任务2.消除无用字符对源程序文本进行处理，消除源程序文本中的注释、空格、换行符以及其他一切对语法分析和代码生成均无关的信息。,12,第三章词法分析,3.1引言一、词法分析基本思想二、词法分析任务1.识别单词2.消除无用字符3.变成内部编码4.建立各种表格5.分配存贮单元（静态变量）6.进行词法检查三、词法分析方式1.将词法分析和语法分析程序分开2.将词法分析程序编写成一个独立子程序四、词法分析方法1.直接分析方法2.状态矩阵法,13,3.1引言二、词法分析任务3.变成内部编码将长度不一、种类不同的单词变成长度统一、格式规整、分类清晰的一种内部机器码表示。,14,第三章词法分析,3.1引言一、词法分析基本思想二、词法分析任务1.识别单词2.消除无用字符3.变成内部编码4.建立各种表格5.分配存贮单元（静态变量）6.进行词法检查三、词法分析方式1.将词法分析和语法分析程序分开2.将词法分析程序编写成一个独立子程序四、词法分析方法1.直接分析方法2.状态矩阵法,15,3.1引言二、词法分析任务4.建立各种表格在词法分析时，可以根据单词特点建立不同表格，如：名字表（标识符表）：源程序中的标识符集中在表中常数表数组向量表、过程表等界限表：包含了保留字、运算符等,16,第三章词法分析,3.1引言一、词法分析基本思想二、词法分析任务1.识别单词2.消除无用字符3.变成内部编码4.建立各种表格5.分配存贮单元（静态变量）6.进行词法检查三、词法分析方式1.将词法分析和语法分析程序分开2.将词法分析程序编写成一个独立子程序四、词法分析方法1.直接分析方法2.状态矩阵法,17,3.1引言二、词法分析任务5.分配存贮单元（静态变量）对简单变量、常量及数组进行静态存贮分配静态存贮分配：在编译时就可以决定应分配内存的大小。动态存贮分配：到运行时才进行的存贮分配。如：变界数组、动态变量。静态存贮分配可以在词法分析阶段进行，也可以在语法分析阶段进行，随具体编译系统而定。,18,第三章词法分析,3.1引言一、词法分析基本思想二、词法分析任务1.识别单词2.消除无用字符3.变成内部编码4.建立各种表格5.分配存贮单元（静态变量）6.进行词法检查三、词法分析方式1.将词法分析和语法分析程序分开2.将词法分析程序编写成一个独立子程序四、词法分析方法1.直接分析方法2.状态矩阵法,19,3.1引言二、词法分析任务6.进行词法检查将一些单词错误检查出来，如保留字PROGRAM、VAR；又例如变量是否有说明或是否重复说明等。,20,第三章词法分析,3.1引言一、词法分析基本思想二、词法分析任务1.识别单词2.消除无用字符3.变成内部编码4.建立各种表格5.分配存贮单元（静态变量）6.进行词法检查三、词法分析方式1.将词法分析和语法分析程序分开2.将词法分析程序编写成一个独立子程序四、词法分析方法1.直接分析方法2.状态矩阵法,21,第三章词法分析,3.1引言一、词法分析基本思想二、词法分析任务1.识别单词2.消除无用字符3.变成内部编码4.建立各种表格5.分配存贮单元（静态变量）6.进行词法检查三、词法分析方式1.将词法分析和语法分析程序分开2.将词法分析程序编写成一个独立子程序四、词法分析方法1.直接分析方法2.状态矩阵法,22,3.1引言三、词法分析方式1.将词法分析和语法分析程序分开在多遍扫描的编译程序中，词法分析可以单独作为一遍扫描来完成，此时可将词法分析程序的输出放在一个中间文件上，语法分析程序可以从该文件上取得它的输入。词法分析从语法分析独立出来的原因：（1）便于集中进行语法分析（2）便于建立有效词法分析技术（3）将给语法分析提供更多更详细信息,字符串表示的源程序,词法分析程序,符号串表示的源程序,字符,单词,23,第三章词法分析,3.1引言一、词法分析基本思想二、词法分析任务1.识别单词2.消除无用字符3.变成内部编码4.建立各种表格5.分配存贮单元（静态变量）6.进行词法检查三、词法分析方式1.将词法分析和语法分析程序分开2.将词法分析程序编写成一个独立子程序四、词法分析方法1.直接分析方法2.状态矩阵法,24,3.1引言三、词法分析方式2.将词法分析程序编写成一个独立子程序在一遍扫描的编译程序中，往往将词法分析编成语法分析的一个子程序，供语法分析时随时调用，每调用一次，则从源程序字符串中读出一个具有独立意义的单词。,优点：不需要在内存中构造和保留中间文件所以节省内存容量,字符串表示的源程序,词法分析程序,语法分析程序,字符,取一符号,符号,25,第三章词法分析,3.1引言一、词法分析基本思想二、词法分析任务1.识别单词2.消除无用字符3.变成内部编码4.建立各种表格5.分配存贮单元（静态变量）6.进行词法检查三、词法分析方式1.将词法分析和语法分析程序分开2.将词法分析程序编写成一个独立子程序四、词法分析方法1.直接分析方法2.状态矩阵法,26,第三章词法分析,3.1引言一、词法分析基本思想二、词法分析任务1.识别单词2.消除无用字符3.变成内部编码4.建立各种表格5.分配存贮单元（静态变量）6.进行词法检查三、词法分析方式1.将词法分析和语法分析程序分开2.将词法分析程序编写成一个独立子程序四、词法分析方法1.直接分析方法2.状态矩阵法,27,3.1引言三、词法分析方法1.直接分析方法根据词法分析任务编成多个不同独立子程序（如：读符号子程序、取单词子程序、拼标识符子程序、处理无符号数子程序），对源程序进行分析加工处理。,28,第三章词法分析,3.1引言一、词法分析基本思想二、词法分析任务1.识别单词2.消除无用字符3.变成内部编码4.建立各种表格5.分配存贮单元（静态变量）6.进行词法检查三、词法分析方式1.将词法分析和语法分析程序分开2.将词法分析程序编写成一个独立子程序四、词法分析方法1.直接分析方法2.状态矩阵法,29,3.1引言三、词法分析方法2.状态矩阵法根据一张二维状态矩阵表对源程序进行控制分析。这部分内容将在语法分析时介绍。,30,第三章词法分析,3.1引言一、词法分析基本思想二、词法分析任务三、词法分析方式四、词法分析方法3.2单词的内部编码一、单词二、内部编码3.3正规文法和状态转换图一、正规文法二、状态转换图三、正规文法与状态转换图3.4词法分析程序设计与实现一、源程序的输入二、缓冲区及预处理三、超前搜索四、由词法语法规则画状态转换图五、词法分析程序的设计与实现,3.5正规文法和有穷自动机一、用正规文法描述单词二、由正规文法构造状态转换图三、有穷自动机FA四、有穷自动机和正规文法的关系五、DFA与NFA的关系3.6正规表达式和有穷自动机一、正规表达式和正规集的定义二、正规表达式的性质三、正规文法、正规表达式与有穷自动机四、由正规表达式构造确定有穷自动机五、确定有穷自动机的化简3.7词法分析程序的自动生成一、问题的提出二、语言LEX一般描述三、LEX编译程序的实现四、LEX目标程序,31,第三章词法分析,3.1引言一、词法分析基本思想二、词法分析任务三、词法分析方式四、词法分析方法3.2单词的内部编码一、单词二、内部编码3.3正规文法和状态转换图一、正规文法二、状态转换图三、正规文法与状态转换图3.4词法分析程序设计与实现一、源程序的输入二、缓冲区及预处理三、超前搜索四、由词法语法规则画状态转换图五、词法分析程序的设计与实现,3.5正规文法和有穷自动机一、用正规文法描述单词二、由正规文法构造状态转换图三、有穷自动机FA四、有穷自动机和正规文法的关系五、DFA与NFA的关系3.6正规表达式和有穷自动机一、正规表达式和正规集的定义二、正规表达式的性质三、正规文法、正规表达式与有穷自动机四、由正规表达式构造确定有穷自动机五、确定有穷自动机的化简3.7词法分析程序的自动生成一、问题的提出二、语言LEX一般描述三、LEX编译程序的实现四、LEX目标程序,32,第三章词法分析,3.2单词的内部编码一、单词二、内部编码1.单词类别2.单词自身值,33,第三章词法分析,3.2单词的内部编码一、单词二、内部编码1.单词类别2.单词自身值,34,3.2单词的内部编码一、单词这部分内容在第一章中已介绍，在此简单回顾一下。所谓单词，是指那些具有独立含义的最小语法单位。单词可分为以下几种类型：（）保留字：PROGRAM,VAR,IF,FOR,AND等。（）标识符：是用户选来表示常量、变量、类型、过程等名字。（3）常数：分为整型、实型、布尔型、字符型等，如2，3.1416等。（）运算符：分为算术运算符（，*，等），逻辑运算符（，），关系运算符（=）等。（）界限符：如逗号、分号、括号等。,35,第三章词法分析,3.2单词的内部编码一、单词二、内部编码1.单词类别2.单词自身值,36,对于单词类别可以用整数表示，用来指示单词的种类。例如上面的例子，我们可以用个不同的整数作为它们单词类别的编码。单词的内部编码是词法分析的输出形式,3.2单词的内部编码二、内部编码1.单词类别,单词类型,单词自身值,37,3.2单词的内部编码二、内部编码2.单词自身值可以是单词某种形式内部编码，也可以是该单词在某些表格中地址码。如第一章所讲，保留字、运算符和界限符用内部固定编码值作为单词值；标识符取其在标识符表中的地址码；常量取其在常数表中的地址码。例如：有下列单词：单词内部编码单词内部编码IF2+25THEN3*26ELSE434,38,单词内部编码（35）36：=37单词地址码a1200b1201c1202d1203b20401003101,语句：ifa10thenb1:=(c1+3)elseb:=0经词法分析变成如下的内部编码形式：Ifa101222004343100thenb1:=(132201537535C1+3)22024243101536elseb:=01422045373102,39,第三章词法分析,3.1引言一、词法分析基本思想二、词法分析任务三、词法分析方式四、词法分析方法3.2单词的内部编码一、单词二、内部编码3.3正规文法和状态转换图一、正规文法二、状态转换图三、正规文法与状态转换图3.4词法分析程序设计与实现一、源程序的输入二、缓冲区及预处理三、超前搜索四、由词法语法规则画状态转换图五、词法分析程序的设计与实现,3.5正规文法和有穷自动机一、用正规文法描述单词二、由正规文法构造状态转换图三、有穷自动机FA四、有穷自动机和正规文法的关系五、DFA与NFA的关系3.6正规表达式和有穷自动机一、正规表达式和正规集的定义二、正规表达式的性质三、正规文法、正规表达式与有穷自动机四、由正规表达式构造确定有穷自动机五、确定有穷自动机的化简3.7词法分析程序的自动生成一、问题的提出二、语言LEX一般描述三、LEX编译程序的实现四、LEX目标程序,40,第三章词法分析,3.1引言一、词法分析基本思想二、词法分析任务三、词法分析方式四、词法分析方法3.2单词的内部编码一、单词二、内部编码3.3正规文法和状态转换图一、正规文法二、状态转换图三、正规文法与状态转换图3.4词法分析程序设计与实现一、源程序的输入二、缓冲区及预处理三、超前搜索四、由词法语法规则画状态转换图五、词法分析程序的设计与实现,3.5正规文法和有穷自动机一、用正规文法描述单词二、由正规文法构造状态转换图三、有穷自动机FA四、有穷自动机和正规文法的关系五、DFA与NFA的关系3.6正规表达式和有穷自动机一、正规表达式和正规集的定义二、正规表达式的性质三、正规文法、正规表达式与有穷自动机四、由正规表达式构造确定有穷自动机五、确定有穷自动机的化简3.7词法分析程序的自动生成一、问题的提出二、语言LEX一般描述三、LEX编译程序的实现四、LEX目标程序,41,第三章词法分析,3.3正规文法和状态转换图一、正规文法二、状态转换图1.定义2.功能三、正规文法与状态转换图1.由正规文法构造状态转换图2.由正规文法状态转换图识别句子（单词）,42,第三章词法分析,3.3正规文法和状态转换图一、正规文法二、状态转换图1.定义2.功能三、正规文法与状态转换图1.由正规文法构造状态转换图2.由正规文法状态转换图识别句子（单词）,43,3.3正规文法和状态转换图一、正规文法在介绍词法分析程序的设计之前，先来看一下正规文法和状态转换图它们是词法分析的理论基础。一、正规文法正规文法就是乔姆斯基(Chomsky)文法分类中的3型文法，如果P中规则形式为：A=aB或A=a其中A,BVN，aVT，则称文法G为右线性文法。如P中规则形式为:A=Ba或A=a，则称文法G为左线性文法。3型文法与词法分析密切相关如：=字母|字母|数字左线性文法又如：=+|-|*|/正规文法,44,第三章词法分析,3.3正规文法和状态转换图一、正规文法二、状态转换图1.定义2.功能三、正规文法与状态转换图1.由正规文法构造状态转换图2.由正规文法状态转换图识别句子（单词）,45,第三章词法分析,3.3正规文法和状态转换图一、正规文法二、状态转换图1.定义2.功能三、正规文法与状态转换图1.由正规文法构造状态转换图2.由正规文法状态转换图识别句子（单词）,46,3.3正规文法和状态转换图二、状态转换图1.定义转换图实际上是一个有限方向图，图中结点代表状态，用圆圈表示。状态之间用箭弧连接，箭弧上标记（字符如x，y）代表射出结（即箭弧始结）状态下可能出现的输入字符.如：,该状态转换图表示在状态1下读入x转到状态2，若在状态1下读入字符y，则转到状态3。,1,X,2,3,Y,47,3.3正规文法和状态转换图二、状态转换图2.功能一个状态转换图可以用于识别（或接受）一定的字符串。例如：识别标识符的转换图如下图所示,0,字母,字母或数字,其他,*,1,48,其中为初态，为终态（双圆圈表示）。这个转换图识别（接受）标识符过程是：（1）从初态开始，若在状态之下输入字符是一个字母则转入状态。（2）在状态之下，若下一个输入字符为字母或数字，则读进它，并重新进入状态1。（3）重复（2），直到状态发现输入字符不再是字母或数字时就进入状态。状是终态，它意味着到此已识别出一个标识符，识别过程宣告终止。终态结上打个星号，表示多读进一个不属于标识符的字符，应把它退还给输入串。（4）如果在开始状态0下，输入字符不是字母，则意味着识别不出标识符按同样的方法，同学们可以考虑一下整数的识别状态转换图及识别过程,49,第三章词法分析,3.3正规文法和状态转换图一、正规文法二、状态转换图1.定义2.功能三、正规文法与状态转换图1.由正规文法构造状态转换图2.由正规文法状态转换图识别句子（单词）,50,第三章词法分析,3.3正规文法和状态转换图一、正规文法二、状态转换图1.定义2.功能三、正规文法与状态转换图1.由正规文法构造状态转换图2.由正规文法状态转换图识别句子（单词）,51,对于一个左线性文法GE：U=a或U=BaU,BVN，aVT（1）设一个开始状态S，SVN（2）对于每一条规则U=a，从状态S向状态U画一条箭弧，标记为aaSU(3)对于每一条规则U=Ba，从状态B向状态U画一条箭弧，标记为aaBU(4)识别符E为状态转换图的终态由以上规则，我们就可以构造一个左线性文法状态转换图。,3.3正规文法和状态转换图三、正规文法与状态转换图1.由正规文法(左线性文法)构造状态转换图,52,例如：设有左线性文法（，），其中：，U，UU由该文法所确定的语言为，根据上述构造状态转换图的规则，该文法状态转换图如下图所示。,53,3.3正规文法和状态转换图三、正规文法与状态转换图2.由正规文法状态转换图识别句子（单词）如：符号串0110是上述文法的句子，因为：从开始状态S出发，读入0转入V，再读入1转入Z，再读入1转入U，最后读入0转入Z，且Z是终态。又如：符号串101001也是该文法的一个句子。实际上这是一个自底向上分析方法进行分析。,由此可以看出正规文法的状态转换图有助于识别正规文法产生的句子。,步骤当前状态x的余留部分1S1010012U010013Z10014U0015Z016V17Z,识别字符串x=101001,句子101001语法树,Z,V,1,Z,U,Z,U,0,0,1,0,1,54,第三章词法分析,3.1引言一、词法分析基本思想二、词法分析任务三、词法分析方式四、词法分析方法3.2单词的内部编码一、单词二、内部编码3.3正规文法和状态转换图一、正规文法二、状态转换图三、正规文法与状态转换图3.4词法分析程序设计与实现一、源程序的输入二、缓冲区及预处理三、超前搜索四、由词法语法规则画状态转换图五、词法分析程序的设计与实现,3.5正规文法和有穷自动机一、用正规文法描述单词二、由正规文法构造状态转换图三、有穷自动机FA四、有穷自动机和正规文法的关系五、DFA与NFA的关系3.6正规表达式和有穷自动机一、正规表达式和正规集的定义二、正规表达式的性质三、正规文法、正规表达式与有穷自动机四、由正规表达式构造确定有穷自动机五、确定有穷自动机的化简3.7词法分析程序的自动生成一、问题的提出二、语言LEX一般描述三、LEX编译程序的实现四、LEX目标程序,55,第三章词法分析,3.1引言一、词法分析基本思想二、词法分析任务三、词法分析方式四、词法分析方法3.2单词的内部编码一、单词二、内部编码3.3正规文法和状态转换图一、正规文法二、状态转换图三、正规文法与状态转换图3.4词法分析程序设计与实现一、源程序的输入二、缓冲区及预处理三、超前搜索四、由词法语法规则画状态转换图五、词法分析程序的设计与实现,3.5正规文法和有穷自动机一、用正规文法描述单词二、由正规文法构造状态转换图三、有穷自动机FA四、有穷自动机和正规文法的关系五、DFA与NFA的关系3.6正规表达式和有穷自动机一、正规表达式和正规集的定义二、正规表达式的性质三、正规文法、正规表达式与有穷自动机四、由正规表达式构造确定有穷自动机五、确定有穷自动机的化简3.7词法分析程序的自动生成一、问题的提出二、语言LEX一般描述三、LEX编译程序的实现四、LEX目标程序,56,第三章词法分析,3.4词法分析程序设计与实现一、源程序的输入二、缓冲区及预处理1、扫描缓冲区2、预处理三、超前搜索1、问题的提出2、工作原理四、由词法语法规则画状态转换图1、语言子集单词符号2、单词的正规文法规则3、构造状态转换图五、词法分析程序的设计与实现,57,第三章词法分析,3.4词法分析程序设计与实现一、源程序的输入二、缓冲区及预处理1、扫描缓冲区2、预处理三、超前搜索1、问题的提出2、工作原理四、由词法语法规则画状态转换图1、语言子集单词符号2、单词的正规文法规则3、构造状态转换图五、词法分析程序的设计与实现,58,3.4词法分析程序设计与实现一、源程序的输入1.内存比较大的情况下,直接输入到内存的一个源程序区(1)一个字符占一个字节(2)词法分析程序从源程序区读入字符2.内存不足的情况下，将源程序以文件的形式存贮在外部介质上，如磁盘、磁带等。可以先在内存中开辟一个大小适宜的缓冲区，这个缓冲区称为输入缓冲区。词法分析程序工作时，先从外部介质上将输入符号串分批读入缓冲区，单词符号的识别可在这个缓冲区中进行.具体处理时还要开辟一个扫描缓冲区。,59,第三章词法分析,3.4词法分析程序设计与实现一、源程序的输入二、缓冲区及预处理1、扫描缓冲区2、预处理三、超前搜索1、问题的提出2、工作原理四、由词法语法规则画状态转换图1、语言子集单词符号2、单词的正规文法规则3、构造状态转换图五、词法分析程序的设计与实现,60,第三章词法分析,3.4词法分析程序设计与实现一、源程序的输入二、缓冲区及预处理1、扫描缓冲区2、预处理三、超前搜索1、问题的提出2、工作原理四、由词法语法规则画状态转换图1、语言子集单词符号2、单词的正规文法规则3、构造状态转换图五、词法分析程序的设计与实现,61,3.4词法分析程序设计与实现二、扫描缓冲区及预处理1.扫描缓冲区（1）定义：扫描缓冲区就是在内存中开辟一部分单元，供识别单词用。注意：扫描缓冲区和缓冲区是不同的，缓冲区是从外存上读入部分字符，而扫描缓冲区仅是为识别单词用。（2）工作原理在扫描缓冲区中一般设两个指示器，一个指向当前正在识别单词开始位置，另一个用于向前搜索寻找单词的终点。不论扫描缓冲区定为多大都不能保证单词符号不会被它的边界所打断，因此，扫描缓冲区最好使用如下所示的一分为二的区域（每半区可容120个字符）：扫描缓冲区1扫描缓冲区2起始指示器搜索指示器,62,1)开始时扫描缓冲区皆为空。2)调用预处理子程序，将120个字符填满扫描缓冲区。并将两个指示器指向扫描缓冲区的第个字符。3)将搜索指示器向后移动,当识别出一个单词之后，搜索指示器已指向下一个单词的第一个字符,然后再将起始指示器移到搜索指示器指向字符,接着搜索指示器又开始扫描第二个单词。当搜索指示器越界时，说明缓冲区中的字符不足一个单词，这时再调用预处理子程序，再将120个字符填满扫描缓冲区，再将搜索指示器扫描缓冲区第个字符。这样，两个扫描缓冲区交替工作。4)一般描缓冲区长度可以存放最长一个单词，即可正常工作；否则，就不能保证单词符号不会被缓冲区边界所打断。,63,3.4词法分析程序设计与实现二、扫描缓冲区及预处理2、预处理预处理目的是将一些无用的空白符、跳格符、回车换行符等编辑性字符剔除掉。其工作原理是每次从缓冲区读入一个字符后，便进行判断，如属于无用字符则将其删除不用，再读下一个字符，直至读出一个有用字符为止。,64,第三章词法分析,3.4词法分析程序设计与实现一、源程序的输入二、缓冲区及预处理1、扫描缓冲区2、预处理三、超前搜索1、问题的提出2、工作原理四、由词法语法规则画状态转换图1、语言子集单词符号2、单词的正规文法规则3、构造状态转换图五、词法分析程序的设计与实现,65,第三章词法分析,3.4词法分析程序设计与实现一、源程序的输入二、缓冲区及预处理1、扫描缓冲区2、预处理三、超前搜索1、问题的提出2、工作原理四、由词法语法规则画状态转换图1、语言子集单词符号2、单词的正规文法规则3、构造状态转换图五、词法分析程序的设计与实现,66,3.4词法分析程序设计与实现三、超前搜索1、问题的提出,所谓超前读字符（也称超前搜索或向前扫描），是指仅向前读取字符，判别该字符是什么，不做别的处理工作。当判明情况以后,再回过头来处理已读过的字符。如：某语句ABCDE:=2,从A开始依次读字符，直到E还不能判断出标识符ABCDE已结束，还需继续读下面的字符，当发现E后字符既不是字母又不是数字时，才确定ABCDE为标识符。又如：如FORTRAN语言，只设关键字（如DO，IF，GOTO等），而无保留字。在语句中，关键字、标号和标识符之间，并无明显的分界符，为了识别这些单词，就要采用超前搜索的方法。,67,（）DO99K=1,10（）DO99K=1.10这两个语句都是正确的语句。语句（）是语句，它是以关键字开头。语句（）是赋值语句，它是以用户自己定义的标识符K开头的。语句（）和（）区别在于等号之后第一个界限符，语句（）是逗号，语句（）是句末号。对于语句（）和（）来说，尽管都以“”两个字符开头，我们不能一见“”就认定是语句。我们必须超前搜索，看看是否有等号，如果有，再向前搜索，若下个界限符是逗点，则是关键字，否则为非关键字，它只是用户定义标识符头两个字母。,例如有以下两个语言的语句：,68,3.4词法分析程序设计与实现三、超前搜索2.工作原理向前搜索由起始指示器和搜索指示器协同工作，搜索指示器一直向前搜索直到可以判断单词类别后再退回原来位置。,69,第三章词法分析,3.4词法分析程序设计与实现一、源程序的输入二、缓冲区及预处理1、扫描缓冲区2、预处理三、超前搜索1、问题的提出2、工作原理四、由词法语法规则画状态转换图1、语言子集单词符号2、单词的正规文法规则3、构造状态转换图五、词法分析程序的设计与实现,70,第三章词法分析,3.4词法分析程序设计与实现一、源程序的输入二、缓冲区及预处理1、扫描缓冲区2、预处理三、超前搜索1、问题的提出2、工作原理四、由词法语法规则画状态转换图1、语言子集单词符号2、单词的正规文法规则3、构造状态转换图五、词法分析程序的设计与实现,71,3.4词法分析程序设计与实现四、由词法规则画状态转换图.语言子集单词符号下表列出了这个语言所有单词符号，以及它们种别编码和内部值。,基本符号种别编码助记符内码值BEGIN1$BEGINEND2$ENDWHILE3$WHILEDO4$SEMI标识符5$ID内部字符串整常数6$INT标准二进制形式;7$SEMT+8$PLUS*9$STAR:=10$ASSIGN=11$LE12$LT:13$COLON,72,3.4词法分析程序设计与实现四、由词法规则画状态转换图2.单词的正规文法规则对于表.中的基本符号（单词）可用下述正规文法规则(左线性）加以描述：标识符字母标识符数字标识符字母整常数数字整常数数字单分界符；双分界符冒号小于号冒号：小于号,73,3.构造状态转换图（1）先构造每一个单词的状态转换图。例如:=字母|字母|数字按照前面所述规则U:=aU:=Ba:=数字|数字,S,U,a,B,U,a,S,标志符,字母,字母/数字,出口,其他符号,S,整常数,数字,数字,出口,非数字,3.4词法分析程序设计与实现四、由词法语法规则画状态转换图,74,（2）将所有单词的状态转换图合并成一张状态转换图。,0,字母,1,3,8,11,字母或数字,*,*,*,*,非字母或数字,非数字,非,非,数字,数字,;,+,*,:,其他,75,第三章词法分析,3.4词法分析程序设计与实现一、源程序的输入二、缓冲区及预处理1、扫描缓冲区2、预处理三、超前搜索1、问题的提出2、工作原理四、由词法语法规则画状态转换图1、语言子集单词符号2、单词的正规文法规则3、构造状态转换图五、词法分析程序的设计与实现,76,第三章词法分析,3.4词法分析程序设计与实现一、源程序的输入二、缓冲区及预处理1、扫描缓冲区2、预处理三、超前搜索1、问题的提出2、工作原理四、由词法语法规则画状态转换图1、语言子集单词符号2、单词的正规文法规则3、构造状态转换图五、词法分析程序的设计与实现,77,3.4词法分析程序设计与实现五、词法分析程序的实现有了状态转换图很容易写出词法分析程序，下面考虑把词法分析程序作为一个子程序来构造，每当语法分析程序需要一个单词符号时就调用这个子程序。在此对保留字不专设状态转换图，只作标识符处理识别出标识符后，再去查保留字表，以确定是保留字还是普通标识符。下面我们根据前述的状态转换图来构造由表3.2给出的PASCAL子语言的词法分析程序。首先我们引入一些变量和过程：（）字符变量，它存放着新读入的源程序字符。（）字符数组，它存放构成单词符号的字符串。（）过程，读入下一个源程序字符至中，并把字符指针后移一个位置。,78,（）过程GETNBC，先检查CHAR中是否为空白字符，若是则反复调用GETCHAR直至CHAR中读入的是一个非空白字符。（）过程CONCAT，将CHAR字连接到TOKEN后面。例如，假定TOKEN原来的值为STUDENT，而CHAR中存放着，则调用过程CONCAT之后，TOKEN的新值为STUDENTS。（）布尔函数LETTER，若CHAR中字符为字母则返回TRUE，否则返回FALSE。（）布尔函数DIGIT，若CHAR中字符为数字则返回TRUE，否则返回FALSE。（）函数RESERVE，由TOKEN字符串查保留字表，若TOKEN中字符串为保留字则返回其种别编码，否则返回值为。（）过程RETRACT，将字符指针向前移一个位置，CHAR置空白字符。,79,现在我们可以写出前面所述的子语言的词法分析程序：Start:token:=;置为空串getchar;getnbc;CASEcharOFAZ:BEGINWHILEletterORdigitDOBEGINConcat;getchar;END；retract；c:=reserveIFc=0THENreturn($ID,token)ELSEreturn(c,)END；,80,09:WHILEdigitDOBEGINConcat；getchar；END；retract；return（INT,DTB）END；;:return($SEMI，)；:return（$PLUS，）；*:return($STAR，）；,81,:BEGIN；getchar；IFcharTHENreturn（$ASSIGN,）；ELSEretract；return($COLON,)END；:BEGINgetchar；charTHENreturn($LE,)；ELSEretract;return($LT,)ENDENDOFCASE；ERROR；出错处理GOTOstart；返回开始处，进行下一个单词的识别,82,第三章词法分析,3.1引言一、词法分析基本思想二、词法分析任务三、词法分析方式四、词法分析方法3.2单词的内部编码一、单词二、内部编码3.3正规文法和状态转换图一、正规文法二、状态转换图三、正规文法与状态转换图3.4词法分析程序设计与实现一、源程序的输入二、缓冲区及预处理三、超前搜索四、由词法语法规则画状态转换图五、词法分析程序的设计与实现,3.5正规文法和有穷自动机一、用正规文法描述单词二、由正规文法构造状态转换图三、有穷自动机FA四、有穷自动机和正规文法的关系五、DFA与NFA的关系3.6正规表达式和有穷自动机一、正规表达式和正规集的定义二、正规表达式的性质三、正规文法、正规表达式与有穷自动机四、由正规表达式构造确定有穷自动机五、确定有穷自动机的化简3.7词法分析程序的自动生成一、问题的提出二、语言LEX一般描述三、LEX编译程序的实现四、LEX目标程序,83,第三章词法分析,3.1引言一、词法分析基本思想二、词法分析任务三、词法分析方式四、词法分析方法3.2单词的内部编码一、单词二、内部编码3.3正规文法和状态转换图一、正规文法二、状态转换图三、正规文法与状态转换图3.4词法分析程序设计与实现一、源程序的输入二、缓冲区及预处理三、超前搜索四、由词法语法规则画状态转换图五、词法分析程序的设计与实现,3.5正规文法和有穷自动机一、用正规文法描述单词二、由正规文法构造状态转换图三、有穷自动机FA四、有穷自动机和正规文法的关系五、DFA与NFA的关系3.6正规表达式和有穷自动机一、正规表达式和正规集的定义二、正规表达式的性质三、正规文法、正规表达式与有穷自动机四、由正规表达式构造确定有穷自动机五、确定有穷自动机的化简3.7词法分析程序的自动生成一、问题的提出二、语言LEX一般描述三、LEX编译程序的实现四、LEX目标程序,84,第三章词法分析,3.5正规文法和有穷自动机一、用正规文法描述单词二、由正规文法构造状态转换图1.由右线性文法构造状态转换图2.左线性文法和右线性文法之间的关系三、有穷自动机FA1.确定有穷自动机DFA2.非确定有限自动机NFA四、有穷自动机和正规文法的关系1.两个定理2.由正规文法构造有穷自动机（FA）M3.由有穷自动机(FA)M构造正规文法(右线性文法）五、DFA与NFA的关系,85,第三章词法分析,3.5正规文法和有穷自动机一、用正规文法描述单词二、由正规文法构造状态转换图1.由右线性文法构造状态转换图2.左线性文法和右线性文法之间的关系三、有穷自动机FA1.确定有穷自动机DFA2.非确定有限自动机NFA四、有穷自动机和正规文法的关系1.两个定理2.由正规文法构造有穷自动机（FA）M3.由有穷自动机(FA)M构造正规文法(右线性文法）五、DFA与NFA的关系,86,3.5正规文法和有穷自动机一、用正规文法描述单词形式语言基础知识告诉我们，每一种文法所产生的语言都有对应的自动机0型语言图灵机1型语言线性界限自动机2型语言下推自动机3型语言有限自动机3型语言也称正规文法，用正规文法可以对单词进行描述。正规文法分为左线性文法，如：U:=BaU:=a，右线性文法，如：U:=aBU:=a本节将运用有限自动机对正规文法进一步研究，包括有限自动机对词法分析程序的构造和自动生成的作用。在上一节，我们已用左线性文法描述了语言子集单词在这里就不再重复了。,87,第三章词法分析,3.5正规文法和有穷自动机一、用正规文法描述单词二、由正规文法构造状态转换图1.由右线性文法构造状态转换图2.左线性文法和右线性文法之间的关系三、有穷自动机FA1.确定有穷自动机DFA2.非确定有限自动机NFA四、有穷自动机和正规文法的关系1.两个定理2.由正规文法构造有穷自动机（FA）M3.由有穷自动机(FA)M构造正规文法(右线性文法）五、DFA与NFA的关系,88,第三章词法分析,3.5正规文法和有穷自动机一、用正规文法描述单词二、由正规文法构造状态转换图1.由右线性文法构造状态转换图2.左线性文法和右线性文法之间的关系三、有穷自动机FA1.确定有穷自动机DFA2.非确定有限自动机NFA四、有穷自动机和正规文法的关系1.两个定理2.由正规文法构造有穷自动机（FA）M3.由有穷自动机(FA)M构造正规文法(右线性文法）五、DFA与NFA的关系,89,对于一个右线性文法GE：U=a或U=aBU,BVN，aVT（1）设一个终止状态Q，QVN（2）对于中每一条形如Ua的文法规则，从状态U向终态引一条箭弧线并标记符号a。aUQ（3）对中每一条形如UaB的文法规则，则从状态U向状态引一条箭弧线并标记符号a。aUB,3.5正规文法和有穷自动机二、由正规文法构造状态转换图1由右线性文法构造状态转换图关于左线性文法到状态转换图的转换，在前面已经介绍过。在这里主要介绍一下如何根据右线性文法来构造状态转换图以及左右线性文法的关系。,90,(4)对于规则U=（空符号），从状态U向状态Q画一条弧线，标记为.(5)文法识别符号是初始状态。（左线性文法中识别符号是终态）注：根据左线性文法对应的状态转换图分析文法的句子是一种自底向上的分析方法；但是，根据右线性文法对应的状态转换图分析文法的句子却是一种自上而下的分析方法。例设有关于单词无符号数的文法（，），其中:，d，,91,dEdFdd这里d表示数字，E，F，表示空字符，表示无符号数，其一般形式为：dd.ddEFdd显然，这是一个右线性文法，根据上述构造状态转换图的规则，该文法状态转换图如下图所示。,N1,Q,E,N2,N3,N4,N5,N6,N7,d,d,d,d,d,d,E,E,F,.,.,dEdEd,92,有了状态转换图以后，根据它识别单词就很容易了。例如对于字符串34.56，从初始状态开始，游历状态图，有：22.（到达终态）可见字符串34.56为状态转换图所接受，故34.56是该文法的一个句子。,93,3.5正规文法和有穷自动机二、由正规文法构造状态转换图2.左线性文法和右线性文法之间的关系左线性文法和右线性文法之间存在一定关系，下面给出形式语言中的两条定理。定理1：对于每一个左线性文法GL都存在一个右线性文法GR，有L（GR）=L（GL）定理2：对于每一个右线性文法GR都存在一个左线性文法GL，有L（GL）=L（GR）这两个定理说明，GL和GR是等价的，也就是说，给定一个右线性文法可以构造对应的左线性文法;同样,给一个左线性文法也可以构造一个右线性文法.,94,右线性文法的产生式SaSa1A1A1a2A2A2a3,左线性文法的产生式SaA1a1A2A1a2SA2a3,在此我们不作详细证明，仅给出他们之间的等价关系：,95,上面的等价关系在本例题中具体化为:左线性文法产生式SA0SB1A0A1B0B1,右线性文法产生式A0B1S0AS1AS0BS1B,例如:设左线性文法（，S）,其中:=A,B,S=0,1P:SA0|B1A0|1B0|1则L(GL)=00,01,10,11.,96,则右线性文法（，S）,其中:=A,B,S=0,1P:S0A|1A|0B|1BA0B1则L(GR)=00,01,10,11.所以L(GL)=L(GR),说明左线性文法和右线性文法