第五章

 一、移进归约

        1.基本思想
用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一    部分替换成(归约为)该产生式的左部符号。
2.归约

是指根据文法的产生式规则，把产生式的右部替换成左部符号。

自下而上分析法

自下而上分析法是从输入串开始，逐步进行”规约“，直至规约到文法的开始符号；或者说，从语法树的末端开始，步步向上”规约“，直至根结。

Ⅰ、归约

1、短语：令G是一个文法，S是文法的开始符号，假定αβδ是文法G的一个句型，如果有S=*>αAδ，且S=+>β，则称β是句型αβδ相对于非终结符的短语。

2、直接短语：特别是，如果有A=>β，则称β是句型αβδ相对于规则的A->β的直接短语。

3、句柄：一个句型的最左直接短语称为该句型的句柄。

4、规范归约：假定α是文法G的一个句子，我们称序列αn，αn-1，......，α0是α的一个规范归约，如果此序列满足（1）α0=α；（2）α0为文法的开始符，即α0=S；（3）对任何i，0<i<=n，αi-1是从αi经把句柄替换为相应产生式的左部符号而得到的。从而可以得到，规范归约是关于α的一个最右推导的逆过程，因此，规范归约也成为最左归约。形式语言中。最右推导常被称为规范推导。