自顶向下的句法分析.ppt

《自顶向下的句法分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章自顶向下的句法分析自顶向下分析方法递归下降分析法LL(1)分析法自底向上分析方法算符优先分析法LR分析法4.1句法分析器概述句法分析是编译程序的核心部分。任务：识别由词法分析得出的单词序列是否是合法的句子。理论基础：上下文无关文法和下推自动机句法分析方法：自顶向下(top-down)的句法分析：反复使用不同产生式进行推导以谋求与输入符号串相匹配。自底向上(bottom-up)的句法分析：对输入符号串寻找不同产生式进行归约直到文法开始符号。注：这里所说的输入符号指词法分析所识别的单词。确定的自顶向下分析思想例文法G1[S]:SpASqBAcAdAaBdBBbW=p

2、ccadd自顶向下的推导过程：SpApcAdpccAddpccaddSpASpAcAdSpAcAdcAdSpAcAdcAda文法G1[S]:SpA

3、qBAcAd

4、aBdB

5、b文法的特点：每个产生式的右部都由终结符号开始。如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。文法G2[S]:SApSBqAaAcABbBdBW=ccap自顶向下的推导过程：SApcApccApccapSApSApcASApcAcASApcAcAa文法G2[S]:SAp

6、BqAa

7、cABb

8、dB文法的特点：每个产生式的右部不全是由终结符号开始。如果两

9、个产生式有相同的左部，那么它们的右部由不同的终结符或非终结符开始。文法中无空产生式。为了实现确定的(即无回溯的)自顶向下分析，则要求文法满足下述两个条件：(1)文法不含左递归直接左递归：AA…间接左递归：AB…，B+A左递归文法使自上而下分析工作陷入死循环。例如，如果有产生式EE+TEE+TE+T+TE+T+T+T…(2)无回溯，对文法的任一非终结符号，当其产生式右部有多个候选式可供选择时，各候选式所推导出的终结符号串的首字符集合要两两不相交。例如，如果有文法G[S]：SxAyAab∣a输入串xay的分析就需要回溯。带回溯的自顶向下分析方法实际上是一种穷举的试探方法

10、，其分析效率极低。消除左递归1.直接左递归方法是引入一个新的非终结符，把含有左递归的产生式改为右递归。设关于A的产生式为AA1∣A2∣…∣Am∣1∣2∣…∣n其中，每个i都不为且每个j都不以A开头，则消除A的直接左递归就是将其改写为：例如，含有直接左递归的表达式文法G[E]为：G[E]:EE+T∣TTT*F∣FF(E)∣i消去直接左递归后得到文法G'[E]为：G'[E]:ETE'E'+TE'∣TFT'T'*FT'∣F(E)∣i2.间接左递归将间接左递归变为直接左递归，然后消除直接左递归。如文法G[A]含有间接左递归：AaBAaBAaBAB

11、bABbABbBAcBaBcBaBcB'

12、dB'BdBBbcB'bcB'

13、εBd消除文法中一切左递归的算法要求：无回路(即不存在A+A的推导)充分条件：文法不含形如AA的有害产生式，也不含A的空产生式。(1)将所有非终结符排序：A1、A2、…、An；(2)for(i=1;i<=n;i++){for(j=1;j<=i−1;j++){若Aj的所有产生式为：Aj1

14、2

15、…

16、k则把形如AiAjr的产生式变换为：Ai1r

17、2r

18、…

19、kr}消除Ai规则中的一切直接左递归;}(3)删除无用的产生式这里第二步所做的工作是：a)若产生式出现直接左递归则用消除

20、直接左递归的方法消除掉。b)若产生式右部最左符号是非终结符且其序号大于左部的非终结符，则不处理。c)若序号小于左部的非终结符，则将这序号小的非终结符用其右部串来取代，然后消除新的直接左递归。注意：1）若非终结符排列顺序不同，改写后的文法也不同，但它们是等价的。2）开始符号不能改变。例：对下面文法消除左递归：(1)SQc

21、c(2)QRb

22、b(3)RSa

23、a1)对非终结符排序：S、Q、R2)把(1)代入(3)得：(4)RQca

24、ca

25、a再把(2)代入(4)得：(5)RRbca

26、bca

27、ca

28、a对(5)消除直接左递归得：(6)RbcaR'

29、caR'

30、aR'(7)R'bcaR'

31、

32、得到不含左递归的文法：(1)、(2)、(6)、(7)对非终结符也可以有不同的排序。1）对非终结符重新排序：R、Q、S2）把(3)代入(2)得：(4')QSab

33、ab

34、b再把(4')代入(1)得：(5')SSabc

35、abc

36、bc

37、c对(5')消除直接左递归得：(6')SabcS'

38、bcS'

39、cS'(7')S'abcS'

40、得到不含左递归的文法：(6')、(7')(1)SQc

41、c(2)QRb

42、b(3)RSa

43、a消除回溯产生回溯的原因