13
4.4.2 算符优先文法的定义 • 3 算符优先文法的定义
设有一个不含 规则的OG文法G，
如果任意两个终结符间至多有一种算符 关系存在， 则称G是算符优先文法，也称OPG文法。
结论：算符优先文法是无二义的。
编译原理 算符优先分析法
14
4.4.3 算符优先关系表的构造
• 1 FIRSTVT集、 LASTVT集
规范归约:
自上而下最右推导的逆过程。
编译原理 算符优先分析法
18
例4.12文法G[E]:
E E+T|T
E
T T*F|F
E +T
F (E)|id
句子id*id+id的
T
F
自下向上的语法分析过程。
T * F id
规范归约是最右推导的 逆过程。
*优先于＋：
＋优先于*：
(1)id+id*id
(1)id+id*id
(2)E+id*id
(2)E+id*id
(3)E+E*id
(3)E+E*id
(4)E+E*E
(4)E*id
(5)E+E
(5)E*E
(6)E
(6)E
编译原理 算符优先分析法
7
4.4.1 方法概述
• 3 优先关系种类
任何两个相邻的终结符a和b可能的优先关系有3 种： a b: a的优先级低于b
FIRSTVT
LASTVT
E
{+,*,(,id}
{+,*,),id}
T
{*,(,id}
{*,),id}
F
{(,id}
{),id}
编译原理 算符优先分析法
17
4.4.4 算符优先分析算法的设计
• 0 算符优先分析法与规范归约的区别
算符优先分析法:
只考虑终结符之间的优先关系来确定可归 约串，而与非终结符无关。
4.3 自下而上分析法的一般原理
• 1 自下而上语法分析概述
基本思想：用一个寄存文法符号的栈，将一个 输入串反向至文法的开始符号。
特点：效率高、文法限制少。
编译原理 算符优先分析法
1
1 自下而上语法分析概述
• 移进－归约过程实例。 例4.11 设有文法G[A]： (1)A aBcDe (2)B b (3)B Bb (4)D d
d进栈
7
$aBcd
e$
用D d归约
8
$aBcD
e$
e进栈
9
$aBcDe
$
用AaBcDe归约
10
$A $ 编译原理 算符优先分析法
分析成功
3
2 移进－归约的基本思想
(1)用一个栈寄存文法符号，移进将一个终结符 推进栈; (2)归约是将0个或多个符号从栈中弹出，用相应 产生式的左部一个非终结符压入栈;
a b: a的优先级等于b
a b: a的优先级高于b
注：优先关系与出现的左右次序有关，不同于数
学符号<,=,>。
编译原理 算符优先分析法
8
4.4.1 方法概述 • 4 优先关系矩阵(表)
矩阵的行和列都是文法的终结符; 矩阵元素是两终结符间的优先关系。
算符优先分析法借助优先关系表寻找句型的可 归约串。
把栈顶被归约的一串符号称为可归约串;
(3)重复这一过程直至整个输入串分析完毕;
(4)最终栈中只剩下左界符$和开始符号S，则所 分析的输入串是文法的正确句子;否则，出错。
编译原理 算符优先分析法
4
3 分类 ◆算符优先分析法
用 最左素短语 刻画可归约串
◆规范归约分析法 简单优先分析法
LR分析法
用 句柄 刻画可归约串
编译原理 算符优先分析法
9
算符优先关系表实例
+ * id
+ * id ( ) $
当前输入串首字符
()$
栈顶第一个终结符
编译原理 算符优先分析法
10
4.4.2 算符优先文法的定义
• 1 算符文法的定义
设有文法G，若G中没有形如U …VW…的规则 ，其中V和W为非终结符，则G称为算符文法， 也称OG文法。
编译原理 算符优先分析法
5
4.4 算符优先分析法
• 4.4.1 方法概述 • 1 特点
适合分析各类表达式; 宜于手工实现; 规定运算符之间的优先顺序(优先关系，结合性 质)。
通过比较算符之间的优先关系确定可归约串。
编译原理 算符优先分析法
6
4.4.1 方法概述
• 2 优先关系
例 文法G[E]： E E+E|E*E|(E)|id 对输入串id+id*id的规范归约过程。
规则。
＋
(2)a b :含有P …aR…的规则，且Rb…或
R
＋
Qb…
＋
(3)a b:含有P …Rb…的规则，且R…a或 R＋ …aQ。
编译原理 算符优先分析法
12
4.4.2 算符优先文法的定义 • 2 算符优先关系的定义
规定：
若S
＋
a…或S
＋
Ca…，则$
a
＋
＋
若S …a或S …aC，则a $
编译原理 算符优先分析法
对输入串abbcde$的移进－归约分析过程
编译原理 算符优先分析法
2
对输入串abbcde$移进－归约分析过程：
步骤
符号栈
输入串
动作
0
$
abbcde$
a进栈
1
$a
bbcde$
b进栈2$ab Nhomakorabeabcde$
用B b归约
3
$aB
bcde$
b进栈
4
$aBb
cde$
用B Bb归约
5
$aB
cde$
c进栈
6
$aBc
de$
＋
FIRSTVT(A)={b|A b… 或
＋
A Bb… ,b VT,B VN} 即：非终结符Ａ往下推导所有可能出现的首个 算符的集合．
LASTVT(A)={a|A
＋
…a
A
＋
…aB,
a
VT,B VN}
即：非终结符Ａ往下推导所有可能出现的最后
一个算符的集合．
编译原理 算符优先分析法
15
4.4.3 算符优先关系表的构造
(3) 最后，在表中填入界符的优先关系：
对FIRSTVT(S)中所有b,置$ b;
对 LASTVT(S)中所有a,置a $.
置 $ $。
编译原理 算符优先分析法
16
例4.12 文法G[E]: E E+T|T T T*F|F F (E)|id
构造该文法的算符优先关系表。
Homework: (P105)- 4.5 (2)
性质：
1.在算符文法中任何句型都不包含两个相邻的 非终结符。 2.如Ab或bA出现在算符文法的句型中，则中 任何含b的短语必含有A。
编译原理 算符优先分析法
11
4.4.2 算符优先文法的定义
• 2 算符优先关系的定义
在OG中定义算符优先关系： (1)a b :含有P …ab…，或 P …aQb…的
• 2 算符优先关系表的构造方法 (1)为每个非终结符Ａ计算FIRSTVT(A),LASTVT(A)
(2)计算算符之间的优先关系，并填表。计算方法：
★ 关系:若A …ab… 或A…aBb,则a b
★ 关系:若A…aB…,则bFIRSTVT(B),a b ★ 关系:若A…Bb…,则aLASTVT(B),a b