编译原理课后习题解答(2).pdf

编译原理课后习题解答 第 2 章 2 2 节 语法定义 解 1 生成aa a 的推导如下 S SS SS S aS S aa S aa a 2 语法分析树如图 3 文法生成的语言是以 a 为基本运算分量的 和 运算表达式的后缀形式 证明 用对生成符号串中的运算符个数的归纳法证明 归纳基础 当运算符个数 0 时 即 S a a 是表达式 a 的后缀形式 归纳步骤 假设运算符个数 k 时 S 能推导出 是含有 k 个运算符的表达式 A 的后 缀形式 那么当符号串 w 中的运算符个数 k 1 时 可能的最右推导有两种 1 S SS Sa a 2 S SS Sa a 显然符号串 由一个 S 推导得到 中的运算符个数为 k 个 根据假设 是某个表达式 B 的后缀式 那么 1 a 是表达式 B a 的后缀式 2 a 是表达式 B a 的后缀式 证毕 龙书本科教学版习题解答仅供教学参考 1 7西北大学 Gong Xq 解答 1 L 0n1n n 1 证明 考虑 推导 1 步时 有 S 01 推导 2 步时 S 0S1 0011 以此类推 推导 n 步时 S 0S1 00S11 0 0S1 1 0 01 1 可以得到 n 个 0 和 n 个 1 对任意串 0n1n都存在一个推导 S 0 01 1 2 文法生成以 a 为基本运算分量的 和 运算的前缀表达式 证明略 3 文法生成具有对称括号对的串 证明略 4 文法生成 a 和 b 的个数相等的串 证明 用关于 a 和 b 个数的归纳法证明 归纳基础 一步推导时 S 其中 a 和 b 的个数都为 0 归纳步骤 设 S 经过少于 n 步推导得到的串 中 a 和 b 的个数相等 则 n 步的推导形如 S aSbS x 或 S bSaS y aSbS 和 bSaS 中的 S 经过少于 n 步能推出终结符号串 且其中 a 和 b 的个数都相等 所以经过 aSbS 和 bSaS 推导出的 x 和 y 中的 a 和 b 个数也相等 证毕 5 文法生成基本运算分量为 a 的由二元运算 连接和一元运算 构成的表达式 表达式 可以加括号 证明略 龙书本科教学版习题解答仅供教学参考 2 7西北大学 Gong Xq 解答 文法 3 4 5 有二义性 证明 3 对文法的句子 存在两棵不同的语法分析树如下 S S SS S S S S S SS S S S 所以文法是二义的 4 对文法的句子 abab 存在两棵不同的语法分析树如下 aSb S S bSa S a S b S S aSb S 所以文法是二义的 5 对文法的句子 aaa 存在两棵不同的语法分析树如下 S SS SS a a a S SS SS a a a 所以文法是二义的 龙书本科教学版习题解答仅供教学参考 3 7西北大学 Gong Xq 解答 1 S SS SS SS SS id num 2 list list id id 3 list id list id 4 E E T E T T T T F T F F F id num E 5 E E T E T T T T F T F F F E E id num E 1 证明 对语法分析树的结点数目使用数学归纳法 归纳基础 当语法分析树有两个结点时 形如 num 111001 num 生成的串分别为 11 和 1001 表示的值为 3 和 9 能被 3 整除 归纳步骤 假设语法分析树的结点数目少于 n 时生成的二进制串的值能被 3 整除 那么当 结点数目等于 n 时 语法分析树的根有下面两种可能的形式 龙书本科教学版习题解答仅供教学参考 4 7西北大学 Gong Xq 0 num num1 num2 num num1 1 对第一种情况 以 num1 为根的子树中结点数目少于 n 生成的二进制串 x 的值能被 3 整除 那么 num 为根的语法分析树生成的二进制串为 x0 值为 x 的值乘以 2 能被 3 整除 2 对第二种情况 以 num1 和 num2 为根的子树中结点数目都少于 n 生成的二进制串 x 和 y 的值都能被 3 整除 那么 以 num 为根的语法分析树生成的二进制串为 xy 其值为 xval 2 y yval 也能被 3 整除 所以 文法生成的二进制串能被 3 整除 证毕 2 文法不能生成所有能被 3 整除的二进制串 例如串 10101 的值为 21 能被 3 整除 但不 能由文法生成 产生式产生式 说明说明 S R Q P N B I II III E IV V VB IX F X XX XXX G XL L LF XC H C CC CCC J CD D DH CM K M MM MMM MMMM N B E P FN GN F G Q HP JP HN JN H J R KQ KP KN K S 是开始符号 生成 5000 以内的罗马数字 1 3 4 9 10 20 30 30 40 50 60 70 80 90 100 200 300 400 500 600 700 800 900 1000 2000 3000 4000 一位数 两位数 三位数 四位数 龙书本科教学版习题解答仅供教学参考 5 7西北大学 Gong Xq 2 3 节 语法制导翻译 产生式 翻译方案 E E1 T E pre E1 pre T pre E E1 T E pre E1 pre T pre E T E pre T pre T T1 F T pre T1 pre F pre T T1 F T pre T1 pre F pre T F T pre F pre F id F pre id lexeme F num F pre num value F E F pre E pre E E T T F T F 9 F 5 2 pre 9 pre 5 pre 2 pre 9 pre 9 pre 5 pre 52 pre 9 52 龙书本科教学版习题解答仅供教学参考 6 7西北大学 Gong Xq 产生式 翻译方案 E E1E2 E m E1 m E2 m E E1E2 E m E1 m E2 m E E1E2 E m E1 m E2 m E E1E2 E m E1 m E2 m E num E m num value E id E m id lexeme 产生式 翻译方案 E E1E2 E m E1 m E