自顶向下的分析(Top-Down Parsing)

从分析树的顶部(根节点)向底部(叶节点)方向构造分析树

可以看成是从文法开始符号S推导出词串w的过程

每一步推导中,都需要做两个选择

  • 替换当前句型中的哪个非终结符
  • 用该非终结符的哪个候选式进行替换

最左推导(Left-most Derivation)

在最左推导中,总是选择每个句型的最左非终结符进行替换

如果S =>*lm α,则称α是当前文法的最左句型(left-sentential form)

最右推导(Right-most Derivation)

在最右推导中,总是选择每个句型的最右非终结符进行替换

在自底向上的分析中,总是采用最左归约的方式,因此把最左归约称为规范归约,而最右推导相应地称为规范推导。

最左推导和最右推导的唯一性

自顶向下的语法分析采用最左推导方式

  • 总是选择每个句型的最左非终结符进行替换
  • 根据输入流中的下一个终结符,选择最左非终结符的一个候选式

例:

文法

① E → T E’
② E’→ + T E’|ε
③ T → F T’
④ T’→ * F T’|ε
⑤ F → ( E )|id

输入

id + id * id

自顶向下语法分析的通用形式

递归下降分析 (Recursive-Descent Parsing)

  • 由一组过程组成,每个过程对应一个非终结符
  • 从文法开始符号S对应的过程开始,其中递归调用文法中其它非终结符对应的过程。如果S对应的过程体恰好扫描了整个输入串,则成功完成语法分析
void A( ) {
 选择一个A产生式, A →X1 X2 … Xk ;
 for ( i = 1 to k ) {
    if ( Xi是一个非终结符号)
        调用过程 Xi ( ) ; 
    else if ( Xi 等于当前的输入符号a) 
        读入下一个输入符号;
    else /* 发生了一个错误 */ ;
} }

可能需要回溯(backtracking),导致效率较低

预测分析 (Predictive Parsing)

  • 预测分析是递归下降分析技术的一个特例,通过在输入中向前看固定个数(通常是一个)符号来选择正确的A-产生式。

  • 可以对某些文法构造出向前看k个输入符号的预测分析器,该类文法有时也称为LL(k) 文法类

  • 预测分析不需要回溯,是一种确定的自顶向下分析方法

最后修改日期:2020年5月31日

留言

撰写回覆或留言