Top-Down parsing 自顶向下分析
从分析树的顶部（根节点）向底部（叶节点）方向构造分析树
可以看成是从文法开始符号S 推导出词串w的过程
image.png
每一步推导中，都需要做两个选择
替换当前句型中的那个非终结符
用该非终结符的那个候选式进行替换
最左推导
在最左推导中，总是选择每个句型的最左非终结符进行替换
image.png
image.png
最右推导
在最右推导中，总是选择每个句型的最右非终结符进行替换
image.png
在自底向上的分析中，总是采用最左归约的方式，因此把最左归约称为规范归约，而最右推导相应的称为规范推导
最左推导 和 最右推导的 唯一性
image.png
最终的推导结果是一致的
自顶向下的语法分析采用最左推导方式
总是选择每个句型的最左非终结符进行替换
根据输入流中的下一个终结符，选择最左非终结符的一个候选式
image.png
自顶向下语法分析的通用形式
递归下降分析 recursive-descent Parsing
由一组过程组成，每个过程对应一个非终结符
从文法开始符号S 对应的过程开始 其中递归调用文法中其他非终结符对应的过程。如果S对应的过程体恰好扫描了整个输入串，则成功完成语法分析
image.png
预测分析
image.png
网友评论