LALR(1)方法
?它具有 SLR(1)的状态数少的优点和 LR(1)
的适用范围广的优点。
?LALR(1)方法的功能介于 SLR(1)和 LR(1)
之间。
?LALR(1)状态机的状态个数和 LR(0)状态
机的状态个数相同，而其展望符则即不
采用 SLR(1)的 Follow集方法，也不采用
LR(1)的完全精确法。
LALR(1)的思想来源
?LR(1)状态机和 LR(0)状态机从它们所表
示的自动机角度来看是等价的 ；
?自动机可通过合并等价状态来减少状态
个数。
?在 LR(1)状态机出现很多同心状态，而
LALR(1)状态机则不产生同心的状态，
从而大大减少状态数，这就是 LALR(1)和
LR(1)的主要差别。
LALR(1)状态机的定义方式：
?用 LR(1)状态机来定义；
?用 LR(0)状态机来定义。
LALR(1)状态机的构造方法：
?先构造 LR(1)状态机，后构造 LALR(1)状态机
?按 LR(1)状态机的方式构造，但发现同心状态
时不产生新状态，而是采用合并状态的方法。
?先构造 LR(0)状态机，而后用传播方式求出每
个项目的展望符集。
相关的术语
? 假设 [A→ ???,b]是 LR(1)项目，则称其中
的 LR(0)项目部分 A→ ???为该 项目的心。
? 如果 LR(1)状态机中的两个状态具有相同的
心，则称它们为 同心状态。
? 例
假设在 LR(1)状态机中有状态 S1和 S2：
S1 = { [A→ ???,a1 ],[B→ ??,b1 ] },
S2 = { [A→ ???,a2 ],[B→ ??,b2 ] }
? Core(S1)= { A→ ???,B→ ?? },
? Core(S2)= { A→ ???,B→ ?? },
? SameCoreState( S1 )= { S 1,S2 }
? Merge({S1,S2}) = { [A→ ???,{a1,a2} ]，
[B→ ??,{b1,b2}] }
由 LR(1)SM构造 LALR(1)SM的算法
?初始化：
OldSS:=LR(1)状态机的状态集； NewSSS:={}；
?构造 LALR(1)的状态集：
while OldSS ? {} do
begin S,=OneStateOf(OldSS)；
NewSSS:=NewSSS∪SameCoreState(S) ；
OldSS,=OldSS- SameCoreState(S)；
end
?确定 LALR状态给的转向边：
对于 SS1,SS2 ?NewSSS,画 Merge(SS1) Merge(SS2)
当且仅存在 S1?SS1和 S2?SS2,使得 S1 S2 (LR(1)
状态机 )
X
X
LALR(1)的投影函数的定义
??3, StateSet0 ? (VT∪ {#} ) → 2?
?3(S,a)＝ { Reduce j | [ B→ ??,a ]?Cognate(S)
B→ ?是产生式 j }
∪ {if 存在 [A→ ??a?,?]?S then {Shift } }
S是由 LR(0)项目组成的 LALR状态 ;
Cognate(S)则表示在 LR(1)状态机中以 S为心的
所有状态的 LR(1)项目之集。
?当且仅当对任一 LALR状态 S和 a?(VT∪# )都
有 |?3 (S,a)| ? 1,称文法 G是 LALR(1)文法 。
LALR(1)分析表的构造
Action表的构造：
?Action(S,a)=Shift i,若 ?3 (S,a)={Shift }且
a?#,GoTo(S,a)=Si
?Action(S,a)=Reduce j, 若 ?3 (S,a)={Reduce j}
?Action(S,#)=Accept, 若 ?3 (S,＃ )={shift }
?Action(S,a)=Error, 若 ?3 (S,a)=?
GoTo表的构造：
?GoTo(S,a)=Si,若存在 S*?States_Contain(S)
Si*?States_Contain(Si),使得在 LR(1)状态机
中有 S*到 Si*的 a输出边 。
? 0型项目,黑点在最前的项目；它们是别的项目
派生出来的 (增广项目例外）。
例如 A→ ?aBc。
? Afirst, AFirst(A→ ??X?)= First(?)
? *型项目,若 AFirst(I)包含 ?，则称 (S,I)为 *
型项目，表示其展望符可传播。
LALR(1)SM的传播构造方法
展望符的产生
? 如果项目 (S,I)是由项目 (Si,Ij),i=…,j=… 产生，则称
这些项目 (Si,Ij)为 发射 (S,I)的项目 。令 (S,I)的展望
集为 L。
? 若 (S,I)=A → ?X?? 为非 0型项目：发射 (S,I) 的项目
(Si,Ij)具有形式 A → ??X?,令展望符集为 Lij,则有
等式,
L= ?Lij
?若 (S,I)=A→ ??为 0型项目：发射 (S,I)的项目具有形
式 D→ ?i?A?i,令展望符集为 Li,则有等式：
L = ?Li*
Li*= if ??First(?i) then First(?i)-{?}?Li else First(?i)
传播部分
自生部分
展望符传播算法：
?构造 LR(0)状态机时, 对于每个项目 (Si,Ij)构造其传播表 。
?展望符初始化,令增广项目 Z→ ?S的展望符集为 {#},令
其它项目的展望符集为 {}。
?计算自生展望符,
? 顺次扫描下一项目 (S,I ) ；
?若 (S,I)形如 A→ ??a?(a?VT),不做处理, 否做下面工作；
? 计算 AFirst(S,I )并加到 (S,I )所发射到的所有 0型项目
的展望符集上；
? 若 ? ?AFirst(S,I ),则给 (S,I )加可传播标记 * ；
? 重复上述过程, 直至全扫描完为止 。 （ 转下 ）
(接上 )
?传播展望符,
? 若不产生新的传播项则结束, 否则继续进行
? 选择一个未处理过的项目 (S,I,L) ；
? 将 L追加到 (S,I)所发射的非 0型项目的展望符集
上；
? 若 (S,I)是 *型项目, 则把 L追加到 (S,I) 发射的所
有 0型项目的展望符集上 ；
? 重复上述传播过程 。
#Z→ ?BB
B→ ?aB
B→ ?b
Z→ B?B
B→ ?aB
B→ ?b
B→ a?B
B→?aB
B→?b
B→ b?
Z→BB ?
B→aB ?
B B
b
ba
b
a
a
B
AFirst(0,1)= {a,b}
0
1
2
3
4
5
AFirst(2,1)={?}
{#}{a,b} {}*
{}
{}*
{}
{}
AFirst(3,1)={?}
{}
{}
{}
{} #
#
ab#
ab#
ab#
ab#
#
ab#
带传播的 LR(0)状态机
?它具有 SLR(1)的状态数少的优点和 LR(1)
的适用范围广的优点。
?LALR(1)方法的功能介于 SLR(1)和 LR(1)
之间。
?LALR(1)状态机的状态个数和 LR(0)状态
机的状态个数相同，而其展望符则即不
采用 SLR(1)的 Follow集方法，也不采用
LR(1)的完全精确法。
LALR(1)的思想来源
?LR(1)状态机和 LR(0)状态机从它们所表
示的自动机角度来看是等价的 ；
?自动机可通过合并等价状态来减少状态
个数。
?在 LR(1)状态机出现很多同心状态，而
LALR(1)状态机则不产生同心的状态，
从而大大减少状态数，这就是 LALR(1)和
LR(1)的主要差别。
LALR(1)状态机的定义方式：
?用 LR(1)状态机来定义；
?用 LR(0)状态机来定义。
LALR(1)状态机的构造方法：
?先构造 LR(1)状态机，后构造 LALR(1)状态机
?按 LR(1)状态机的方式构造，但发现同心状态
时不产生新状态，而是采用合并状态的方法。
?先构造 LR(0)状态机，而后用传播方式求出每
个项目的展望符集。
相关的术语
? 假设 [A→ ???,b]是 LR(1)项目，则称其中
的 LR(0)项目部分 A→ ???为该 项目的心。
? 如果 LR(1)状态机中的两个状态具有相同的
心，则称它们为 同心状态。
? 例
假设在 LR(1)状态机中有状态 S1和 S2：
S1 = { [A→ ???,a1 ],[B→ ??,b1 ] },
S2 = { [A→ ???,a2 ],[B→ ??,b2 ] }
? Core(S1)= { A→ ???,B→ ?? },
? Core(S2)= { A→ ???,B→ ?? },
? SameCoreState( S1 )= { S 1,S2 }
? Merge({S1,S2}) = { [A→ ???,{a1,a2} ]，
[B→ ??,{b1,b2}] }
由 LR(1)SM构造 LALR(1)SM的算法
?初始化：
OldSS:=LR(1)状态机的状态集； NewSSS:={}；
?构造 LALR(1)的状态集：
while OldSS ? {} do
begin S,=OneStateOf(OldSS)；
NewSSS:=NewSSS∪SameCoreState(S) ；
OldSS,=OldSS- SameCoreState(S)；
end
?确定 LALR状态给的转向边：
对于 SS1,SS2 ?NewSSS,画 Merge(SS1) Merge(SS2)
当且仅存在 S1?SS1和 S2?SS2,使得 S1 S2 (LR(1)
状态机 )
X
X
LALR(1)的投影函数的定义
??3, StateSet0 ? (VT∪ {#} ) → 2?
?3(S,a)＝ { Reduce j | [ B→ ??,a ]?Cognate(S)
B→ ?是产生式 j }
∪ {if 存在 [A→ ??a?,?]?S then {Shift } }
S是由 LR(0)项目组成的 LALR状态 ;
Cognate(S)则表示在 LR(1)状态机中以 S为心的
所有状态的 LR(1)项目之集。
?当且仅当对任一 LALR状态 S和 a?(VT∪# )都
有 |?3 (S,a)| ? 1,称文法 G是 LALR(1)文法 。
LALR(1)分析表的构造
Action表的构造：
?Action(S,a)=Shift i,若 ?3 (S,a)={Shift }且
a?#,GoTo(S,a)=Si
?Action(S,a)=Reduce j, 若 ?3 (S,a)={Reduce j}
?Action(S,#)=Accept, 若 ?3 (S,＃ )={shift }
?Action(S,a)=Error, 若 ?3 (S,a)=?
GoTo表的构造：
?GoTo(S,a)=Si,若存在 S*?States_Contain(S)
Si*?States_Contain(Si),使得在 LR(1)状态机
中有 S*到 Si*的 a输出边 。
? 0型项目,黑点在最前的项目；它们是别的项目
派生出来的 (增广项目例外）。
例如 A→ ?aBc。
? Afirst, AFirst(A→ ??X?)= First(?)
? *型项目,若 AFirst(I)包含 ?，则称 (S,I)为 *
型项目，表示其展望符可传播。
LALR(1)SM的传播构造方法
展望符的产生
? 如果项目 (S,I)是由项目 (Si,Ij),i=…,j=… 产生，则称
这些项目 (Si,Ij)为 发射 (S,I)的项目 。令 (S,I)的展望
集为 L。
? 若 (S,I)=A → ?X?? 为非 0型项目：发射 (S,I) 的项目
(Si,Ij)具有形式 A → ??X?,令展望符集为 Lij,则有
等式,
L= ?Lij
?若 (S,I)=A→ ??为 0型项目：发射 (S,I)的项目具有形
式 D→ ?i?A?i,令展望符集为 Li,则有等式：
L = ?Li*
Li*= if ??First(?i) then First(?i)-{?}?Li else First(?i)
传播部分
自生部分
展望符传播算法：
?构造 LR(0)状态机时, 对于每个项目 (Si,Ij)构造其传播表 。
?展望符初始化,令增广项目 Z→ ?S的展望符集为 {#},令
其它项目的展望符集为 {}。
?计算自生展望符,
? 顺次扫描下一项目 (S,I ) ；
?若 (S,I)形如 A→ ??a?(a?VT),不做处理, 否做下面工作；
? 计算 AFirst(S,I )并加到 (S,I )所发射到的所有 0型项目
的展望符集上；
? 若 ? ?AFirst(S,I ),则给 (S,I )加可传播标记 * ；
? 重复上述过程, 直至全扫描完为止 。 （ 转下 ）
(接上 )
?传播展望符,
? 若不产生新的传播项则结束, 否则继续进行
? 选择一个未处理过的项目 (S,I,L) ；
? 将 L追加到 (S,I)所发射的非 0型项目的展望符集
上；
? 若 (S,I)是 *型项目, 则把 L追加到 (S,I) 发射的所
有 0型项目的展望符集上 ；
? 重复上述传播过程 。
#Z→ ?BB
B→ ?aB
B→ ?b
Z→ B?B
B→ ?aB
B→ ?b
B→ a?B
B→?aB
B→?b
B→ b?
Z→BB ?
B→aB ?
B B
b
ba
b
a
a
B
AFirst(0,1)= {a,b}
0
1
2
3
4
5
AFirst(2,1)={?}
{#}{a,b} {}*
{}
{}*
{}
{}
AFirst(3,1)={?}
{}
{}
{}
{} #
#
ab#
ab#
ab#
ab#
#
ab#
带传播的 LR(0)状态机
