主要内容：
? LR(1)分析方法
Z ? E
E ? (L,E)
E ? S
L ? L,E
L ? E
S ? id
S ? (S)
Z ? ?E
E??(L,E)
E??S
S??id
S??(S)
0
E?(?L,E)
S?(?S)
L??L,E
L??E
E??(L,E)
E??S
S??id
S??(S)
1
E?S?
S?(S?)
2
(
S
?1(S2,) ) = {Shift,Reduce3}
?LR(0)方法不依赖输入流，直接判定归约，
容易出现冲突。
?SLR(1)方法简单的把非终极符的 follow集做
为可归约的依据，并不精确。
?一个非终极符在不同的位置上出现，它所允
许的后继符是不同的。 LR(1)针对不同产生
式上的非终极符，分别定义其后继符集（展
望符集 Reducelookup）,减少了移入 /归约
冲突。
LR(1)分析方法
? LR(1)方法研究的对象是二元组,(?,b)，
其中 ?是活前缀，而 b是一个输入符号。我
们称上述 (?,b)为 LR1前缀模式 。
? 如果 ?是文法的归约活前缀,b是 ?的合法后
继续符，则称 (?,b)为 LR1归约前缀模式。
LR1归约前缀的派生定理
? 假设 ?0是拓广产生式的右部,#是输入流
的结束符，则有：
( ?0[p],# )是 LR1归约前缀模式。
? 设 ( ?A?[p],b )是 LR1归约前缀模式，
且 A→ ?是 q产生式，则 (??[q],a)也是
LR1归约前缀模式，其中 a?First(?b)。
? LR(1)项目,[A→ ???,a ]。 LR(0)项目及一个
VT?{#}的展望符集合
? IS:LR(1)项目集
? IS(X):
IS(X) = {[A→ ?X??,a] |[A→ ??X?,a]?IS }
? CLOSURE ( IS ) = IS∪
{[B→ ??,b] |[A→ ??B?,a]? CLOSURE(IS),
B→ ?是产生式,b?First(?a)}
LRSM1的构造算法
1,初始项目集：
ISS=CLOSURE({ [Z→ ?S,{ # } ]})
2,若所有状态都处理完，则结束
3,选一未处理完状态 IS,对所有语法符号
X?（ VT?VN ?{#}),求 ISX,令
IS’ = CLOSURE(ISX),若 IS’不为空：
若 IS’为新状态，则增加 IS IS’,把 IS’加
入 LRSM1中；否则为图中某个状态 ISj,则在 IS
和 ISj之间增加一条转换边,IS ISj
4,转到步骤 2
X
X
? 非 SLR(1)文法：
Z → S
S → L= R
S → R
L → aR
L → b
R → L
0
Z??S
S??L=R
S??R
L??aR
L??b
R??L
#
#
#
= #
= #
#
1
Z?S? #
2
S?L?=R
R?L?
#
#
6
S?L= ? R
R?? L
L??aR
L??b
#
#
#
#
7
S?L=R ? #
3
S?R? #
4
L?b? =#
10
L?aR? #=
5
L?a?R
R??L
L??aR
L??b
# =
# =
# =
# =
11
R?L? # =
8
L?a?R
R??L
L??aR
L??b
#
#
#
#
9
R?L? #
12
L?b? #
13
R?aR? #
S
L
a
bR
b
=
R
L
R L
a
b a
a
L
R
b
LR(1)文法
? 投影函数 ?2,
? ?2,StateSet ? ( VT∪ {#})→ 2?
? ?2(S,a)=
{Reducej |[B→ ??,a]?S,B→ ?是产生式 j}
∪ ( if [A→ ??a?,b]?S
then {Shift} )
?如果 LR(1)状态机的任一状态 S和输入符 a，
都使得 |? 2(S,a)|≤ 1,则称文法为 LR (1)文
法,
LR(1) 分析表的构造
Action 表的构造：
? Action(S,a) = Error 若 ?2(S,a) =?
? Action(S,#) = Accept 若 ?2(S,#)={Reduce 1}
? Action(S,a) = Reduce j 若 ?2(S,a)= {Reduce j}
? Action(S,a) = Shift i 若 ?2(S,a)= {Shift}
and GoTo(S,a)=Si
GoTo表的构造：
? GoTo(S,X) = Si 若 S与 Si状态有 X转向边，
X为非终极符。
R413
R512
R6R611
R4R410
R69
139S12S88
R27
79S12S86
1011S4S55
R5R54
R33
R6S62
A1
321S4S50
RLS#=ba
LR(1)驱动程序
? LR(1)的驱动程序与 SLR(1)的驱动程序
是相同的，可共用一个。
状态栈 符号栈 输入串 Action GoTo
0 aab=b# S5
0,5 a ab=b# S5
0,5,5 aa b=b# S4
0,5,5,4 aab =b# R5 11
0,5,5,11 aaL =b# R6 10
0,5,5,10 aaR =b# R4 11
0,5,11 aL =b# R6 10
0,5,10 aR =b# R4 2
0,2 L =b# S6
0,6 L= b# S12
0,6,12 L=b # R5 9
0,6,9 L=L # R6 7
0,6,7 L=R # R2 1
0,1 S # A
?设文法 G[S]为：
S?AS | ?
A ?aA | b
证明 G[S]是 LR(1)文法；构造它的 LR(1)分
析表；给出符号串 abab#的分析过程