编译原理复习整理(重点含答案).pdf

1、给出下面语言的相应文法。nni

L1={abc|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确定化，最小化）

1/22

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)|^|ab|

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,^,+,),#}=φ

2/22

FIRST((E))∩FIRST(a)∩FIRST(b)∩FIRST(^)=φ

所以,该文法式LL(1)文法.

(3)

+*()ab^#

EETEETEETEETE

EE

EEE



TFTTFTTFTTFT

T

TTTTTTTTTTT

T

FFPFFPFFPFFPF

