编译原理复习整理(重点含答案)
1、给出下面语言的相应文法 。 L1=anbnci|n1,i0从n，i的不同取值来把L1分成两部分：前半部分是anbn：AaAb|ab后半部分是ci：BBc|所以整个文法G1S可以写为：G1(S):SAB ； AaAb|ab ；BcB|3、构造一个DFA，它接受S=a，b上所有包含ab的字符串。（要求：先将正规式转化为NFA，再将NFA确定化，最小化）4、对下面的文法G:ETE E+E| TFT TT|FPF F *F| P(E)|a|b|（1）证明这个文法是LL(1)的。（2）构造它的预测分析表。(1)FIRST(E)=(,a,b,FIRST(E')=+,FIRST(T)=(,a,b,FIRST(T')=(,a,b,FIRST(F)=(,a,b,FIRST(F')=*,FIRST(P)=(,a,b,FOLLOW(E)=#,)FOLLOW(E')=#,)FOLLOW(T)=+,),#FOLLOW(T')=+,),#FOLLOW(F)=(,a,b,+,),#FOLLOW(F')=(,a,b,+,),#FOLLOW(P)=*,(,a,b,+,),#(2)考虑下列产生式:FIRST(+E)FIRST()=+=FIRST(+E)FOLLOW(E')=+#,)=FIRST(T)FIRST()=(,a,b,=FIRST(T)FOLLOW(T')=(,a,b,+,),#=FIRST(*F')FIRST()=*=FIRST(*F')FOLLOW(F')=*(,a,b,+,),#=FIRST(E)FIRST(a) FIRST(b) FIRST()=所以,该文法式LL(1)文法.(3)+*()ab#EE'TT'FF'P5、 考虑文法: SAS|b ASA|a（1）列出这个文法的所有LR(0) 项目。0. 1.2.3.4.5.6.7.8.9.10.11.(2)给出识别文法所有活前缀的DFA。1987 S A S 11100 a 432 A S 6 b 5确定化：SAab0,2,5,7,101,2,5,7,8,102,3,5,7,101161,2,5,7,8,102,5,7,8,102,3,5,7,9,101162,3,5,7,102,4,5,7,8,102,3,5,7,101162,5,7,8,102,5,7,8,102,3,5,7,9,101162,3,5,7,9,102,4,5,7,8,102,3,5,7,101162,4,5,7,8,102,5,7,8,102,3,5,7,9,10116116 A S3:5:6: S A a b S a A S b S A b a A4:0:7: A S b a a b b a2:1: DFA6、设有文法：PP+Q|Q QQ*R|R R(P)|i（1）证明Q*R+Q+Q是它的一个句型。（3分)P=>P+Q=>P+Q+Q=>Q+Q+Q=>Q*R+Q+Q（2） 给出Q*R+Q+Q的所有短语，直接短语和句柄。(4分)短语: Q*R,Q*R+Q,Q*R+Q+Q 直接短语: Q*R 句柄: Q*R（3）给出句子+*的最右推导。(4分)（4）给出句子+*的最左推导。(4分)7、设有文法：EE+T|T TT*F|F F(E)|i（1）证明E+T*F是它的一个句型。（3分)（2）给出E+T*F的所有短语，直接短语和句柄。(4分)短语: E+T*F, T*F, 直接短语: T*F 句柄: T*F（3） 给出句子+*的最右推导。(4分)11、构造下面正规式相应的DFA1(0|1)*10114、对下面的文法G:Expr- Expr Expr(Expr)|Var ExprTail ExprTail- Expr|Varid VarTail VarTail(Expr) |（1） 构造LL(1)分析表。（12分）（2） 给出对句子idid(id)的分析过程。（8分）16、已知文法GS 为： S->a|(T)T->T,S|S 消除文法GS中的左递归，得文法G´S。 文法G´S是否为LL(1)的？若是，给出它的预测分析表。FIRST(S)=a,( FIRST(T)=a,( FIRST()=, FOLLOW(S)=),# FOLLOW(T)=) FOLLOW()=)预测分析表a(),#ST是LL(1)文法17、对下面的文法G:S ® S Ú a T | a T | Ú a T T ® Ù a T | Ù a(1) 消除该文法的左递归和提取左公因子；构造各非终结符的FIRST和FOLLOW集合；18、文法G(S)及其LR分析表如下，请给出串baba#的分析过程。(1) S DbB(2) D d(3) D (4) B a(5) B Bba(6) B LR分析表2、写出表达式a=b*c+b*d对应的逆波兰式、四元式序列和三元式序列。 答：逆波兰式： abc*bd*+:= 四元式序列：三元式序列: OP ARG1 ARG2(1) (*， b， c， t1) (1) (* b， c )(2) (*， b， d， t2) (2) (* b， d )(3) (+， t1， t2，t3) (3) (+ (1)， (2)(4) (:=， t3， /， a)(4) (:= (3)， a)八、语义分析题1、将语句if (A<0) Ú (B>0) then while (C>0) do C:=C-D翻译成四元式答案：100 (j<， A， 0， 104)101 (j， -， -， 102)102 (j>， B， 0， 104)103 (j， -， -， 109)104 (j>， C， 0， 106)105 (j， -， -， 109)106 (-， C， D， T1)107 (:=， T1， -， C)108 (j， -， -， 104)1092、写出下面语句经语法制导翻译后所生成的四元式代码序列。 if x<y then while e>c do c:=c+1 else x:=x+5答案：假设初始为100，则四元式代码序列为 100ifx<ygoto102101goto107102ife>cgoto104103goto109104M:=C+1105C:=M106goto102107N:=X+5108X:=N1098、写出表达式a+b*(c-d)对应的逆波兰式和三元式序列。答案：逆波兰式：(abcd-*+) 三元式序列: OP ARG1 ARG2 (1) - c d (2) * b (1) (3) + a (2) 1编译程序是对高级语言程序的解释执行。(× )2一个有限状态自动机中，有且仅有一个唯一的终态。(×)3一个算符优先文法可能不存在算符优先函数与之对应。 ( )4语法分析时必须先消除文法中的左递归
