自上而下分析法_社会科学术语 - 威林百科weilinceramic.com

自上而下分析法

社会科学术语

自上而下分析法是从文法开始符号开始，不断进行推导，直到推导所得的符号串与输入串相同为止。

详细解析

基本方法

一：带回溯的分析方法。

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

主旨

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

性质

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

过程

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

面临的问题

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

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

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

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

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

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

参考资料

最新修订时间：2022-01-16 13:53

条目作者

概述

参考资料