编译原理期中测试答案.doc

精品文档编译原理期中测试答案三、单项选择题(每题3分，共15分)1设有文法GS: S(AS)|(b)A(SaA)|(a)该文法的句型(b)a(a)(b)有 C 个直接短语。A.1 B. 2 C. 3 D. 42如果一个文法满足 D ，则称该文法是二义性文法。(1) 文法的某一个句子存在两个（包括两个）以上的语法树(2) 文法的某一个句子存在两个（包括两个）以上的最左推导(3) 文法的某一个句子存在两个（包括两个）以上的最右推导(4) 在进行归约时，文法的某些规范句型的句柄不唯一上述描述中的所有正确描述有：A. (1) B. (1)(2) C. (1)(2)(3) D. (1)(2)(3)(4)3构造一个不带回溯的自顶向下语法分析器，要求文法满足 E 。 A. 对每个形如Ax1|x2|xn的产生式，要求FIRST(xi)与FIRST(xj)的交集为空集(ij)B. 对每个形如Ax1|x2|xn的产生式，若xi，则要求FIRST(xj)与FOLLOW(A)的交集为空集(ij) C. 不含左递归 D. A和B同时满足 E. A、B和C同时满足4、给定文法AbA|cc，下列符号串中，是该文法的句子的是 C 。 cc bcbc bcbcc bccbcc bbbccA B. C. D. 5、若一个句型中出现了某一产生式的右部，则此右部 B 是该句型的句柄。A.一定 B. 不一定 C. 一定不 D. 无法判断四、简述题(每题5分，共20分)1、写一上下文无关文法,它能产生语言。SA#B AAa|eBBb|e2、将文法GS 改写为等价的GS，使GS不含左递归和左公共因子。GS： SbSAe | bA AAb | d 答：文法GS 改写为等价的不含左递归和左公共因子的GSSbB BSAe | A Ad A A bA | 3、什么是文法的二义性？下面的文法是二义的吗？为什么？GS： SAB | ABD Aa BCD |D Cc Dd答：如果一个文法存在某个句子对应两棵不同的语法树，则该文法是二义的。是，句子acd 有两个完全不同的语法树。4、 设文法GA: ABB X | BAX Xa | Xb | a | b 试求出文法GA产生的语言对应的正则式。解: X X(a |b) | a | b X (a |b)( a | b)* 代入B X | BAB (a |b)( a | b)* | BA B (a |b) ( a | b)* A*代入A(a |b) ( a | b)* A*(a|b)(a|b)* (a|b)(a|b)*)*五、计算题(共41分)1、已知文法G(S):Sa|(T)TT,S|S 给出句子(a,(a,a)的最左推导并画出语法树； 给出句型(T,S),a)的短语、直接短语、句柄。(10分)答：最左推导：(2分)S=(T)=(T,S)=(S,S)=(a,S)=(a,(T)=(a,(T,S)=(a,(S,S)=(a,(a,S)=(a,(a,a)语法树： S T ( ) （二）创业优势分析T 2003年，上海市人均GDP按户籍人口计算就达到46700元，是1995年的2.5倍；居民家庭人均月可支配收入为14867元，是1995年的2.1倍。收入不断增加的同时，居民的消费支出也在增加。2003年上海居民人均消费支出为11040元，其中服务性消费支出为3369元，是1995年的3.6倍。, 我们熟练的掌握计算机应用，我们可以在网上搜索一些流行因素，还可以把自己小店里的商品拿到网上去卖，为我们小店提供了多种经营方式。S 动漫书籍 化妆品 其他S 虽然调查显示我们的创意计划有很大的发展空间，但是各种如“漂亮女生”和“碧芝”等连锁饰品店在不久的将来将对我们的创意小屋会产生很大的威胁。a ( 然而影响我们大学生消费的最主要的因素是我们的生活费还是有限，故也限制了我们一定的购买能力。因此在价格方面要做适当考虑：我们所推出的手工艺制品的价位绝大部分都是在50元以下。一定会适合我们的学生朋友。T ) T “碧芝”的成功归于他的唯一，这独一无二的物品就吸引了各种女性的眼光。, S 图1-1大学生月生活费分布S a 一、消费者分析a 3给出与正规式R（ab）*（a|b*）ba等价的NFA。（5分）答案：是 否4将下图的NFA确定化为DFA。（8分）答案：用子集法确定化如下表IIaIb状态X,1,21,2.1,2,31,2,Y1,2.1,2.1,2,Y1,2.1,2,31,2,31,2,31,2,3X123确定化后如下图5、设文法G(S):SS+aF|aF|+aFF*aF|*a 消除左递归和回溯； 构造相应的FIRST和FOLLOW集合； 构造预测分析表(12分)答： (消除左递归2分，提公共左因子2分)SaFS|+aFSS+aFS|F*aFFF|(4分)FIRST(S)=a,+ FOLLOW(S)=#FIRST(S)=+, FOLLOW(S)=#FIRST(F)=* FOLLOW(F)=+,#FIRST(F)=*,) FOLLOW(F)=+,#(4分)-a+*#SSaFSS+aFS-S-S+aFS-SF-F*aF-F-FFFF精品文档