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

主要内容: LR(1)分析方法

主要内容：  LR(1)分析方法

Z→E E E→>(L,E) E→(L,E) E→S →(L,E) E→S s→)id s→(°S) s→·(S) →°L,E L→LE °E L→E E→>°(L,E E→·S s→id S→id s→s) s→(S) s T1(S2,))=(Shift, Reduce3] E→S s-(S°)

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}

CLR(O)方法不依赖输入流,直接判定归约, 容易出现冲突。 SLR(1)方法简单的把非终极符的 follow集做 为可归约的依据,并不精确。 个非终极符在不同的位置上出现,它所允 许的后继符是不同的。LR(1)针对不同产生 式上的非终极符,分别定义其后继符集(展 望符集 Reduce lookup),减少了移入/归约 冲突

 LR(0)方法不依赖输入流，直接判定归约， 容易出现冲突。  SLR(1)方法简单的把非终极符的follow集做 为可归约的依据，并不精确。  一个非终极符在不同的位置上出现，它所允 许的后继符是不同的。LR(1)针对不同产生 式上的非终极符，分别定义其后继符集（展 望符集Reducelookup），减少了移入/归约 冲突

LR(1)分析方法 LR(1)方法研究的对象是二元组:(oa,b), 其中a是活前缀,而b是一个输入符号。我 们称上述(α,b)为LR前缀模式。 如果α是文法的归约活前缀,b是a的合法后 继续符,则称(α,b)为LR归约前缀模式

LR(1)分析方法 ◼ LR(1)方法研究的对象是二元组：( , b)， 其中是活前缀，而b是一个输入符号。我 们称上述( , b)为LR1前缀模式。 ◼ 如果是文法的归约活前缀，b是的合法后 继续符，则称( , b)为LR1归约前缀模式

LR归约前缀的派生定理 假设a是拓广产生式的右部,#是输入流 的结束符,则有 (α[p],#)是LR归约前缀模式 1设(αAβ[p],b)是LR归约前缀模式, LR归约前缀模式,其中a∈ First(z设 且A→π是q产生式,则(aπ[q],a)也

LR1归约前缀的派生定理 ◼ 假设0是拓广产生式的右部，#是输入流 的结束符，则有： ( 0 [p], # )是LR1归约前缀模式。 ◼ 设( A[p], b )是LR1归约前缀模式， 且A→是q产生式，则([q] , a)也是 LR1归约前缀模式，其中aFirst(b)

LR(1)项目:[A→α°Bβ,a]。LR(o)项目及一个 V∪{#的展望符集合 S:LR(1)项目集 S So=[A→aB,a]|[A→aXB,a]∈lS ■CL0SURE(1S)=|SU B→∽,b]|[A→aB,a]∈CL0SURE(Is), B→是产生式,b∈ First(βa)

◼ 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)}

LRSM的构造算法 1.初始项目集: SS=cL0SURE([[Z→●s,[#}]}) 若所有状态都处理完,则结束 3.选一未处理完状态|S,对所有语法符号 X∈(V∪M∪{#),求|S,令 S= CLOSURE(IS),若lS不为空: 若|S为新状态,则增加|s lS,把lS加 入LRSM1中;否则为图中某个状态|S,则在|S 和lS之间增加一条转换边:lS S 4.转到步骤2

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: SLL aR b R→

◼ 非SLR(1)文法： Z → S S → L= R S → R L → aR L → b R → L

0 6 Z→S·# S→>L=·R|# s→L=R·# S→°L=R|# R→)●L R →)·R# aR# L→》●aR=# s→L·=R# L→>●b # →●b R→L● # R→>°L# 9 R a R→L·# 8 3 L→>a●R|# a·R# S→>R。# bR→。L R→)·L# →·aR# →·aR# L→●b# →●b# R R 13 L→b·|=# R→>aR·# 10 12 11 L→>aR·# L→b·# R→L·#

0Z→• S S→•L=R S→•R L→•aR L→•b R→•L ### = # = # # 1Z → S • # 2S → L •=R R → L • ## 6S →L= • R R → • L L→•aR L→•b #### 7S →L=R • # 3S → R • # 4L → b • =# 10L→aR • #= 5L → a • R R → • L L→•aR L→•b # = # = # = # = 11R→ L • # = 8L → a • R R → • L L→•aR L→•b #### 9R → L • # 12L→ b • # 13R→aR • # SLa R b b = R L R L a b a aLR b

LR(1)文法 投影函数2 r2: StateLet x(ⅤTU{#)→29 T(S, a) { Reducej b→π·,a]∈S,B→π是产生式j} U(if[A→aaβB,b]∈S then Shift) C如果LR(1)状态机的任一状态S和输入符a, 都使得2(S,a)≤1,则称文法为LR(1)文 法

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)文 法