编译原理练习答案蒋宗礼第三章.pdf

第一部分 重点知识回顾 第二章第二章 词法分析词法分析 词法分析的任务是 从左至右逐个字符地对源程序进行扫描 产生一个个的单词符号 把作为字符串的源程序改造成为单词符号串的中间程序 因此 词法分析器的功能是输入源 程序 输出单词符号 且输出的单词符号常常表示成如下的二元式 单词种别 单词自身的值 我们可以把词法分析器安排成一个子程序 每当语法分析器需要一个单词符号时 就调 用这个子程序 每一次调用 词法分析器就从输入串中识别出一个单词符号 把它交给语法 分析器 1 状态转换图 使用状态转换图是设计词法分析程序 扫描器 的一种好途径 转换图是一张有限方向 图 在状态转换图中 结点代表状态 用圆圈表示 状态之间用有向弧连结 有向弧上的标 记代表着可能出现的输入字符 一张转换图只包含有限个状态 其中有一个被认为是初态 而且实际上至少要有一个终态 用双圈表示 例如 识别标识符的状态转换图如图 2 1 所 示 其中 0 为初态 2 为终态 终态结上打着星号 意味着多读进了一个不属于标识符部分 的字符 应把它退还给输入串 用手工设计词法分析器的方法是 先使用状态转换图描述出所有的单词符号 然后用程 序实现状态转换图 最简单的办法是让每个状态对应一小段程序 2 正规表达式与有限自动机 有限自动机理论是描述词法规则的基本理论 一条词法规则表示为一个正规表达式 简 称正规式 而一个正规表达式又可化为一个确定的有限自动机 这个有限自动机就可以用 来识别该词法规则定义的所有单词符号 把程序设计语言的所有词法规则都构造出相应的有 限自动机 就得到了一个词法分析器 词法分析器自动生成的过程是 根据某种程序设计语言的词法规则 写出相应的正规式 再根据这些正规式 写出某种语言 比如 LEX 的源程序 由 LEX 编译程序翻译后便得到 了一个词法分析器 它可以用来识别该程序语言的全部单词 所以 要实现词法分析器的自 动生成 关键是要有某种语言 比如 LEX 的编译程序 一旦有了这个编译程序 就可以 通过它得到其他各种程序语言的词法分析器 正规式与正规集 对于字母表 我们感兴趣的是它的一些特殊字集 即正规集 下面是正规式和正规集 的递归定义 1 和 都是 上的正规式 它们所表示的正规集分别为 和 2 任何 a 则称 a 是 上的一个正规式 它所表示的正规集为 a 3 假定 U 和 V 都是 上的正规式 它们所表示的正规集分别为 L U 和 L V 编译原理练习答案蒋宗礼 则 U V U V 和 U 也都是正规式 它们所表示的正规集分别为 L U L V L U L V 连接积 和 L U 闭包 仅通过有限次使用上述三步骤定义的表达式才是 上的正规式 仅由这些正规式所表示 的字集才是 上的正规集 令 U V 和 W 均为正规式 则下述关系成立 1 U V V U 交换律 2 U V W U V W 或 U VW UV W 结合律 3 U V W UV UW 或 V W U VU WU 分配律 4 U U U 若两个正规式所表示的正规集相同 则认为二者等价 例如 b ab ba b a b a b 注意 a b a b ab a b 相互都不等价 它们表示的含义如图所示 确定有限自动机 DFA 一个确定的有限自动机 DFA M 是一个五元式 M Q f s0 Z 其中 1 Q 是一个有限集 它的每个元素称为一个状态 2 是一个有穷字母表 它的每个元素称为一个输入字符 3 f 是一个从 Q 至 Q 的 单值 部分映射 f q a p 意味着当现行状态为 q 输 入字符为 a 时 将转换到下一状态 p 我们把 p 称为 q 的一个后继状态 4 s0 S 是唯一的初态 5 Z Q 是一个终态集 可空 一个确定的有限自动机可以用一个矩阵表示 该矩阵的行表示状态 列表示输入字符 矩阵元素表示 f q a 的值 这个矩阵称为状态转换矩阵 一个确定的有限自动机也可以表示成一张 确定的 状态转换图 状态转换图的构造方 法是 若确定的有限自动机M 含有 m个状态和 n个输入字符 则这个图含有 m个状态结点 每个结点顶多有 n 条有向弧射出和别的结点相连接 每条弧用 中的一个互不相同的输入字 符作标记 整个图含有唯一的一个初态结和若干个 可以是 0 个 终态结点 对于 中的任何字 若存在一条从初态到某一终态结的道路 且这条路上所有弧的 标记符连接成的字等于 则称 可为确定的有限自动机 M 所识别 读出或接受 若 M 的初态结同时又是终态结点 则空字 可为 M 所识别 或接受 确定的有限自动机 M 所 能识别字的全体记为 L M 注意 确定的有限自动机其确定性表现在映射 f Q Q 是一个单值函数 也就是说 对 任何状态 q Q 和输入符号 a f q a 唯一地确定了下一个状态 非确定有限自动机 NFA 如果允许 f 是一个多值函数 就得到非确定自动机的概念 一个非确定有限自动机 NFA M 是一个五元式 M Q f s0 Z 在确定有限自动机的描述中 1 2 5 同确定有限自动机 而 3 为 f 是一个 以 Q 到 Q 的子集的映射 即 f S 2Q 显然 一个含有 m 个状态和 n 个输入字符的非确定有限自动机可表示成一张状态图 该图含有 m 个状态结点 每个结可射出若干条有向弧与别的结点相连接 每条弧用 中的 一个字 不一定要不同的字且可以是空字 作标记 称为输入字 整个图至少含有一个 初态结点以及若干个 可以是 0 个 终态结点 某些结既可以是初态结点又可以是终态结点 注意 DFA 是 NFA 的特例 对于每个非确定有限自动机 M 存在着一个确定有限自动机 M 使得 L M L M 即两个有限自动机等价 3 正规式到有限自动机的变换 由正规式到有限自动机的变换过程是 首先根据正规式构造出非确定的有限自动机 然 后用子集法将其确定化 再进行最小化 最后得到一个状态最小的确定的有限自动机 将正规式转换成非确定有限自动机 1 首先把正规式 V 表示成图所示的拓广转换图 2 通过对 v 进行分裂和加进新结的办法 逐步把这个图转换成每条弧都标记有 的 一个字符或 的图 其转换规则如图所示 在整个分裂过程中 所有新结点均用不同的名字 保留 X 和 Y 为全图的唯一初态结点 和终态结点 至此 我们得到了一个非确定有限自动机 第二部分第二部分 例题与习题例题与习题 重重重重点点点点与与与与难难难难点点点点 重点 词法分析器的输入 输出 用于识别符号的状态转移图的构造 根据状态转移图实现 词法分析器 难点 词法的正规文法表示 正规表达式表示 状态转移图表示 它们之间的转换 基基基基本本本本要要要要求求求求 明确词法分析的任务 熟练掌握词法的正规文法表示 正规表达式表示 状态转移图表 示及它们之间的转换 掌握词法分析器的设计与实现 重点掌握根据状态转移图实现词法分 析器 例例例例题题题题解解解解析析析析 例 1 用正规表达式标识符的文法 解 设标识符是由字母和数字组成的有限长的符号串 且第一个符号只能是字母 用 l 表示字母 a b z A B Z d 表示数字 0 1 9 标识符的正规表达式表示为 l l d l l d l d 例 用正规文法描述标识符的文法 解 用 l 表示字母 a b z A B Z d 表示数字 0 1 9 定义文法 G G d l S T P S P S l lT T l lT T d dS 得到标识符文法的右线性文法表示 或者 定义文法 G G d l S T P S P S l S Sd S Sl 得到标识符文法的左线性文法表示 或者通过正规表达式转换为正规文法的方法得到标识符文法的正规文法 引入开始符号 S 构造 S l l d 引入非终结符 T 分分解解 连连接接 的的正正规规式式 构构造 造 S l T T l d 因因为为 l d l d l d l d l lT T d dT T 得得到到产产生生式式的的集集合合 P P S S l lT T T T l lT T d dT T 构构成成右右线线性性文文法法 l l d d S S T T P P S S 例 3 用状态图描述标识符 变量名等 的文法 解 用正规文法转换为状态图的方法 标识符的正规文法 S S l lT T T T l lT T d dT T 是一个右线性文法 按照由右线性正规文法构造状态转换图的方法 构造标识符的状态转换图如下 l d 其它 终态 初态 例 4 叙述下面的正规式描述的语言 并画出接受该语言的最简 DFA 的状态转换图 1 01 0 解 描述的语言是 所有不含子串 001 的 0 和 1 的串 例 5 给定如下正规式 0 0 1 1 1 写出相应的正规文法 2 画出相应的状态转移图 解 1 引入非终结符 S A S 0 0 1 1 0A A 0 1 1 0 1 1 1 0 1 1 1 0 1 0 1 1 1 0A 1A 得到正规文法 G S S 0A A 0A 1A 1 2 中给出的是一个右线性文法 按照由右线性正规文法构造状态转换图的方法 构造相应的状态转移图如图 1 图 1 文法 G 的状态转换图 例 6 给定文法 G Z 0 V U 1 V 0 试构造状态转换图 并利用所得的状态转换图判别符号串 100101 和 100111 是否该文法的句 子 解 增加一个终态 得到该文法对应的状态转换图如图 所示 S U V Z 图 文法 G 的状态转换图 对符号串 100101 的识别过程经历了状态 S Z 终止于终止状态 Z 所以 100101 是此文法的句子 对符号串 100111 的识别过程经历了状态 S 识别出 10011 后 在 状态 无法进一步识别 所以 100111 不是此文法的句子 例 7 给出描述包含奇数个 1 或奇数个 0 个二进制数串的正规表达式 解 解题思路 本题求二进制串 并且要求包含奇数个 0 或奇数个 1 由于 0 和 1 都可以在二进制串中 任何地方出现 所以本题只需要考虑一种情况 另外一种情况也可以类似求得 考虑包含奇 数个 0 的字符串 由于只关心 0 的个数的奇偶数 我们可以把二进制串分成多段来考虑 第 1 段为二进制串的开始到第 1 个 0 为止 这一段包含 1 个 0 并且 0 的前面有 0 个或多个 1 对于剩下的二进制串按照每段包含两个 0 的方式去划分 即以 0 开始 以 0 结尾 中间可以 有 0 个或多个 1 如果一个二进制串被这样划分完后 剩下的部分如果全部是全 1 串 这些 全 1 串在前面划分的串之间或最后 则该二进制串就具有奇数个 0 所以该二进制可以这 样描述 以第 1 段 1 开始 后面由全 1 串 1 以及包含两个 0 的串 01 0 组成 所以包含奇数个 0 的正规表达式为 1 0 1 01 0 本题的解答则是 1 0 1 01 0 0 1 0 10 1 例 8 语言 L 是所有由偶数个 0 和偶数个 1 组成的句子的集合 给出定义 L 的正规文法 解 解题思路 这道题可以从状态转换图着手 由于每读入 1 个 0 0 的个数的奇偶数就会变 每 读入 1 个 1 1 的个的奇偶数也会改变 因此本题可以引入 4 个状态 分别代表偶数个 0 和 1 奇数个 0 和 1 奇数个 1 偶数个 0 和奇数个 0 偶数个 1 那么 能接受语言 L 的状态转换图如下图 3 所示 图 3 语言 L 的状态转换图 其中 状态 S 代表偶数个 0 和 1 既是初始状态 也是终止状态 然后 根据该 状态转换图可以写出相应的正规文法就可以了 通常由 DFA 的状态转换图构造 右线性 正规文法的方法如下 1 DFA 的状态对应于正规文法的非终结符 2 DFA 的转换弧上的字符对应于文法的终结符 3 DFA 的初态对应于正规文法的开始非终结符 4 DFA 的转换关系对应于产生式规则 若 如果 B 不为终态 则对应于产生式 A cB 如果 B 为终态 则对应于产生式 A cB c 5 如果 DFA 的初态 S 同时也是该 DFA 的一个终态 则加入产生式 S 解答 接受语言 L 的正规文法为 S 0A 1C A 0S 1B 0 C 0B 1S 1 B 0C 1A S A B C 0 0 0 0 1 1 1 1 C A B 例 9 给出接受 0 1 上不含子串 010 的所有串的正规表达式和 DFA 解 解题思路 本题有两种解题思路 一种是直接构造一个满足条件的状态转换图 然后根据状态转换 图求正规表达式 另一种方法是分析题意直接写出满足条件的正规表达式 方法 1 直接写出满足条件的状态转换图 在状态转换图中引入 3 个状态 初始状态 S 也是终止状态 表示当前读入的串中不包含子串 010 并且最后读入的字符是 1 或没读 入任何字符 初始状态读入字符 0 后进入一个新的状态 A 状态 A 表示当前读入的串中不包 含子串 010 并且最后读入的字符是 0 状态 A 如果读入字符 1 后进入新状态 B 状态 B 表 示当前读入的串中不包含子串 010 并且最后读入的字符是 01 状态 B 不接受字符 0 然后 用 0 1 连接各状态就构造出了满足条件的状态转换图 如下图 4 所示 然后根据状态转换 图来求正规表达式 这里就不详细说明了 方法 2 直接写出满足条件的正规表达式 考虑满足条件的字符串中的 1 在串的开始部分 可以有 0 个或多个 1 串的尾部也可以有 0 个或多个 1 但串的之间只要出现 1 则至少在 两个以上 所以满足条件的正规表达式为 1 0 111 1 解答 所求正规表达式为 1 0 111 1 所求 DFA 如图 4 所示 例 10 一个人带着狼 山羊和白菜在一条河的左岸 有一条船 大小正好能装下这个人和其 它 3 件东西中的一件 人和他的随行物都要过到河的右岸 人每次只能将一件东西摆渡过河 但若人将狼和羊留在同一岸而无人照顾的话 狼将把羊吃掉 类似的 羊也可能会吃掉白菜 请问是否有可能摆渡过河 并使得羊和白菜都不会被吃掉 如果可能 请用有限自动机写出 渡河的方法 解 解题思路 这是一道经典的智力题 很显然是有办法渡河的 关键是如何用有限自动机来求解渡河 的方法 有限自动机描述的是状态和状态之间的转换 对于本题 可以把人 狼 山羊和白 菜都在左岸作为有限自动机的初始状态 而把他们都在右岸作为终止状态 只要构造一个自 动机使得存在一条从初始状态到终止状态的路径就可以了 首先构造有限自动机的状态集 可以用 M W G C 表示人 狼 山羊和白菜 都在左岸 用 M W G C 表示人 狼 山羊和白菜都在右岸 可能存在状态共有 1 4 4 3 4 1 22 个 但其中有些状态是不安全的 如 G C M W 表示人和 狼在右岸 山羊和白菜在左岸 山羊会吃了白菜 去掉不安全的状态 剩下的状态就是要构 造的有限自动状态集 共 10 个状态 0 1 1 1 0 SA B 2 26 状态转换图 图 4 M W G C M W G C M W G C M W C G M G C W C M W G G M W C W M G C M G W C W C M G 接下来为有限自动机添加箭弧 用 M 表示人独自过河 用 MW 表示人和狼一起过 河 用 MG 表示人和山羊一起过河 用 MC 表示人和白菜一起过河 在状态之间只要可 以使用箭弧 则得到一个状态转换图 如图 5 所示 观察所求得的有限自动机的状态转换图 可以发现从初始状态到终止状态之间存在两条 较短的路径 它们分别为 MG M MW MG MC M MG 和 MG M MC MG MW M MG 这两条路径就是两种正确的渡河方法 解答 分析题意 求得相应有限自动机的状态转换图如图 5 所示 从图中直接可以得到两种渡 河方法 MG M MW MG MC M MG 和 MG M MC MG MW M MG 路径 MG M MW MG MC M MG 的解释为第 1 步 人带山羊过河 到右岸 第 2 步 人独自过河 到左岸 第 3 步 人带狼过河 到右 岸 第 4 步 人带山羊过河 到左岸 第 5 步 人带白菜过河 到右岸 第 6 步 人独 自过河 到左岸 第 7 步 人带山羊过河 到右岸 另一条路径的解释类似 例 11 试给出识别 语言的无符号整数的正规式和状态转换图 解 1 正规式描述 八进制数 oct 0 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 十进制数 dec 1 9 0 9 0 十六进制数 hex 0 x 0 1 9 a f A F 0 9 a f A F 2 识别不同进制数的状态图 八进制整数 oct 0 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 十进制数 0 7 其它 0