程序设计语言 编译原理(第三版)第3章

第 章词法分析 任务 从左至右逐个字符地对源程序进行扫描 产生一个个的单词符号 把作为字符串的源程序改造成为单词符号串 3 1对于词法分析器的要求 3 2词法分析器的设计 3 3正规表达式与有限自动机 3 4词法分析器的自动产生 略 1 3 1对于词法分析器的要求一 功能和输出形式二 接口设计 2 对于词法分析器的要求 一 功能和输出形式 功能 输入源程序 输出单词符号 单词符号的分类 关键字 由程序语言定义的具有固定意义的标识符 也称为保留字或基本字 例如 Pascal语言中beginendifwhile等 标识符 用来表示各种名字 如变量名 数组名 过程名等 常数 整型 实型 布尔型 文字型等例 1003 14159truesample 运算符 界符 等 3 输出的单词符号形式二元式 单词种别 单词符号的属性值 对于词法分析器的要求 单词符号的编码 标识符 一般统归为一种常数 常按整型 实型 布尔型等分类关键字 全体视为一种 一字一种运算符 一符一种界符 一符一种 通常用 整数编码 单词符号的特征或特性 4 例 考虑下述 代码段 while i j i 对于词法分析器的要求 经词法分析器处理后 它将被转换为如下的单词符号序列 5 对于词法分析器的要求 二 接口设计 词法分析器作为一个独立的子程序 但并不一定作为独立的一遍 优点 使整个编译程序的结构更简洁 清晰和条理化 6 3 2词法分析器的设计一 输入和预处理二 单词符号的识别三 状态转换图及其实现 7 预处理 剔掉空白符 跳格符 回车符 换行符 注解部分等 一 输入 预处理 词法分析器的设计 原因 编辑性字符除了出现在文字常数中之外 在别处的任何出现都无意义 注解部分不是程序的必要组成部分 它的作用仅在于改善程序的易读性和易理解性 8 每当词法分析器调用时 就处理出一串确定长度 如120个字符 的输入字符 并将其装进词法分析器所确定的扫描缓冲区中 预处理子程序 词法分析器的设计 9 图 源程序输入缓冲区的对半互补结构 词法分析器的设计 10 二 单词符号的识别 超前搜索1 关键字的识别 FORTRAN语言的需要超前搜索 2 标识符的识别 在程序中标识符的出现都后跟着算符或界符 3 常数的识别 多数语言算术常数的表示大体相似 对它们的识别也是很直接的 但对于某些语言的常数的识别也需用超前搜索的方法 逻辑常数和用引号括起来的字符串常数很容易识别 4 算符和界符的识别 应将那些由多个字符复合成的算符和界符拼合成一个单词符号 因为这些字符串是不可分的整体 若分划开来 便失去了原来的意义 需用超前搜索的方法 词法分析器的设计 11 三 状态转换图及其实现 1 状态转换图及其示例状态转换图 有限方向图 结点 代表状态 用圆圈表示 状态之间用弧连接 箭弧上的标记 字符 代表在射出结点 即始结点 状态下可能出现的输入字符或字符类 一张转换图只包含有限个状态 即有限个结点 其中一个为初态 而且实际上至少要有一个终态 用双圈表示 词法分析器的设计 12 例 例 课本42页表3 1 43页图3 3 词法分析器的设计 13 2 状态转换图的实现实现方法 用程序实现 让每个状态结点对应一小段程序 A 变量和过程说明ch字符变量 存放最新读进的源程序字符 strToken字符数组 存放构成单词符号的字符串 GetChar子程序过程 将下一输入字符读到ch中 搜索指示器前移一字符位置 GetBC子程序过程 检查ch中的字符是否为空白 若是 则调用GetChar直至ch中进入一个非空白字符 Concat子程序过程 将ch中的字符连接到strToken之后 词法分析器的设计 14 IsLetter和IsDigit布尔函数过程 它们分别判断ch中的字符是否为字母和数字 Reserve整型函数过程 对strToken中的字符串查找保留字表 若它是一个保留字则返回它的编码 否则返回0值 假定0不是保留字的编码 Retract子程序过程 将搜索指示器回调一个字符位置 将ch置为空白字符 InsertId整型函数过程 将strToken中的标识符插入符号表 返回符号表指针 InsertConst整型函数过程 将strToken中的常数插入常数表 返回常数表指针 词法分析器的设计 15 B 示例小程序 图中结点i所对应的程序段可表示为 GetChar if IsLetter 状态j的对应程序段 elseif IsDigit 状态k的对应程序段 elseif ch 状态l的对应程序段 else 错误处理 图中结点i所对应的程序段可表示为 GetChar while IsLetter orIsDigit GetChar 状态j的对应程序段 词法分析器的设计 16 C 示例大程序课本43页图3 3 45 46页 词法分析器的设计 17 3 3正规表达式与有限自动机一 单词符号的描述1 正规式与正规集2 正规文法二 有限自动机1 3 NFA与DFA的等价4 DFA的化简三 正规式与有限自动机的等价性四 正规文法与有限自动机的等价性 18 正规表达式与有限自动机 一 单词符号的描述 1 正规式与正规集 1 递归定义 都是 上的正规式 正规集 和 正规式 正规集 正规式 正规集 和 那么 和 也都是正规式 正规集 和 仅由有限次使用上述三步骤而得到的表达式才是 上的正规式 仅由这些正规式所表示的字集才是 上正规集 19 正规表达式与有限自动机 例题 令 下面是 上的正规式和相应的正规集 正规式ba a a b a b aa bb a b 正规集 上所有以b为首后跟任意多个a的字 上所有以a为首的字 上所有含有两个相继的a或两个相继的b的字 20 正规表达式与有限自动机 正规式 A B A B 0 1 0 1 0 1 令 则 一个正规式的正规集与之完全等价 只是表达形式不同 正规集 上的 标识符 的全体 上的 数 的全体 21 正规表达式与有限自动机 2 运算 或 表示从各选择对象中选择 连接积 表示 连接 起来 闭包 任意有限次的自重复连接 22 正规表达式与有限自动机 例题 L r s L rs L a b c B L a b L a b C a bc a b c ab c d ab c d L r L s r s r s L r L s rs L a b L c a b c ac bc a b aa ab ba bb a b bb bbb 23 3 等价 若两个正规式所表示的正规集相同 则认为二者等价 两个等价的正规式 和 记为 正规表达式与有限自动机 例 b ab ba b a b a b 24 令 均为正规式 则 交换律 结合律 结合律 U V W UV UW 分配律 V W U VU WU U U UU U U U 正规表达式与有限自动机 25 例题 已知字母表 a b c 试求在该字母表上的仅包括一个b的所有串的集合相对应的正规式 正规表达式与有限自动机 B 已知字母表 a b c 若集合是包括了最多一个b的所有串 求其相应的正规式 a c b a c a c a c b a c 26 正规表达式与有限自动机 1 正规文法的形式左线性文法 任何产生式为A B 或A 其中 VT A B VN右线性文法 任何产生式为A B或A 其中 VT A B VN 2 描述能力正规文法所描述的是 VN VT 上的正规集 多数程序设计语言的单词的词法都能用正规文法来描述 2 正规文法 单词符号 27 正规表达式与有限自动机 3 例题例1 程序设计语言中的几类单词可用下述规则描述 标识符 字母数字 字母数字 字母数字 字母数字 无符号整数 无符号整数 运算符 等号 等号 等号 界符 中的任一英文字母 中的任一数字 28 正规表达式与有限自动机 二 有限自动机FA FiniteAufomofa 1 定义 DFAM是一个五元式M S S0 F S 有限集 其中的每个元素称为一个状态 有穷字母表 其中的每个元素称为一个输入字符 S S 即 状态s S a S a 唯一的确定下一状态 S a S 当现行状态为S 输入字符为a时 将转换到下一状态S S的一个后继状态s0 S 唯一的初态F S 是一个终态集 可空 1 确定有限自动机DFA 29 正规表达式与有限自动机 2 DFA的两种表达方式 A 状态转换矩阵 例 DFAM 0 1 2 3 a b 0 3 其中 为 0 a 1 0 b 2 1 a 3 1 b 2 2 a 1 2 b 3 3 a 3 3 b 3 30 则其状态转换矩阵为 正规表达式与有限自动机 31 B 状态转换图 正规表达式与有限自动机 DFAMm个状态 图中有m个状态结点n个字符 每个结点顶多有n条箭弧射出每条箭弧用 中的一个不同输入字符作标记整张图含有唯一的一个初态结点和若干个 可为0 终态结点 32 正规表达式与有限自动机 3 识别 读出 接受 对于任何 中的任何字 若存在一条从初态结点到某一终态结点的通路 且这条通路上所有弧的标记符连接成的字等于 则称 可为DFAM所识别 接受 读出 若M的初态结点同时又是终态结点 则空字 可为M所识别 接受 DFAM所能识别的字的全体记为L M 若一个DFAM的输入字母表为 则称M是 上的一个DFA 33 正规表达式与有限自动机 4 定理 上的一个字集V 是正规的 当且仅当存在 上的DFAM 使得V L M 34 正规表达式与有限自动机 2 非确定有限自动机 NFA 1 一个NFA是一个五元式M S S0 F 35 正规表达式与有限自动机 2 状态转换图 注 1 每条弧用 中的一个字 可以是空字 作为输入字 2 整张图至少含有一个初态结点以及若干个 可为0个 终态结点 3 某些结点既可为初态结点也可为终态结点 36 正规表达式与有限自动机 3 识别 读出 接受 对于 中的任何一个 若存在一条从某一初态结点到某一终态结点的通路 且这条通路上所有弧的标记字依序连接成的字 忽略那些标记为 的弧 等于 则称 可为NFAM所识别 读出 接受 若M的某些结点既是初态结点又是终态结点 或者存在一条从某个初态结点到某个终态结点的 通路 则空字 可为M所接受 37 正规表达式与有限自动机 DFA与NFA的区别 1 NFA可有若干个开始状态 而DFA只有一个 2 DFA的映像为 S SNFA的映像为 S 2S 结论 DFA是NFA的特例 38 正规表达式与有限自动机 3 正规式 NFA DFA 1 正规式 NFA 引进新的初态结点X和终态结点Y 从X到S0中任意状态结点连一条 箭弧 从F中任意状态结点连一条 箭弧到Y 方法 39 对M的状态转换图进一步施行如下图所示的替换 其中k是新引入的状态 重复这种分裂过程直至状态转换图中的每条箭弧上的标记或为 或为 中的单个字母 将最终得到的NFA记为M 显然L M L M 正规表达式与有限自动机 3 正规式 NFA DFA 1 正规式 NFA 替换规则 代之以 代之以 代之以 40 正规表达式与有限自动机 2 NFA DFA构造DFAM 使得L M L M L M 1 构造状态转换矩阵 假定I是M 的状态集的子集 定义I的 闭包 CLOSURE I 为 a 若q I 则q CLOSURE I b 若q I 那么从q出发经任意条 弧而能到达的任何状态q 都属于 CLOSURE I 41 假定I是M 的状态集的子集 a 定义Ia CLOSURE J 其中 J是那些可从I中的某一状态结点出发经过一条a弧而到达的状态结点的全体 正规表达式与有限自动机 2 NFA DFA构造DFAM 使得L M L M L M 42 构造状态转换矩阵 假定 a1 ak 该矩阵的首行首列为 CLOSURE X 假设每行的第一列状态子集已经确定为I 则下面依次求该行的第i 1列Iai i 1 k 然后 检查该行上的所有状态子集 看它们是否已在表的第一列中出现 将未曾出现者填入到后面空行的第一列 重复上述过程 直至出现在第i 1列上的所有状态子集均已在第一列上出现 因为M 的状态子集的个数是有限的 所以上述过程必定在有限步内终止 正规表达式与有限自动机 2 NFA DFA构造DFAM 使得L M L M L M 43 将构造出来的上述转换矩阵视为状态转换表 其中每个状态子集视为新的状态 对其进行编号 该表唯一地刻划了一个DFAM 初态 表中首行首列的状态 终态 含有原终态的状态子集 2 构造状态转换表 正规表达式与有限自动机 例 已知正规式 求其对应的最简DFA 步骤 正规式 NFA 状态转换矩阵 重命名的状态转换表 化简后的状态表 DFA 44 正规表达式与有限自动机 例 已知正规式 a b aa bb a b 求其对应的最简DFA 解 1 构造NFAM 45 正规表达式与有限自动机 2 构造DFA的状态转换矩阵 46 正规表达式与有限自动机 3 构造重新命名后的状态转换矩阵DFAM L M L M L M 47 正规表达式与有限自动机 4 化简DFAM 将M的状态分为两组 终态组 3 4 5 6 非终态组 0 1 2 考察 3 4 5 6 3 4 5 6 a 3 4 5 6 3 4 5 6 b 3 4 5 6 它不能再分划再考察 0 1 2 0 1 2 a 1 3 而 1 3 3 4 5 6 1 3 0 1 2 0 1 2 中三个状态不等价 将其分为 0 0 2 13 0 21 此时 整个分划中含有三组 3 4 5 6 1 0 2 考察 0 2 b 2 5 3 4 5 6 1 0 2 中任意一个 将其分为 0 2 a a 48 正规表达式与有限自动机 至此 整个分划中含有四组 3 4 5 6 0 1 2 且每个组均不可再分 令 3 4 5 6 为状态3 则 49 正规表达式与有限自动机 等价状态 假设DFA中有两个P和Q 若从P出发能识别某一字符串X而停止于终态 则从Q出发也能识别字符串X而停止于终态 反之亦然 我们就称状态P和Q等价 若P和Q不等价 则说P和Q是可区分的 DFAM的最小化过程 旨在将M的状态集分割成一些两两不相交的子集 使得任何两个不同的子集中的状态都是可区别的 而同一子集中的任何两个状态都是等价的 这样以一个状态作为代表而删去其他等价的状态 就获得了状态个数最少的DFA 50 三 正规式与有限自动机的等价性关系定理定理 上的NFAM所能识别的语言L M 可以用 上的正规式来表示 即 对 上的NFAM 可构造一个正规式 使得L L M 定理 上任何正规式 存在DFAM使得L M L 即 由正规式 可以构造一个DFAM 使得L M L 正规表达式与有限自动机 51 正规表达式与有限自动机 三 正规式与有限自动机的等价性 1 有限自动机 正规式 1 把状态转换图的概念拓广 令每条弧上都可以用一个正规式作标记 2 在M的转换图上加两个结点 x y 从x用 弧连接到M的所有初态结点 从M的终态结点用 弧连接到y 这个新的NFA为M 且L M L M 3 通过引入的3条有限自动机替换规则逐步消去M 中的所有结点 直到只剩下x和y为止 这样 在x至y的弧线上的标记就是 上的正规式 也就是M接受的正规式 52 正规表达式与有限自动机 1 有限自动机 正规式 替换规则 代之以 代之以 代之以 三 正规式与有限自动机的等价性 53 从开始结点出发 探索一切到终点的路径即可 当有循环时 即用 解决 当有两条可选路径时 用 解决 如此就可顺利写出正规式了 正规表达式与有限自动机 三 正规式与有限自动机的等价性 1 有限自动机 正规式 54 例 年 中科软件所 给出下列自动机所描述的语言 解答 从左到右可写为 化简 用集合形式表达为 55 练习 将下面的DFAM所接受的语言表示为正规式 56 正规表达式与有限自动机 2 正规式 有限自动机 三 正规式与有限自动机的等价性 57 证明过程如下 1 若正规式有零个运算符时 正规式 构造NFA为 对应正规式 构造NFA为 对应正规式a 构造NFA为 2 假设正规式有k k 1 个运算符时结论成立 3 则正规式有k 1 k 1 个运算符时 2 正规式 有限自动机 58 R st R s x y N s R s t 2 正规式 有限自动机 59 书上例子P56 2 正规式 有限自动机 60 转换规则 1 由正规式 构造一个如下仅有两个结点x y的状态图 2 按所引入的3条正规式分裂规则分裂 3 重复步骤2直到每个弧上的标记是 上的一个字符或 为止 4 将所得的NFAM 因为包含 弧 进行确定化就得到DFA 61 正规式分裂规则 62 例 根据正规式 a b aa bb a b 构造DFAM 使之等价 63 练习1 L R a b abb 构造NFA使L N L R 练习2 L R a b abb 构造NFA使L N L R 64 练习1 L R a b abb 构造NFA使L N L R 解 65 练习2 L R a b abb 构造NFA使L N L R 解 66 正规表达式与有限自动机 四 正规文法与有限自动机的等价性 关系定理 对每一个右线性正规文法G或左线性正规文法G 都存在一个有限自动机M 使得L M L G 2 对每一个FAM 都存在一个右线性正规文法GR和左线性正规文法GL 使得L M L GR L GL 67 正规表达式与有限自动机 证明1 1 右线性正规文法 0 使得 字母表 与 相同 则 令 中的 为 的一个状态 的开始符号 是开始状态 增加一个新状态 作为 的终态 则 对 中的形如 a 的产生式 构造 的一个转换函数 a 对 中形如 a的产生式 其中a为终结符或 构造 的一个转换函数 a 1 正规文法 FA F Z 0 S S Z 68 正规表达式与有限自动机 例题 已知文法 画出与其等价的 69 正规表达式与有限自动机 证明1 2