第5章自下而上的语法案例.ppt

第5章 自下而上的语法分析 5.1 自下而上的语法分析概述 5.2 LR分析法的基本原理 5.3 项目集规范族的构造 5.4 有效项目（略） 5.5 LR(0)分析表的构造 5.6 SLR(1)分析表的构造 5.7 LR语法分析器的控制程序 5.8 二义文法在LR分析法中的应用 5.9 应用举例（略） 5.10 LR分析法在词法分析器自动构造中的应用（略） 5.2 LR分析法的基本原理 5.3项目集规范族的构造 5.5 LR(0)分析表的构造 5.6 SLR(1)分析表的构造㈠SLR(1)分析法的引出 5.7 LR语法分析器的控制程序 5.8 二义文法在LR分析法中的应用 ㈢构造法 SLR(1)分析表的构造是在LR(0)分析表基础上进行的，只要对LR(0)分析表的构造方法稍加修改，就可获得SLR(1)分析表的构造方法，修改部分如下所述： ⑴预备工作（增加④ ） ④计算非终结符的follow集。 ⑵构造法（①③④⑤同LR(0) 分析表构造法） ②若归约项目A→α.∈Ii，对于任何a∈follow(A)，置M[i][a]=rk（k是产生式A→α的编号，r表示归约）。 接上例，构造G的SLR(1)分析表。解： ⑴预备工作 ①文法拓广（同上） ②产生式编号（同上） ③构造状态转换函数GO(I,X)和项目集规范族（同上） ④计算非终结符的follow集 folow(S)={#}、folow(E)={#,+,)}、 folow(T)={#,+,),*}、folow(F)={#,+,),*} ⑵构造分析表 上述分析表中不含多重定义，所以分析表是SLR(1)分析表。使用SLR(1)分析表的语法分析器称为SLR(1)分析器。 0. S→E 1. E→E+T 2. E→T 3. T→T*F 4. T→F 5. F→(E) 6. F→i folow(T)=folow(F)={#,+,),*} ，folow(E)={#,+,)} ⑶SLR(1)分析法讨论 ①SLR(1)分析表和SLR(1)文法 根据上述方法构造的分析表若不含多重定义入口，则该表是SLR(1)分析表，相应文法是SLR(1)文法。 ②LR(0)文法一定是SLR(1)文法，反之未必成立。 ③SLR(1)分析法在理论上并不严格，但SLR(1)分析法很实用，又比较容易实现，能解决大部分语言的识别问题。 理由： 根据follow集的定义，a∈follow(A)仅仅表示在某些句型中终结符a紧跟在非终结符A的后面，并不是表示在所有包含A的句型中，终结符a都紧跟在非终结符A的后面。要真正严格地并且精确地向前看一个输入符号的话，那就要使用规范LR分析法，即LR(1)分析法。 ㈠数据结构 ①LR分析表 ②状态栈 在归约时，控制程序应按原路径折回，故在分析过程中需将所经历的状态记录下来，以便获得折回点。设置状态栈，用于记录分析过程中所经历的状态，即路径。 ③符号栈 用于记录路径的符号，它和状态栈等高。符号栈的设置是为了便于说明，实际语法分析器无符号栈。 ④产生式右部符号串长度 因每个状态仅识别一个符号，退回的状态数和构成句柄的字符数相等，故需存储产生式右部符号串长度。 ⑤产生式左部符号 归约后，根据左部符号进入下一状态。 * 从叶结点出发，步步向上归约。若能归约到根结点，说明输入串是文法的一个句子，否则输入串存在语法错误。 ㈠常用的自下而上语法分析方法 ①算符优先分析法（本书略） 宜于手工构造，特别适合于算术表达式的语法分析。但适用范围较小，实用意义不大。 ②LR分析法 适用范围广，宜于自动生成，目前大多数编译程序的语法分析器都采用LR分析法。 ㈡LR分析器组成 由控制程序和分析表组成。控制程序与文法无关，分析表随文法而异。 ㈢LR分析法的优点 适用范围大，对文法要求低，无需消除左递归，无需消除左因子。 ㈣LR分析法的缺点 实现代价高，LR分析表的规模要比同一文法的LL(1)分析表大得多。 ㈤LR分析法的分类 ①LR(0)分析法 简单、分析能力弱，是LR分析法的基础。 ②SLR(1)分析法 或称简单LR分析法。分析能力中，实现代价同LR(0)，比较容易实现，具有实用价值。 ③LR(1)分析法（本书略） 或称规范LR分析法，分析能力强，实现代价高，或者说分析表的规模非常大。 ④LALR(1)分析法（本书略） 或称向前LR分析法。分析能力介于SLR(1)和LR(1)之间，实现代价同LR(0)，有实用价值，但构造方法较复杂。 a A b a A a A c a A c d a A a b a a A c B a A c