编译原理期中测试答案.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 , S S a ( T ) T , S 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)=