1
第 6章 补充 算符 优先分析算符优先文法的定义算符优先关系表的构造算符优先分析算法算符优先分析法的局限性
2
算符优先分析
自下而上分析算法 模型 ----移进归约
算符优先分析不是 规范归约算符优先分析的 可归约 串 是 句型的 最左素短语定义 cfg（上下文无关文法） G 的句型的 素短语 是一个短语，它 至少包含一个终结符,且除自身外 不再包含其他素短语 。处于句型最左边的素短语为 最左素短语文法 G[S]
S αAδ且 A?则称?是句型 α? δ相对于非终结符 A的 短语
*
3
文法 G[E]：
(1) E→ E+T
(2) E→ T
(3) T→ T*F
(4) T→ F
(5) F→ P?F|P
(6) P→ (E)
(7) P→ i
句型 T+T*F+i
其短语有：
T+T*F+i
T+T*F
T
T*F
i
E
E T+
+E T
F
* FTT i
最左素短语为,T*F
句型 T+T+F的素短语为,T+T
E +
+ T
F
E
句型 T+T+i的素短语为,T+T,i
素短语为,T*F,i
E
T
T
i
4
分析程序模型总控程序算符优先关系表 产生式输入串 #
#
输出
5
如何确定算符优先关系？
人为 确定：
（ 1） i的优先级最高
（ 1）?优先级次于 i，右结合
（ 2） *和 /优先级次之，左结合
（ 3） +和 -优先级最低，左结合
（ 4）括号 ‘ (’,‘)’的优先级大于括号外的运算符，小于括号内的运算符，
内括号的优先性大于外括号
（ 5） #的优先性低于与其相邻的算符文法 G[E],E→ E+E|E-E|E*E|E/E|E?E|(E)|i
+ - * /
( ) i #
+ > > < < < < > < >
- > > < < < < > < >
* > > > > < < > < >
/ > > > > < < > < >
> > > > < < > < >
( < < < < < < = <
) > > > > > > >
i > > > > > > >
# < < < < < < < =
算符优先关系表
6
算符优先文法的定义
定义,如果不含空产生式的上下文无关文法 G 中没有形如 A?… BC… 的产生式，其中 B,C∈V N 则称
G 为算符文法（ OG）。
例 1 G[E],E→ E+E|E-|E*E|E/E|E?E|(E)|i
例 2 G’[E],E→E＋ T|T
T→T*F|F
F→P↑F｜ P
P→(E)|i
性质 1：在算符文法中任何句型都不包含两个相邻的非终结符,
性质 2：如 Ab 或 bA 出现在算符文法的 句型? 中，其中
A∈V N,b∈ VT,则? 中任何 含 b 的短语必含有 A。
7
算符优先关系在 OG中 定义 （算符优先关系）
a = b G中有形如,A?… ab…
或 A?… aBb...的产生式。
a < b G中有形如,A?… aB… 的产生式,
而 B b… 或 B Cb…
a > b G中有形如,A?…B b… 的产生式,而 B … a 或 B … aC
规定 若 S a… 或 S Ca… 则 # < a
若 S … a 或 S … aC 则 a > #




8
在 OG文法 G 中，若 任意两个终结符间至多有一种 算符优先关系存在，则称 G 为 算符优先文法 (OPG)。
注意：允许 b>c,c>b;
不允许 b>c,b<c,b=c中 任两个 同时 存在。
b=c 不一 定 c = b。
例 1中：“（” =,）”，“）” <>“（”。
结论,算符优先文法是无二义的。
9
算符优先关系表的构造首先定义如下两个集合：
FIRSTVT(B)=｛ b｜ B b… 或 B Cb… ｝
LASTVT(B)=｛ a｜ B …a 或 B …aC ｝
按如下算法计算出给定文法中任何两个终结符对 (a,b)之间的优先关系：
1) ‘=‘关系
– 直接看产生式的右部，若出现了
A → …ab…或 A → …aBb,则 a=b
2)’<‘关系
– 求出每个非终结符 B的 FIRSTVT(B)
– 若 A→ …aB…,则?b∈ FIRSTVT(B),则 a<b
3)’>’关系
– 求出每个非终结符 B的 LASTVT(B)
– 若 A→ …Bb…,则?a∈ LASTVT(B),则 a>b


10
计算算符优先关系例文法 G’[E’]：
(0) E’→ #E#
(1) E→ E+T
(2) E→ T
(3) T→ T*F
(4) T→ F
(5) F→ P?F|P
(6) P→ (E)
(7) P→ i
FIRSTVT(E’)={#}
FIRSTVT(E)={+,*,?,(,i}
FIRSTVT(T)={*,?,(,i}
FIRSTVT(F)={?,(,i}
FIRSTVT(P)={(,i}
LASTVT(E’)={#}
LASTVT(E)={+,*,?,),i}
LASTVT(T)={*,?,),i}
LASTVT(F)={?,),i}
LASTVT(P)={),i}
11
(0)E’→ #E# (1) E→ E+T (2) E→ T (3) T→ T*F (4) T→ F
(5) F→ P?F|P (6) P→ (E) (7) P→ i
3)‘>’关系找形如,A→ …Bb…的产生式
E#,则 LASTVT(E)>#
E+,则 LASTVT(E)>+
T*,则 LASTVT(T)>*
P?,则 LASTVT(P)>?
E),则 LASTVT(E)>)
2）‘ <’关系找形如 A→ …aB…的产生式
#E：则 #<FIRSTVT(E)
+T,则 +<FIRSTVT(T)
*F,则 *<FIRSTVT(F)
F,则?<FIRSTVT(F)
(E,则 (<FIRSTVT(E)
1)‘=’关系由产生式 (0)和 (6),得
#=#,( = )
12
表达式 文法 G’[E’]的 算符优先关表
+ *
( ) i #
+ > < < < > < >
* > > < < > < >
> > < < > < >
( < < < < = <
) > > > > >
i > > > > >
# < < < < < =
13
算符优先分析算法算符优先文法句型的性质算符文法的任何一个句型应为如下形式：
＃ N1a1N2a2,.,Nnan Nn+1＃
其中 N k(1≤k≤n+1)为非终结符或空,ak(1≤k≤n)为终结符算符优先文法句型的最左素短语 NiaiNi+1ai+1,.,Njaj Nj+1满足：
ai-1 ＜ ai
ai =ai+1 =…… =a j-1 =aj
aj ＞ aj+1
即,ai-1<ai=ai-1=...= aj-1 = aj> aj+1
14
算符优先分析算法
1 k:= 1; S [ k ],=,#”
2 repeat read 下一符号到 a;
3 if S[ k ]? Vt then j,= k else j,= k-1;
4 while S[ j ] > a do
5 { repeat
6 Q,= S[ j ];
7 if S[ j-1]? Vt then j,= j-1
8 else j:= j-2
9 until S [ j ] < Q;
10 将 S[ j+1] S[ j+2 ]…S[ k ] 归约到某个 N;//
11 k,= j+1;
12 S[ k ]:= N;
13 }
14 if ( S [ j ] < a or S[ j ] = a)
15 then { k,= k+1; S[ k],= a}
16 else error
17 until a =,#”
15
算符优先分析法
简单，直观，有利于表达式分析，易于手工实现
比规范归约快
可能导致把错误的句子得到正确的归约