第4章语法分析详解.ppt

对活前缀有效的LR(1)项目 定义 LR(1)项目[A????，a]对活前缀 ?=??有效，iff 存在规范推导 S ?? ?Ay ? ???y y?VT* 且满足条件： (1)当y≠?时，a∈FIRST(y)： (2)当y=?时，a=#. 例如，对于上例中文法，有 S ?CbBA?CbBab?CbDbab A ? ? ? y 可知[B→D·b，a] 对前缀?=?? =CbD 有效 S??CbDbab?Cba bab A ? ? ?=? y 可知[D→a·，b] 对前缀?=?? =Cba 有效 求LR(1)项目集闭包算法 类似于LR(0)分析，识别文法全部活前缀的DFA的状态是由LR(1)项目集表示的.每个项目集由若干对相应的活前缀有效的LR(1)项目组成. 对每个LR(1)项目集I，相应的闭包CLOSURE(I)的定义为 I?CLOSURE(I)： 设项目[A?? ?B? ， a] ?CLOSURE(I)，并设它对活前缀 ?=?? 有效，则对所有形如B??的产生式，及每个b?FIRST(?a)，项目[B??? ， b]也对?有效(证明见后)，即将[B??? ， b] =CLOSURE(I)： 重复(2)，直到CLOSURE(I)不再增大. 　　其优先函数的构造过程为： 　　首先：把所有f（a），g（a）的 值置为1然后对算符优先关系矩阵逐行扫描，按前述算法规则的b）～e）修改函数f（a），g（a）的值，这是个迭代过程，一直进行到优先函数的值再无变化为止。 优先函数 g 同第2次迭代结果 f 3 1 1 6 6 6 4 2 g 1 7 1 7 5 5 3 f 2 1 1 5 5 5 3 2 g 1 6 1 6 4 4 2 f 1 1 1 1 1 1 1 1 g 1 1 1 1 1 1 1 f 0（初值） # ） （ i ↑ * + 　 　迭代次数 表达式文法优先函数计算过程 　 + * ↑ i （ ） # f 3 5 5 7 1 7 1 g 2 4 6 6 6 1 1 优先函数 　　对优先函数每个元素的值都增加同一个常数，优先关系不变。因而，对同一个文法的优先关系矩阵对应的优先函数不唯一。 　　然而也有一些优先关系矩阵中 的优先关系是唯一的，却不存 在优先函数f，g的对应关系。 　 a b a ? ? b ? ? 　　由于若存在优先函数f，g，则必定满足下列条件， 　　由矩阵的第一行应有f（a）=g（a），　　　f（a）g（b）。 　　由矩阵的第二行应有f（b）=g（a），　　　f（b）=g（b）。 　　这样导致有f（a）=g（a）=f（b）=g（b）。 　　与f（a）g（b）矛盾，因而优先函数不存在。 4.2.4 LR分析法 迄今为止我们所学的分析方法对文法都有一定的要求，即有局限性： 1965年D.Knuth提出了分析效率极高的LR(k)分析技术： LR分析： 自左至右扫描的自底向上的分析： 在分析的每一步，只须根据分析栈中的已移进的和已归约出的符号，并至多向前扫描k个字符就能确定应采取什么分析动作(移进、归约、接受、报错)： LR分析对文法要求很少，效率极高，且能及时发现错误，是目前最广泛使用的方法：一般用前后文无关文法描述的语言均可用LR分析法 LR分析综述 计算机理论研究已证明了如下结论： LR(k)文法是无二义性文法： LR(k)文法与LR(1)文法等价. 由于常见的程序设计语言均能由LR(1)文法产生，因此我们只讨论k=0，1两种情况： 本节中，我们将先介绍LR分析器的逻辑结构及工作原理，再分别介绍几种LR分析器(即LR(0)，SLR(1)，LR(1)和LALR(1))的构造： LR(0)简单，能力低： SLR(1)能力强于LR(0)： LR(1)能力强，但分析表大： LALR(1)能力介于SLR(1)与LR(1)之间，表大小与SLR(1)相同，是最常用的分析方法 LR分析器的逻辑结构及工作原理 分析器自左至右地扫描输入串的各符号，并根据当前分析栈的内容及正扫描的符号按分析表的指示完成相应的动作。 分析栈记录了已分析的内容及当前的状态： 开始时，栈内放入#及开始状态S0，随着分析的深入，栈内容总是刻划了当前的状态，及分析的“历史”。 总控程序 分析表 分 析 栈 a1 a2 … ai …an# Sm Xm … S1 X1 S0 # 分析栈的内容 LR分析表 是LR分析器的核心，它由分析动作(ACTION)表和状态转移(GOTO)表两个子表组成： ACTION[Sm，ai]指明当栈顶为Sm，输入符为ai时应完成的分析动作： GOTO[Sm，Xi]指明当分析栈移进一个输入符号或按某产生