编译原理复习整理(重点含)选读.docx

1、给出下面语言的相应文法 。 L1={anbnci|n≥1,i≥0}从n，i的不同取值来把L1分成两部分：前半部分是anbn：A→aAb|ab后半部分是ci：B→Bc|ε所以整个文法G1[S]可以写为：G1(S):S→AB ； A→aAb|ab ；B→cB|ε3、构造一个DFA，它接受={a，b}上所有包含ab的字符串。（要求：先将正规式转化为NFA，再将NFA确定化，最小化）4、对下面的文法G:E→TE’ E’→+E|ε T→FT’ T’→T|εF→PF’ 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^#EETTFFP考虑文法: S→AS|b A→SA|a（1）列出这个文法的所有LR(0) 项目。0.1.2.3.4.5.6.7.8.9.10.11.(2)给出识别文法所有活前缀的DFA。 S A S a A Sb确定化：SAab{0,2,5,7,10}{1,2,5,7,8,10}{2,3,5,7,10}{11}{6}{1,2,5,7,8,10}{2,5,7,8,10}{2,3,5,7,9,10}{11}{6}{2,3,5,7,10}{2,4,5,7,8,10}{2,3,5,7,10}{11}{6}{2,5,7,8,10}{2,5,7,8,10}{2,3,5,7,9,10}{11}{6}{2,3,5,7,9,10}{2,4,5,7,8,10}{2,3,5,7,10}{11}{6}{2,4,5,7,8,10}{2,5,7,8,10}{2,3,5,7,9,10}{11}{6}{11}φφφφ{6}φφφφ A S S A a b S a A S b S A b a A A Sb a a b b a DFA6、设有文法：P→P+Q|QQ→Q*R|RR→(P)|i（1）证明Q*R+Q+Q是它的一个句型。（3分)P=P+Q=P+Q+Q=Q+Q+Q=Q*R+Q+Q给出Q*R+Q+Q的所有短语，直接短语和句柄。(4分)短语: Q*R,Q*R+Q,Q*R+Q+Q 直接短语: Q*R 句柄: Q*R（3）给出句子ｉ+ｉ*ｉ的最右推导。(4分)（4）给出句子ｉ+ｉ*ｉ的最左推导。(4分)7、设有文法：E→E+T|TT→T*F|FF→(E)|i（1）证明E+T*