吉林大学：《编译原理》课程教学资源（PPT课件讲稿）LALR（1）方法

LALR(1)方法 +它具有SLR(1)的状态数少的优点和LR(1) 的适用范围广的优点。 +LALR(1)方法的功能介于SLR(1)和LR(1 之间。 LALR(1)状态机的状态个数和LR(0)状态 机的状态个数相同,而其展望符则即不 采用SLR(1)的 Follow集方法,也不采用 LR(1)的完全精确法

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(状态机从它们所表 示的自动机角度来看是等价的 自动机可通过合并等价状态来减少状态 个数。 在LR(1)状态机出现很多同心状态,而 LALR(1)状态机则不产生同心的状态 从而大大减少状态数,这就是LALR(1)和 LR(1)的主要差别

LALR(1)的思想来源 LR(1)状态机和LR(0)状态机从它们所表 示的自动机角度来看是等价的 ； 自动机可通过合并等价状态来减少状态 个数。 在LR(1)状态机出现很多同心状态，而 LALR(1)状态机则不产生同心的状态， 从而大大减少状态数，这就是LALR(1)和 LR(1)的主要差别

LALR(1)状态机的定义方式: ÷用LR(1)状态机来定义; +用LR0状态机来定义。 LALR(1)状态机的构造方法 先构造LR(1)状态机,后构造LALR(1)状态机 ÷按LR(1)状态机的方式构造,但发现同心状态 时不产生新状态,而是采用合并状态的方法 先构造LR(0)状态机,而后用传播方式求出每 个项目的展望符集

LALR(1)状态机的定义方式： 用LR(1)状态机来定义； 用LR(0)状态机来定义。 LALR(1)状态机的构造方法： 先构造LR(1)状态机，后构造LALR(1)状态机 按LR(1)状态机的方式构造，但发现同心状态 时不产生新状态，而是采用合并状态的方法。 先构造LR(0)状态机，而后用传播方式求出每 个项目的展望符集

相关的术语 ÷假设[A→a·β,b是LR1)项目,则称其中 的LR(0)项目部分A→a·B为该项目的心。 如果LR(1)状态机中的两个状态具有相同的 心,则称它们为同心状态

相关的术语  假设[A→•, b]是LR(1)项目，则称其中 的LR(0)项目部分A→•为该项目的心。  如果LR(1)状态机中的两个状态具有相同的 心，则称它们为同心状态

例 假设在LR(1)状态机中有状态S1和S2 |A→°β,a1l,「B→π°,b1 S2={|A→°β,a2],|B→T●,b2]} Core(S1)={A→°β,B→T●}, Core(S2)={A→0阝,B→T} Same CoreState(s=s1,s, Merge(b1,32了 )={|A→a●B,{a1,a2 IB→°,{b1,b2

 例 假设在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的算法 ◆初始化: 0|dSs:=LR(1)状态机的状态集; NewSSs:=}; ◆构造LALR(1)的状态集: while0ldsS≠t}do beg in s: =oneStateOf(oI dSs) NewSSS: =NewSSS U Same CoreState(s) oldSs =oldSs- Same CoreState(s) end ◆确定LALR状态给的转向边 对于S8,SS2∈ NewSSs,画 Merge(SS1)→ Merge(S2 当且仅存在S1SS1和S2∈S2,使得S1-S2(LR(1) 状态机)

由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)的投影函数的定义 r3: Statelet×(VrU{#)→29 r3(S,a)={ Reduce j[B→兀·,al∈ Cognate(S) B→∽是产生式j} Uff存在[A→aaB,?] es then{Shit}} S是由LR(0项目组成的LALR状态; Cognate(S则表示在LR(1状态机中以S为心的 所有状态的LR(1)项目之集 当且仅当对任一LALR状态S和a∈(V1∪#)都 有r3S,a)≤1,称文法G是LALR(1)文法

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,若r3(S,a)={Shif}且 a≠#,GoTo(S,a)=S1 tAction(S, a)=Reducej, r3(S, a)=Reduce j ◆ Action(S,#)= Accept,若r3(S,#)={ shift} +Action(S, a)=Error, #r3(S, a)=0 GT表的构造: GoTo(S,a)=S,若存在S*∈ States Contain(S S1∈ States contain(S),使得在LR(1)状态机 中有S到S的a输出边

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输出边

LALR(1)SM的传播构造方法 0型项目:黑点在最前的项目;它们是别的项目 派生出来的(增广项目例外)。 例如A→●aBc Afirst: AFirst(A→·XB)= First(β) *型项目:若 AFirst()包含λ,则称(S,1)为* 型项目,表示其展望符可传播

 0型项目：黑点在最前的项目；它们是别的项目 派生出来的(增广项目例外）。 例如A→•aBc。  Afirst ：AFirst(A→•X)= First()  *型项目：若AFirst(I)包含，则称(S, I)为* 型项目，表示其展望符可传播。 LALR(1)SM的传播构造方法

展望符的产生 ÷如果项目(S,D是由项目(S,功)=…产生,则称 这些项目(S,为发射S,D的项目。令(S,D的展望 集为L。 若(S,D=A→0X为非0型项目:发射S,D的项目 S)具有形式A→aXB,令展望符集为L;?则有 等式: 传播部分 L=1 若S,D=A→为0型项目:发射(S的项目具有形 式D→Aβ,令展望符集为L则有等式: 自生部分 Li*=ifhe First(B) then First(B i)-aULi else First(Bi)

展望符的产生  如果项目(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 ) 传播部分 自生部分