语法分析自上而下分析.ppt

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

1、语法分析自上而下分析在第三章，用正规式描述了单词符号的结构，并研究了如何用有限自动机构造词法分析器的问题。由于正规式与正规文法是等价的，它们的描述能力有限，而高级语言的语法结构适合用上下文无关文法描述，因此，我们将上下文无关文法用作语法分析的基础。本章和下一章，我们将介绍编译程序构造中的一些典型的语法分析方法。语法分析—自上而下分析语法分析器的功能自上而下分析面临的问题LL（1）分析法左递归的消除消除回溯、提左因子LL（1）分析条件递归下降分析程序构造预测分析程序预测分析程序工作过程预测分析表的构造作业语法分析器的功能语法分析是编译过程的核心部分。它的任务是在词

2、法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。语言的语法结构是用上下文无关文法描述的。因此，语法分析器的工作本质上就是按文法的产生式，识别输入符号串是否为一个句子。所说的输入串是指由单词符号（文法的终结符）组成的有限序列。对一个文法，当给你一串（终结）符号时，怎样知道它是不是该文法的一个句子（“程序”）呢？这就要判断，看是否能从文法的开始符号出发推导出这个输入串。或者，从概念上讲，就是要建立一棵与输入串相匹配的语法分析树。按照语法分析树的建立方法，我们可以粗略地把语法分析办法分成两类：一类是自上而下分析法，另一类是自下而上分析法。自上而

3、下分析面临的问题自上而下就是从文法的开始符号出发，向下推导，推出句子。我们首先将简单地介绍自上而下分析的一般方法。这种方法是带“回溯”的。下一节，将着重讨论一种广为使用的不带回溯的递归子程序（递归下降）分析方法。自上而下分析的主旨是，对任何输入串，试图用一切可能的办法，从文法开始符号（根结）出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。这种分析过程本质上是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。例4.1假定有文法（1）S→xAy（2）A→**

4、*（4.1）以及输入串x*y(记为α）。为了自上而下构造α的语法树，我们首先按

5、文法的开始符号产生根结S，并让指示器IP指向输入串的第一个符号x。然后，用S的规则（此处关于S的规则仅有一条）把这棵树发展为SxAy非终结符A有两个候选，试着用它的第一个候选(A→**)去匹配输入串，于是把语法树发展为SxAy**子树A的最左子结和IP所指的符号*相符，然后我们再把IP调为指向下一符号并让A的第二个子结进入工作。但A的第二子结*和当前所指的符号y不一致。因此，A告失败。这意味着A的第一个候选此刻不适用于构造α的语法树。这时应该回头（回溯），看A是否还有别的候选。为了这种回溯，我们一方面应把A的第一候选所发展的子树注销掉，另一方面应把IP恢复为进入A

6、时的原值，也就是让它重新指向第二个输入符号，。现在我们试探A的第二个候选（A→*），即考虑如下的语法树：SxAy*由于子树A只有一个子结，而且它和IP所指的符号相一致，于是，A完成了匹配任务。在A获得匹配后，指示器IP应指向下一个未被触及符号y。在S的第二子结A完成匹配后，接着就轮到第三个子结y进行工作。由于这个子结和最后一个输入符号相符，于是，我们完成了为α构造语法树的任务，证明了α是一个句子。实现这种自上而下的带回溯试探法的一个简单途径是让每个非终结符对应一个递归子程序。每个这种子程序可作为一个布尔过程。一旦发现它的某个候选与输入串相匹配，就用这个候选去扩展语

7、法树，并返回“真”值；否则，保持原来的语法树和IP值不变，并返回“假”值。但是，自上而下分析法存在许多困难和缺点首先，是文法的左递归性问题。一个文法是含有左递归的，如果存在非终结符PP⇒+Pα含有左递归的文法将使上述的自上而下的分析过程陷入无限循环。即，当试图用P去匹配输入串时，我们会发现，在没有识别任何输入符号的情况下，又得重新要求P去进行新的匹配。因此，使用自上而下分析法必须消除文法的左递归性。其次，由于回溯，就碰到一大堆麻烦事情。如果我们走了一大段错路，最后必须回头，那么，就应把已经做的一大堆语义工作（指中间代码产生工作和各种表格的簿记工作）推倒重来。这些事

8、情既麻烦又费时间，应设法消除回溯。第三，在上述的自上而下分析过程中，当一个非终结符用某一候选匹配成功时，这种成功可能仅是暂时的。例如，就文法(4.1)而言，考虑输入串x**y。若对A首先使用第二个候选式，A将成功地把它的唯一子结*匹配于输入串的第二个符号。但S的第三个子结Y与第三个输入符号*不匹配。因而，导致了无法识别输入串x**y是一个句子的事实。然而，若A首先使用它的第一个候选**，则整个输入串即可获得成功分析。这意味着，A首先使用第二个候选所得的成功匹配是虚假的。由于这种虚假现象，我们需要更复杂的回溯技术。一般说，要消除虚假匹配是很困难的。但若从最长的候选开

9、始匹配，虚