编译原理课件语法分析总结.ppt

《编译原理课件语法分析总结.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、确定的自上而下分析法自下而上分析法递归下降分析法预测分析法本章小结本章介绍了四种典型的语法分析方法算符优先分析法LR分析法LR(0)分析法SLR(1)分析法LR(1)分析法LALR(1)分析法确定的自上而下分析法要求描述语言的文法是LL(1)文法。1.LL(1)文法的判别方法。(1)求文法每个产生式右部符号串的FIRST集。(2)求文法各个非终结符的FOLLOW集。本章小结一.确定的自上而下分析法(3)求文法每个产生式的SELECT集。(4)求相同左部产生式的SELECT交集。对文法G的每一个非终结符A的产生式SELECT(A→αi)∩SELECT(A→αj)=Φ(i≠j)则文法G是一个

2、LL(1)文法本章小结A→α1

3、α2

4、…

5、αn下面条件成立:2.LL(1)文法是无左递归、无二义性文法。3.将非LL(1)文法改写为LL(1)文法的方法。(1)消除文法直接左递归P→Pα

6、β改写为P→βP',P'→αP'

7、ε或P→β{α}本章小结(2)提取公共左因子本章小结若A→αβ1

8、αβ2

9、…

10、αβn提取公共左因子将文法改写成:A→αA'A'→β1

11、β2

12、…

13、βn4.根据文法规则构造递归下降分析程序和预测分析表的方法5.注意LL(1)分析法与LR分析法的区别本章小结LL(1)分析法(预测分析法)是自上而下的语法分析法,要求文法为LL(1)文法LR分析法是自下而上的语法分析法,只要文法

14、是上下文无关文法例1设有文法G[E]：为消除文法直接左递规,请改写文法,改写后的文法为:本章小结E→E+T

15、E－T

16、TT→T*F

17、T/F

18、FF→(E)

19、idT{+T

20、－T}E→本章小结E→E+T

21、E－T

22、TT→T*F

23、T/F

24、FF→(E)

25、idF{*F

26、/F}T→(E)

27、idF→例2设有文法G[S]S→aAbDe

28、dA→BSD

29、eB→SAc

30、cD

31、εD→Se

32、ε本章小结1.计算文法G[S]每个非终结符的FIRST集和FOLLOW集。2.判断文法G[S]是否LL(1)文法。本章小结对每一文法符号X∈V,求FIRST(X)的规则:FIRST(α)={a

33、αa…且a∈VT}*,则规定ε∈FI

34、RST(α)若αε*1.若X∈VT,则FIRST(X)={X}2.若X∈VN且有X→a…,则把a加入FIRST(X)中,若X→ε,则把ε加入FIRST(X)中3.若X→Y…,Y∈VN,则把FIRST(Y)中所有非ε元素加入FIRST(X)中FIRST(S)=FIRST(aAbDe)∪FIRST(d)={a,d}本章小结FIRST(A)=FIRST(B)∪FIRST(e)=FIRST(S)∪FIRST(cD)∪{e}={a,d,c,e}S→aAbDe

35、dA→BSD

36、eB→SAc

37、cD

38、εD→Se

39、ε问:能否∪ε因为从A*/ε,所以εFIRST(A)FIRST(B)=FIRST(S)∪

40、FIRST(cD)∪{ε}={a,d,c,ε}FIRST(D)=FIRST(Se)∪{ε}={a,d,ε}本章小结FOLLOW(A)={a

41、S…Aa…且a∈VT}*若有S…A,*则规定$∈FOLLOW(A)。求FOLLOW(A)的规则:1.对文法的开始符号S,令$∈FOLLOW(S)2.若A→αBβ是一条规则,则将FIRST(β){ε}加到FOLLOW(B)中3.若A→αB是一条规则,或A→αBβ是一条规则而βε,则把FOLLOW(A)加到FOLLOW(B)中*FOLLOW(S)={$,a,b,c,d,e}FOLLOW(A)={b,c}本章小结FOLLOW(B)={a,d}FOL

42、LOW(D)={a,b,c,d,e}S→aAbDe

43、dA→BSD

44、eB→SAc

45、cD

46、εD→Se

47、εFIRST(D)={a,d,ε}FIRST(S)={a,d}FIRST(A)={a,d,c,e}根据LL(1)文法的定义有:SELECT(S→aAbDe)∩SELECT(S→d)=FIRST(aAbDe)∩FIRST(d)=Φ本章小结SELECT(A→BSD)∩SELECT(A→e)=FIRST(BSD)∩FIRST(e)=ΦS→aAbDe

48、dA→BSD

49、eB→SAc

50、cD

51、εD→Se

52、εSELECT(B→SAc)∩SELECT(B→cD)=FIRST(SAc)∩FIRST(cD)=ΦSE

53、LECT(B→SAc)∩SELECT(B→ε)=FIRST(SAc)∩{ε,a,d}≠ΦFOLLOW(B)={a,d}所以该文法不是LL(1)文法本章小结(二)LR分析法大多数用上下文无关文法描述的语言都可以用相应的LR分析器予以识别。1.LR分析法是一种规范归约分析法，本章小结2.从给定的上下文无关文法构造LR分析表的方法是：对LR(1)或LALR(1)分析表，构造LR(1)项目集规范族。(1)对LR(0)或SLR(1)分析表，构