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

龙书本科教学版习题解答 仅供教学参考 编译原理课后习题解答 第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 龙书本科教学版习题解答 仅供教学参考 解答： n n 1）L={0 1 | n=1} 证明：①考虑，推导1 步时，有S 01 推导2 步时， S 0S1 0011 以此类推，推导n 步时，S 0S1 00S11 ... 0...0S1...1 0...01...1 可以得到n 个0 和n 个1 n n ②对任意串0 1 都存在一个推导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 S ( S ) S S ( S ) S ε ε ε ε S ( S ) S S ( S ) S ε