如何判断一个文法是LL(1)文法.ppt

《如何判断一个文法是LL(1)文法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、LL的含义－自左向右扫描分析输入符号串－从识别符号开始生成句子的最左推导LL(1):向前看一个输入符号，便能唯一确定当前应选择的规则LL(k):向前看k个输入符号，才能唯一确定当前应选择的规则4.2.3LL(1)文法的判别要构造确定的自顶向下分析程序要求描述文法必须是LL(1)文法同一非终结符有多个候选式时引起回溯的原因【例4.1】α=acbG[S]:S→aAbA→cd

2、c（1）候选式的终结首符号相同（2）候选式的终结首符号相同【例4.8】S→AaA→a

3、1.FIRST集FIRST(α)：从α可能推导出的所有开头终结符号或ε对于文法G的所有非终结符的每个候选式，其终

4、结首符号集称为FIRST集，定义如下：，则规定∈FIRST()若【例】S→aAbA→cd

5、ca…，a∈VTFIRST()={a

6、FIRST(aAb)={a}FIRST(cd)={c}FIRST(c)={c}【例】S→AaA→a

7、FIRST(a)={a}FIRST()={}FIRST(Aa)={a}FIRST(S)={a}FIRST(A)={c}FIRST(S)={a}FIRST(A)={a,}（1）若α=aα′，且a∈VT，则a∈FIRST(α)；例：FIRST(i)={i}FIRST(+TE')={+}E→TE'E'→+TE'

8、T→FT'T'→*

9、FT'

10、F→(E)

11、i构造FIRST集的算法（2）若α=Xα′，X∈VN，且有产生式X→b…，则把b加入到FIRST(α)中；例：FIRST(FT')={(,i}??①将FIRST(X1)中的一切非ε的终结符加进FIRST(α)；②若ε∈FIRST(X1),则将FIRST(X2)中的一切非ε的终结符加进FIRST(α)；③若ε∈FIRST(X1)且ε∈FIRST(X2),则将FIRST(X3)中的一切非ε的终结符加进FIRST(α)；④依此类推，若对于一切1≤i≤n,ε∈FIRST(Xi)，则将ε加进FIRST(α)。（3）若α=X1X2…Xnα′，其中Xi∈VN,1

12、≤i≤n；E→TE'E'→+TE'

13、T→FT'T'→*FT'

14、F→(E)

15、i例：FIRST(FT')=注意：要顺序往下做，一旦不满足条件，过程就要中断进行FIRST(F)-{ε}={(,i}FIRST(F)={(,i}FIRST(T’)={*,ε}FIRST(T)=FIRST(F)-{ε}={(,i}FIRST(E’)={+,ε}FIRST(E)=FIRST(T)-{ε}={(,i}FIRST(TE’)=FIRST(T)-{ε}={(,i}FIRST(+TE’)={+}FIRST(ε)={ε}FIRST(FT’)=FIRST(F)-{ε}={(,i}FIRST(*F

16、T’)={*}FIRST(（E）)={(}FIRST(i)={i}【例4.9】G[E]E→TE'E'→+TE'

17、T→FT'T'→*FT'

18、F→(E)

19、i2.FOLLOW集FOLLOW(A)：是所有句型中紧接A之后的终结符号或#对于文法G的非终结符的后继符号集称为FOLLOW集，定义如下：…A，则规定#∈FOLLOW(A)若S…Aa…，a∈VT}FOLLOW(A)={a

20、SE→TE'E'→+TE'

21、T→FT'T'→*FT'

22、F→(E)

23、iT+TE'，则+∈FOLLOW(T)E构造集合FOLLOW的算法（1）若为开始符号，则把“#”加入FOLLOW(A)中；（2）若

24、B→A(≠)，则把FIRST()-{}加入FOLLOW(A)中；注：FOLLOW集合中不能有ε（3）若B→A或B→A，且则把FOLLOW(B)加入FOLLOW(A)中。，E→TE'E'→+TE'

25、T→FT'T'→*FT'

26、F→(E)

27、i#∈FOLLOW(E)由F→(E)可知，)∈FOLLOW(E)由E→TE'，应把FOLLOW(E)加入∈FOLLOW(E')由E'→+TE'且E'ε，应把FOLLOW(E')加入FOLLOW(T)【例4.10】G[E]E→TE'E'→+TE'

28、T→FT'T'→*FT'

29、F→(E)

30、i求FOLLOWFOLLO

31、W(E)={#,)}∵E是开始符号∴#∈FOLLOW(E)又F→(E)∴)∈FOLLOW(E)FOLLOW(E’)={#,)}∵E→TE’∴FOLLOW(E)加入FOLLOW(E’)FOLLOW(T)={+,),#}∵E’→+TE’∴FIRST(E’)-{ε}加入FOLLOW(T)又E’ε，∴FOLLOW(E’)加入FOLLOW(T)FOLLOW(T’)=FOLLOW(T)={+,),#}∵T→FT’∴FOLLOW(T)加入FOLLOW(T’)FOLLOW(F)={*,+,),#}∵T→FT’∴FOLLOW(F)=FIRST（T’）-{