自顶向下语法分析方法.ppt

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

1、第5章自顶向下语法分析方法语法分析（SyntaxAnalysis）是编译程序的核心部分。词法分析只是将字符形式的源程序中的各个单词识别出来，形成单词的机内表示形式，但是这些单词串如何构成更大的语法成分——语句，那就由语法分析来完成。语法分析的主要任务就是“组词成句”，即在词法分析识别出单词串的基础上，根据语言的语法规则，识别出各类语法成分，如“语句”、“程序”等。将完成语法分析任务的程序称为语法分析程序，也称为语法分析器或简称分析器。程序设计语言的语法结构是用上下文无关文法描述的，因此，语法分析器的实现原理就是

2、按所给定的文法G，识别输入符号串α是否为一个句子（即α∈L(G)成立吗？），同时检查和处理语法错误。语法分析的关键是句型识别问题。给定一串单词（即文法的终结符），怎样知道它是不是该文法产生的一个句子呢？可以利用推导，或者利用语法树来进行判断。一般来说，语法分析的过程就是为一个句子建立语法树的过程。语法分析的方法很多，按照建立语法树的不同方向，通常将语法分析分为两类，一类是自顶向下分析法，另一类是自底向上分析法。本章主要介绍自顶向下分析法，自底向上分析法。第4章教学内容语法分析的任务；确定的自顶向下语法分析的基本

3、思想；LL(1)文法的定义和判别方法；非LL(1)文法到LL(1)文法的等价变换；确定的自顶向下分析方法：递归下降分析法预测分析法自底向上语法分析的基本思想；短语、直接短语和句柄的定义，以及如何利用语法树寻找短语、直接短语和句柄。自底向上语法分析方法：优先分析法LR分析法一、自顶向下的语法分析思想【自顶向下（top-down）分析法的基本思想】自顶向下语法分析的基本思想是以文法的开始符号为树根，采用最左推导，试图自上而下地为输入的单词串构造一棵语法树。若语法树的端末节点从左向右排列恰好是输入串，则该输入串就是文

4、法的句子，否则就不是。这种分析过程实质是一种试探过程，是反复使用不同产生式来匹配输入串的过程。示例【例4.1】设有以下文法G1[S]:S→aABA→bA

5、cB→dBe

6、de输入串abbcde的最左推导如下：SaABabABabbABabbcBabbcde因此，输入串abbcde是该文法G1的句子。下面从建立语法树来看句子的推导过程。为了自顶向下地构造输入串abbcde的语法树，首先按文法的开始符号产生根节点S，再根据产生式规则自顶向下地生长这棵语法树。语法树的建立过程如图所示。SaABbAbAcde自

7、顶向下分析法也称面向目标的分析方法，在对输入串进行最左推导的过程中，在选择产生式时其实是一种试探方法，如果每一步选择产生式来匹配的时候都能够每选必中，则这种方法称为确定的分析方法；否则在选择产生式时面临多种可能，不知道选择哪一个产生式合适，就是不确定的分析方法。因此自顶向下分析法又可分为确定的和不确定的两种，确定的分析方法对文法有一定的限制，但由于实现方法简单、直观，便于手工构造或自动生成语法分析器，因而仍是目前常用的方法之一。不确定的方法即带回溯的分析方法，这种方法实际上是一种穷举的试探方法，因此效率低，代价

8、高，因而极少使用。1.不确定的自顶向下分析不确定的自顶向下分析法的基本思想是，对任何输入串α试图用一切可能的办法，从文法的开始符号出发，自上而下的为它建立一棵语法树。如果试探成功，则α为相应文法的句子，否则α就不是文法句子。这种分析过程本质上是一种穷举试探过程，是反复使用不同规则，谋求匹配输入串的过程。因此这种匹配过程往往一次不能成功，需要重新匹配，称为回溯。引起回溯的原因在于文法中关于某个非终结符的产生式有多个时，而根据面临的输入符无法唯一确定选择哪个产生式来匹配，从而引起回溯。自顶向下分析法中存在的问题回溯

9、问题左递归问题回溯问题回溯时需要恢复到出错点位置，删去曾经匹配过的符号，还包括一些语义处理。因此处理回溯是一项复杂的工作，在回溯时，要清除在回溯之前编译程序所做的大量记录工作，然后重新开始记录，这就降低了语法分析的效率。避免回溯是自顶向下语法分析中需要解决的问题之一。回溯的具体表现回溯具体表现为下列两种情况：1.由于相同左部的产生式的候选式的FIRST集交集不为空而引起回溯。2.由于相同左部非终结符的候选式存在能推导出ε的产生式，且该非终结符的FOLLOW集中含有其它候选式的FIRST集的元素。表现一示例由于相

10、同左部的产生式的候选式的FIRST集交集不为空而引起回溯：【例4．6】设有文法G6[S]为：S→xAyA→**

11、*串x*y的分析过程SxAy**(S,x)选择产生式S→xAy当前要替换的非终结符当前要匹配的输入符(A,*)可选择两个产生式A→**或A→*SxAy*回溯：回到出错点，重新选择产生式A→*，成功原因上述文法发生回溯的原因就在于A的两个产生式的候选式的第一个符号都是*，从而根