第三章 词法分析(1).ppt

南京邮电大学计算机学院蒋凌云 教材：编译技术原理及其实现方法王汝传 编著编编 译译 原原 理理 Compiler Principles1 1 第三章 词 法 分 析3.1 3.1 引言引言 一、词法分析基本思想 二、词法分析任务 三、词法分析方式 四、词法分析方法3.2 3.2 单词的内部编码单词的内部编码 一、单词 二、内部编码3.3 3.3 正规文法和状态转换图正规文法和状态转换图 一、正规文法 二、状态转换图 三、正规文法与状态转换图3.4 3.4 词法分析程序设计与实现词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理 三、超前搜索 四、由词法语法规则画状态转换图 五、词法分析程序的设计与实现3.5 3.5 正规文法和有穷自动机正规文法和有穷自动机 一、用正规文法描述单词 二、由正规文法构造状态转换图 三、有穷自动机FA 四、有穷自动机和正规文法的关系 五、DFA与NFA的关系3.6 3.6 正规表达式和有穷自动机正规表达式和有穷自动机 一、正规表达式和正规集的定义一、正规表达式和正规集的定义 二、正规表达式的性质二、正规表达式的性质 三、正规文法、正规表达式与有穷自动机三、正规文法、正规表达式与有穷自动机 四、由正规表达式构造确定有穷自动机四、由正规表达式构造确定有穷自动机 五、确定有穷自动机的化简五、确定有穷自动机的化简3.7 3.7 词法分析程序的自动生成词法分析程序的自动生成 一、问题的提出一、问题的提出 二、语言二、语言LEXLEX一般描述一般描述 三、三、LEXLEX编译程序的实现编译程序的实现 四、四、LEXLEX目标程序目标程序2 2 第三章 词 法 分 析3.1 3.1 引言引言 一、词法分析基本思想 二、词法分析任务 三、词法分析方式 四、词法分析方法3.2 3.2 单词的内部编码单词的内部编码 一、单词 二、内部编码3.3 3.3 正规文法和状态转换图正规文法和状态转换图 一、正规文法 二、状态转换图 三、正规文法与状态转换图3.4 3.4 词法分析程序设计与实现词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理 三、超前搜索 四、由词法语法规则画状态转换图 五、词法分析程序的设计与实现3.5 3.5 正规文法和有穷自动机正规文法和有穷自动机 一、用正规文法描述单词 二、由正规文法构造状态转换图 三、有穷自动机FA 四、有穷自动机和正规文法的关系 五、DFA与NFA的关系3.6 3.6 正规表达式和有穷自动机正规表达式和有穷自动机 一、正规表达式和正规集的定义 二、正规表达式的性质 三、正规文法、正规表达式与有穷自动机 四、由正规表达式构造确定有穷自动机 五、确定有穷自动机的化简3.7 3.7 词法分析程序的自动生成词法分析程序的自动生成 一、问题的提出 二、语言LEX一般描述 三、LEX编译程序的实现 四、LEX目标程序3 3 第三章 词 法 分 析3.1 引言引言 一、一、词法分析基本思想词法分析基本思想 二、词法分析任务二、词法分析任务 1.1.识别单词识别单词 2.2.消除无用字符消除无用字符 3.3.变成内部编码变成内部编码 4.4.建立各种表格建立各种表格 5.5.分配存贮单元（静态变量）分配存贮单元（静态变量）6.6.进行词法检查进行词法检查 三、词法分析方式三、词法分析方式 1.1.将词法分析和语法分析程序分开将词法分析和语法分析程序分开 2.2.将词法分析程序编写成一个独立子程序将词法分析程序编写成一个独立子程序 四、词法分析方法四、词法分析方法 1.1.直接分析方法直接分析方法 2.2.状态矩阵法状态矩阵法4 43.1 3.1 引引 言言经过第一章的学习，我们已经初步了解了编译过程及各经过第一章的学习，我们已经初步了解了编译过程及各经过第一章的学习，我们已经初步了解了编译过程及各经过第一章的学习，我们已经初步了解了编译过程及各阶段的功能，从本章开始我门将详细叙述各阶段是如何阶段的功能，从本章开始我门将详细叙述各阶段是如何阶段的功能，从本章开始我门将详细叙述各阶段是如何阶段的功能，从本章开始我门将详细叙述各阶段是如何工作的。首先来看一下工作的。首先来看一下工作的。首先来看一下工作的。首先来看一下词法分析词法分析词法分析词法分析，这是编译的第一步，这是编译的第一步，这是编译的第一步，这是编译的第一步，也是编译的重点，下面我们将将详细介绍词法分析的方也是编译的重点，下面我们将将详细介绍词法分析的方也是编译的重点，下面我们将将详细介绍词法分析的方也是编译的重点，下面我们将将详细介绍词法分析的方法。法。法。法。源源程程序序词法词法词法词法分析分析分析分析程序程序程序程序语法语法分析分析程序程序语义语义分析分析程序程序中间中间代码代码生成生成代码代码优化优化程序程序目标目标代码代码生成生成目目标标程程序序信信 息息 表表 管管 理理 程程 序序错错 误误 检检 查查 和和 处处 理理 程程 序序5 5 第三章 词 法 分 析3.1 引言引言 一、一、词法分析基本思想词法分析基本思想 二、词法分析任务二、词法分析任务 1.1.识别单词识别单词 2.2.消除无用字符消除无用字符 3.3.变成内部编码变成内部编码 4.4.建立各种表格建立各种表格 5.5.分配存贮单元（静态变量）分配存贮单元（静态变量）6.6.进行词法检查进行词法检查 三、词法分析方式三、词法分析方式 1.1.将词法分析和语法分析程序分开将词法分析和语法分析程序分开 2.2.将词法分析程序编写成一个独立子程序将词法分析程序编写成一个独立子程序 四、词法分析方法四、词法分析方法 1.1.直接分析方法直接分析方法 2.2.状态矩阵法状态矩阵法6 63.1 引言引言 一、一、词法分析基本思想词法分析基本思想 扫描源程序扫描源程序 识别单词识别单词 变成中间程序变成中间程序L1（内部编码）。内部编码）。即从左到右逐个字符地扫描源程序，产生一个个独立的单词，即从左到右逐个字符地扫描源程序，产生一个个独立的单词，并将其改变成等价的中间程序，记为：并将其改变成等价的中间程序，记为：L1。实际上是机器的实际上是机器的 内部编码内部编码符号序列符号序列符号序列符号序列单词序列单词序列单词序列单词序列词词词词法法法法分分分分析析析析7 7 第三章 词 法 分 析3.1 引言引言 一、一、词法分析基本思想词法分析基本思想 二、词法分析任务二、词法分析任务 1.1.识别单词识别单词 2.2.消除无用字符消除无用字符 3.3.变成内部编码变成内部编码 4.4.建立各种表格建立各种表格 5.5.分配存贮单元（静态变量）分配存贮单元（静态变量）6.6.进行词法检查进行词法检查 三、词法分析方式三、词法分析方式 1.1.将词法分析和语法分析程序分开将词法分析和语法分析程序分开 2.2.将词法分析程序编写成一个独立子程序将词法分析程序编写成一个独立子程序 四、词法分析方法四、词法分析方法 1.1.直接分析方法直接分析方法 2.2.状态矩阵法状态矩阵法8 83.1 3.1 引引 言言 二、词法分析任务 1.1.识别单词识别单词 扫描源程序的一个个字符，按照语言的词法规则，识别出扫描源程序的一个个字符，按照语言的词法规则，识别出扫描源程序的一个个字符，按照语言的词法规则，识别出扫描源程序的一个个字符，按照语言的词法规则，识别出各类有独立意义的单词。各类有独立意义的单词。各类有独立意义的单词。各类有独立意义的单词。如：如：如：如：begin begin，procedure procedure，+，5.43 5.43，abcabc等。等。等。等。9 9 第三章 词 法 分 析3.1 引言引言 一、一、词法分析基本思想词法分析基本思想 二、词法分析任务二、词法分析任务 1.1.识别单词识别单词 2.2.消除无用字符消除无用字符 3.3.变成内部编码变成内部编码 4.4.建立各种表格建立各种表格 5.5.分配存贮单元（静态变量）分配存贮单元（静态变量）6.6.进行词法检查进行词法检查 三、词法分析方式三、词法分析方式 1.1.将词法分析和语法分析程序分开将词法分析和语法分析程序分开 2.2.将词法分析程序编写成一个独立子程序将词法分析程序编写成一个独立子程序 四、词法分析方法四、词法分析方法 1.1.直接分析方法直接分析方法 2.2.状态矩阵法状态矩阵法10103.1 3.1 引引 言言 二、词法分析任务二、词法分析任务 2.2.2.2.消除无用字符消除无用字符消除无用字符消除无用字符 对源程序文本进行处理，消除源程序文本中的注释、空对源程序文本进行处理，消除源程序文本中的注释、空对源程序文本进行处理，消除源程序文本中的注释、空对源程序文本进行处理，消除源程序文本中的注释、空格、换行符以及其他一切对语法分析和代码生成均无关格、换行符以及其他一切对语法分析和代码生成均无关格、换行符以及其他一切对语法分析和代码生成均无关格、换行符以及其他一切对语法分析和代码生成均无关的信息。的信息。的信息。的信息。1111 第三章 词 法 分 析3.1 引言引言 一、一、词法分析基本思想词法分析基本思想 二、词法分析任务二、词法分析任务 1.1.识别单词识别单词 2.2.消除无用字符消除无用字符 3.3.变成内部编码变成内部编码 4.4.建立各种表格建立各种表格 5.5.分配存贮单元（静态变量）分配存贮单元（静态变量）6.6.进行词法检查进行词法检查 三、词法分析方式三、词法分析方式 1.1.将词法分析和语法分析程序分开将词法分析和语法分析程序分开 2.2.将词法分析程序编写成一个独立子程序将词法分析程序编写成一个独立子程序 四、词法分析方法四、词法分析方法 1.1.直接分析方法直接分析方法 2.2.状态矩阵法状态矩阵法12123.1 3.1 引引 言言 二、词法分析任务二、词法分析任务 3.3.3.3.变成内部编码变成内部编码变成内部编码变成内部编码 将长度不一、种类不同的单词变成长度统一、格式规整、将长度不一、种类不同的单词变成长度统一、格式规整、将长度不一、种类不同的单词变成长度统一、格式规整、将长度不一、种类不同的单词变成长度统一、格式规整、分类清晰的一种内部机器码表示。分类清晰的一种内部机器码表示。分类清晰的一种内部机器码表示。分类清晰的一种内部机器码表示。1313 第三章 词 法 分 析3.1 引言引言 一、一、词法分析基本思想词法分析基本思想 二、词法分析任务二、词法分析任务 1.1.识别单词识别单词 2.2.消除无用字符消除无用字符 3.3.变成内部编码变成内部编码 4.4.建立各种表格建立各种表格 5.5.分配存贮单元（静态变量）分配存贮单元（静态变量）6.6.进行词法检查进行词法检查 三、词法分析方式三、词法分析方式 1.1.将词法分析和语法分析程序分开将词法分析和语法分析程序分开 2.2.将词法分析程序编写成一个独立子程序将词法分析程序编写成一个独立子程序 四、词法分析方法四、词法分析方法 1.1.直接分析方法直接分析方法 2.2.状态矩阵法状态矩阵法14143.1 3.1 引引 言言 二、词法分析任务二、词法分析任务 4.4.4.4.建立各种表格建立各种表格建立各种表格建立各种表格 在词法分析时，可以根据单词特点建立不同表格，如：在词法分析时，可以根据单词特点建立不同表格，如：在词法分析时，可以根据单词特点建立不同表格，如：在词法分析时，可以根据单词特点建立不同表格，如：名字表（标识符表）：源程序中的标识符集中在表中名字表（标识符表）：源程序中的标识符集中在表中名字表（标识符表）：源程序中的标识符集中在表中名字表（标识符表）：源程序中的标识符集中在表中 常数表常数表常数表常数表 数组向量表、过程表等数组向量表、过程表等数组向量表、过程表等数组向量表、过程表等 界限表：包含了保留字、运算符等界限表：包含了保留字、运算符等界限表：包含了保留字、运算符等界限表：包含了保留字、运算符等1515 第三章 词 法 分 析3.1 引言引言 一、一、词法分析基本思想词法分析基本思想 二、词法分析任务二、词法分析任务 1.1.识别单词识别单词 2.2.消除无用字符消除无用字符 3.3.变成内部编码变成内部编码 4.4.建立各种表格建立各种表格 5.5.分配存贮单元（静态变量）分配存贮单元（静态变量）6.6.进行词法检查进行词法检查 三、词法分析方式三、词法分析方式 1.1.将词法分析和语法分析程序分开将词法分析和语法分析程序分开 2.2.将词法分析程序编写成一个独立子程序将词法分析程序编写成一个独立子程序 四、词法分析方法四、词法分析方法 1.1.直接分析方法直接分析方法 2.2.状态矩阵法状态矩阵法16163.1 3.1 引引 言言 二、词法分析任务二、词法分析任务 5.分配存贮单元（静态变量）分配存贮单元（静态变量）对简单变量、常量及数组进行静态存贮分配对简单变量、常量及数组进行静态存贮分配 静态存贮分配静态存贮分配：在编译时就可以决定应分配内存的大小。：在编译时就可以决定应分配内存的大小。动态存贮分配动态存贮分配：到运行时才进行的存贮分配。：到运行时才进行的存贮分配。如：变界数组、动态变量。如：变界数组、动态变量。静态存贮分配可以在词法分析阶段进行，也可以在语法分析静态存贮分配可以在词法分析阶段进行，也可以在语法分析阶段进行，随具体编译系统而定。阶段进行，随具体编译系统而定。1717 第三章 词 法 分 析3.1 引言引言 一、一、词法分析基本思想词法分析基本思想 二、词法分析任务二、词法分析任务 1.1.识别单词识别单词 2.2.消除无用字符消除无用字符 3.3.变成内部编码变成内部编码 4.4.建立各种表格建立各种表格 5.5.分配存贮单元（静态变量）分配存贮单元（静态变量）6.6.进行词法检查进行词法检查 三、词法分析方式三、词法分析方式 1.1.将词法分析和语法分析程序分开将词法分析和语法分析程序分开 2.2.将词法分析程序编写成一个独立子程序将词法分析程序编写成一个独立子程序 四、词法分析方法四、词法分析方法 1.1.直接分析方法直接分析方法 2.2.状态矩阵法状态矩阵法18183.1 3.1 引引 言言 二、词法分析任务二、词法分析任务 6.6.进行词法检查进行词法检查 将一些单词错误检查出来，将一些单词错误检查出来，如保留字如保留字PROGRAM、VAR；又例如变量是否有说明或是否重复说明等。又例如变量是否有说明或是否重复说明等。1919第三章 词 法 分 析3.1 引言引言 一、一、词法分析基本思想词法分析基本思想 二、词法分析任务二、词法分析任务 1.1.识别单词识别单词 2.2.消除无用字符消除无用字符 3.3.变成内部编码变成内部编码 4.4.建立各种表格建立各种表格 5.5.分配存贮单元（静态变量）分配存贮单元（静态变量）6.6.进行词法检查进行词法检查 三、词法分析方式三、词法分析方式 1.1.将词法分析和语法分析程序分开将词法分析和语法分析程序分开 2.2.将词法分析程序编写成一个独立子程序将词法分析程序编写成一个独立子程序 四、词法分析方法四、词法分析方法 1.1.直接分析方法直接分析方法 2.2.状态矩阵法状态矩阵法2020第三章 词 法 分 析3.1 引言引言 一、一、词法分析基本思想词法分析基本思想 二、词法分析任务二、词法分析任务 1.1.识别单词识别单词 2.2.消除无用字符消除无用字符 3.3.变成内部编码变成内部编码 4.4.建立各种表格建立各种表格 5.5.分配存贮单元（静态变量）分配存贮单元（静态变量）6.6.进行词法检查进行词法检查 三、词法分析方式三、词法分析方式 1.1.将词法分析和语法分析程序分开将词法分析和语法分析程序分开 2.2.将词法分析程序编写成一个独立子程序将词法分析程序编写成一个独立子程序 四、词法分析方法四、词法分析方法 1.1.直接分析方法直接分析方法 2.2.状态矩阵法状态矩阵法21213.1 3.1 引引 言言 三、词法分析方式三、词法分析方式 1.1.将词法分析和语法分析程序分开将词法分析和语法分析程序分开 在多遍扫描的编译程序中，词法分析可以单独作为一遍扫在多遍扫描的编译程序中，词法分析可以单独作为一遍扫描来完成，此时可将词法分析程序的输出放在一个中间文描来完成，此时可将词法分析程序的输出放在一个中间文件上，语法分析程序可以从该文件上取得它的输入。件上，语法分析程序可以从该文件上取得它的输入。词法分析从语法分析词法分析从语法分析独立出来的原因：独立出来的原因：（1 1）便于集中进行语法分析）便于集中进行语法分析 （2 2）便于建立有效词法分析技术）便于建立有效词法分析技术 （3 3）将给语法分析提供更多更详细信息）将给语法分析提供更多更详细信息字符串表示字符串表示字符串表示字符串表示的源程序的源程序的源程序的源程序词法分析程序词法分析程序词法分析程序词法分析程序符号串表示符号串表示符号串表示符号串表示的源程序的源程序的源程序的源程序字符字符单词单词2222第三章 词 法 分 析3.1 引言引言 一、一、词法分析基本思想词法分析基本思想 二、词法分析任务二、词法分析任务 1.1.识别单词识别单词 2.2.消除无用字符消除无用字符 3.3.变成内部编码变成内部编码 4.4.建立各种表格建立各种表格 5.5.分配存贮单元（静态变量）分配存贮单元（静态变量）6.6.进行词法检查进行词法检查 三、词法分析方式三、词法分析方式 1.1.将词法分析和语法分析程序分开将词法分析和语法分析程序分开 2.2.将词法分析程序编写成一个独立子程序将词法分析程序编写成一个独立子程序 四、词法分析方法四、词法分析方法 1.1.直接分析方法直接分析方法 2.2.状态矩阵法状态矩阵法23233.1 3.1 引引 言言 三、词法分析方式三、词法分析方式 2.2.将词法分析程序编写成一个独立子程序将词法分析程序编写成一个独立子程序 在一遍扫描的编译程序中，往往将词法分析编成语法分析的一个子程在一遍扫描的编译程序中，往往将词法分析编成语法分析的一个子程序，供语法分析时随时调用，每调用一次，则从源程序字符串中读出序，供语法分析时随时调用，每调用一次，则从源程序字符串中读出一个具有独立意义的单词。一个具有独立意义的单词。优点：优点：优点：优点：不需要在内存中构造和保留中间文件所以节省内存容量不需要在内存中构造和保留中间文件所以节省内存容量不需要在内存中构造和保留中间文件所以节省内存容量不需要在内存中构造和保留中间文件所以节省内存容量字符串表示字符串表示字符串表示字符串表示的源程序的源程序的源程序的源程序词法分析程序词法分析程序词法分析程序词法分析程序语法分析程序语法分析程序语法分析程序语法分析程序字符字符取一单词取一单词返返 回回2424 第三章 词 法 分 析3.1 引言引言 一、一、词法分析基本思想词法分析基本思想 二、词法分析任务二、词法分析任务 1.1.识别单词识别单词 2.2.消除无用字符消除无用字符 3.3.变成内部编码变成内部编码 4.4.建立各种表格建立各种表格 5.5.分配存贮单元（静态变量）分配存贮单元（静态变量）6.6.进行词法检查进行词法检查 三、词法分析方式三、词法分析方式 1.1.将词法分析和语法分析程序分开将词法分析和语法分析程序分开 2.2.将词法分析程序编写成一个独立子程序将词法分析程序编写成一个独立子程序 四、词法分析方法四、词法分析方法 1.1.直接分析方法直接分析方法 2.2.状态矩阵法状态矩阵法2525 第三章 词 法 分 析3.1 引言引言 一、一、词法分析基本思想词法分析基本思想 二、词法分析任务二、词法分析任务 1.1.识别单词识别单词 2.2.消除无用字符消除无用字符 3.3.变成内部编码变成内部编码 4.4.建立各种表格建立各种表格 5.5.分配存贮单元（静态变量）分配存贮单元（静态变量）6.6.进行词法检查进行词法检查 三、词法分析方式三、词法分析方式 1.1.将词法分析和语法分析程序分开将词法分析和语法分析程序分开 2.2.将词法分析程序编写成一个独立子程序将词法分析程序编写成一个独立子程序 四、词法分析方法四、词法分析方法 1.1.直接分析方法直接分析方法 2.2.状态矩阵法状态矩阵法26263.1 3.1 引引 言言 三、词法分析三、词法分析方法方法 1.1.1.1.直接分析方法直接分析方法直接分析方法直接分析方法 根据词法分析任务编成多个不同独立子程序（如：读符号子根据词法分析任务编成多个不同独立子程序（如：读符号子根据词法分析任务编成多个不同独立子程序（如：读符号子根据词法分析任务编成多个不同独立子程序（如：读符号子 程序、取单词子程序、拼标识符子程序、处理无符号数子程程序、取单词子程序、拼标识符子程序、处理无符号数子程程序、取单词子程序、拼标识符子程序、处理无符号数子程程序、取单词子程序、拼标识符子程序、处理无符号数子程 序），对源程序进行分析加工处理。序），对源程序进行分析加工处理。序），对源程序进行分析加工处理。序），对源程序进行分析加工处理。2727 第三章 词 法 分 析3.1 引言引言 一、一、词法分析基本思想词法分析基本思想 二、词法分析任务二、词法分析任务 1.1.识别单词识别单词 2.2.消除无用字符消除无用字符 3.3.变成内部编码变成内部编码 4.4.建立各种表格建立各种表格 5.5.分配存贮单元（静态变量）分配存贮单元（静态变量）6.6.进行词法检查进行词法检查 三、词法分析方式三、词法分析方式 1.1.将词法分析和语法分析程序分开将词法分析和语法分析程序分开 2.2.将词法分析程序编写成一个独立子程序将词法分析程序编写成一个独立子程序 四、词法分析方法四、词法分析方法 1.1.直接分析方法直接分析方法 2.2.状态矩阵法状态矩阵法28283.13.1 引引 言言 三、词法分析三、词法分析方法方法 2.2.2.2.状态矩阵法状态矩阵法状态矩阵法状态矩阵法 根据一张二维状态矩阵表对源程序进行控制分析。根据一张二维状态矩阵表对源程序进行控制分析。根据一张二维状态矩阵表对源程序进行控制分析。根据一张二维状态矩阵表对源程序进行控制分析。2929 第三章 词 法 分 析3.1 3.1 引言引言 一、词法分析基本思想 二、词法分析任务 三、词法分析方式 四、词法分析方法3.2 3.2 单词的内部编码单词的内部编码 一、单词 二、内部编码3.3 3.3 正规文法和状态转换图正规文法和状态转换图 一、正规文法 二、状态转换图 三、正规文法与状态转换图3.4 3.4 词法分析程序设计与实现词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理 三、超前搜索 四、由词法语法规则画状态转换图 五、词法分析程序的设计与实现3.5 3.5 正规文法和有穷自动机正规文法和有穷自动机 一、用正规文法描述单词 二、由正规文法构造状态转换图 三、有穷自动机FA 四、有穷自动机和正规文法的关系 五、DFA与NFA的关系3.6 3.6 正规表达式和有穷自动机正规表达式和有穷自动机 一、正规表达式和正规集的定义 二、正规表达式的性质 三、正规文法、正规表达式与有穷自动机 四、由正规表达式构造确定有穷自动机 五、确定有穷自动机的化简3.7 3.7 词法分析程序的自动生成词法分析程序的自动生成 一、问题的提出 二、语言LEX一般描述 三、LEX编译程序的实现 四、LEX目标程序3030 第三章 词 法 分 析3.1 3.1 引言引言 一、词法分析基本思想 二、词法分析任务 三、词法分析方式 四、词法分析方法3.2 3.2 单词的内部编码单词的内部编码 一、单词 二、内部编码3.3 3.3 正规文法和状态转换图正规文法和状态转换图 一、正规文法 二、状态转换图 三、正规文法与状态转换图3.4 3.4 词法分析程序设计与实现词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理 三、超前搜索 四、由词法语法规则画状态转换图 五、词法分析程序的设计与实现3.5 3.5 正规文法和有穷自动机正规文法和有穷自动机 一、用正规文法描述单词 二、由正规文法构造状态转换图 三、有穷自动机FA 四、有穷自动机和正规文法的关系 五、DFA与NFA的关系3.6 3.6 正规表达式和有穷自动机正规表达式和有穷自动机 一、正规表达式和正规集的定义 二、正规表达式的性质 三、正规文法、正规表达式与有穷自动机 四、由正规表达式构造确定有穷自动机 五、确定有穷自动机的化简3.7 3.7 词法分析程序的自动生成词法分析程序的自动生成 一、问题的提出 二、语言LEX一般描述 三、LEX编译程序的实现 四、LEX目标程序3131 第三章 词 法 分 析3.2 单词的内部编码 一、单词 二、内部编码 1.单词类别 2.单词自身值 3232 第三章 词 法 分 析3.2 单词的内部编码 一、单词 二、内部编码 1.单词类别 2.单词自身值 3333 3.2 3.2 单词的内部编码单词的内部编码 一、单词这部分内容在第一章中已介绍，在此简单回顾一下这部分内容在第一章中已介绍，在此简单回顾一下。所谓所谓单词单词，是指那些具有独立含义的最小语法单位，是指那些具有独立含义的最小语法单位。单词可分为以下。单词可分为以下几种几种类型类型：（）保留字：（）保留字：PROGRAM,VAR,IF,FOR,AND等等。（）标识符：是用户选来表示常量、变量、类型、过程等名字。（）标识符：是用户选来表示常量、变量、类型、过程等名字。（3）常数：分为整型、实型、布尔型、字符型等，如）常数：分为整型、实型、布尔型、字符型等，如2，3.1416等。等。（）运算符：分为算术运算符（，（）运算符：分为算术运算符（，*，等），逻辑运算符，等），逻辑运算符 （，），关系运算符（，），关系运算符（,=）等。）等。（）界限符：如逗号、分号、括号等。（）界限符：如逗号、分号、括号等。3434 第三章 词 法 分 析3.2 单词的内部编码 一、单词 二、内部编码 1.单词类别 2.单词自身值 3535 对于单词类别可以用整数表示，用来指示单词的种类对于单词类别可以用整数表示，用来指示单词的种类。例。例如上面的例子，我们可以如上面的例子，我们可以用个不同的整数用个不同的整数作为它们单词作为它们单词类别的编码类别的编码。单词的内部编码是单词的内部编码是词法分析的输出形式词法分析的输出形式3.2 3.2 单词的内部编码单词的内部编码 二、内部编码 1.1.单词类别单词类别单词类别单词类别 单词类型单词类型单词类型单词类型单词自身值单词自身值单词自身值单词自身值36363.2 3.2 单词的内部编码单词的内部编码 二、内部编码 2.单词自身值单词自身值 可以是单词某种形式可以是单词某种形式内部编码内部编码，也可以是该单词在某些表格中，也可以是该单词在某些表格中地址码地址码。如第一章所讲，保留字、运算符和界限符用内部固定编码值作为单词如第一章所讲，保留字、运算符和界限符用内部固定编码值作为单词值；标识符取其在标识符表中的地址码值；标识符取其在标识符表中的地址码；常量取其在常数表中的地址；常量取其在常数表中的地址码。码。例如：有下列单词：例如：有下列单词：单词单词 内部编码内部编码 单词单词 内部编码内部编码 IF 002 +025 THEN 003 *026 ELSE 004 0343737 单词单词 内部编码内部编码 （035 ）036 ：=037单词单词 地址码地址码 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 then b1 :=(C1 +3 )else b :=0 1 0022 2004 0343 1001 0032 2015 0375 0352 2024 0243 1015 0361 0042 2045 0373 1023838 第三章 词 法 分 析3.1 3.1 引言引言 一、词法分析基本思想 二、词法分析任务 三、词法分析方式 四、词法分析方法3.2 3.2 单词的内部编码单词的内部编码 一、单词 二、内部编码3.3 3.3 正规文法和状态转换图正规文法和状态转换图 一、正规文法 二、状态转换图 三、正规文法与状态转换图3.4 3.4 词法分析程序设计与实现词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理 三、超前搜索 四、由词法语法规则画状态转换图 五、词法分析程序的设计与实现3.5 3.5 正规文法和有穷自动机正规文法和有穷自动机 一、用正规文法描述单词 二、由正规文法构造状态转换图 三、有穷自动机FA 四、有穷自动机和正规文法的关系 五、DFA与NFA的关系3.6 3.6 正规表达式和有穷自动机正规表达式和有穷自动机 一、正规表达式和正规集的定义 二、正规表达式的性质 三、正规文法、正规表达式与有穷自动机 四、由正规表达式构造确定有穷自动机 五、确定有穷自动机的化简3.7 3.7 词法分析程序的自动生成词法分析程序的自动生成 一、问题的提出 二、语言LEX一般描述 三、LEX编译程序的实现 四、LEX目标程序3939 第三章 词 法 分 析3.1 3.1 引言引言 一、词法分析基本思想 二、词法分析任务 三、词法分析方式 四、词法分析方法3.2 3.2 单词的内部编码单词的内部编码 一、单词 二、内部编码3.3 3.3 正规文法和状态转换图正规文法和状态转换图 一、正规文法 二、状态转换图 三、正规文法与状态转换图3.4 3.4 词法分析程序设计与实现词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理 三、超前搜索 四、由词法语法规则画状态转换图 五、词法分析程序的设计与实现3.5 3.5 正规文法和有穷自动机正规文法和有穷自动机 一、用正规文法描述单词 二、由正规文法构造状态转换图 三、有穷自动机FA 四、有穷自动机和正规文法的关系 五、DFA与NFA的关系3.6 3.6 正规表达式和有穷自动机正规表达式和有穷自动机 一、正规表达式和正规集的定义 二、正规表达式的性质 三、正规文法、正规表达式与有穷自动机 四、由正规表达式构造确定有穷自动机 五、确定有穷自动机的化简3.7 3.7 词法分析程序的自动生成词法分析程序的自动生成 一、问题的提出 二、语言LEX一般描述 三、LEX编译程序的实现 四、LEX目标程序4040 第三章 词 法 分 析 3.3 3.3 正规文法和状态转换图正规文法和状态转换图 一、正规文法一、正规文法 二、状态转换图二、状态转换图 1.1.定义定义 2.2.功能功能 三、正规文法与状态转换图三、正规文法与状态转换图 1.1.由正规文法构造状态转换图由正规文法构造状态转换图 2.2.由正规文法状态转换图识别句子（单词）由正规文法状态转换图识别句子（单词）4141 第三章 词 法 分 析 3.3 3.3 正规文法和状态转换图正规文法和状态转换图 一、正规文法一、正规文法 二、状态转换图二、状态转换图 1.1.定义定义 2.2.功能功能 三、正规文法与状态转换图三、正规文法与状态转换图 1.1.由正规文法构造状态转换图由正规文法构造状态转换图 2.2.由正规文法状态转换图识别句子（单词）由正规文法状态转换图识别句子（单词）4242 3.3 3.3 正规文法和状态转换图正规文法和状态转换图 一、正规文法在介绍词法分析程序的设计之前，先来看一下正规文法和状态转换图在介绍词法分析程序的设计之前，先来看一下正规文法和状态转换图它们是词法分析的理论基础。它们是词法分析的理论基础。一、正规文法一、正规文法 正规文法就是乔姆斯基正规文法就是乔姆斯基(Chomsky)文法分类中的文法分类中的3型文法，如果型文法，如果P中中规则形式为规则形式为：A=a B 或或 A=a其中其中A,BVN，aVT，则称文法则称文法G为右线性文法。如为右线性文法。如P中规则形式为中规则形式为:A=B a 或或 A=a，则称文法则称文法G为左线性文法为左线性文法。3型文法与词法分析密切相关型文法与词法分析密切相关如：如：=字母字母|字母字母|数字数字 左线性文法左线性文法又如：又如：=+|-|*|/正规文法正规文法4343 第三章 词 法 分 析 3.3 3.3 正规文法和状态转换图正规文法和状态转换图 一、正规文法 二、状态转换图 1.定义 2.功能 三、正规文法与状态转换图 1.由正规文法构造状态转换图 2.由正规文法状态转换图识别句子（单词）4444 第三章 词 法 分 析 3.3 3.3 正规文法和状态转换图正规文法和状态转换图 一、正规文法 二、状态转换图 1.定义 2.功能 三、正规文法与状态转换图 1.由正规文法构造状态转换图 2.由正规文法状态转换图识别句子（单词）45453.3 3.3 正规文法和状态转换图正规文法和状态转换图 二、状态转换图二、状态转换图 1.1.定义定义 转换图实际上是一个有限方向图，图中结点代表状态，用圆圈表示。转换图实际上是一个有限方向图，图中结点代表状态，用圆圈表示。状态之间用箭弧连接，箭弧上标记（字符如状态之间用箭弧连接，箭弧上标记（字符如x，y）代表射出结（即箭代表射出结（即箭 弧始结）状态下可能出现的输入字符弧始结）状态下可能出现的输入字符.如：如：该状态转换图表示在状态该状态转换图表示在状态1下下读入读入x转到状态转到状态2，若在状态，若在状态1下读入字符下读入字符y，则转到状态则转到状态3。1 1 1 1X2 2 2 23 3 3 3Y46463.3 3.3 正规文法和状态转换图正规文法和状态转换图 二、状态转换图 2.2.2.2.功能功能功能功能 一个状态转换图可以用于识别（或接受）一一个状态转换图可以用于识别（或接受）一一个状态转换图可以用于识别（或接受）一一个状态转换图可以用于识别（或接受）一 定的字符串。例如：识别标识符的转换图如定的字符串。例如：识别标识符的转换图如定的字符串。例如：识别标识符的转换图如定的字符串。例如：识别标识符的转换图如 下图所示下图所示下图所示下图所示0 0 0 0字母字母字母或数字字母或数字其他其他2 2 2 2*1 1 1 14747 其中为初态，为终态（双圆圈表示）。其中为初态，为终态（双圆圈表示）。这个转换图识别（接受）标识符过程是：这个转换图识别（接受）标识符过程是：（1）从初态开始，若在状态之下输入字符是一个字母则转入状态。从初态开始，若在状态之下输入字符是一个字母则转入状态。（2）在状态之下，若下一个输入字符为字母或数字，则读进它，并重新在状态之下，若下一个输入字符为字母或数字，则读进它，并重新 进入状态进入状态1。（3）重复（重复（2），直到状态发现输入字符不再是字母或数字时就进入），直到状态发现输入字符不再是字母或数字时就进入 状态。状是终态，它意味着到此已识别出一个标识符，识别状态。状是终态，它意味着到此已识别出一个标识符，识别 过程宣告终止。过程宣告终止。终态结上打个星号，表示多读进一个不属于标识符的字符，终态结上打个星号，表示多读进一个不属于标识符的字符，应把它退还给输入串应把它退还给输入串。（4）如果在开始状态如果在开始状态0下，输入字符不是字母，则意味着识别不出标识符下，输入字符不是字母，则意味着识别不出标识符 按同样的方法，同学们可以考虑一下整数的识别状态转换图及识别过程按同样的方法，同学们可以考虑一下整数的识别状态转换图及识别过程4848(1)=(2)=(3)=(4)=0 (5)=1(6)=2(7)=3(8)=4 (9)=5 (10)=6(11)=7 (12)=8(13)=94949 第三章 词 法 分 析 3.3 3.3 正规文法和状态转换图正规文法和状态转换图 一、正规文法 二、状态转换图 1.定义 2.功能 三、正规文法与状态转换图 1.由正规文法构造状态转换图 2.由正规文法状态转换图识别句子（单词）5050