编译原理：第四章3-4

1
4.2 自底向上 的语法分析
? 自底向上 的语法分析是从给定的符号串出发,试图将它归
约为文法的开始符号,
? 两种 自底向上 分析 方法,
– 优先分析 法：在文法符号之间确定优先关系，根据优先关
系确定句型的句柄，进行语法分析。
– LR分析法,向前查看若干个输入符号以确定下一步应采
取的语义动作。
? 自底向上 分析 也需要一个分析栈用于存放分析过程中所
得的文法符号,开始时,先将 #入栈,然后逐步地将输入符
号移进栈,当在栈顶形成 句柄 时,则进行 归约,否则 移进 下
一符号,如果最后所有的符号都移进分析栈并且分析栈中
只剩下 #和文法的开始符号，则表明分析成功。
2
步 骤 分析栈内容 余留符号串 下步动作
0 # b b a a c b # 移进
1 # b b a a c b # 移进
2 # bb a a c b # 移进
3 # bba a c b # 按 A → a 归约
4 # bbA a c b # 按 A → bA 归约
5 # bA a c b # 按 A → bA 归约
6 # A a c b # 移进
7 # Aa c b # 移进
8 # A a c b# 按 S → c 归约
9 # A a S b# 移进
10 # A a S b # 按 B → a S b 归约
11 # AB # 按 S → AB 归约
12 #S # 分析成功
文法, S?AB|c； A?bA|a； B?aSb|c,输入为 bbaacb
自底向上 语法分析的例子
3
关于自底向上分析
? 分析动作有,移进,归约,报错,接受,在分析的每一步,分析
动作 都是由 当前栈里的内容和扫描到的符号确定的,
? 分析过程采用 最左归约 (规范归约 )，句柄肯定出现在栈
顶位置，应注意，一旦 句柄 在栈顶形成,则立即 归约 。
? 问题 1,如何确定句型的句柄？ 栈顶 出现的某 产生式右部
不一定 是 句柄,如前例中第 7步,栈顶的 a不是句柄
? 问题 2：出现句柄时选择哪一个产生式？ 如前例中第 8步,
对于句柄 c，选择 S?c还是 B?c？
4
自底向上分析潜在构造了语法树
? 分析过程隐含地自底向上建立了一棵 语法树,
（ 1）往分析栈移入一个终结符 a时，则在语法树中添加
一个以 a为标记的末端结点。
（ 2）每当将栈顶符号串 X1X2…X m归约为非终结符 A时，
则在语法树中添加一个结点 A，并将串中的符号 X1,
X2,…,X m按自左向右的顺序作为 A的孩子结点。
当分析过程结束时，如果接受了输入的符号串，则一棵
完整的语法树构造成功。
5
4.2.1 简单优先分析法
? 确定句型的 句柄,在文法的各个符号（包括终结符和非
终结符）之间建立优先关系，先从左到右扫描句型中的
符号，根据优先关系确定句柄的尾部（相邻的两个符号
之间具有优先关系,>”），再反向扫描确定句柄的头部
（相邻的两个符号之间具有优先关系,<”） 。
A
… … s t,.,
1,s在句柄中,而 t
不在句柄中
A
… … s t …,.,
2,s与 t均在句
柄中
A
… … s t …,.,
3,s不在句柄中,
而 t在句柄中
一、简单优先关系 的定义, 若 文法 G中存在规范句型
?=…st…,s,t?V,则 s,t与 ?的句柄之间的关系必有下述情
况之一,
6
简单优先文法的定义
对于上述情况，规定
情况 1,s>t; 情况 2,s=t; 情况 3,s<t
4,s和 t均不在句柄中,由于 s和 t在 ?中相邻出现，则一定
存在另一句型，使得 s和 t符合上述三种情况之一,
? 注意,这种优先关系是 不对称 的 !
? 对于在任何句型中都不相邻出现的符号对,规定两个
符号之间 无关系,
定义 4.1 若一文法 G的任何两个符号之间 至多存在一
种优先关系,且任意两个不同的产生式 无相同的右部,
则称 G为 简单优先文法。
7
简单优先文法 举例
例 4.4 考虑文法 G’[E],E?E1； E1?E1+T1 |T1； T1?T；
T?T*F | F； F?(E) | i
由文法的产生式可直接看出,
E1 = +,+=T1,T = *,* = F,(=E,E=)
考查句型 E1+i*i 及 T*(E1+T1)的最右推导,
E=>E1=>E1+T1=>E1+T =>E1+T*F =>E1+T*i =>E1+F*i
=>E1+i*i （ 逆序为最左归约，划线部分为句柄 ）
E=> E1=> T1=> T =>T*F => T*(E) =>T*(E1) =>T*(E1+T1)
不难看出,+<i,i>*,+<F,F>*,*<i,+<T,以及, *<(,(<E1,
E1>),T1>)
8
E E
1
T
1
T F + * ( ) i
E =
E
1
= >
T
1
> >
T > = >
F > > >
+ = < < < <
* = < <
( = < < < < < <
) > > >
i > > >
文法 G’[E]的简单优先矩阵
可把文法的 全部优先关系 用一矩阵来表示,例如前面
所给文法 G’[E]相应的 优先矩阵 为,
9
二,简单优先分析的算法
? 有了优先关系矩阵，就能很容易得找到一个规范句型
的句柄：依次查看当前句型 X1X2… Xm相邻两个符号的
优先关系,一旦出现 Xi+k>Xi+k+1,Xi+k即为句柄的尾符号,
然后从 Xi+k开始向左反向查看已扫描过的符号,直到发
现 Xi-1<Xi,Xi即为句柄的头符号,
? 可以证明,Xi到 Xi+k 之间的符号串 Xi Xi+1… Xi+k恰好构
成了当前句型的句柄,
? 特别地，对于任意符号 Xi，有 #<Xi，并且 Xi>#
10
程序 4-4 简单优先分析 驱动程序
int parser(void){
int i=0,k=0,r;stack[0]='#';
r=a[k++];
do{ int j,LeftSide;
while(!IsHigherThan(stack[i],r))
{stack[++i]=r;r=a[k++];}
j=i;
while(! IsLowerThan (stack[j-
1],stack[j])) j--;
LeftSide=
RightSideOfAProduction
(stack[j],stack[i],i-j+1);
if(LeftSide){ /*LeftSide!=0
means the production exists */
i=j;stack[i]=LeftSide;
}else /* There is no production
which matches the right side */
if(i==2 && r=='#' && stack[i]
== STARTSYSBOL)
return SUCCESS;
else return ERROR;
} while (1);
} /* end of parser */
11
步骤 分析栈 优先关系 r 余留输入串 句柄 所用产生式
0 # < i + i * i #
1 # i > + i * i # i F → i
2 # F > + i * i # F T → F
3 # T > + i * i # T T
1
→ T
4 # T
1
> + i * i # T
1
E
1
→ T
1
5 # E
1
= + i * i #
6 # E
1
+ < i * i #
7 # E
1
+ i > * i # i F → i
8 # E
1
+ F > * i # F T → F
9 # E
1
+ T = * i #
10 # E
1
+ T * < i #
11 # E
1
+ T * i > # # i F → i
12 # E
1
+ T * F > # # T * F T → T*F
13 # E
1
+ T > # # T T
1
→ T
14 # E
1
+ T
1
> # # E
1
+ T
1
E
1
→ E
1
+ T
1
15 # E
1
> # # E
1
E → E
1
16 # E > # # 成功
符号串 i+i*i的语法分析过程
12
三,简单优先分析 矩阵的构造
? 通过考察若干个句型来发现优先关系的方法比较繁琐，
可以一次计算出全部优先关系，得到优先关系矩阵，
为此，引入 V上定义的若干二元关系,
定义 4.2 LEAD?V2,A LEAD B,iff A?B… ?P;
A LEAD+ B,iff A=>+ B…;
定义 4.3 LAST?V2,A LAST B,iff A?…B ?P;
A LAST+ B,iff A=>+ …B
定义 4.4 逆关系 (TRANSPOSE(R)或 ~R),
a ~R b,iff b R a
定义 4.5 si= sj,iff ?U?…s isj..,?P;
13
若干二元关系的定义 (续 )
定义 4.6 si<sj,iff ?U?..,siW..,?P ? W=>+sj… 。
定义 4.7 si>sj,iff ?U?…W 1W2...?P ? W1=>+…s i ?
W2=>*sj…, sj?VT
? 由定义 4.6,si<sj ? ?W?VN,si=W ? W LEAD+ sj
? si (=)(LEAD+) sj; 复合关系
? 由定义 4.7,有 si > sj ? W1= W2 ?W1 LAST+ si ? W2
LEAD* Sj;
其中 W1 LAST+ si ? si TRANSPOSE(LAST+) W1
(或,~(LAST+); LEAD* = I+LEAD+,I为 恒等 关系
综上所述,si > sj ? si ~(LAST+) (=) (I+LEAD+ ) sj
14
优先关系矩阵构造举例
? 上述定义的二元关系 R可以用布尔矩阵 BR来表示，关系
R的布尔矩阵 BR定义为：当 Si R Sj时,BR[i,j]=1; 否则
BR[i,j]=0。
? 对于文法 G,S?Ac; A?AS; A?Aa; A?b，计算相应的
优先关系矩阵如下,
（ 1）构造 B=
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0
0
0
0
0
0
0
0
0
0
00000
10101
00000
c
b
a
A
S
cbaAS
B
15
优先关系矩阵构造举例（续）
（ 2）构造 B<,由 si<sj ? si (=)(LEAD+) sj，构造 BLEAD,
利用 Warshall算法计算 BLEAD+,
已知 B,计算 B+=B+BB+BBB+……B n
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0
0
0
0
0
0
0
0
0
0
00000
01010
00010
c
b
a
A
S
cbaAS
L E A D
B
文法 G,S?Ac; A?AS; A?Aa; A?b
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
0
0
0
0
0
0
0
0
0
0
00000
01010
01010
c
b
a
A
S
cbaAS
L E A D
B
16
Warshall算法
已知 B,计算 B+=B+BB+BBB+……B n
1、置新矩阵 A=B
2、置 i:=1
3、对所有 j,如果 A[j,i]=1,那么,
对 k=1,……,n B[j,k]=B[j,k]+B[i,k]
4,i=i+1
5、如果 i<=n,那么，转到步骤 3;
否则停止。
17
优先关系矩阵构造举例（续）
(3) 构造 B> 文法 G,S?Ac; A?AS; A?Aa; A?b
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
0
0
0
0
0
0
0
0
0
0
00000
01010
00000
0
0
0
0
0
0
0
0
0
0
00000
01010
01010
0
0
0
0
0
0
0
0
0
0
00000
10101
00000
L E A D
BBB
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0
0
0
0
0
0
0
0
0
0
00000
01101
10000
L A S T
B
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
0
0
0
0
0
0
0
0
0
0
00000
11101
10000
L A S T
B
18
优先关系矩阵构造举例（续）
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?? ??
0
0
0
0
0
0
1
1
1
0
00010
00000
00010
)(~
L A S T
T
L A S T
BB
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
? ?
1
1
1
1
1
1
1
1
1
1
11111
00000
11111
1
0
0
1
0
0
0
0
0
0
00100
01010
01011
0
0
0
0
0
0
0
0
0
0
00000
10101
00000
0
0
0
0
0
0
1
1
1
0
00010
00000
00010
*
)(~
'
L E A DL A S T
BBBB
si > sj ? si ~(LAST+)
(=) (I+LEAD+ ) sj
19
优先关系矩阵构造举例（续）
? 因为要求 sj?VT，所以相应于非终
结符的列需要置 0，得到 B> 如右。
? 如果 B= ? B< = B> ? B= = B< ? B> =0，
则表明简单优先矩阵无多重定义的
元素，所给文法为简单优先文法。 ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
1
1
1
1
1
1
0
0
0
0
11100
00000
11100
B
? 将 B=,B>,B< 组装到一个矩阵中，就得到全部的优先关系。
S A a b c
S
A
a
b
c
> > >
= < = < =
> > >
> > >
> > >
20
四,简单优先分析 的局限性
? 简单优先分析法 对文法要求严格,常见的文法一般不是
简单优先文法,
? 例如,当一文法具有左递归符号,且它出现在某产生式右
部的内部时,就会出现冲突, 当 U?…s isj...?P sj?sj...?P
时,由前者,si=sj,由后者,si<sj
同理,当某符号具有右递归,且出现于某右部的中间时,会
有 =与 >的冲突,
? 一般说来,通过消除左 (右 )递归可解决此类冲突，引入新
符号 W，上述两个产生式可以改写为,U?…s iW...?P；
W?sj...?P,这种方法称为 分层法 或 析出法,
21
示例
? 例如,文法 G[E],E?E+T|T; T?T*F|F; F?(E)|i 的优先
矩阵入图 4-5，其中包含多重定义元素。通过 分层法 对文
法 G[E]改写,得到文法 G’[E]，其优先矩阵见 P129图 4-4,
? 应当指出,分层法 不是万能的,当 U<V与 U>V同时存在时,
则无法解决 ;有时解决旧的矛盾时，还会引入新的矛盾。
? 分层法 引入了大量的新 VN符号,使 矩阵 迅速增大,分析效
率也大大降低,
? 文法 G[E]中的句型 E+T*F,按简单优先关系考虑，则有
# < E = + T * F #
如果将 +和 *都看作是算术运算符，则可以规定二者之间
的优先关系，并根据此优先关系确定句柄的位置 —— 算
符优先分析。
?
?
22
4.2.2 算符优先分析法
一,算符文法与算符优先文法
定义 4.8 若文法 G的产生式右部不含两个 VN符相邻的情况,
则称 G为 算符文法,G的 VT符被称为 算符
? 可以证明,算符文法 不会含有两个 VN符相邻的句型
? 常见语言不一定是 算符文法,但可对其进行改造
? 例 PASCAL中的 for循环语句,
<循环语句 >?<循环子句 ><语句 >
<循环子句 >?for<变量 >:= <表达式 > to <表达式 > do
可将其改为,
<循环语句 >?for<变量 >:= <循环表 > do <语句 >
<循环表 > ? <表达式 > to <表达式 >
23
算符优先关系的定义
设文法 G是一 算符文法,且不含 ?-产生式, U,A,B?VN,
a,b?VT，算符优先关系可由以下定义给出,
定义 4.9 (LEADVT) U LEADVT a ? U?[A]a..,?P
定义 4.10 (LASTVT) U LASTVT a ? U?…a[A] ?P
定义 4.11 a b ? ? U?…a[A]b..,?P
定义 4.12 a b ? ? U?…aA..,?P ? (A=>+ [B]b…)
定义 4.13 a b ? ? U?…Ab..,?P ?(A=>+ …a[B])
? 若 算符文法 G的任意一对相邻终结符之间，至多只有上
述三种优先关系之一成立，则称其为 算符优先文法 。
? 通过构造和查看算符文法的优先矩阵可确定它是否为算
符优先文法。
??
??
??
24
算符优先关系矩阵的构造
? 类似于简单优先关系矩阵的构造，可以先构造,
和 优先关系的布尔矩阵，再组装到一个矩阵中。
（ 1）对于 a b，根据定义查看各产生式即可得到。
（ 2）对于 a b,则 由 ?U?…aA..,?P 有 a(=)A;
由 A=>+ [B]b … 有 ?W?[B]b...?P ?
A=>* W…
即 A LEAD* W ? W LEADVT b
从而有 a (=) (LEAD*) (LEADVT) b
??
??
?? ??
??
25
算符优先关系矩阵的构造
? 对于 a b,则由 ? U?…Ab..,?P,有 A (=) b；
由 A=>+…a[B],有 ?W?...a[B]?P ?
A=>*,..W
从而,有 A (LAST*) W ? W LASTVT a,
进而,有 a (~LASTVT) (~ LAST*) A
最后,得 a (~LASTVT) (~ LAST*) (=) b
? 例 G[E],E?E+T|T; T?T*F|F; F?(E)|i 是算符文
法,P137-P138给出了其优先矩阵的构造过程, P139给出
了优先矩阵,
? 算符优先矩阵比简单优先矩阵小得多,
??
26
算符优先分析的算法
? 假设算符优先分析的句型具有一般形式
w=#N1a1N2a2…N nanNn+1#,其中,ai?VT,Ni?VN（可以缺
失）。寻找被归约子串的方法, 从左到右扫描 w,找到第
一个 ai ai+1时,记下 ai,再反向扫描,找到第一个 aj-1 aj,此
时,NjajNj+1aj+1…N iaiNi+1就是应被归约的符号串。
? 注意：上述被归约符号串不一定是 句柄,而是 最左素
短语 。
? 例如，句柄可以仅由一个 VN符构成,但算符优先关系定
义于 VT符之间，上述过程找到的被归约符号串必然包
含一个 VT符，不可能是仅由一个 VN符构成的句柄 。
? 素短语,至少含有一个 VT符的短语，并且除自身外，
不包含其它的素短语； 最左素短语,句型中最左边的素
短语,
?? ??
27
最左素短语示例
例 G[E]:E→E+T ∣ T
T→T*F ∣ F
F→(E) ∣ i
句型,T+T*F+i
短语,T; T*F; T+T*F; i; T+T*F+i
直接短语, T; T*F; i;
句柄,T
素短语,T*F; i
最左素短语,T*F
E
E + T
E + T F
T T * F i
28
算符优先分析中的归约
? 由于被归约的子串是 最左素短语
（ NjajNj+1aj+1…N iaiNi+1 ）,不一定是 句柄,甚至 不
一定是某产生式的右部,因此归约时可能无完全一致
的产生式可用,
? 解决的办法, 在 P中找形为 A? UjajUj+1aj+1…U iaiUi+1的
产生式,其中,每个 ak都与最左素短语中对应位置上的
终结符相同； Uk与 Nk相对应，但可以不相同,
? 若存在这样的产生式,则用其归约,否则报错,
29
算符优先分析示例
? 例 w=i+i*i,分析过程见下表
# i + i * i #
N1 N2 N3
N4
N5
步骤 句型及优先关系 最左素 短语 非终结符
1 # i + i * i # i F
2 # F + i * i # i F
3 # F + F * i # i F
4 # F + F * F # F * F T
5 # F + T # F + T E
6 # E # 成功
????
????
????
??
??
??
?? ??
?? ??
??
句型 i+i*i的树架子
30
算符优先分析的若干结论
? 按 算符优先分析 所确定的归约子串恰好是当前句型的
最左素短语 (可以理论证明，参见参考文献 14,17);
? 算符优先分析 是 自底向上 的,但 并不是 规范归约,因此,
每步所得句型 不是 规范句型 ;
? 由于分析过程中只考虑两个相邻 VT符之间的关系,VT
符之间的 VN符 无关紧要,所以归约所得的 VN符 可任意命
名 ;
? 分析所得的 语法树 不是真正意义上的 语法树,而是其 分
枝构架,它省略了单产生式的归约过程（如前页） ; 如
果不考虑分支架构中的非终结符标记，每一个句子的
分支架构是唯一的。
31
算符优先分析的若干结论（续）
? 一般说来，算符优先分析比简单优先分析更有效。一是
其优先矩阵较小，占存储空间小；二是不包含明显的单
产生式归约。
? 分析算法可容易地形式化,引入一分析栈,先将 ‘ #’压入栈,
分析时总是用 栈顶终结符 与 当前扫描符 进行比较,遇到优
先关系 和 时进栈,遇关系 时，回头查找 最左素短语,
归约之 ;若两个符号无关系,则 报错,若栈顶为开始符 S,扫
描符为 ‘ #’,成功,
? 分析算法的 C程序 见 P141,
???? ??
32
4.2.3 优先函数
? 简单优先关系矩阵为 |V|?|V|阶，当 |V|较大时,|V|2会更大，
其存储是编译程序需考虑的因素之一 ;
? 优先函数 的引用是一种内存占用少并便于使用的方法 ;
? 具体的做法是,为 优先矩阵 定义两个离散函数,f:V?N
g:V?N,满足, si<(=,>) sj时,f(si)<(=,>) g(sj);
? f,g分别称为 入栈优先函数 和 比较优先函数 ;
? 若存在满足上述条件的函数 f,g,则查询两个符号的优先
关系只需比较其 f,g的函数值大小即可,它只占用内存 2|V|
个单元,这种做法称为 优先矩阵的线性化,
? 上述思想对算符优先矩阵同样成立。
33
优先函数举例
? 例如,G[E]的优先函数可取
+ * ( ) i #
f 2 4 0 4 4 0
g 1 3 5 0 5 0
? 并不是所有的 优先矩阵 都可 线性化,如优先矩阵
S1 S2 S3
S1 > < f(S1)>g(S1); f(S1)<g(S2);
S2 = < f(S2)=g(S2); f(S2)<g(S3);
S3 = = f(S3)=g(S1); f(S3)=g(S3);
上述关系可以推导出 f(S1)>f(S1),因此存在矛盾，不存在满足
上述关系的函数 f,g。
( i * + ) #
( < < < < =
i > > > >
* < < > > > >
+ < < < > > >
) > > > >
# < < < <
34
优先函数 (续 )
? 若 优先矩阵 可 线性化,则必有无穷种线性化方案，如下,
+ * ( ) i #
f 3 5 1 5 5 1 G[E]的另一优先函数
g 2 4 6 1 6 1
? 线性化 的问题, 使原来不可比的两个符号变为可比,会 掩
盖（或推迟） 输入串的语法错误 。
? 两种构造优先函数的方法,有向图 (Bell)方法 和 Floyd方
法
35
有向图法
①对于算符（或简单）优先文法中的每一 a∈ VT?{#}
（ a∈ V?{#} ）,使之对应两个结点 fa,ga。
②对于算符优先关系
a 或 b 画一条从 fa到 gb的矢线
a 或 b 画一条从 gb到 fa的矢线
③对每一结点赋一个数,其值为从该结点出发,所能到达的
结点个数 (包含自身 ),
赋给 fa的数为 f(a),赋给 gb的数为 g(b)
④ 检查优先函数 有无矛盾,如有,则优先函数不存在,
??
??
??
??
36
有向图法举例
+ * i #
+
*
i
#
??
??
?? ??
??
??
??
??
??
?? ??
??
??
??
+ * i #
f 4 6 6 1
g 2 5 7 1
f+
g* g#
f# f* fi
g+ gi
例如文法 G[E],
E→E+T ∣ T
T→T*F ∣ F
F→i
37
有向图法的矩阵求解
(1) 作优先关系 ?的 布尔矩阵 GE
(2) 作优先关系 ?的 布尔矩阵的转置矩阵 LET
(3) 构造 2n阶矩阵 B
最后计算出的优先函数见 P147
??
?
??
??
IL E T
GEIB
njkjnSg nkj,...,2,1],[)( 2 1 ??? ??? B
nikiSf nki,...,2,1],[)( 2 1 ?? ??? B
38
Floyd方法
①对每一个 f和 g赋初值,置 f(θ) = g(θ) = 1
② 迭代,即每一符号对 (θ1,θ2)
若 θ1 >θ2 但 f(θ1 ) <= g(θ2 ),
则执行 f(θ1 ) = g(θ2 ) + 1
若 θ1 <θ2 但 f(θ1 ) >= g(θ2 ),
则执行 g(θ2 ) = f(θ1 ) + 1
若 θ1 =θ2 但 f(θ1 ) ≠g(θ2 ),
则令 f(θ1 )和 g(θ2 ) 中的较小者等于较大者
③重复②,直至过程收敛为止,
39
Floyd方法举例
( i * + ) #
(
i
*
+
）
# ??
?? ??
??
??
??
?? ??
??
?? ??
??
??
??
??
??
??
??
??
?? ??
?? ??
?? ??
?? ??
??
例如文法 G[E],
E→E+T ∣ T；
T→T*F ∣ F；
F→(E) | i
的算符优先关系
矩阵如右表。
优先函数 f,g计
算如下,
(1) 置初值,f(()= f(i)= f(*)= f(+)= f())= f(#)=1
g(()= g(i)= g(*)= g(+)= g())= g(#)=1
(2) 由 步骤②的第一种情况, f(i)= f(*)= f(+)= f())=2
??
40
Floyd方法举例（续）
(3) 由 步骤②的第二种情况, g(()=g(i)= g(*)=3; g(+)=2
(4) 步骤②的第三种情况不改变 f,g的值。
(5) 交替执行 步骤②的第一到第三种情况有,
f(i)= f(*)=f())=4; f(+)=3
g(()=g(i)=5; g(*)=4
f(i)= f(*)=f())=5
g(()=g(i)=6
+ * ( ) i #
f 3 5 1 5 5 1
g 2 4 6 1 6 1
41
总结
(1)简单优先分析所确定的可归约串是当前句型的句柄。
(2)算符优先分析所确定的可归约串是当前句型的最左素
短语,
(3)算符优先分析属于自底向上的语法分析,但不是严格
的最左归约。
(4)算符优先分析只考虑终结符号之间的优先关系。
(5)算符优先分析算法很容易程序实现。
(6)算符优先分析是比简单优先分析更有效的分析法。