基本概念

详细解析

基本概念

自上而下分析法：从输入串开始，逐步进行“归约”，直至归约到文法的开始符号；或者说，从语法树的末端开始，步步向上“归约”，直到根结。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。

详细解析

基本方法

一：带回溯的分析方法。

二：不带回溯的递归子程序（递归下降）分析方法。

主旨

对任意输入串，试图用一切可能的办法，从文法开始符号（根结）出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。

性质

这种分析过程本质上是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。

过程

实现这种自上而下的带回溯试探法的一个简单途径是让每个非终结符对应一个递归子程序。每个这种子程序可作为一个布尔过程。一旦发现它的某个候选与输入串相匹配，就用这个候选去扩展语法树，并返回“真”值；否则，保持原来的语法树和IP值不变，并返回“假”值。

面临的问题

首先，是文法的左递归性问题。一个文法是含有左递归的，如果存在非终结符P

含有左递归的文法将使上述的自上而下的分析过程陷入无限循环。即当试图用P去匹配输入串时，我们会发现，在没有识别任何输入符号的情况下，又得重新要求P去进行新的匹配。

其次，由于回溯就碰到一大堆麻烦事情。如果我们走了一大段错路，最后必须回头，那么，就应把已经做的一大堆语义工作推倒重来。

第三，在上述的自上而下分析过程中，当一个非终结符用某一个候选匹配成功时，这种成功可能仅是暂时的。

第四，当最终报告分析不成功时，我们难于知道输入串中出错的确切位置。

最后，由于带回溯的自上而下分析实际上采用了一种穷尽一切可能的试探法，因此效率很低，代价极高。