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

1编译原理CompilerPrinciples徐小龙[e-mail]南京邮电大学.计算机学院第三章词法分析comPilingrunningProgramming教材：《编译技术原理及其实现方法》王汝传编著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正规表达式和有穷自动机一、正规表达式和正规集