广工编译原理试卷A

1、编译原理试卷A一、选择题(每空2分，共20分)1一个正规语言只能对应 (B )？A 一个正规文法；B 一个最小有限状态自动机；2文法 GA :A t aB B Ab B 宀是(B ):A正规文法B二型文法3下面说法正确的是(A ):A 一个SLR (1)文法一定也是 LALR (1)文法B 一个LR (1)文法一定也是 LALR (1)文法4一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL (1)文法的(A ):A必要条件B充分必要条件5. ( D )不是NFA的成分。A由穷字母表B初始状态集合 C终止状态集合D有限状态集合6. ( C )不是编译程序的组成部分A词法分析程序B代码

2、生成程序 C设备管理程序D语法分析程序7 .有文法 G=(S,a,S t SaS, St £ ,S),该文法是(B )。A. LL(1)文法B.二义性文法 C算符优先文法 D SLR(1)文法8给定文法 A t bA|cc，则符号串ccbcbcbcbccbccbccbbbcc中，是该文法句子的是(D )ABCD9表达式A*(B-C*(C/D)的逆波兰表示为(B )A. ABC-CD/* B. ABCCD/*-* C. ABC-*CD/* D.前三个选项都不对10 LR(1)文法都是(A )A无二义性且无左递归B可能有二义性但无左递归C无二义性但可能有无左递归D 可以既有二义性又有左递

3、归二、问答题 第1题(10分)将文法GS改写为等价的 G S使G S不含左递归和左公共因子。GS : St bSAe | bAAt Ab | d答：文法GS改写为等价的不含左递归和左公共因子的G'S为:St bBBt SAe|Aat d A'A' t bA' |£第2题(10分)给出与正规式 R =( ab) * ( a|b*) ba等价的NFA。答:与正规式R=( ab) * (a|b*) ba等价的NFA如下图第3题(10分)1b3答：用子集法确定化如下表用子集法对所给图的确定化IIaIb状态X,1,21,2.1,2,3X1,2 1,2.1,2,3

4、11,2,31,2,Y1,2,321,2,Y1,2.1,2,33确定化后如下图第4题（10分）给出文法GS的LR（1）项目集规范族中Io项目集的全体项目。GS为:S t BD|DB t aD|bD t B答:解：Io2) V t d4) A t a6) A t£第5题（10分）文法GM及其LR分析表如下，请给出对串dbba#的分析过程。GM: 1) M t VbA3) V t£5) A t Ababda#MAV0r3S3121acc2S43r24r6S5r665r4r46S7r17S88r5r5答：对串dbba#的分析过程如下表对输入串dbba#的分析过程步骤状态栈文法符号

5、栈剩余输入符号动作10#dbba#移进203#dbba#用V归约302#Vbba#移进4024#Vbba#用A归约50246#VbAba#移进602467#VbAba#移进7024678#VbAba#用A tAba归约80246#VbA#用M tVbA归约901#M#接受第6题(20分)某语言的拓广文法 G'为：(0) S 't T(1) T taBd| &(2) B tTb| &证明G不是LR(O)文法而是SLR(1)文法，请给出 SLR(1)分析表。答：拓广文法 G',增加产生式 S' tT在项目集I。中：有移进项目TaB和归约项目T f存在

6、移进-归约冲突，所以 G不是LR(O)文法。若产生式排序为：(0) S' tt(1) T t aBdT t £ B t TbB t £G'的LR(0)项目集族及识别活前缀的DFA如下图所示:识别G'活前缀的DFA由产生式知：Follow(T)=#,bFollow(B)= d在I冲：Follow(T) n a=#, b n a= 口在I冲：Follow(B) n a= d n a=匚；Follow(T) n a=#, b n a= 口Follow(B) n Follow(T) = d n # , b=O所以在Io, I2，中的移进-归约和归约-归约冲突可以由Follow集解决，所以G 是SLR(1)文法。构造的SLR(1)分析表如下表。SLR(1)分析表n ameACTIONGOTOabd#TB0S2r2r211acc2S2r2r4r2433S54S65r1r163第7题(10分)对产生C语言中的条件表达式的文法GE : EtE?E:E写出相应的翻译文法。答：E1 t e? BackPatch($1.TC,NXQ);$.FC=$1.FC;E2t E1E2:$.pla