简单优先分析方法
?一种 shift-reduce分析方法
?根据文法符号的优先关系确定句柄
?文法符号的优先关系的确定
简单优先分析中的三种关系
?X ? Y, 当且仅当存在一个产生式 A→ … XY…
?X ? Y, 当且仅当存在一个产生式 A→ … XB…
并有 B?+Y… 。
?X ? Y, 当且仅当存在一个产生式 A→ … BC…
并有 B?+… X,C?*Y… 。
?文法 G为 简单优先文法 如果满足：
? 对于任意两个语法符号 X和 Y,至多成立一种
优先关系；
? 任意两个产生式都具有不同的右部。
文法优先关系的确定
? FIRST(W) ={S | W ?+ S…, S?(VN?VT)}
? LAST(W) ={S | W ?+ … S,S?(VN ?VT)}
?若有 U?… SiSj…, 则有 Si ? Sj ;
?若有 U?… SiW…,任 Sj?FIRST(W),有 Si? Sj
?若有 U?… VW…,任 Si?LAST(V),
Sj?(FIRST(W) ?{W})则有 Si ?Sj
输入流的结束标志 ‘ ＃ ’,文法的开始符为 Z，
?S?FIRST(Z),有 #?S,; 且＃ ?Z
?S?LAST(Z),有 S?#,; 且 Z?＃
? 例：
Z ? bMb
M ? a
M ?(L
L ? Ma)
#
)
a
(
b
L
M
Z
#)a(bLMZ
)a L )b
M ( aa ( b
LMZ
FIRST
LAST
?
?
?
?
?
??
?
?
?
? ? ?
?
?
?
?
?
? ?
简单优先分析算法要点
? 找第一个使 Sj?Sj+1的 Sj
? 从 Sj开始往前 (左 )找第一个使 Si-1?Si的 Si
? 用 SiSi+1… Sj去查产生式的右部，并用相应
的左部符号代替句柄 SiSi+1… Sj (归约 ) 。
? 重复上述过程，直至输入符结束。如果归
约出文法的开始符号则成功。否则失败。
简单优先分析实例
符号栈 关系 输入流
# ? b ( a a ) b #
# b ? ( a a ) b #
# b ( ? a a ) b #
# b ( a ? a ) b #
# b ( M ? a ) b #
# b ( M a ? ) b #
# b ( M a ) ? b #
# b ( L ? b #
# b M ? b #
# b M b ? #
# Z ? #
二义性文法的处理
? 任何语法分析方法都拒绝二义性，会引
起分析动作的不确定。
? 解决二义性的方法：
改变文法，消除二义性。
增加额外的规则
? 利用二义性简化语法分析
? 例条件语句定义：
[i] S ? if E then S else S
[j] S ? if E then S
? 表达式文法：
E ? E + E
E ? E * E
E ? id
E ? ( E )
第四章总结
? 上下文无关文法 (CFG), (VN,VT,S,P)
? 语法分析树,二义性文法，句柄
? 文法分析算法,三个集合的定义及求法
? 语法分析作用,目的是判定输入串是否为
文法所接受的语言
语法分析方法
? 自顶向下分析：
思想,从文法开始符出发，适当选择产生式，
力图推导出输入串。
关键问题,产生式的选择
主要方法：
递归下降法
LL(1)分析方法
等价变换,消除公共前缀，消除左递归
分析条件：
分析方法：
分析过程：
? 自底向上分析：
思想,从输入串出发，从左到右进行归约，
直至归约出文法的开始符。
关键问题,何时归约、归约产生式的选择
主要分析方法－ LR分析方法：
LR(0)
SLR(1)
LR(1)
LALR(1)
简单优先分析方法, 优先关系矩阵
LR分析方法比较：
LRSM的构造（展望符的计算）：
判断分析条件：
构造分析表：
分析过程：
LR分析方法的比较
? 状态数：
LR(0)=SLR(1)=LALR(1)<LR(1)
? 展望符的确定：
LR(0)无展望符； SLR(1)利用 Follow集解
决冲突； LR(1)针对不同位置确定展望符，
LALR(1)利用合并 /传播方法计算展望符。
? 分析能力：
LR(0) < SLR(1) < LALR(1) < LR(1)
? 应用：
LALR(1)较通用,LR(1)属于理论方法。
? 习题
? 写出如下文法的递归下降分析程序和 LL(1)分析表
P → begin d;X end
X → d;X | sY
Y → ;sY | ?
? 有文法如下：
G1,S?Aa| bAc| dc| bda A?d
G2,S?Aa| bAc| Bc| bBa A?d B?d
证明 G1是 LALR(1)文法但不是 SLR(1)文法，并构造
LALR(1)分析表； G2是 LR(1)文法但不是 LALR(1)文
法并构造 LR(1)分析表。
? 判断文法是否是简单优先文法 (判断是否有多重定义 )
S?A/ A?Aa A?AS A?/
?一种 shift-reduce分析方法
?根据文法符号的优先关系确定句柄
?文法符号的优先关系的确定
简单优先分析中的三种关系
?X ? Y, 当且仅当存在一个产生式 A→ … XY…
?X ? Y, 当且仅当存在一个产生式 A→ … XB…
并有 B?+Y… 。
?X ? Y, 当且仅当存在一个产生式 A→ … BC…
并有 B?+… X,C?*Y… 。
?文法 G为 简单优先文法 如果满足：
? 对于任意两个语法符号 X和 Y,至多成立一种
优先关系；
? 任意两个产生式都具有不同的右部。
文法优先关系的确定
? FIRST(W) ={S | W ?+ S…, S?(VN?VT)}
? LAST(W) ={S | W ?+ … S,S?(VN ?VT)}
?若有 U?… SiSj…, 则有 Si ? Sj ;
?若有 U?… SiW…,任 Sj?FIRST(W),有 Si? Sj
?若有 U?… VW…,任 Si?LAST(V),
Sj?(FIRST(W) ?{W})则有 Si ?Sj
输入流的结束标志 ‘ ＃ ’,文法的开始符为 Z，
?S?FIRST(Z),有 #?S,; 且＃ ?Z
?S?LAST(Z),有 S?#,; 且 Z?＃
? 例：
Z ? bMb
M ? a
M ?(L
L ? Ma)
#
)
a
(
b
L
M
Z
#)a(bLMZ
)a L )b
M ( aa ( b
LMZ
FIRST
LAST
?
?
?
?
?
??
?
?
?
? ? ?
?
?
?
?
?
? ?
简单优先分析算法要点
? 找第一个使 Sj?Sj+1的 Sj
? 从 Sj开始往前 (左 )找第一个使 Si-1?Si的 Si
? 用 SiSi+1… Sj去查产生式的右部，并用相应
的左部符号代替句柄 SiSi+1… Sj (归约 ) 。
? 重复上述过程，直至输入符结束。如果归
约出文法的开始符号则成功。否则失败。
简单优先分析实例
符号栈 关系 输入流
# ? b ( a a ) b #
# b ? ( a a ) b #
# b ( ? a a ) b #
# b ( a ? a ) b #
# b ( M ? a ) b #
# b ( M a ? ) b #
# b ( M a ) ? b #
# b ( L ? b #
# b M ? b #
# b M b ? #
# Z ? #
二义性文法的处理
? 任何语法分析方法都拒绝二义性，会引
起分析动作的不确定。
? 解决二义性的方法：
改变文法，消除二义性。
增加额外的规则
? 利用二义性简化语法分析
? 例条件语句定义：
[i] S ? if E then S else S
[j] S ? if E then S
? 表达式文法：
E ? E + E
E ? E * E
E ? id
E ? ( E )
第四章总结
? 上下文无关文法 (CFG), (VN,VT,S,P)
? 语法分析树,二义性文法，句柄
? 文法分析算法,三个集合的定义及求法
? 语法分析作用,目的是判定输入串是否为
文法所接受的语言
语法分析方法
? 自顶向下分析：
思想,从文法开始符出发，适当选择产生式，
力图推导出输入串。
关键问题,产生式的选择
主要方法：
递归下降法
LL(1)分析方法
等价变换,消除公共前缀，消除左递归
分析条件：
分析方法：
分析过程：
? 自底向上分析：
思想,从输入串出发，从左到右进行归约，
直至归约出文法的开始符。
关键问题,何时归约、归约产生式的选择
主要分析方法－ LR分析方法：
LR(0)
SLR(1)
LR(1)
LALR(1)
简单优先分析方法, 优先关系矩阵
LR分析方法比较：
LRSM的构造（展望符的计算）：
判断分析条件：
构造分析表：
分析过程：
LR分析方法的比较
? 状态数：
LR(0)=SLR(1)=LALR(1)<LR(1)
? 展望符的确定：
LR(0)无展望符； SLR(1)利用 Follow集解
决冲突； LR(1)针对不同位置确定展望符，
LALR(1)利用合并 /传播方法计算展望符。
? 分析能力：
LR(0) < SLR(1) < LALR(1) < LR(1)
? 应用：
LALR(1)较通用,LR(1)属于理论方法。
? 习题
? 写出如下文法的递归下降分析程序和 LL(1)分析表
P → begin d;X end
X → d;X | sY
Y → ;sY | ?
? 有文法如下：
G1,S?Aa| bAc| dc| bda A?d
G2,S?Aa| bAc| Bc| bBa A?d B?d
证明 G1是 LALR(1)文法但不是 SLR(1)文法，并构造
LALR(1)分析表； G2是 LR(1)文法但不是 LALR(1)文
法并构造 LR(1)分析表。
? 判断文法是否是简单优先文法 (判断是否有多重定义 )
S?A/ A?Aa A?AS A?/
