第五章 自底向上分析方法 LR(0)分析法 1 LR(K)分析法 第一个L表示：相应的语法分析将按自左至右的顺序扫描输入符号串；

Presentation on theme: "第五章 自底向上分析方法 LR(0)分析法 1 LR(K)分析法 第一个L表示：相应的语法分析将按自左至右的顺序扫描输入符号串；"— Presentation transcript:

1 第五章 自底向上分析方法 LR(0)分析法 1 LR(K)分析法 第一个L表示：相应的语法分析将按自左至右的顺序扫描输入符号串；
括号中的“k”：则表示在分析过程中需要向前展望k个输入符号才能决定是移入还是归约，并且归约是用哪个产生式。

2 唐纳德•克努特(Donald Ervin Knuth) (1938__)
——经典巨著《计算机程序设计的艺术》的年轻作者 洋洋数百万言的多卷本《计算机程序设计的艺术》(The Art of Computer Programming)堪称计算机科学理论与技术的经典巨著，有评论认为其作用与地位可与数学史上欧几里得的《几何学原理》相比。唐纳德•克努特因而荣获1974年度的图灵奖。 计算机科学技术中两个最基本的概念：“算法”(Algorithm)和“数据结构”(Data Structure)就是克努特于29岁时提出来的。 1973年他首创双向链表。 在编译器设计方面，著名的LR(k)文法也是克努特于1965年在对自左至右、自底向上的移进一归约分析进行了深刻剖析的基础上，经过高度概括和集中以后发明的。

3 1.2 LR(k)分析法优缺点 优点： 分析方法对文法的限制很少，因而大多数能用上下文无关文法描述的程序设计语言都可用LR(k)分析法进行有效的分析。 LR(k)分析方法适用范围较广、分析速度快，并且能准确及时地发现语法错误，因此，LR分析法是当前最一般的语法分析方法。 缺点： 对于实用语言文法分析器的构造量非常大，K越大构造越复杂。

4 1.3 主要LR分析法 四种不同LR分析方法： LR(0)分析法 种方法的局限性很大，但它是建立其它较一般的LR分析法的基础；
SLR(1)分析法 虽然有一些文法构造不出SLR(1)分析表，但是，这是一种比较容易实现又极有使用价值的方法； LR(1)分析法 这种分析法能力最强，能够适用一大类文法，但实现代价过高，或者说，分析表所占空间非常大。 LALR(1)分析法 这种分析方法的能力介于SLR(1)和LR(1)之间，是一种即实用又高效的分析方法。

5 •accbde a•ccbde ac•cbde aA•cbde aAc•bde aA•bde aAb•de aAbd•e aAbde•
例1 G[S]： SaAbB[1] Ac [2]| Ac[3] Be [4]| dB[5] 分析字符串accbde。 S a A b B •accbde a•ccbde ac•cbde aA•cbde aAc•bde aA•bde aAb•de aAbd•e aAbde• aAbdB• aAbB• S• A c d B c e 如果输入流是正确的： 当前符号栈内容和剩余输入流构成句型。 符号栈内容：不含句柄，或含句柄且句柄在最右端。

6 2 LR类分析方法的基本概念和术语 规范句型：用最右推导导出的句型。
规范活前缀：若某一规范句型的规范前缀不含句柄或含一个句柄并且具有形式=(是句柄)，则称规范前缀为规范活前缀(简称活前缀）。 归约规范活前缀：若活前缀是含句柄的活前缀，即有=，且是句柄，则称活前缀为归约规范活前缀（简称归约活前缀或可归活前缀）。 示例

7 定义续 活前缀的描述性定义：形成可归前缀之前，包括可归前缀在内所有规范句型的前缀都称为活前缀。它的右端不超过该句型句柄的末端。
活前缀 为一个或若干规范句型的前缀。 它是规范归约过程中的任何时刻已分析过的部分，即在分析栈（符号栈）中的符号串均为规范句型的活前缀，表明输入串的已被分析过的部分是该文法某规范句型的一个正确部分。

8 •accbde ε a•ccbde a ac•cbde ac aA•cbde aA aAc•bde aAc aA•bde aAb•de
S 例1 G[S]： SaAbB[1] Ac [2]| Ac[3] Be [4]| dB[5] 分析字符串accbde。 a A b B •accbde a•ccbde ac•cbde aA•cbde aAc•bde aA•bde aAb•de aAbd•e aAbde• aAbdB• aAbB• S• ε a ac aA aAc aAb aAbd aAbde aAbdB aAbB S A c d B 归约活前缀 c e 归约活前缀 归约活前缀 归约活前缀 归约活前缀

9 3 LR类分析方法的关键问题 如何判断分析栈内容是否为归约活前缀 能唯一的确定归约活前缀中的句柄 如果解决了这两个问题，语法分析就好办了。
出现在符号栈里，我们知道他是可归前缀了，然后还能确定句柄，就可以做了，把这两个问题想清楚实际上就好做了，剩下的就是细节的问题和实现效率的问题，都不是关键的，最关键的就是解决这两个问题。按照定义，可以给一些原则判断可归前缀。

10 4 归约活前缀的求取 派生定理 开始符产生式的右部是归约活前缀。 如果A是归约活前缀，且A→是产生式，则也是归约活前缀。
任何归约活前缀，都可按上述方式被派生。 设文法开始符的产生式是： S →1|2|…|n 则文法G的可归活前缀集合为：RPSG={1,…,n}{|ARPSG,A→P}

11 可归活前缀： aAcBe A → b [2] ab A → Ab[3] aAb B → d[4] aAcd 可归活前缀集：
例2：计算下列文法的可归前缀集。 G[S]: S → aAcBe [1] A → b [2] A → Ab [3] B → d [4] 设文法开始符的产生式是： S →1|2|…|n 则文法G的可归活前缀集合为：RPSG={1,…,n}{|ARPSG,A→P} 可归活前缀： 开始符产生式的右部 aAcBe A → b [2] ab A → Ab[3] aAb B → d[4] aAcd 可归活前缀集： ｛aAcBe，ab,aAb,aAcd｝

12 识别活前缀自动机 ｛aAcBe，ab,aAb,aAcd｝ a 1 A c B e b b d G[S]: S → aAcBe [1]
符号栈 输入流 动作 abbbcde # a bbbcde # ab bbcde# aA bbcde# aAb bcde# aA bcde# aAb cde# aA cde# aAc de# aAcd e# aAcB e# aAcBe # S # 移入 移入 G[S]: S → aAcBe [1] A → b [2] A → Ab [3] B → d [4] 归约2 移入 归约3 移入 归约3 移入 移入 ｛aAcBe，ab,aAb,aAcd｝ 归约4 移入 归约1 成功 a 1 2 3 A c [1] 4 B 5 e [2] b [3] b [4] d

13 5 LR(0)分析法 基本概念 1.LR(0)项目： 若A→是产生式，则称A→为LR(0)项目(简称项目）
项目的含义：分析过程中到达某一个步骤的状态。圆点的左部表示分析过程的某个时刻欲用该产生式归约时已经识别过的部分，圆点右部表示期待的后缀部分。 例：S → aAc 对应四个LR(0)项目： S → aAc 表明我们希望接下来在输入中看的一个从aAc推导得到的串，这时符号栈为空。 S → aAc 表明刚在输入中看到了一个a，我们希望接下来看到一个能从Ac推导得到的串。这时符号栈中包含活前缀a。 S → aAc 表明刚在输入中看到了一个可以由aA推导得到的串。这时符号栈中包含活前缀aA。 S → aAc 表明我们已经看到了产生式体aAc，已经是时候把aAc归约为S了。符号栈中为归约活前缀，右部为句柄。

14 LR(0)分析法基本概念（续1） 2.项目集的闭包：假设IS是LR(0)项目集，则称下面CLOSURE(IS)为IS的闭包集：
= IS  {A→ | Y→ACLOSURE(IS)， A→是产生式 } 例：G[S]: S → aAc[1] A → dbb[2] A → b[3] 令项目集IS={S → aAc[1]} 则： CLOSURE(IS) ={S → aAc[1] ， A →  dbb[2]， A → b[3] }

15 LR(0)分析法基本概念（续1） 例：G[S]:
项目集的闭包CLOSURE(IS)：表示分析项目集IS中每一个项目Y→A圆点右部A可能推导出的子串的某个前缀可以从A推导得到，推导时可以应用的所有可能的A的产生式。 例：G[S]: S E E  E+T | T T  T*F | F F  (E) | id 令项目集IS={S →  E} CLOSURE(IS): S →  E E →  E+T E →  T T → T*F T → F F → (E) F → id

16 LR(0)分析法基本概念（续2） 3.项目集的投影：假设IS是LR(0)项目集，则称下面定义的IS(X) 为IS关于X的投影集：
IS(X) = {A→X |A→XIS, X(VTVN)} 项目集IS关于X的投影集的含义：项目集中每个项目A→X所描述的状态，处理完一个符号X后所对应的后继状态。 例：G[S]: S → aAc[1] A → dbb[2] A → b[3] 令项目集IS={S → aAc[1] ， A → dbb[2] ， A → b[3] } 则： IS(A)={S → aA  c[1]} IS(S)={ } IS(d)={A →dbb [3] } IS(b)={A →b [3] } IS(a)={ } IS(c)={ }

17 LR(0)分析法基本概念（续3） 4.项目集的转换函数（GO函数）：若IS是一个LR(0)项目集，X(VTVN)，函数GO(IS, X)定义为： GO(IS, X)=CLOSURE(IS(X))， 其中IS(X)为LR(0)项目集IS关于X的投影。 例：G[S]: S → aAc[1] A → dbb[2] A → b[3] 令项目集IS={S → aAc[1] } 则： GO(IS, a )= CLOSURE(IS(a)) = CLOSURE({S → aAc[1]}) = {S → aAc[1] ， A →  dbb[2]， A →  b[3] }

18 构造LR(0)活前缀状态机LRSM 为了使“成功”状态易于识别，通常LR文法要求文法的开始符唯一且不出现于产生式的右部，因此要增加一个新的产生式,称拓广产生式: ZS 其中:S是原文法的开始符，而Z则是新符号。

19 构造LR(0)活前缀状态机LRSM的算法 x x
Step1.构造初始状态IS0：IS0=CLOSURE({Z→S})，并给IS0标上NO。 Step2.从已构造的LRSM部分图选择被标为NO的任一状态IS，删除NO， 对每个符号XVTVN，做下面动作： 1) 令ISj = CLOSURE( IS(X)) 。 2) 若ISj非空： ①如果在LRSM部分图中已有ISj项目集， 则在IS和ISj之间画有向X边：IS ISj 。 ②如果在LRSM部分图中没有ISj项目集， 则将ISj作为LRSM的一个新的状态节点，并给ISj标上NO， 并在IS和ISj之间画有向X边： IS ISj 。 重复Step2 ，直至没有被标记为NO的状态结点为止。 x x

20 形如A→• 的项目称为归约型项目 形如A→• 的项目称为移入型项目

21 例2：计算下列文法的LR(0)状态机。 文法G[S]： SaAbB[1] Ac [2]| Ac[3] Be [4]| dB[5]

22 aAbd+ B 9 B ε aAbd+ 7 aAbB 8 a d a 1 aA B 3 A b aAb 5 c c aAc 4 ac e 2
文法G[S]： SaAbB[1] A c [2]| Ac[3] Be [4]| dB[5] B ε d S → aAbB[1] aAbd+ B dB[5] B  e [4] B  dB[5] 7 e a aAbB S → aAbB [1] 8 d a S → aAbB[1] A → c[2] A → Ac[3] 1 aA B S → aAbB[1] A → Ac[3] 3 A b aAb S → aAbB[1] B  e [4] B  dB[5] 5 c c aAc ac 4 A → A c [3] e 2 A → c  [2] aAbe , aAbd+e B e  [4] 6 G[S]的LRSM

23 例3：构造LR(0)状态机 S  E $ E  E + T E  T T  id T ( E )

24 T T 6 9 ( ( 5 id id E id ( E + 1 3 7 + $ ) T 2 4 8 T→( E) E→ E+T
S  E $ E  E + T E  T T  id T ( E ) T T 6 T→( E) E→ E+T E→ T T→ id T→ ( E ) S→ E $ E→ E+T E→ T T→ id T→ ( E ) 9 E→T  ( ( 5 T→id  id id E id ( E + 1 S→E $ E→E +T 3 E→E+  T T→ id T→ (E) 7 T→(E ) E→E +T + $ ) T 2 S→E $ 4 E→E+T  8 T→(E) 

25 LRSM给出了所有的可归活前缀 LRSM中的每个状态将对应一个项目集： （1）其中一部分是由先驱状态分出来 (称为基本项目)； （2）一部分则是由基本项目扩展出来的 (称为扩展项目或派生项目)。派生部 分项目的特点是其中的“”出现在产 生式右部的最左侧。

26 LRSM不能直接用于LR分析,因为它识别的是VTVN上的符号串，而语法识别的是VT组成的句子。但它提供了LR分析所需的信息。
移入/归约信息: [A→a]、[A→]; 移入/归约后的转向状态信息.