编译原理,课件第6章自底向上优先分析法

时间：2025-04-25

第6章自底向上优先分析法自底向上优先分析法简单优先分析法算符优先分析法算符优先文法的定义算符优先关系表的构造算符优先分析算法算符优先分析法的局限性

自底向上分析法自底向上分析法，也称移进-规约分析法。思想：对输入符号串自左向右进行扫描，并将输入符逐个移入一个栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄或可规约串(该句柄对应某产生式的右部)时，就用产生式左部的非终结符代替之；这称为一步规约。

自底向上分析的移进-规约过程是自顶向下的最右推导的逆过程。

将输入分成两部分：未消化的和半消化的半消化的 Input#未消化的

总控程序

output

产生式表

分析表

例子G[S]:S->aAcBe A->b A->Ab B->d

输入串abbcde

abbcde的最右推导为： S aAcBe aAcde aAbcde abbcde

例子(续)G[S]:S->aAcBe A->b A->Ab B->d

输入串abbcde

abbcde的移进-规约过程为： S aAcBe aAcde aAbcde abbcde

文法G[S]: (1) S → aAcBe (2) A → b (3) A → Ab (4) B → d

步骤符号栈1) 2) 3) 4) 5) 6) 7) # #a #ab #aA #aAb #aA #aAc

输入符号串abbcde# bbcde# bcde# bcde# cde# cde# de#

动作移进移进归约(A→b) 移进归约(A→Ab) 移进移进

S A B

8)9) 10) 11)

# aAcd#aAcB #aAcBe #S

e#e# # #

归约(B→d)移进归约接受

a b b c d e 符号串abbcde是否是G[S]的句子 S aAcBe aAcde aAbcde abbcde

对输入串abbcde#的移进-规约分析过程

自底向上的移进-规约过程也是自底向上构造语法树的过程，每步规约都是构造一棵子树；输入串结束时刚好构造出整个语法树。规约过程总是对出现在栈顶的句柄进行。

如何确定句柄呢？

自底向上优先分析法优先分析法分为：简单优先分析法和算符优先分析法。简单优先分析法：按一定的原则求出该文法所有符号(终结符和非终结符)之间的优先关系，按照这种关系确定规约过程中的句柄；是规范规约。算符优先分析法：只规定算符(终结符)之间的优先关系；不是规范规约。适用于表达式的规约。

简单优先分析优先关系： X=Y 表示X和Y的优先关系相等； X>Y 表示X的优先性比Y的优先性大； X<Y 表示X的优先性比Y的优先性小；优先关系定义： X=Y 当且仅当G中存在产生式规则A …XY... X<Y 当且仅当G中存在产生式规则 A …XB...,且B Y... X>Y 当且仅当G中存在产生式规则 * A …BD...,且B ...X和D Y...

例子G[S]:S -> bAb A -> (B|a B -> Aa)(1) =关系： b=A, A=b, (=B, A=a, a=) (2) <关系 b< (, b<a; (<(, (<a, (<A (3) >关系 )>b, a>b, B>b; )>a, a>a, B>a;以上关系也可从语法树中得到！

简单优先文法满足以下条件的文

法： (1) 在文法符号集V中，任意两个符号之间最多只有一种优先关系成立； (2) 在文法中任意两个产生式没有相同的右部。

简单优先分析法根据已知优先文法构造相应优先关系矩阵，设置符号栈S;算法如下： (1) 将输入符号串a1a2 …an#依次存入符号栈S,直到栈顶符号ai的优先性>下一输入符号aj时为止。 (2) 栈顶当前符号ai为句柄末尾符，由此向下在栈中找句柄的头符号ak,即找到ak-1<ak为止。 (3) 由句柄ak …ai在文法产生式中查找右部为 ak …ai的产生式，若找到则用相应左部代替句柄；若找不到则出错。 (4) 重复上述步骤直到规约完输入符号串。

算符优先分析法

算符优先分析自下而上分析算法：模型(移进-归约) 算符优先分析不是规范归约适用于算术表达式的语法分析

分析程序模型输入串# 总控程序 # 算符优先关系表产生式输出

G[E]:E→E+E|E*E|i 对输入串i+i*i#的规约过程步骤1 2 # #i

栈

当前符号i +

剩余输入+i*i# i*i#

移进或规约

移进规约3

34 5

#E#E+ #E+i

+i *