4.24LR分析法 1965年 D. Knuth提出了分析效率很高的LR(k)分 析技术; 口LR分析:自左至右扫描的自底向上的分析; 在分析的每一步,只须根据分析栈中的已移进的 和已归约出的符号,并至多向前扫描k个字符就 能确定应采取什么分析动作(移进、归约、接受、 报错 LR分析对文法要求很少效率很高,且能及时发 现错误,是目前最广泛使用的方法,一般用CFG描 述的语言均可用LR分析法
1 4.2.4 LR分析法 1965年D.Knuth提出了分析效率很高的LR(k)分 析技术; LR分析: 自左至右扫描的自底向上的分析; 在分析的每一步,只须根据分析栈中的已移进的 和已归约出的符号,并至多向前扫描k个字符就 能确定应采取什么分析动作(移进、归约、接受、 报错); LR分析对文法要求很少,效率很高,且能及时发 现错误,是目前最广泛使用的方法;一般用CFG描 述的语言均可用LR分析法
LR分祈缭迷 已证明的结论: LR(k)文法是无二义性文法 LR(k)文法与LR(1)文法等价 由于常见的程序设计语言均能由LR(1)文法产生,因此只讨论 下面的四种LR分析器: LR(①)简单,分析能力最低; SLR(1)分析能力强于LR(O) LR(1)分析能力最强,但分析表大 LALR(1)分析能力介于SLR(1)与LR(1)之间,分析表的规模 与SLR(1)相同,是最常用的LR分析方法
2 LR分析综述 已证明的结论: – LR(k)文法是无二义性文法; – LR(k)文法与LR(1)文法等价. 由于常见的程序设计语言均能由LR(1)文法产生,因此只讨论 下面的四种LR分析器： – LR(0)简单,分析能力最低; – SLR(1)分析能力强于LR(0); – LR(1)分析能力最强,但分析表大; – LALR(1)分析能力介于SLR(1)与LR(1)之间,分析表的规模 与SLR(1)相同,是最常用的LR分析方法
LR分析噩的逻辑结构及工作原理 分析器自左至右地扫描输入串的 a1…a 各符号,并根据当前分析栈的内 容及正扫描的符号按分析表的指 示完成相应的动作。 分总控程序 分析栈记录了已分析的内容及当 析栈 前的状态; 分析表 开始时,栈内放入#及开始状态 0 随着分析的深入,栈内容总 是刻划了当前的状态,及分析的 “历史” 内容
3 LR分析器的逻辑结构及工作原理 分析器自左至右地扫描输入串的 各符号，并根据当前分析栈的内 容及正扫描的符号按分析表的指 示完成相应的动作。 分析栈记录了已分析的内容及当 前的状态； 开始时，栈内放入#及开始状态 S0，随着分析的深入，栈内容总 是刻划了当前的状态，及分析的 “历史”。 总控程序 分析表 分 析 栈 a1 a2 … ai …an# Sm Xm … S1 X1 S0 # 内 容 状 态
1 ACTION[SI, a,1 ACTION[S: a2] ACTIONSI al S2 ACTION[S2, a,1 ACTION[S2, a2 ACTIONIS,, a, Sn ACTION[Sn, a1] ACTION[Sn, a2 ACTIONSn, a, ACTION表(分析动作表) GOTO(S X1]GOTO(SI X].GOTO[S,, X] S2GOTOIS2, X1] GOTO[S2, X2] GOTOS,, X, Sn GOTO[Sn X11 GOTO[S,,X2 GOTOSn, XII GOTO表(状态转换表)
4 LR分析表 a1 a2 … al S1 ACTION[S1 ,a1 ] ACTION[S1 ,a2 ] … ACTION[S1 ,al ] S2 ACTION[S2 ,a1 ] ACTION[S2 ,a2 ] … ACTION[S2 , al ] … … … … … Sn ACTION[Sn ,a1 ] ACTION[Sn ,a2 ] … ACTION[Sn , al ] X1 X2 … Xl S1 GOTO[S1 ,X1 ] GOTO[S1 ,X2 ] … GOTO[S1 ,Xl ] S2 GOTO[S2 ,X1 ] GOTO[S2 ,X2 ] … GOTO[S2 ,Xl ] … … … … … Sn GOTO[Sn ,X1 ] GOTO[Sn ,X2 ] … GOTO[Sn ,Xl ] ACTION 表（分析动作表） GOTO表（状态转换表）
LR分析表实例 设已给文法G]:1.L→EL:2.L→E;3.E→a;4.E少b,产 生的语言为:单个ab或用逗号隔开的多个a2b符号串 文法的LR分析表(s表示移进操作) ab,# #L E 3 2 0123456 acc r r 4 123456 ACTION表 GOTO表
5 LR分析表实例 设已给文法G[L]: 1. L→E,L；2. L→E；3. E→a；4. E→b，产 生的语言为：单个a,b或用逗号隔开的多个a,b符号串 文法的LR分析表(s表示移进操作) a b ， # 0 s s 1 acc 2 s r2 3 r3 r3 4 r4 r4 5 s s 6 r1 a b ， # L E 0 3 4 1 2 1 2 5 3 4 5 3 4 6 2 6 ACTION表 GOTO表
分的合先 可看出GOTO表中所有关于终结符的状态转换都与 ACTION表中的移进操作对应,因此可将相应的列合并 得到下面的分析表(关于V符的状态转换仍然保留): 状态 ACTION GOTO 实际的分析表往 a 5/m/12/往是稀疏的,可 E 采用更紧凑的格 式存储。 3 r 6 6
6 分析表的合并 可看出,GOTO表中所有关于终结符的状态转换都与 ACTION表中的移进操作对应，因此可将相应的列合并， 得到下面的分析表（关于VN符的状态转换仍然保留）： 状态 ACTION GOTO a b ， # L E 0 s3 s4 1 2 1 acc 2 s5 r2 3 r3 r3 4 r4 r4 5 s3 s4 6 2 6 r1 实际的分析表往 往是稀疏的，可 采用更紧凑的格 式存储
LR分器的作程 1.分析开始时,首先将初始状 态S及#压入栈; SS1S2…Sm 2设在分析的某一步分析栈#X1X2Xm32+12…1,# 和余留输入串处于格局 用Sma查 ACTION表,并根据指示完成相应的动作,分析 动作有移进归约报错接受四种 (1)移进Sk:表明句柄尚未在栈顶形成,正期待继续移进 输入符号a以形成句柄,并且移入后状态转移到Sk,故 将a和S压入栈,格局如下 S.S,S. Sms I #X12…Xma1a+1a1+2…an#
7 LR分析器的工作过程 1. 分析开始时,首先将初始状 态S0及#压入栈; 2. 设在分析的某一步,分析栈 和余留输入串处于格局: S0S1S2…Sm # X1X2…Xm aiai+1ai+2…an# 用Sm,ai查ACTION表,并根据指示完成相应的动作,分析 动作有移进,归约,报错,接受四种: (1)移进sk：表明句柄尚未在栈顶形成,正期待继续移进 输入符号ai以形成句柄,并且移入后状态转移到Sk ，故 将ai和Sk压入栈，格局如下: S0S1S2…SmSk # X1X2…Xmai ai+1ai+2…an#
LR分新器的三作越程续 (2)归约r:其中r表示按P的第j产生式A→Xmk+1Xmk+2Xm 进行归约这表明栈顶部的符号串Xmk1Xmk2符号) 是当 前句型的句柄将栈顶符号串Xmk+Xmk+2 从栈顶退出,再将A压入栈此时的格局为 m-k #X1X2…Xm:Aa:a+1a+2…,an# 再以(SmkA)查GOTO表,得S将S压入栈得到格局 #XIX.X A 1ai+2 a,#
8 LR分析器的工作过程（续） (2)归约rj：其中rj表示按P的第j产生式A→Xm-k+1Xm-k+2Xm 进行归约;这表明栈顶部的符号串Xm-k+1Xm-k+2Xm是当 前句型的句柄. 将栈顶符号串Xm-k+1Xm-k+2Xm(k个符号) 从栈顶退出,再将A压入栈,此时的格局为 S0S1S2…Sm-k # X1X2…Xm-kA aiai+1ai+2…an# 再以（Sm-k ,A）查GOTO表,得Sk ,将Sk压入栈,得到格局: S0S1S2…Sm-rSk # X1X2…Xm-rA aiai+1ai+2…an#
LR分器的已作程统) ●(3)若 ACTION(Smna)-=“acc”,则表明当前输入串已被成功地 分析完毕结束; (4)若 ACTION(Sm,a)= ERROR,则表明当前输入串有语法 错误转入出错处理程序 3.重复步骤2的工作,直到分析的某步的格局为 其中Z为文法的开始符号,Sz是使 ACTION(S2#)=“acc 的唯一状态
9 LR分析器的工作过程(续) (3)若ACTION(Sm,ai )=“acc” ,则表明当前输入串已被成功地 分析完毕,结束; (4)若ACTION(Sm,ai )=“ERROR” ,则表明当前输入串有语法 错误,转入出错处理程序; 3. 重复步骤2.的工作,直到分析的某步的格局为: S0SZ # Z # 其中,Z为文法 的开始符号, SZ是使ACTION(SZ ,#)=“acc” 的唯一状态
符号串“ab,a”的LR分析过程 步骤状态栈中符号余留符号分析动作 下一状态 a, b, a# 3 123 # b, a# r GOTOO,E=2 02 #E b, a# 025 #E, ba#t 0254 fE, b a# r GOTO5,E=2 56789 0252 #.E # 02525 #E,E, aft 3 025253#EEa # GOTO5,E=2 025252 #EEE # GOTO5, L=6 10 025256#E,EL # GOTO5, L=6 0256 #.L # GOTOJO, LIF1 12 01 #L #
10 符号串“a,b,a”的LR分析过程 步骤 状态 栈中符号 余留符号 分析动作 下一状态 1 0 # a,b,a# s3 3 2 03 #a ,b,a# r3 GOTO[0,E]=2 3 02 #E ,b,a# s5 5 4 025 #E, b,a# s4 4 5 0254 #E,b ,a# r4 GOTO[5,E]=2 6 0252 #E,E ,a# s5 5 7 02525 #E,E, a# s3 3 8 025253 #E,E,a # r3 GOTO[5,E]=2 9 025252 #E,E,E # r2 GOTO[5,L]=6 10 025256 #E,E,L # r1 GOTO[5,L]=6 11 0256 #E,L # r1 GOTO[0,L]=1 12 01 #L #