北京交通大学计算机与信息技术学院：《编译原理》课程教学资源（PPT课件讲稿）第四章 语法分析和语法分析程序（4.3）SLR（1）分析表的构造

三、SLR(1)分的造 常见程序设计语言都不是LR(O)的所以LR(0)分 析表实用性较差 例如,典型的分程序结构 B→BB→bD;SeD→D,ddS→s;S|s不是 LR(O)文法 甚至常见的简单表达式文法G]也不是LR(0)文 法

1 三、SLR(1)分析表的构造 常见程序设计语言都不是LR(0)的,所以LR(0)分 析表实用性较差. 例如,典型的分程序结构: B’ →B B →bD;Se D →D;d|d S →s;S |s 不是 LR(0)文法. 甚至常见的简单表达式文法G[E]也不是LR(0)文 法

B→BB→ bD: Se D→D;ddS→s;S|s Ia:B'→·B B I1:B→B B→·bD;Se I2:B→b·D:Se DI:B→bD D→·D;d D→D:;d 1tS→s D→·d s→·8;S 5:B→bD D→d D→D;*d 14:B→bD:S e 5 I1:S→s;S d 1 B→bD;Se I:D→Dd 图4-17识别G[B]活前缀的DFA

2 B’ →B B →bD;Se D →D;d|d S →s;S |s

表4-14G[B的LR(0)分析表 ACTION GOTO b # B 1 3 2 6 Cs r r r It 不过常见的程序设计语言相应的LR(0)分析表冲突项目 较少,可以对分析表做一定的修改,消除“约”或 “归的归绚”冲突

3 不过,常见的程序设计语言相应的LR(0)分析表冲突项目 较少,可以对分析表做一定的修改,消除“移进-归约”或 “归约-归约”冲突

SLR(1)钱的的造《》 考虑LRQ分析表的造表算法规则2,对于中归约项目A→0 不管下一输入符号是谁均进行归约若I1中同时含有B→0bβ 及C→>α两类项目时,上述填表方法必然得到冲突的分析表 一般地I1{A1→x·a1B1…,A→aaBn,B1→)x…,…,Bn→ 如果能根据下一输入符号a对上述冲突加以区分,则冲突可解决 当集合 FOLLOW(B)(1sk≌n)与{a1,a2,,an两两互不相交时,则 可按下述方法解决冲突 va∈V∪{#}, IFa∈{a1,a2,…,a} THEN ACTION[i,al=s; ElSE IF aeFOLLOW(B THEN ACTIONLi, a]=rBj-a ELSE ACTIONi,a]="ERR

4 SLR(1)分析表的构造（续） 考虑LR(0)分析表的造表算法规则(2),对于Ii中归约项目A→·, 不管下一输入符号是谁,均进行归约. 若Ii中同时含有B→·b 及C→·两类项目时,上述填表方法必然得到冲突的分析表. 一般地,Ii={A1→·a11,…,Am →·amm,B1→·,…,Bn →·} 如果能根据下一输入符号a对上述冲突加以区分,则冲突可解决. 当集合FOLLOW(Bk)(1≦k≦n)与{a1,a2,…,am}两两互不相交时,则 可按下述方法解决冲突: aVT{#}, IF a{a1,a2,…,am} THEN ACTION[i,a]=sj ELSE IF aFOLLOW(Bj) THEN ACTION[i,a]=rBj→ ELSE ACTION[i,a]=“ERR

SLR(1)分的的追《续 上述方法就是SLR(1)( Simple lr(1)规则按照 SLR(1)规则,只须将LR(0)分析表的填表规则(2)修 改为: (2)若归约项目A→α·属于I1,且A→α是P中第j 生式,则对于 VaEFOLLOW(A),置 ACTION[i,a]=r; 注:其它规则不变 对于给定的文法G,若其相应的SLR(1)分析表无冲 突项,则称G是SLR(1)文法

5 SLR(1)分析表的构造（续） 上述方法就是SLR(1) (Simple LR(1))规则.按照 SLR(1)规则,只须将LR(0)分析表的填表规则(2)修 改为: (2’) 若归约项目A→•属于Ii,且A→是P中第j产 生式,则对于aFOLLOW(A),置ACTION[i,a]=rj 注:其它规则不变! 对于给定的文法G,若其相应的SLR(1)分析表无冲 突项,则称G是SLR(1)文法

G[B]的SLR(1)分析表 创分程序文法GB中,I={S→>s·;S,S→>s·}含有 冲突,但 FOLLOW(S)={e}≠{;},故冲突可解决 ACTION GOTO b d B dco 012345678901 3 G

6 G[B]的SLR(1)分析表 例 分程序文法G[B]中,I8={S→s•;S, S→s•}含有 冲突,但FOLLOW(S)={e} ≠{;},故冲突可解决

四、LR(1)分析表的的造 尽管SLR(1)分析表简单实用,但还不能解决所有问题; 例如,文法S’→SS→ CbBA A→Aab|abB→C|Db C→aD→a相应的DFA见下页。 其中项目集I10={ SCbA,A→Aab}中存在“移进-归约” 冲突,由 FOLLOW(S)={#}≠{a},冲突是可解决的 但项目集Ig={C→a,D→a-}中, FOLLOW(C)={a,b}, FOLLOW(D)={b},存在公共元素b,不能解决此冲突 还需考虑另一个条件:归约后得到的符号串应该是一个 规范句型的前缀,即当分析栈内容为#6a,输入符为a时, 若将α归约为A,则#δAa必须是某一规范句型的前缀,否则 这个归约就是无效的

7 四、LR(1)分析表的构造 尽管SLR(1)分析表简单实用,但还不能解决所有问题; 例如,文法 S’→S S→CbBA A→Aab|ab B→C|Db C→a D→a 相应的DFA见下页。 – 其中项目集I10={S→CbBA·,A→A·ab}中存在“移进-归约” 冲突,由FOLLOW(S)={#} ≠{a}, 冲突是可解决的. – 但项目集I8={C→a·,D→a·}中, FOLLOW(C)={a,b}, FOLLOW(D)={b},存在公共元素b，不能解决此冲突. 还需考虑另一个条件：归约后得到的符号串应该是一个 规范句型的前缀，即当分析栈内容为#,输入符为a时, 若将归约为A,则#Aa必须是某一规范句型的前缀,否则 这个归约就是无效的

I12:A→ab 1 s→S b 12:S→C·bBA I:A→a·b 1:S→:S s→·CbBA a 13:S→CbB·A B A→·Aab I,:S→Cb·BA A→·ab I3:C→a B→:C A B→·Db C a C I1s;S→CbBA D→ A→A·ab I1:A→Aa·b lk:B→C Ir;B→D·b b 14: A→Aab l2:B→Db

8

LR(1)分析表的《续 例如对于上述文法的规范因此,将#6aa.归约成#8Aa 句型 Cbabab,分析达到格局:的前提条件不仅仅是要求 0121418 bab a∈ FOLLOW(A),还必须要求8Aa #cba 是某规范句型的前缀 时,由于输入符 在原来的每个LR(O)项目 b∈FOL0W(C),若用C来归 [A-·B]中放置一向前搜 约,得到 索符号a:[A→αB,al,称 为LR(1)项目 0121416 bab #c bc 要求每个LR(1)项目对相应 但CbC不是任何规范句型的 的活前缀是有效的,以保 前缀!因此应该用D来归约 证每一步分析都能得到规 得到规范句型的前缀CbD 范句型的活前缀

9 LR(1)分析表的构造（续） 例如,对于上述文法的规范 句型Cbabab,分析达到格局： I0I2I4I8 bab # C b a 时,由于输入符 b∈FOLLOW(C), 若用C来归 约,得到 I0I2I4I6 bab # C b C 但CbC不是任何规范句型的 前缀!因此应该用D来归约， 得到规范句型的前缀CbD. 因此,将#a归约成#Aa… 的前提条件不仅仅是要求 a∈FOLLOW(A),还必须要求Aa 是某规范句型的前缀. – 在原来的每个LR(0)项目 [A→•]中放置一向前搜 索符号a: [A→•,a],称 为LR(1)项目. – 要求每个LR(1)项目对相应 的活前缀是有效的，以保 证每一步分析都能得到规 范句型的活前缀

对先级有就的LR(1)项目 SLR(1)项目[A→>a°β,a]对活前缀y=8a有效,存在 规范推导:S→*δy→8αβyy∈Ⅵ,且满足条件 (1)当y≠E时,a∈ FIRST(y); (2)当y=E时,a=# 例如,对于上例中文法S’→SS→ CbBA A→ Lablab B→>C|DbC→aD→a,有 S→CbBA→Cbab= Cbba 可知[B→D·b,a] 对前缀y=6a A8aBy=CbD有效 S→* CbAb→ Cba bab 可知[D→a·,b 对前缀γ=8a A 8 Y =Cba有效

10 对活前缀有效的LR(1)项目 定义 LR(1)项目[A→•,a]对活前缀 =有效,iff 存在 规范推导：S Ay  y yVT * ，且满足条件: (1)当y≠时,a∈FIRST(y); (2)当y=时,a=#. 例如,对于上例中文法S’→S S→CbBA A→Aab|ab B→C|Db C→a D→a,有 S CbBACbBabCbDbab A    y 可知[B→D • b, a] 对前缀= =CbD 有效 SCbDbabCba bab A   = y 可知[D→a •, b] 对前缀= =Cba 有效