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

1 编译原理CompilerPrinciples 第三章词法分析 教材 编译技术原理及其实现方法 王汝传编著 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 26ELSE4 34 38 单词内部编码 35 36 37单词地址码a1200b1201c1202d1203b20401003101 语句 ifa1 0thenb1 c1 3 elseb 0经词法分析变成如下的内部编码形式 Ifa1 01222004343100thenb1 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 B VN a VT 则称文法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 对于一个左线性文法G E U a或U BaU B VN a VT 1 设一个开始状态S S VN 2 对于每一条规则U a 从状态S向状态U画一条箭弧 标记为aaSU 3 对于每一条规则U Ba 从状态B向状态U画一条箭弧 标记为aaBU 4 识别符E为状态转换图的终态由以上规则 我们就可以构造一个左线性文法状态转换图 3 3正规文法和状态转换图三 正规文法与状态转换图1 由正规文法 左线性文法 构造状态转换图 52 例如 设有左线性文法 其中 U U U 由该文法所确定的语言为 根据上述构造状态转换图的规则 该文法状态转换图如下图所示 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 LE 12 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 CASEcharOF A Z BEGIN WHILEletterORdigitDO BEGIN Concat getchar END retract c reserve IFc 0THENreturn ID token ELSEreturn c END 80 0 9 WHILEdigitDO BEGIN Concat getchar END retract return INT DTB END return SEMI return PLUS return STAR 81 BEGIN getchar IFchar THENreturn ASSIGN ELSEretract return COLON END BEGIN getchar char THENreturn LE ELSEretract return LT END ENDOFCASE 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 对于一个右线性文法G E U a或U aBU B VN a VT 1 设一个终止状态Q Q VN 2 对于 中每一条形如U a的文法规则 从状态U向终态 引一条箭弧线并标记符号a aUQ 3 对 中每一条形如U aB的文法规则 则从状态U向状态 引一条箭弧线并标记符号a aUB 3 5正规文法和有穷自动机二 由正规文法构造状态转换图1 由右线性文法构造状态转换图关于左线性文法到状态转换图的转换 在前面已经介绍过 在这里主要介绍一下如何根据右线性文法来构造状态转换图以及左右线性文法的关系 90 4 对于规则U 空符号 从状态U向状态Q画一条弧线 标记为 5 文法识别符号是初始状态 左线性文法中识别符号是终态 注 根据左线性文法对应的状态转换图分析文法的句子是一种自底向上的分析方法 但是 根据右线性文法对应的状态转换图分析文法的句子却是一种自上而下的分析方法 例设有关于单词 无符号数 的文法 其中 d 91 d E d F d d 这里d表示数字 E F 表示空字符 表示无符号数 其一般形式为 d d d dEFd d显然 这是一个右线性文法 根据上述构造状态转换图的规则 该文法状态转换图如下图所示 N1 Q E N2 N3 N4 N5 N6 N7 d d d d d d E E F d E d E d 92 有了状态转换图以后 根据它识别单词就很容易了 例如对于字符串34 56 从初始状态 开始 游历状态图 有 2 2 到达终态 可见字符串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 1 P S A0 B1A 0 1B 0 1则L GL 00 01 10 11 96 则右线性文法 S 其中 A B S 0 1 P S 0A 1A 0B 1BA 0B 1则L GR 00 01 10 11 所以L GL L GR 说明左线性文法和右线性文法是等价的 97 第三章词法分析 3 5正规文法和有穷自动机一 用正规文法描述单词二 由正规文法构造状态转换图1 由右线性文法构造状态转换图2 左线性文法和右线性文法之间的关系三 有穷自动机FA1 确定有穷自动机DFA2 非确定有限自动机NFA四 有穷自动机和正规文法的关系1 两个定理2 由正规文法构造有穷自动机 FA M3 由有穷自动机 FA M构造正规文法 右线性文法 五 DFA与NFA的关系 98 第三章词法分析 3 5正规文法和有穷自动机一 用正规文法描述单词二 由正规文法构造状态转换图1 由右线性文法构造状态转换图2 左线性文法和右线性文法之间的关系三 有穷自动机FA1 确定有穷自动机DFA2 非确定有限自动机NFA四 有穷自动机和正规文法的关系1 两个定理2 由正规文法构造有穷自动机 FA M3 由有穷自动机 FA M构造正规文法 右线性文法 五 DFA与NFA的关系 99 3 5正规文法和有穷自动机三 有穷自动机FA1 确定有穷自动机DFA有穷自动机是对状态转换图进一步形式化描述 这对词法分析程序的构造 特别是对词法分析程序的自动生成将带来很大的方便 实际上 有穷自动机是1953年由Huffman提出一种数学模型 主要用于研究时序电路 生物网络神经等 如 电梯控制就是有穷自动机的典型应用 另外 我们在人工智能 形式语言理论研究也要应用有穷自动机 100 是状态有穷的非空集合 中每一个元素是一个状态 是一个有穷输入字母表 中的每一个元素称为输入字符 是 到 的单值映射 或函数 即 q a pq p K a 它表示 当前状态为q 输入字符为a时 将转到下一状态p p是q的一个后继状态 由于映射是单值 所以称确定有穷自动机 为开始状态 是唯一一个初态 是终止状态集合 是 的子集 确定有穷自动机DFA DeterministicFiniteAutomaton 1 形式定义一个确定的有穷自动机 是一个五元组 即 其中 101 有一条输入带 带子上有一个个单元 每个单元记录VT中一个字符 带子向右无限延伸有限状态控制器由状态集K中各种状态组成 形成有限控制器 初始状态为S输入读头 在有限控制器作用下可依次读入符号 在状态S下读入符号a1 改变状态到P1 即 S a1 P1 在P1状态下再读入符号a2 改变状态到P2 即 P1 a2 P2 在该识别过程中 状态的改变由有限控制器根据状态转换函数来决定 2 有穷自动机的物理模型有穷自动机的物理模型有助于更好地理解有穷自动机的操作过程 如图 a1a2a3 有限控制器 102 一个用有穷自动机的原理对电梯运行控制的例子 乘客要求层号 即输入信号 电梯当前所处的层数及运动方向 即状态 状态的变化 即由当前的状态和信号到下一个状态 103 例设 0 1 2 3 a b M 0 3 其中 a b 状态转换函数 0 a 0 b a b a b a 3 b 初始状态 终止状态集 104 3 状态转换图及