自上而下语法分析

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

1、第四章自顶向下语法分析方法自顶向下分析的一般过程和问题FIRST和FOLLOW集定义和计算LL(1)文法定义LL(1)分析程序实现4.1语法分析概述语法分析是编译过程的核心，其任务是在词法分析识别出正确的单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。高级语言的语法结构适合用上下文无关文法来描述，上下文无关文法是语法分析的基础。语法分析在编译系统中所处的位置语法分析器的输入Token序列：词法分析的输出，是各个单词都正确的源程序的变换形式，是一个有限序列语法分析器的输出分析树：表示方法？见教材P

2、89错误处理信息：定位、继续编译语法分析的接口设计语法分析器的功能按照语言的语法构成规则,识别输入的符号串能否构成一个句子。这些规则是用文法的产生式来定义的。问题对给定的一个输入串，如何判定它是不是一个句子？方法根据文法的产生式规则，从开始符号出发，看能否推导出与这个输入串匹配的句子。这就需要建立与输入串匹配的语法分析树。G=({E},{i,+,*,(,)},P,E)P：EE+EEE*EE(E)Ei解：使用最左推导：EE*E(E)*E(E+E)*E(i+E)*E(i+i)*E(i+i)*

3、i例1：判定输入串(i+i)*i是否是下述文法的句子？结论：能够从开始符号出发推导出给定的输入串，因此，是句子。77例2：已知符号串S=cad文法G[Z]:Z→cAdA→ab

4、a求证：SL(G[Z])分析过程是设法建立一棵语法树,使语法树的末端结点与给定符号串相匹配.1.开始:令Z为根结点Z2.用Z的右部,符号串去匹配输入串·ZcAd完成一步推导ZcAd检查c-c匹配A是非终结符,将匹配任务交给A883.选用A的右部符号串匹配输入串A有两个右部,选第一个·cAdabZ完成进一步推导Aab检查,a-a匹配

5、,b-d不匹配(失败)但是还不能冒然宣布SL(G[Z])4.回溯即砍掉A的子树改选A的第二右部·ZcAdaAa检查a-a匹配d-d匹配建立语法树,末端结点为cad与输入cad相匹配,建立了推导序列ZcAdcad∴cadL(G(Z))S=cadG[Z]:Z→cAdA→ab

6、a分析工作要部分地或全部地退回去重做叫回溯常用的语法分析方法：自顶向下分析法：从文法的开始符号出发，向下推导(使用最左推导)，尽可能使用各种产生式，推导出与输入串匹配的句子，从而建立语法树。自底向上分析法：从输入符号串开始，逐步进行

7、归约(最右推导的逆过程)，直至归约到文法的开始符号，从而建立语法树。具体分类：自顶向下分析递归下降分析预测分析(LL)自底向上分析算符优先分析LR分析4.2自顶向下语法分析自上而下分析主要是：对任何输入串，试图用一切可能的办法，从文法的开始符号出发，自上而下地为输入串建立一个语法树。从推导的角度看，从开始符号出发，使用最左推导，试图推导出与输入符号串相同的句子。从语法树的角度看，从根节点出发，反复使用所有可能的产生式，谋求输入串的匹配，试图向下构造一棵语法树，其末端节点正好与输入符号串相同。需要反复试探。句型

8、的推导最左（最右）推导：在推导的任何一步αβ，其中α、β是句型，都是对α中的最左（右）非终结符进行替换最右推导被称为规范推导。由规范推导所得的句型称为规范句型。复习自顶向下分析方法特点1.分析过程是带有预测的，对输入符号串要预测属于什么语法成分，然后根据该语法成分的文法建立语法树。2.分析过程是一种试探过程，是尽一切办法(选用不同规则)设法建立语法树的过程，由于是试探过程，故难免有失败，所以分析过程需进行回溯，因此我们也称这种方法是带回溯的自顶向下分析方法。例1：设有文法(1)SxAy(2)A>

9、>=现

10、有输入串：x>=y其分析过程如右：SxAy**失败，需要退回，重新选取A的侯选式，这时使得分析器的动作不稳定思考：产生回溯的原因？X>=y输入符号串：问题1：回溯真正原因是：文法的产生式有问题。回溯问题1414什么是回溯?分析工作要部分地或全部地退回去重做叫回溯造成回溯的条件：文法中，对于某个非终结符号的规则其右部有多个选择，并根据所面临的输入符号不能准确的确定所要选择时，就可能出现回溯。回溯带来的问题：严重的效率低，只有在理论上的意义而无实际意义U::=1

11、2

12、3左递归：文法中存在某个AVn，有AA

13、。直接左递归：有产生式AA间接左递归：例2：设有文法G(E)：(1)EE+T

14、T(2)TT*F

15、F(3)F(E)

16、i现有输入串i*i+i,分析过程是：EE+TE+TE+T…失败：对左递归文法使用最左推导，出现死循环。思考：产生左递归的原因？问题2：左递归真正原因是：文法的产生式有问题。结论1.左递归和回溯问题的产生直接与描述语言的文法有关2.应该改造文法，使其不含左递归和回溯，才能进行确