三、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→·a11,…,Am →·amm,B1→·,…,Bn →·} 如果能根据下一输入符号a对上述冲突加以区分,则冲突可解决. 当集合FOLLOW(Bk)(1≦k≦n)与{a1,a2,…,am}两两互不相交时,则 可按下述方法解决冲突: aVT{#}, IF a{a1,a2,…,am} THEN ACTION[i,a]=sj ELSE IF aFOLLOW(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产 生式,则对于aFOLLOW(A),置ACTION[i,a]=rj 注:其它规则不变! 对于给定的文法G,若其相应的SLR(1)分析表无冲 突项,则称G是SLR(1)文法