发表于: 更新于: 浏览: 33

自上而下分析

自下而上分析

规约

规约就是找到句型中的一部分，存在一个产生式的左部与其完全相同，使用这个产生式左部替换这一部分的过程。
短语 \beta 在待分析句型 \alpha\beta\delta 中满足 S\Rightarrow^{\ast}\alpha A\delta 和 A\Rightarrow^{\ast} \beta 。特殊地，能够被一次规约的部分称为直接短语。例如，A → β 存在，则 β 是一个直接短语。

举个例子，考虑文法：

E\rightarrow T|E+T\\ T\rightarrow F|T\ast F\\ F\rightarrow i|(E)

句型 i\ast i + i 中 i + i 并不是一个短语，尽管有推导 E\Rightarrow^{\ast}i+i，但是不存在从起始符开始的推导 E\Rightarrow^{\ast}i\ast E 。

规范规约

句柄是一个句型中的最左直接短语。
规范规约就是不断将句柄替换为对应的产生式左部，最终得到起始符的过程。
实际上，规范规约就是最右推导的逆过程。可以这样思考：逆过程优先处理左边，则顺过程优先处理右边。
注意，规范规约并不是一个具体的为文法分析方法，原因是在没有语法分析树的情况下，是无法得到当前句型中的句柄的（仅凭产生式判断是不够的）。

算符优先分析

算符优先文法是指一个文法满足：任意产生式的右部都不包含两个相继的非终结符，即没有形如: ...QR... 的产生式右部。这种文法可以使用算符优先分析法进行文法分析。

算符优先分析是自下而上归约的分析方法，但不执行严格的最左归约（规范规约），而是通过算符之间的优先关系对“可归约串”进行规约。

算符优先分析用 '>' '<' '=' 描述符号之间的优先关系。与数学中的不等式不同，\alpha < \beta 和 \beta < \alpha 是可以同时存在而不冲突的，但是 \alpha < \beta 和 \alpha > \beta 是不可同时存在的。换言之，一个有序对 <\alpha,\beta> ，仅存在一个或零个优先关系或与之对应。

分析时，需要维护一个单调栈，其中的终结符优先级单调递增。对于任意栈顶以下的终结符 \alpha 和栈顶终结符 \beta，满足 \alpha < \beta 或 \alpha = \beta。（注意 α 和 β 的顺序）
已经入栈的符号串，必将满足以下形式：N_ia_ia_{i+1}...N_{i+1}a_j...N_{i+2}...