《编译原理第6,7章.ppt

6.1 自下而上分析基本问题 6.1.1归约的概念 G =（VT，VN，S，P），α，β ∈（VT∪VN）*，A→β∈P，αAw ?αβw。 归约的过程是，已知αβw和产生式A→β，用产生式A→β左部A替换αβw中的β，得到符号串αAw。 从输入符号串出发，每次从被归约的句型中找到一个产生式的右部，用其左部替换之，得到新的句型，直至归约到文法的开始符号。 例子：文法G的产生式定义为：S→aAcBe A→b A→Ab B→d 输入句子为：abbcde 首先看看最右推导：S?aAcBe?aAcde?aAbcde?abbcde（使用产生式的顺序为：S→aAcBe B→d A→Ab A→b） 6.1.2规范归约 短语、直接短语、句柄 令G是一个文法，S是文法的开始符号，假定αβδ是文法G的一个句型，如果有： S αAδ且A β 则称β是句型αβδ相对于非终结符A的短语。特别是，如果有： A?β，则称β是句型αβδ相对于规则 A→β的直接短语，一个句型的最左直接短语称为该句型的句柄。 对于短语、直接短语、句柄的寻找，可以检查语法树中从根结点开始出发向下，找每一非终结符的所有叶子结点，将这些结点从左到右组成串，这些串就是该句型的所有短语，其中相对于叶子结点的直接父结点的短语为直接短语，在树中最左的直接短语为该句型的句柄。 直接短语肯定是某个产生式的右部候选式之一。 句柄的“最左”特征使得在移进-归约方法中，它始终处于符号栈的栈顶。 例：文法： E→T|E＋T T→F|T*F F→i|（E） 句型：i1*i2＋i3其中：短语有i1、i2、i3、i1*i2、i1*i2＋i3 直接短语：i1、i2、i3；句柄：i1 例：文法如上 句型：E+T*F+i 短语：E+T*F+i，E+T*F，T*F，i 直接短语：T*F和i 句柄：T*F 规范归约 假定?是文法G的一个句子。称右句型序列?n，?n-1，…，?1，?0是?的一个规范归约，如果序列满足： 1）?n= ?，?0=S；（从句子规约到文法的开始符号） 2）?i（0≤i n），?i ?i+1（?i是?i＋1经过把句柄替换成相应产生式左部符号而得到的。） 规范归约是关于?的一个最右推导的逆过程。（注意：并不是所有的归约都是规范，比如算符优先分析就不是规范归约，当然就不是一个最右推导的逆过程） 如果文法G是无二义的，那么，规范推导（最右推导）的逆过程必是规范归约（最左归约）。 ?βw表示一个规范句型，?必定是在β归约之前进行的规范归约得到的结果，? ?（VT∪VN）*，w ? VT*。 6.1.3 “移进—归约”分析法的栈实现?? “移进一归约”分析器使用一个栈和一个存放输入符号串w的缓冲器。分析器的初始状态为： 栈???????? 输入???????? ?? ＃???????? w＃? 工作过程：自左至右把串w 的符号一一移进栈里，一旦栈顶形成句柄时，就进行归约。这种归约可能持续多次，直至栈顶不再呈现句柄为止。然后，继续向栈里移进符号，重复这个过程，直至最终形成如下格局： ??栈???????? 输入 ???? ?＃S???????? ＃ 例： 文法：S?aAcBe A ?b?Ab B ?d句子：abbcde 6.2算符优先分析 6.2.1算符优先文法及优先表的构造 6.2.1.1算符文法的定义 设G是一个文法，如果G中不存在形如A??及A?αBCβ的产生式(其中A，B，C∈VN，α，? ? (VN∪VT)*，且其中不含有相邻非终结符号），即G中右部不含具有相邻非终结符号的产生式，则称G为算符文法。 例如： 文法：E→E＋E|E-E|E*E|E/E|E↑E|(E)|-E|id 是算符文法。 文法：E→EAE|（E）|－E|id ? A→＋|－|*|/|↑ 不是算符文法。因右部EAE具有相邻的非终结符号。 算符：这里的算符是指文法中的终结符。终结符a、b之间的优先关系有三种： a . b a的优先性低于b a = b a的优先性等于b a . b a的优先性高于b 算术关系“”，“=”和“”与优先关系具有十分不同的性质。例如，a＜. b并不一定意味着b . a，例如：+ . （ 且有（ . +。 决定优先关系方法： （a） 直观方法：代数规则； （b）对于一个无二义性文法，有机械方法。 6.2.1.2算符优先文法 算符优先文法的定义： 假定G是一个不含ε－产生式的算符文法。对于任何一对终结符a、b