三, 预测分析程序
? 构成,下推栈,预测分析表,控制程序,输入串
1,预测分析表
?形式,M[A,a]矩阵,A?VN,a ?VT?{$}
?内容,A→α 或出错标志 (空白 )
预测分析表
E
E’
T
T’
F
i + * ( ) $
E→TE’ E→TE’
E’→+TE’
T→FT’ T→FT’
T’→*FT’
F→i F→(E)
E’→ε E’→ε
T’→ε T’→ε T’→ε
2,分析方法
初始时,$和开始符入栈,输入指针指
向第一个符号,然后根据下推栈栈顶
符 x和当前输入符 a进行工作,
① x=a=$,成功
② x=a?$,匹配
③ x?VN,查表
例,i+i*i的分析过程
下推栈 输入串 查分析表
i+i*i$ $E
$E’T
$E’T’F
$E’T’
$E’T’i
$E’
$E’T
$E’T+
i+i*i$
+i*i$
i+i*i$
i+i*i$
+i*i$
+i*i$
i*i$
E→TE’
T→FT’
T→FT’
F→i
T’→ε
E’→+TE’
$E’T’F
i*i$ $E’T’i
$E’T’
$E’T’F*
$E’T’i
$E’T’F
$E’T’
$
$E’
*i$
i$
*i$
i$
$
$
$
T’→*FT’
结束
F→i
T’→ε
i*i$ F→i
E’→ε
四, LL(1)文法
1,FIRST集
(1)定义,对 α?(VT?VN)*,有
FIRST（ α） ＝ {a|α?a.,,,a?VT}
若 α?ε,则 ε?FIRST(α)
(2)对文法符号 X?VT?VN
(3)当 α=X1X2… Xn时
*
*
?X?VT,则 FIRST(X)={X};
?X?VN,分三种情形,
X?a…
X?Y…
X?Y1Y2…Y k
2,FOLLOW集
(1)定义,对 A?VN,有
FOLLOW(A)={a│S ?.,,Aa.,,,a?VT}
若 S ?,..A,则 $?FOLLOW(A),其中 S为开始符号
*
*
(2)求法
? $ ? FOLLOW(S)
? A→αBβ, 将 FIRST(?)-{?}加入 FOLLOW(B)
? A→αB 或者 A→αBβ 且 β?ε,将 FOLLOW(A) 加入
FOLLOW(B)
注意, 求 FOLLOW(B)实际上是考察 B在产生式右
端的每一次出现
*
例, G(E) E→TE’
E’→+TE’│ε
T→FT’
T’→*FT’ │ε
F→(E)│i
E
E’
T
T’
F
FIRST FOLLOW
( i
( i
( i
+ ?
* ?
) $
) $
+ ) $
+ ) $
* + ) $
3,LL(1)文法定义
设 上 下 文 无 关 文 法 G 的 产 生 式 形 如
A→ ?1|?2|… |?m,当 G满足下述条件时则称为
LL(1)文法,
① FIRST(?i) ? FIRST(?j)=Φ,
i?j,i,j=1,2,.,,,n
② 若 ?i??,则 FIRST(?j) ? FOLLOW(A)=Φ,
j=1,2,.,,,n且 j?i。
于是,在自顶向下分析时,可根据当前输入符号
a选择 a?FIRST(?i)的 A→ ?i。
*
五, 预测分析表的构造
1,构造算法
对每个产生式 A→α
① 对 ?a?FIRST(α),将 A→α 记入 M[A,a]中 ;
② 若 ε?FIRST(α),对 ?b?FOLLOW(A),
将 A→α 记入 M[A,a]中 ;
③ 凡未被定义的 M[A,a]项中标以出错标志 。
如, G(E) E→TE’
E’→+TE’│ε
T→FT’
T’→*FT’ │ε
F→(E)│i
E
E’
T
T’
F
FIRST FOLLOW
( i
( i
( i
+ ?
* ?
) $
) $
+ ) $
+ ) $
* + ) $
预测分析表
E
E’
T
T’
F
i + * ( ) $
E→TE’ E→TE’
E’→+TE’
T→FT’ T→FT’
T’→*FT’
F→i F→(E)
E’→ε E’→ε
T’→ε T’→ε T’→ε
2,预测分析表的改进
① M[A,a]中只记产生式右部 ;
② 对 α=x1x2.,,xn,在 [M,a]中记 xn xn-1..,x1;
③ 当 xn xn-1..,x1的 x1?VT时,x1必为 a,
x1无须入栈,只移动输入指针 。
第三节 自底向上语法分析
?方法,从输入串开始,归约,直至文法
开始符。
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
(
(
)
)
$
$
>
>
>
<
>
<
<
<
<
>
>
>
<
<
<
<
<
<
<
<
>
>
>
>
>
>
>
>
=
=
算符优先关系表