学习资料
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)考虑下列产生式:
E???E|?T??T|?F??*F?|?P?(E)|^|a|b
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)
+ * ( ) a b ^ # 仅供学习与参考 学习资料
E E' T T' F F' P E?TE' E?TE' E?TE' E?TE' E???E E??? E??? T?FT? T?FT? T?FT? T?FT? T??? T??T T??? T??T T??T T??T T??? F?PF? F?PF? F?PF? F?PF? F??? F??*F? F??? F??? F??? F??? F??? F??? P?(E) P?a P?b P?^
5、考虑文法: S→AS|b A→SA|a（1）列出这个文法的所有LR(0) 项目。
0.S???S 1.S??S? 2.S??AS 3.4.S?A?SS?AS? 5.S??b6.S?b?7.A??SA8.A?S?A 9.A?SA? 10.A??a 11.A?a?
(2)给出识别文法所有活前缀的DFA。
S A ? 7 8 9 S 仅供学习与参考
1 学习资料
? ? ? ? a 10 0
? ? ? 2 3 A S ? ?
b 确定化：
{0,2,5,7,10} S {1,2,5,7,8,10} {1,2,5,7,8,10} {2,3,5,7,10} {2,4,5,7,8,10} {2,5,7,8,10} {2,3,5,7,9,10} {2,4,5,7,8,10} {2,5,7,8,10} {2,4,5,7,8,10} {2,5,7,8,10} {2,3,5,7,9,10} {11} {6} {2,3,5,7,9,10} {2,3,5,7,10} {11} {11} {6} {6} {2,3,5,7,10} {11} {6} {2,5,7,8,10} {2,3,5,7,9,10} {11} {6} A {2,3,5,7,10} a {11} b {6} 5 4 11 6 仅供学习与参考
学习资料
{11} {6}
A S
3:S?5:A?S?A 6:A?SA? φ φ φ φ φ φ φ φ ?S? A?S?A S A a S??AS S??b A??SA
A??SA S??b A??a b
S a A S b S A b a A
0:S???S 4:S?A?S 7:S?AS? S??AS S?A?S S??AS S??AS A?S?A A S S??b S??b 仅供学习与参考 A??SA S??AS S??b
编译原理复习整理(重点含答案)培训资料
