自顶向下分析概述
# 自顶向下分析概述
# 自顶向下的分析(Top-Down Parsing) 的特点
特点
- 从分析树的顶部(根节点)向底部(叶节点)方向构造分析树
- 可以看成是从文法开始符号
推导出终结符号串 的过程 推导过程示意图
每一步推导中,都需要做两个选择
- 替换当前句型中的哪个非终结符
- 根据选择的非终结符所处的位置,可分为最左推导与最右推导
- 用该非终结符的哪个候选式进行替换
# 最左推导(Left-most Derivation)
在最左推导中,总是选择每个句型的最左非终结符进行替换
最左推导示意图
#
最左句型
- 如果
经过若干步最左推导可得到 , 则记为 - 称
是当前文法的最左句型(left-sentential form) 的形式为 为终结符号串
- 称
# 自顶向下的语法分析采用最左推导方式
根据输入流中的当前字符(终结符),选择最左非终结符的一个候选式
- 如果有一个候选式符合输入字符串,则读入下一个字符
- 如果不匹配,且候选式中有
, 则选择 , 然后继续选择最左非终结符进行匹配
自顶向下语法的执行过程
# 自顶向下语法分析的通用形式
# 递归下降分析
递归下降 (Recursive-Descent Parsing) 分析是自顶向下语法分析的通用形式
由一组过程组成,每个过程对应一个非终结符
从文法开始符号
对应的过程开始,其中递归调用文法中其它非终结符对应的过程 - 如果
对应的过程体恰好扫描了整个输入串,则成功完成语法分析
代码示例
void A( ) { 选择一个A产生式, A →X1 X2 … Xk ; for ( i = 1 to k ) { if ( Xi是一个非终结符号) 调用过程 Xi ( ) ; else if ( Xi 等于当前的输入符号a) 读入下一个输入符号; else /* 发生了一个错误 */ ; } }
1
2
3
4
5
6
7
8
9
10示意图
- 如果
如果 A 有多个候选式, 可能需要回溯(backtracking),导致效率较低
- 需要回溯的分析,称为不确定的分析
# 预测分析
预测分析的特点
- 预测分析是递归下降分析技术的一个特例
- 通过在输入中向前看固定个数(通常是一个)的符号来选择正确的
产生式 - 可以对某些文法构造出向前看
个输入符号的预测分析器,该类文法有时也称为 文法类
- 可以对某些文法构造出向前看
- 预测分析不需要回溯,是一种确定的自顶向下分析方法
编辑 (opens new window)