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表