第五章 自底向上分析方法 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 1.2 LR(k)分析法优缺点 优点： 分析方法对文法的限制很少，适用范围较广（可用于大多数上下文无关文法描述的程序语言）、分析速度快，并且能准确及时地发现语法错误，因此，LR分析法是当前最一般的语法分析方法。 缺点： 对于实用语言文法分析器的构造量非常大，K越大构造越复杂。

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

4 •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 如果输入流是正确的： 当前符号栈内容和剩余输入流构成句型。 符号栈内容：不含句柄，或含句柄且句柄在最右端。

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

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

7 •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 归约活前缀 LR类分析方法的关键问题 如何判断分析栈内容是否为归约活前缀 能唯一的确定归约活前缀中的句柄 归约活前缀 归约活前缀 归约活前缀

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

9 可归活前缀： aAcBe A → be [2] abe A → ab [3] aab B → d[4] aAcd 可归活前缀集：
例2：计算下列文法的可归前缀集。 G[S]: S → aAcBe [1] A → be [2] A → ab [3] B → d [4] 可归活前缀： 开始符S产生式的右部 aAcBe A → be [2] abe A → ab [3] aab B → d[4] aAcd 可归活前缀集： ｛aAcBe，abe,aab,aAcd｝

10 识别活前缀自动机 ｛aAcBe，abe,aab,aAcd｝ a 1 A c B e b e a b d G[S]:
符号栈 输入流 动作 aabcde # a abcde # aa bcde# aab cde# aA cde# aAc de# aAcd e# aAcB e# aAcBe # S # 移入 移入 G[S]: S → aAcBe [1] A → be [2] A → ab [3] B → d [4] 移入 归约3 移入 移入 归约4 移入 归约1 ｛aAcBe，abe,aab,aAcd｝ 成功 a 1 2 3 A c [1] 4 B 5 e [2] b 6 e [3] a 7 b [4] d

11 识别活前缀自动机的表示 ｛aAcBe，abe,aab,aAcd｝ a 1 A c B e b e a b d G[S]:
S → aAcBe [1] A → be [2] A → ab [3] B → d [4] ｛aAcBe，abe,aab,aAcd｝ S →aAcBe S →aAcBe S →aAcBe S →aAcBe S →aAcBe S →aAcBe A → be B → d A → ab a 1 2 3 A c [1] 4 B 5 e [2] b 6 e [3] a 7 b [4] d A → be A → be A → ab A → ab B → d

12 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了。符号栈中为归约活前缀，右部为句柄。

13 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] }

14 LR(0)分析法基本概念（续1） 例：G[S]:
项目集的闭包CLOSURE(IS)：表示项目集IS中每一个Y→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

15 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 → aAB[1] A → dbb[2] A → b[3] B → e[4] 令项目集IS={S → aAB[1] ， A → dbb[2] ， A → b[3] } 则： IS(A)={S → aA  B[1]} IS(S)={ } IS(d)={A →dbb [2] } IS(b)={A →b [3] } IS(a)={ } IS(c)={ }

16 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] } S → aAc Si=IS S → aAc A → dbb A → b Sj=Go(IS,a) a

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

18 构造LR(0)活前缀状态机LRSM的算法 A e Step1.构造初始状态IS0：IS0=CLOSURE({Z→S});
Step2.已构造的LRSM的任一状态IS， 对每个符号XVTVN，通过项目集转移函数GoTo(IS,X)求其后继状态ISj ： 重复Step2 ，直至所有状态处理完毕。 Sj=Go(Si,A) Si=IS A S → ABc A → e S → ABc B→ dbb B→ b e Sk=Go(Si,e) A → e

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

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

21 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

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

23 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) 

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

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

26 练习： 设有文法G[Z]如下: Z AB A aB | b B aB | b 构造该文法的LR(0)活前缀状态机