编译原理与技术讲义-第4章.ppt

《编译原理与技术讲义-第4章.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、编译原理与技术第4章自顶向下的语法分析青岛大学信息工程学院主要内容自顶向下语法分析概述LL(1)文法递归下降分析技术预测分析技术LL(1)分析中的错误处理编译原理与技术24.1自顶向下语法分析的一般方法基本思想：对任何输入串，试图用一切可能的办法，从文法开始符号出发，自上而下，从左到右地为输入串建立分析树。或者说，为输入串寻找最左推导。特点：本质上是一种试探过程，反复使用不同的产生式谋求匹配输入串。编译原理与技术3例4.1：设文法G[S]：S→cAd，A→ab

2、a，输入串为cad，自顶向下进行语法分析，并构造相应语法树。4.1自顶向下语法分析的一般方法先按文法

3、的开始符号产生根结点S，选择S惟一的产生式构造语法树，如图4.1(a)所示。把S的子结点从左到右与输入串中的字符相比较，第一个子结点c匹配输入串第一个符号。第二个子结点是非终结符A，要选择A的产生式进一步构造。而A有两个候选式，先选择A→ab构造语法树，如图4.1(b)所示。(a)(b)(c)图4.1输入串cad的语法分析树编译原理与技术4此时A的最左子结点a匹配输入串第二个符号。而A的第二个子结点b和输入串第三个符号不一致，说明A的这个产生式不能用来产生该输入串。这就需要回到子结点A，选用另一个产生式A→a来构造语法树，如图4.1(c)所示。这种回头选用其他

4、产生式的过程称为回溯。回溯时，要把由前面产生式A→ab得到的子树删除，并重新读入在子结点A处的当时符号a。用新的产生式构造语法树后，A的子结点为a，与当前符号一致，读入最后一个输入符号d。此时结点A完成匹配，它的右边是结点d，与当前符号一致。这样就完成了输入串的匹配，说明输入串cad是该文法的一个句子。上面的分析同时也给出了输入串cad的最左推导过程：ScAdcad。4.1自顶向下语法分析的一般方法(a)(b)(c)编译原理与技术5这种一般方法存在一些问题：(1)左递归问题自顶向下分析采取最左推导，文法中含有左递归会使自上而下的分析过程陷入无限循环。因此，

5、必须消除文法的左递归。(2)回溯问题反复寻找可正确匹配的产生式时可能需要不断回溯，虚假匹配现象需要使用更复杂的回溯技术。这样将会产生许多额外工作，因此应设法消除回溯。4.1自顶向下语法分析的一般方法编译原理与技术6(3)出错处理分析不成功时，要确定出错的具体位置比较困难。(4)效率问题这种带回溯的自顶向下方法实际上是一种穷尽一切可能的试探法，因此效率很低，代价较高，从而该方法只有理论意义，在实际应用中价值不大。4.1自顶向下语法分析的一般方法编译原理与技术74.2LL(1)文法要实现无回溯的自顶向下语法分析，对相应文法必须要有一定的限制。首先，文法应该不含左递

6、归，若文法中含有左递归，则需使用文法的等价变换消除左递归。其次，还要消除回溯。通过提取左因子消除某些文法的回溯，为什么？没有左递归和左因子的文法是否一定可以进行确定的自顶向下分析？编译原理与技术8首符集FIRST4.2LL(1)文法例4.2：文法G1[S]:S→pA

7、qBA→cAd

8、aB→dB

9、bw1=pccadd自顶向下的推导过程：SpApcAdpccAddpccadd语法树：ddSpASpAcAdSpAcAdcAdSpAcAcAa编译原理与技术94.2LL(1)文法文法G1[S]:S→pA

10、qBA→cAd

11、aB→dB

12、b这个文法的特点：每个产生式的

13、右部都由终结符号开始。如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。对于这样的文法，分析输入串时，可以跟据输入串的当前符号确定选取产生式。比如w1=pccadd，第一个符号是p，而从开始符号S出发，只有选择产生式S→pA推导，才能出现符号p。同样，要出现第二个符号c，必须选择产生式A→cAd。这样，虽然具有相同左部的产生式不只一个，但文法的特点决定了每一步推导只能选择惟一的产生式，从而可以避免回溯。编译原理与技术104.2LL(1)文法例4.3：文法G2[S]:S→Aa

14、BbA→a

15、cAB→b

16、dBw2=ccaa自顶向下的推导过程：SAac

17、AaccAaccaa语法树：SAaSAacASAacAcASAacAcAa编译原理与技术114.2LL(1)文法文法G2[S]:S→Aa

18、BbA→a

19、cAB→b

20、dB这个文法的特点：每个产生式的右部不全是由终结符号开始。如果两个产生式有相同的左部，那么它们的右部由不同的终结符或非终结符开始。文法中无空产生式。对于这样的文法，分析输入串时，也可以跟据输入串的当前符号确定地选取产生式。比如推导w2=ccaa时，首先考虑开始符号S，它可以推出以A或B开头的符号串。而由以A和B为左部的产生式可知，A只能推出以a,c开头的符号串，B只能推出以b,d开头的符号串。因此

21、，要得到w2的第一个符号c，只有选择产