25/1/261第六章自底向上的优先分析法•自底向上语法分析概述•简单优先分析•算符优先分析25/1/2626.1自底向上语法分析概述•自底向上语法分析试图将一个字符串归约至开始符号。•自下而上语法分析比自顶向下语法分析更有效率，对语法的限制更少•“移进-归约”：从输入字符串开始，逐步进行归约直到归约到文法的开始符号。25/1/263文法G[S]：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→dabbcde步骤符号栈输入符号串动作1）#abbcde#移进2）#abbcde#移进A3）#abbcde#归约(A→b)4）#aAbcde#移进A5）#aAbcde#归约(A→Ab)6）#aAcde#移进7）#aAcde#移进B8）#aAcde#归约(B→d)9）#aAcBe#移进11）#S#接受S10）#aAcBe#归约(S→aAcBe)分析符号串abbcde是否G[S]的句子对输入串abbcde#的移进-规约分析过程25/1/264•归约过程恰好是最右推导的逆过程：•规范归约定义：•假定α是文法G的一个句子，我们称序列αn,αn-1,…α0是α的一个规范归约。如果此序列满足：1、αn=α2、α0为开始符号。3、对任何i,0
