编译原理课后习题解答2

编译原理课后习题解答第2章22节语法定义解1）生成AAA的推导如下SSSSSSASSAASAAA2）语法分析树如图3）文法生成的语言是以A为基本运算分量的和运算表达式的后缀形式。证明用对生成符号串中的运算符个数的归纳法证明归纳基础当运算符个数0时，即SA，A是表达式A的后缀形式归纳步骤假设运算符个数K时，S能推导出，是含有K个运算符的表达式A的后缀形式；那么当符号串W中的运算符个数K1时，可能的最右推导有两种1SSSSAA2SSSSAA显然符号串由一个S推导得到，中的运算符个数为K个，根据假设，是某个表达式B的后缀式；那么1A是表达式BA的后缀式2A是表达式BA的后缀式证毕。龙书本科教学版习题解答仅供教学参考17西北大学GONGXQ解答1）L0N1N|N1证明考虑，推导1步时，有S01推导2步时，S0S10011以此类推，推导N步时，S0S100S1100S110011可以得到N个0和N个1对任意串0N1N都存在一个推导S00112）文法生成以A为基本运算分量的和运算的前缀表达式。证明略。3）文法生成具有对称括号对的串。证明略。4）文法生成A和B的个数相等的串。证明用关于A和B个数的归纳法证明。归纳基础一步推导时，S，其中A和B的个数都为0。归纳步骤设S经过少于N步推导得到的串中A和B的个数相等；则N步的推导形如SASBSX或SBSASYASBS和BSAS中的S经过少于N步能推出终结符号串，且其中A和B的个数都相等；所以经过ASBS和BSAS推导出的X和Y中的A和B个数也相等。证毕。5）文法生成基本运算分量为A的由二元运算、连接和一元运算构成的表达式，表达式可以加括号。证明略。龙书本科教学版习题解答仅供教学参考27西北大学GONGXQ解答文法3）、4）、5）有二义性。证明3）对文法的句子，存在两棵不同的语法分析树如下SSSSSSSSSSSSSS所以文法是二义的。4）对文法的句子ABAB，存在两棵不同的语法分析树如下ASBSSBSASASBSSASBS所以文法是二义的。5）对文法的句子AAA，存在两棵不同的语法分析树如下SSSSSAAASSSSSAAA所以文法是二义的。龙书本科教学版习题解答仅供教学参考37西北大学GONGXQ解答1）SSS|SS|SS|SS/|ID|NUM2）LISTLIST,ID|ID3）LISTID,LIST|ID4）EET|ET|TTTF|T/F|FFID|NUM|E5）EET|ET|TTTF|T/F|FFE|E|ID|NUM|E1）证明对语法分析树的结点数目使用数学归纳法。归纳基础当语法分析树有两个结点时，形如NUM111001NUM生成的串分别为11和1001，表示的值为3和9，能被3整除。归纳步骤假设语法分析树的结点数目少于N时生成的二进制串的值能被3整除，那么当结点数目等于N时，语法分析树的根有下面两种可能的形式龙书本科教学版习题解答仅供教学参考47西北大学GONGXQ0NUMNUM1NUM2NUMNUM1（1）对第一种情况，以NUM1为根的子树中结点数目少于N，生成的二进制串X的值能被3整除；那么NUM为根的语法分析树生成的二进制串为X0，值为X的值乘以2，能被3整除。（2）对第二种情况，以NUM1和NUM2为根的子树中结点数目都少于N，生成的二进制串X和Y的值都能被3整除；那么，以NUM为根的语法分析树生成的二进制串为XY，其值为XVAL2|Y|YVAL，也能被3整除。所以，文法生成的二进制串能被3整除。证毕。2）文法不能生成所有能被3整除的二进制串，例如串10101的值为21，能被3整除，但不能由文法生成。产生式说明SR|Q|P|NBI|II|IIIEIV|V|VB|IXFX|XX|XXXGXL|L|LF|XCHC|CC|CCCJCD|D|DH|CMKM|MM|MMM|MMMMNB|EPFN|GN|F|GQHP|JP|HN|JN|H|JRKQ|KP|KN|KS是开始符号，生成5000以内的罗马数字134910,20,3030,40,50,60,70,80,90100,200,300400,500,600,700,800,9001000,2000,3000,4000一位数两位数三位数四位数龙书本科教学版习题解答仅供教学参考57西北大学GONGXQ23节语法制导翻译产生式翻译方案EE1TEPRE|E1PRE|TPREEE1TEPRE|E1PRE|TPREETEPRETPRETT1FTPRE|T1PRE|FPRETT1/FTPRE/|T1PRE|FPRETFTPREFPREFIDFPREIDLEXEMEFNUMFPRENUMVALUEFEFPREEPREEETTFTF9F52PRE9PRE5PRE2PRE9PRE9PRE5PRE52PRE952龙书本科教学版习题解答仅供教学参考67西北大学GONGXQ产生式翻译方案EE1E2EM|E1M|E2M|EE1E2EM|E1M|E2M|EE1E2EM|E1M|E2M|EE1E2/EM|E1M|/|E2M|ENUMEMNUMVALUEEIDEMIDLEXEME产生式翻译方案EE1E2EM