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

主要内容 句SLR(1)分析方法

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

LR(0分析方法的不足 CLR(0)方法对文法的要求严格。 CLR(0)方法容易出现冲突状态

LR(0)分析方法的不足  LR(0)方法对文法的要求严格。  LR(0)方法容易出现冲突状态

个文法例 S→E#[1 E→E+T[2] E→T[3] T→T×P[4] T→P[5] P→id[6] P→(E)[7

一个文法例: ◼ GE: S→E # [1] ◼ E→E + T [2] ◼ E→T [3] ◼ T→T  P [4] ◼ T→P [5] ◼ P→id [6] ◼ P→( E ) [7]

0 E S→·E#[1] s→E·# E→·T [3] T→·TxP[4 P P→·id[6] T→P● P→·(E)[7 id P→id● E→T T→T●xP T E→·E+T 8 T→·T×P E P→·id P→·id (E ● (E T T→T*P 图4553C的LRSM

图 4 . 5 . 5 . 3 G  E 的LRSM 0 + EP id #+ P id ( T T id (   id E ( P ) 4 E→ T • T→ T •  P 7 P→ id • 5 E→ E + • T T→ • T  P T→ • P P→ • id P→ • (E) 3 T→ P • 4 S→ E • # E→ E • + T 1 S→ • E # [1] E→ • E+T [2] E→ • T [3] T→ • T  P [4] T→ • P [5] P→ • id [6] P→ • (E) [7] 0 T→ T  • P P→ • id P→ • (E) 8 T→ T * P • 9 E→ E+T • T→ T •  P 11 P→ (E • ) E→ E • +T 12 P→(E) • 10 P ( T P → ( • E ) E→ • E+T E→ • T T→ • T  P T→ • P P→ • id P→ • (E) 6 7 8 S→ E# • 2

如果某个状态有如下项目集: A→a·,B→β·,D→μ·dy},则存在 着归约-归约,归约-移入冲突 若用A→c●归约,则当前输入符应在A 的Foow集中 若用B→β·归约,则当前输入符应在B 的 Follow集 若移入,则当前输入符应为d

如果某个状态有如下项目集： { A → •, B → •, D→ • d  }，则存在 着归约-归约，归约-移入冲突 ◼ 若用A → •归约，则当前输入符应在A 的Follow集中 ◼ 若用B → •归约，则当前输入符应在B 的Follow集 ◼ 若移入，则当前输入符应为d

SLR(1)分析条件 LRSM中存在着状态 {A101°, ●·9 B1→B1·2a1r1 o多 ●。● B●arn} n nn FOllOw(A…⌒ Follow(An) }=

SLR(1)分析条件 ◼ LRSM0中存在着状态 { A1 →1 •，…，An →n •， B1→1 •a1 r1，…，Bn → n •an rn } Follow(A1 )…  Follow(An ) {a1 ,…,an }=

SLR(1)文法的定义 SLR(1)文法的投影函数定义如下: r: Statelet×(rU{#)→2 TI(S,a) ReducejB→兀●∈S,a∈ Follow(B),B→兀∈P U(i在X→a·aB∈S且acⅤ then{Shi) C如果LRSM中的每个状态S,对任意a∈Vr 使得r(S,a)≤l,则称相应文法为SLR(1)文法

SLR(1)文法的定义 ◼ SLR(1)文法的投影函数 1定义如下： •  1：StateSet  (VT∪{#})→2  •  1 (S,a) = {Reduce j |B→•S,aFollow(B),B→ P} ∪(if存在X→•aS且aVT then {Shift})  如果LRSM0中的每个状态S，对任意 aVT， 使得| 1 (S,a)|1，则称相应文法为SLR(1)文法

SLR(1) Action表的构造 Ar(S, #=Shift Action( S, #)=Accept 若r(S,a)={ Shift且a≠# Action(S,a)= Shift AT(S,a)=Reduce j Action( S, a)=Reduce j AT(S, a)=0 Action(S, a)=Error

SLR(1)__Action表的构造 ◼ 若 1 (S,#)={Shift} Action( S, # )=Accept ◼ 若 1 (S,a)={Shift }且a# Action( S, a) =Shift ◼ 若 1 (S,a)={Reduce j} Action( S, a) =Reduce j ◼ 若 1 (S,a)= Action( S, a) = Error

SLR(1)GoT表的构造 GoTo(S,X)=S',当LRSM中有S8 GoTo(S,X)=eror,否则 合并的SLR(1)分析表,合并方法: Action'(s, a)=Shift i 当 Action'(s,a)=Shif且GoTo(S,a)= GoTO(s,X=S 当Go0(S,X)=S;且X∈VN

SLR(1)__GoTo表的构造 ◼ GoTo( S, X) = S  ， 当LRSM0中有S S ◼ GoTo( S, X) = error，否则 ◼ 合并的SLR(1)分析表，合并方法: Action( S, a) = Shift i , 当Action(S, a)= Shift且GoTo(S,a)=Si GoTo( S, X) = Si , 当GoTo(S,X)=Si 且XVN X

0 E S→·E#[1] s→E·# E→·T [3] T→·TxP[4 P P→·id[6] T→P● P→·(E)[7 id P→id● E→T T→T●xP T E→·E+T 8 T→·T×P E P→·id P→·id (E ● (E T T→T*P 图4553C的LRSM

图 4 . 5 . 5 . 3 G  E 的LRSM 0 + EP id #+ P id ( T T id (   id E ( P ) 4 E→ T • T→ T •  P 7 P→ id • 5 E→ E + • T T→ • T  P T→ • P P→ • id P→ • (E) 3 T→ P • 4 S→ E • # E→ E • + T 1 S→ • E # [1] E→ • E+T [2] E→ • T [3] T→ • T  P [4] T→ • P [5] P→ • id [6] P→ • (E) [7] 0 T→ T  • P P→ • id P→ • (E) 8 T→ T * P • 9 E→ E+T • T→ T •  P 11 P→ (E • ) E→ E • +T 12 P→(E) • 10 P ( T P → ( • E ) E→ • E+T E→ • T T→ • T  P T→ • P P→ • id P→ • (E) 6 7 8 S→ E# • 2