编译原理课件Chapt4-2.ppt

《编译原理课件Chapt4-2.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第四章语法分析—自上而下分析编译原理本章主要内容本章主要介绍语法分析的处理语法分析的任务自顶向下分析法4.3.2消除回溯、提左因子为了消除回溯就必须保证：对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应是确信无疑的。A→1

2、2

3、…

4、nSa….IPA......同一非终结符有多个候选式时引起回溯的原因【例】α=acbG[S]:S→aAbA→cd

5、c（1）候选式的终结首符号相同令G是一个不含左递归的文法，对G的所有非终结符的每个候选定义它的终

6、结首符集FIRST()为：特别是，若，则规定FIRST()。如果非终结符A的所有候选首符集两两不相交，即A的任何两个不同候选i和jFIRST(i)∩FIRST(j)＝当要求A匹配输入串时，A就能根据它所面临的第一个输入符号a，准确地指派某一个候选前去执行任务。这个候选就是那个终结首符集含a的。1.FIRST集FIRST(α)：从α可能推导出的所有开头终结符号或ε对于文法G的所有非终结符的每个候选式，其终结首符号集称为FIRST集，定义如下：，则规定∈FIRST()若【例】S→aAbA→cd

7、ca

8、…，a∈VTFIRST()={a

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

10、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'

11、T→FT'T'→*FT'

12、F→(E)

13、i构造FIRST集的算法（2）若α

14、=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≤i≤n；E→

15、TE'E'→+TE'

16、T→FT'T'→*FT'

17、F→(E)

18、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(*FT’)=

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

20、T→FT'T'→*FT'

21、F→(E)

22、i如何将一个文法改造成任何非终结符的所有候选首符集两两不相交呢？提取公共左因子:假定关于A的规则是A→1

23、2

24、…

25、n

26、1

27、2

28、…

29、m(其中，每个不以开头)那么，可以把这些规则改写成A→A

30、1

31、2

32、…

33、mA→1

34、2

35、…

36、n经过反复提取左因子，就能够把每个非终结符(包括新引进者)的所有候选首符集变成为两两不相交。当一个文法不含左递归，并且满足每个

37、非终结符的所有候选首符集两两不相交，是不是就一定能进行有效的自上而下的分析了呢？E→TEE→+TE

38、T→FTT→*FT

39、F→(E)

40、ii+i例如：i+iIPEG(E):E→TEE→+TE

41、T→FTT→*FT

42、F→(E)

43、ii+iIPETE’G(E):E→TEE→+TE

44、T→FTT→*FT

45、F→(E)

46、ii+iIPETE’FT’G(E):E→TEE→+TE

47、T→FTT→*FT

48、F→(E)

49、ii+iIPETE’FT’iG(E):E→TEE→+TE

50、T→FT

51、T→*FT

52、F→(E)

53、ii+iIPETE’FT’iG(E):E→TEE→+TE

54、T→FTT→*FT

55、F→(E)

56、ii+iIPETE’FT’iG(E):E→TEE→+TE

57、T→FTT→*FT

58、F→(E)

59、ii+iIPETE’FT’i+TE’G(E)