《编译原理_06LR法解读》由会员分享，可在线阅读，更多相关《编译原理_06LR法解读（21页珍藏版）》请在金锄头文库上搜索。
1、第第7 7章章 LRLR分析法分析法 1 7.1 LR分析法概述 7.2 LR(0)分析法 主要内容 2 课题：LR分析法基本思想和LR(0)分析法 目的要求： 1.理解LR分析法的基本思想； 2.了解LR(0)分析法； 教学重点： 1.LR分析法的基本思想； 2.前缀、活前缀与可归前缀等概念 教学难点 ： LR(0)分析法 教学课时：2 教学方法：多媒体教学 教学内容和步骤 ：（如下） 第 十四 讲 3 我们已经学过自顶向下和自底向上两种分 析方法。 自底向上分析法是一种移进-归约过程，其 关键问题是在分析过程中如何确定句柄。 LR分析方法也是通过求句柄并逐步归约来 进行语法分析的。是规范归
2、约。 在算符优先分析法中，句柄是通过运算符 的优先关系而求得，LR方法中句柄是通过求 可归前缀而求得。 7.1 LR分析方法概述 4 所谓LR(K)分析就是根据当前分析栈中的符号 串和向右顺序查看输入串的K(K0)个符号就可 以唯一确定分析器的动作的一种方法。 LR分析法的特点：对文法限制较低、速度快 、准确，并能及时指出出错的位置。 LR(0)分析法对文法的限制较多，因此实用性 很差，但是它是构造其他LR分析器的基础。 5 1. 一个LR分析器由3个部分组成： (1) 总控程序，也可以称为驱动程序。对所有的LR 分析器总控程序都是相同的。 (2) 分析表或分析函数，分析表又可分为动作表（ A
3、CTION）和状态转换表（GOTO）两个部分。 (3) 分析栈，包括文法符号栈和相应的状态栈。 分析器的动作就是由栈顶状态和当前输入符号所 决定。 LR分析器 6 2. 分析器的动作决定于栈顶状态和当前输入符号，有 四种可能： (1) 移进：栈顶未出现句柄，当前输入符号进符号栈 ，状态转换，新的状态进状态栈； (2) 归约：栈顶出现句柄，按某个产生式进行归约。 归约后的文法符号进符号栈，同时根据状态转换表 ，新状态进状态栈。 (3) 接受(acc) ：符号栈只剩开始符且当前输入符号为 #，则分析成功。 (4) 出错(error) ：栈顶状态与当前输入符不匹配。 7 几个基本概念：前缀、活前缀与
4、可归前缀 设有符号串 ，文法G的某句型 ： 前缀： 是句型的头， 则称为句型前缀； 活前缀： 是句型前缀，且是规范句型。 可归前缀： 是文法G的一个活前缀，且的末端 恰好是规范句型的句柄的末端。 也可以说，活前缀就是指形成可归前缀之前包 括可归前缀在内的所有规范句型的前缀。 r 7.2 LR(0)分析法 8 形式定义如下： 对于文法GS，若 (最右推导) SA ， Vt* 如果符号串是串的头，则是的前缀，(或 者称是规范句型的前缀，注意:| |=|) ，又称是文法G的一个活前缀；若| |=|(即 含句柄)，则称是文法G的一个可归前缀。 下面我们来分析一个具体的例子： * 9 例1：文法GS ：
5、 S aAcBe A b A Ab B d 为产生式加序号变为： S aAcBe1 A b2 A Ab3 B d4 对于输入串abbcde句子的最右推导如下： SaAcBe1 aAcd4e1 aAb3cd4e1 ab2b3cd4e1 10 对它的逆过程最左归约(规范归约)为： ab2b3cd4e1 aAb3cd4e1 aAcd4e1 aAcBe1 S 我们把每次采取归约动作前的符号串部 分称为可归前缀。 11 活前缀为一个或若干规范句型的前缀。在规 范归约过程中的任何时刻只要已分析过的部分( 即在符号栈中的符号串)均为规范句型的活前缀 ，则表明已分析过的部分是正确的。 例如：有下面规范句型的前
6、缀： ，a，ab ，a，aA，aAb ，a，aA，aAc，aAcd ，a，aA，aAc，aAcB，aAcBe 不难发现a， aA，aAc是 多个规范句 型前缀和活 前缀。 12 LR(0)项目集规范族的构造 1. 基本概念 (1) 项目：在文法G中每个产生式的右部适当位 置添加一个圆点构成项目。 例如：产生式SaAcBe对应有6个项目。 0 SaAcBe 1 SaAcBe 2 SaAcBe 3 SaAcBe 4 SaAcBe 5 SaAcBe 注意： 产生式 A 仅有一个项目A 13 项目的含义与圆点位置有关：左部表示用该产 生式归约时已识别部分，右部为待识别部分。 当右部为 时，表示句柄形成
7、，进行归约。 每个项目相当于NFA中的一个状态 （由此亦可以构造出文法相应的NFA，进而求 出DFA，只是仍然十分复杂。见教材P131页例 题） (2)项目集：是指构成识别一个文法活前缀的 DFA的每个状态中所含项目的集合。 (3) 项目集规范族：是指上述DFA中项目集的全 体。 14 (4)关于状态I的闭包CLOSURE(I)：(其中I为拓 广文法G的一个项目) CLOSURE(I)的计算方法如下： I CLOSURE(I) 若A BCLOSURE(I), 且BVN则 B CLOSURE(I)，为符号串。 重复直到CLOSURE(I)不再增加为止。 例.文法GS： S A AaAb A c
8、设开始状态为S0，则 S0=S A CLOSURE(S0)=S A , A aAb,A c 15 (5) 项目类型： 项目类型有归约项目、移进项目、待约项目 和接受项目。 归约项目：圆点后符号为 的项目称为归约 项目。 如：A 此时已对分析结束，栈顶句柄形 成，从而可按相应的产生式进行归约。 移进项目：符号为终结符的项目称为移进项 目。如A X，XVT 此时X进符号栈，相应状态进状态栈。 待约项目：圆点后符号为非终结符的项目， 称为待约项目。此时期待着向X进行归约。 16 接受项目：当归约项目为S S 时则表明 已分析成功，即输入串为该文法的句子，相应 状态为接受状态。 注意：一个项目集中可能
9、包含上述多种项目， 但是不允许下述情况之一存在，否则不相容。 移进与归约项目并存移进-归约冲突 归约与归约项目并存归约-归约冲突 (6) LR(0)文法 若一个文法的LR(0)项目集规范族中不存在上 述两种冲突，则称该文法为LR(0)文法。 17 2. LR(0)分析表的构造 构造原则： 设有文法GS，则LR(0)分析表的构造规则为 ： 对于A XIk，且GO (Ik,X)= Ij 若X Vt，则置actionIk,X= Ij 若X Vn，则置gotoIk,X=j 例如：若有项目集A，B此时 栈顶为，根据项目集无法确定是移进还是归约 。项目集是不相容的。 18 对于A Ik ，若A是文法的第j
10、个产 生式，则对所有的XVt和X= #，均置 actionIk,x=rj 若S S Ik ，则置actionIk,#=acc 其他均置出错。 19 LR分析方法是通过求句柄并逐步归约来进行语法 分析的， 句柄是通过求可归前缀而求得，是规范归 约。 LR分析法的特点：对文法限制较低、速度快、准 确，并能及时指出出错的位置。 LR(0)分析法对文法的限制较多，因此实用性很差 ，但是它是构造其他LR分析器的基础。 LR分析器由总控程序、分析表和分析栈三个部分 组成。 若一个文法的LR(0)项目集规范族中不存在移进-归 约冲突和归约-归约冲突，则称该文法为LR(0)文法。 基本概念：前缀、活前缀与可归前缀。 教学总结 20 1.与优先分析法相比较，LR分析法有哪些特点和优点 2.基本概念：前缀、活前缀、可归前缀、 LR(0) 文法 作 业 21
