第三节 自底向上语法分析
?方法,从输入串开始,归约,直至文法
开始符。
O,规范归约简介
1,什么叫规范归约?
假定 ?是文法 G的一个句子,序列 ?n,?n-1,…,?0
满足下述条件时称为规范归约 。
(1) ?n=α;
(2) ?0为文法的开始符,即 ?0 =S;
(3)对 ?i,0<i?n,?i-1是从 ?i经把句柄替换为相
应产生式的左部符号而得到的 。
2,分析过程
例 1,G(E) E→E+T│T
T→T*F│F
F→(E) │i
i+i*i的分析过程
E
E T +
F T
i
i
*
F
T
i
F
i+i*i
F+i*i
T+i*i
E+i*i
E+F*i
E+T*i
E+T*F
E+T
E
例 2,G(S) S→aAcBe
A→Ab|b
B→d
abbcde的分析过程
S
a A c B e
A b d
b
abbcde
aAbcde
aAcde
aAcBe
S
一, 算符优先分析法
1,算符文法
上下文无关文法 G,没有形如 P→ε 或
P→,,,QR.,,的产生式,则称 G为 算符文法
2,终结符之间的优先关系
对算符文法 G,a,b?VT 定义
(1)a=b,G中有 P→,,,ab.,,
或 P→,,,aQb.,,
(2)a<b,G中有 P→,,,aQ.,,且 Q?b…
或 Q?Rb..,
(3)a>b,G中有 P→,,,Qb.,, 且 Q?.,,a
或 Q?… aR
+
+
+
+
3,算符优先文法
若算符文法 G的任何终结符 a,b之间
的优先关系至多有 =,>,<中的一个,
则 G为一算符优先文法 。
据定义, 构造下述文法 G0的优先关系表
G0（ E）,
E→E+T|T
T→T*F|F
F→(E)|i
+
+
*
*
i
i
(
(
)
)
$
$
>
>
>
<
>
<
<
<
<
>
>
>
<
<
<
<
<
<
<
<
>
>
>
>
>
>
>
>
=
=
算符优先关系表
从上表可知,
(1)相同终结符之间的优先关系未必是 =
(2)有 a<b,未必有 b>a
(3)a,b之间未必一定有优先关系
故 =,<,>不同于关系运算符, 等
于,,, 小于,,, 大于,
4,算符优先分析方法
设 a为栈顶终结符
初始化, $?栈
读一符号 ?b
a=b=$
a<b或 a=b
a>b
归约最左素短语,最左素短语出栈,左部符号入栈
结束
b入栈
出错
Y
N
Y
Y
N
N
?归约最左素短语的方法,
这是一种结构归约,处于栈顶待归约的最左
素短语与对应的产生式在结构上应一致,即长
度一致,对应的终结符一致,而非终结符可以不
一致 。
例 G(E) E→E+T│T
T→T*F│F
F→(E) │i
i+i*i的分析过程
步骤
1
2
3
4
5
6
7
8
9
10
11
下推栈 输入串 动作
$ i+i*i$ $<i,移进 i
$i +i*i$ i>+,用 F?i归约
$F +i*i$ $<+,移进 +
$F+ i*i$ +<i,移进 i
$F+i *i$ i>*,用 F?i归约
$F+F *i$ +<*,移进 *
$F+F* i$ *<i,移进 i
$F+F*i $
$
$
$
i>$,用 F?i归约
*>$,用 T?T*F归约
+>$,用 E?E+T归约
结束
$F+F*F
$F+T
$E
E
E T +
F T
i
i
*
F
T
i
F
E
E T +
F T
i
i
*
F
T
F
E
E T +
F T *
F
T
F
E
E T +
F T
i
*
F
T
F
E
E T +
T
F
E
E T +
F T
i
i
*
F
T
i
F
i+i*i
F+i*i
T+i*i
E+i*i
E+F*i
E+T*i
E+T*F
E+T
E
5,优先关系表的构造
(1)FIRSTVT集
FIRSTVT(P)={a|P?a…,或 P?Qa…,a ?VT,Q ?VN}
?若 P?a… 或 P?Qa…,则 a?FIRSTVT(P);
?若 P?Q…,则 FIRSTVT(Q)?FIRSTVT(P);
直至 FIRSTVT(P)不再增大。
+ +
(2)FIRSTVT集
LASTVT(P)={a|P?...a,或 P?…aQ,a ?VT,Q ?VN}
?若 P?...a或 P?…aQ,则 a?LASTVT(P);
?若 P?...Q,则 LASTVT(Q)?LASTVT(P);
直至 LASTVT(P)不再增大。
+ +
例 G(E) E→E+T│T
T→T*F│F
F→(E) │i
E
T
F
FIRSTVT LASTVT
( i + *
( i
) i + *
) i *
) i
( i *
(3)构造优先关系表的算法
FOR 每条产生式 P?X1X2…X n DO
FOR i:=1 TO n-1 DO
BEGIN
IF Xi和 Xi+1均为终结符 THEN Xi= Xi+1;
IF i<=n-2 且 Xi和 Xi+2均为终结符 但 Xi?VN
THEN Xi=Xi+2;
IF Xi?VT,Xi+1?VN
THEN ?a?FIRSTVT(Xi+1) Xi<a;
IF Xi?VN,Xi+1?VT
THEN ?a?LASTVT(Xi) a>Xi+1
END;
例 G(E) E→E+T│T
T→T*F│F
F→(E) │i
E
T
F
FIRSTVT LASTVT
( i + *
( i
) i + *
) i *
) i
( i *
考察 E→E+T 中的 E和 +, +和 T
考察 T→T*F 中的 T和 *, *和 F
考察 F→(E) 中的 (和 E, (和 ), E和 )
+
+
*
*
i
i
(
(
)
)
$
$
>
>
>
<
>
<
<
<
<
>
>
>
<
<
<
<
<
<
<
<
>
>
>
>
>
>
>
>
=
=
算符优先关系表