第四章_3 LR分析法.pptx

1、4.5 LR分析法，1概要LR分析法是从下到上规范归约的语法分析方法。l、r、从左到右扫描输入串、从最右导出的逆过程、规范归约、4.5 LR分析法、2特征、优点：缺点：句法限制少，结构LR分析器功能多，难以实现。 用YACC自动生成LALR(1)分析器。4.5 LR分析法、3种LR类型、LR(0)、SLR(1)、LR(1)、LALR(1)、基础、理论过剩、理论过剩、实用、4.5 LR分析法。 4.5.1 LR分析器的工作原理和过程、1 LR分析器结构、LR分析表、总控制程序、a1、am、$、ai、输出分析堆栈这两个指针同步。 分析堆栈，状态堆栈，语法符号堆栈， 4.5.1 LR它是由分析行为表

2、(ACTION )状态转移表(GOTO )、LR分析表实例、状态、ACTION、GOTO、a、(、)、和、两部分组成的4.5.1 LR分析器的工作原理和过程、3 LR分析器的工作过程示例4 . 4.5.2 LR(0)分析法，0 LR分析表的结构步骤(1)从语法结构识别语法的所有规范句型活动前缀的DFA (2)将DFA转换为一张LR分析表的4.5.2 LR(0)分析法，例如，字符串abc的前缀为：a，ab，abc 例如：若某句法规范文型aaAbb$，其句柄为aAb，则在前缀：a、aa、aaA、aaAb、aabb、AABB $ .活动前缀：a、aa、aaA、LR分析中，需要构筑识别活动前缀的DFA

3、。 句法的结尾符号和非结尾符号都作为输入符号，在把符号输入堆栈的同时，状态也变换。 4.5.2 LR(0)分析法、2 LR(0)项目活前缀和句柄的三个关系： (1)全部包括a，即句柄形成，归约。 (2)部分包含a，形成手柄部分，移动或预约。 (3)零包括a，未形成、移动或保留。a、a、a、4.5.2 LR(0)分析法，将在2 LR(0)项目的右部带有圆点的产生式称为LR(0)项目。 特别是对于a的LR(0)项目a，4.5.2 LR(0)分析法、3 LR(0)项目分类归约项目a移动到项目a，归约项目A B接受项目s、4.5.2 LR(0)的状态： LR(0)项目集LR(0)项目的集合用闭包函数、

4、GO函数构建DFA的构成部分。 闭包函数(设CLOSURE(I )为项目集，则CLOSURE(I )包含： I的所有项目。 如果I中有A B，那么B r也属于CLOSURE(I )。 重复上一步，直到CLOSURE(I )变大为止。 GO函数GO(I，X)=CLOSRUE(J). JA X |A X I，例句法4.14.ss1.sa2.sb3.aab4.4.5.2 LR(0)分析法，构筑识别四活前缀的DFA方法(0)扩展语法，导入s，制作s，加上规则编号求出(CLOSURE(S S )，得到初始项目集。 (2)对于构筑的项目集，适用GO函数，求后续的状态(3)重复(2)，直到新的项目集不再出现

5、。 构成识别一个语法活动前缀的DFA的整个状态，称为该语法的LR(0)项集规范族。 构建4.14语法的LR(0)项目集规范族。LR(0)语法：不存在转移归约，或者归约并存。 I1:S S，示例4.14语法GS: S (S) S a (1)结构识别句法范文型活动前缀的DFA。 (2)判断该语法是否是LR(0)语法，如果是，则制作LR(0)分析表。 如果不是的话，我来说明理由。 扩展语法，赋予各规则编号：0. S S 1. S (S) 2. S a，4.5.2 LR(0)分析法，5 LR(0)分析表的结构(ACTION) B=J (3)A，对于所有的终结符号a，ACTION(I，a)=rj (4)

6、S S， 如果设置其他空白单元所创建的LR分析表中不包含多重定义，则该表为LR(0)分析表。 可以制作LR(0)分析表的语法是LR(0)语法。示例4.14语法GS: S (S) S a (1)结构识别句法范文型活用前缀的DFA； (2)判断该语法是否是LR(0)语法，如果是，则制作LR(0)分析表。 如果不是的话，我来说明理由。 扩展语法，赋予各规则编号：0. S S 1. S (S) 2. S a，4.5.2 LR(0)分析法，结论： LR(0)分析器不需要正向输入符号，如果约g是LR(0)语法，则为SLR(1)语法，LR(1)语法，LALR(1) 4.5.3 SLR(1)分析法、1 LR(

7、0)项目集的冲突情况LR(0)语法难以满足。 (P85 )例4.16中的语法分析引起冲突的原因： LR(0)分析法中的归约项目的处理方法，在一个项目集中同时包含移动和归约项目的情况下，或者有多个归约项目的情况下，必定产生多重定义。 例4.16的竞争项目。 I1:EE EE T、I0:I2:ET TT*F、I9:EE T TT*F、4.5.3 SLR(1)分析法、2 SLR(1)语法SLR(1)或简单的LR(1)方法可以是与一个语法有矛盾的LR(1)方法。 分析、4.5.3 SLR(1)方法、3 SLR(1)方法假设一个LR(0)项集合I中有m个移动项和n个归约项：如果I=A11a11 FOLL

8、OW(B2)、FOLLOW(Bn )两者都交叉，则SLR(1)方法(2)在2) aFOLLOW(Bi )的情况下，以Bi ri签约。 A11a11 A22a22 Ammamm B1r1 B2r2 Bnrn，停止字符串，输入字符串标题字符，解析例4.16中的冲突项目集I1，I2，I9。 I1: E E E E T、I 23360 e TT * f、I 23360 e TT * f、FOLLOW(E)=$、follow结论：如果语法的SLR(1)分析表中不包含多重定义要素，则将该语法称为SLR(1)语法。 结构例4.15的SLR(1)分析表。、4.5.4 LR(1)分析法、1对发生原因SLR(1)

9、归约项目的处理，发生无效归约：即，FOLLOW集中的一部分终结符不属于规范句型解析方法：重新定义lr的4.5.4 LR(1)分析法、2 LR(1) a是终止符号，称为检索符号，作用于归约项目=时，仅在输入符号为a时成为合同。4.5.4 LR(1)分析法、3结构LR(1)项目集族(0)引入I=s s、$为初始项目。 (1)项目集I的闭包函数CLOSURE I的任何项目都属于CLOSURE(I )。 a、b、a属于关闭(I )，如果有B r、b首先(a )，则b、b也属于关闭(I )。 重复步骤直到项目集不再放大。 (2)变换函数GO与LR(0)变换函数的构造方法相同，检索子在变换函数中不变。例4

10、.18构造语法g的LR(1)项目集族。 建立g :0.s s1. s lr2. s r3. l * r4. l I5. r l、i=s、$、其他LR(1)项目集群。4.5.4 LR(1)分析法、4 LR(1)分析表的构造方法与LR(0)分析表的构造方法基本相同，只对归约项目进行修正：如果归约项目a、a是Ik，则对检索文字a放置ACTIONk，g 3360.s1. s (s )2. 2 4.5.4 LR(1)分析法，5结论如果一个语法的LR(1)分析表没有多重定义入口。 或者任意一个LR(1)项目集合中没有动作冲突，将其语法称为LR(1)语法。 LR(1)分析法引起状态数的激增，应用有限，导入L

11、ALR(1)法。 4.5.5 LALR(1)分析法，1特征LALR(1)分析法介于LR(1)和SLR(1)之间，采用与LR(1)相同的搜索子方法，状态数为SLR(1)和2基本思想为LR(1)集群中所有同心的项目例如4.20 0. S S 1. S (S) 2. S a利用LR(1)分析法构建其它项目集DFA :i03360s、$ S (S )、$ S a、$、I I 43360 s (s )、$、I 63360 sa、i53360S (S )和S a、I 73360 s (s )、i23360s(s )和S a、i:sa、$、I 43360 s (s )和$、I7: S(S )和I 73360 s (s ) LL(1)语法的判定预测分析表。 2从下到上的语法分析方法：素句和最左素句运算符优先分析表。 4种LR语法的关系设置活前缀和项目分类