LR（0）分析-《编译原理与实践》

LR（0）分析是最简单的一种LR分析方法，最容易实现。LR（0）分析法具有很大的局限性，但却是进行其他LR分析的基础。LR（0）分析的每一步都是根据当前分析栈的栈顶状态，利用LR（0）分析表确定应该执行的分析动作，无须向前查看任何输入符号。

1.LR（0）项目和拓广文法

文法G的一个LR（0）项目，简称项目，是指在G的某个产生式右部的某个位置添加一个圆点。例如，产生式S→aAcBe对应有6个项目

(1)S→·aAcBe (4)S→aAc·Be

(2)S→a·AcBe(5) (5)S→aAcB·e

(3)S→aA·cBe (6)S→aAcBe·

产生式A→ε只对应一个项目A→·。

项目表示分析过程中已经分析过的部分。例如，上述项目（1）表示希望用S的右部进行归约，而希望输入符号为a；项目（2）表示已经与输入符号a匹配，需分析A推出的符号串；项目（3）表示A的右部得到匹配，已经归约为A，希望遇到输入符号c；最后，项目（6）表示S的右部全部分析完毕，句柄已经形成，可以进行归约。

在一个项目中紧跟在圆点后面的符号称为项目的后继符号，表示下一时刻将会遇到的符号。根据圆点所在的位置和后继符号的类型，可以将项目分为以下几种：

（1）归约项目

圆点在最右端的项目，即后继符号为空。如A→α·，表明一个产生式的右部已分析完，句柄已形成，可以归约。

（2）接受项目

文法的开始符号S的归约项目，如S→α·，表示最后一次归约，分析成功结束。

（3）移进项目

后继符号为终结符的项目，如A→α·aβ，其中a为终结符，分析动作是将a移进分析栈。

（4）待归约项目

后继符号为非终结符的项目，如A→α·Bβ，其中B为非终结符，表明所对应的项目等待将非终结符B所能推出的串归约为B，才能继续向后分析。

构造文法G的LR（0）项目时，为使接受状态易于识别，先要对原文法进行拓广。对于右部含有开始符号的文法，拓广文法可以确保在归约过程中，不会混淆是已归约到文法的最初开始符号，还是文法右部出现的开始符号。

假设S是文法G的开始符号，增加产生式S→S即可得到拓广文法G，S为G的开始符号。在拓广文法G中，开始符号S只在左部出现，有且仅有一个接受项目S→S·。此外，S→·S将作为识别的开始项目。

2.Closure（I）和GOTO（I，X）函数

若干个项目组成的集合称为项目集。设I是文法G的项目集，项目集I的闭包Closure（I）是从I出发由下面两条规则构造的项目集：

（1）初始时，将I的每个项目都加入Closure（I）中；

（2）如果A→α·Bβ在Closure（I）中，将所有不在Closure（I）中的形如B→·γ的项目加入Closure（I）中；重复执行规则（2），直至没有更多的项目可加入Closure（I）为止。

直观地说，Closure（I）中的项目A→α·Bβ表明在分析过程的某一时刻，希望看到从Bβ推出的符号串。那么，如果B→γ是一个产生式，实际上是希望看到从γ推出的符号串。因此，需要将B→·γ加入Closure（I）中。

例5.8 如下表达式拓广文法，设I={E→·E}，计算Closure（I）。

E→E

E→E+T|T

T→T*F|F

F→(E)|i

Closure(I)={E→·E,E→·E+T,E→·T,T→·T*F,T→·F,F→·(E),F→·i}

假设项目集I中的项目形如A→α·Xβ，项目集I的状态转换函数GOTO（I，X）定义为

GOTO(I,X)=Closure({A→αX·β})

注意，A→αX·β和A→α·Xβ源于同一个产生式，仅圆点相差一个位置。A→αX·β称为A→α·Xβ的后继项目。因此，GOTO（I，X）是由项目集I出发沿标记为X的有向边到达I的后继状态。

例5.9 令I={E→E·，E→E·+T}，求GOTO（I，+）。

GOTO（I，+）就是检查I中所有圆点之后紧跟着+的项目，即项目

E→E·+T

然后，将这个项目的圆点右移一位，得到项目

E→E+·T

最后，计算项目集{E→E+·T}的闭包，得到GOTO（I，+）={E→E+·T，T→·T*F，T→·F，F→·（E），F→·i}

3.LR（0）项目集规范族

对于文法G，通过Closure和GOTO函数可以构造一个识别G的所有规范句型的活前缀DFA。DFA的初始状态是由开始项目S→·S及其闭包构成的项目集。GOTO函数将依据不同的后继符号进行新项目集的构造，产生DFA新的状态和状态转移。新状态表明识别出同一个句型不同的活前缀，直至可归约前缀。

初始状态以及GOTO函数构造出的所有状态称为拓广文法G的LR（0）项目集规范族。构造文法G的LR（0）项目集规范族和识别规范句型活前缀的DFA的方法如算法5.4所示。这个DFA是构造文法G的LR（0）分析表的基础。

算法5.4 构造LR（0）项目集规范族和识别活前缀的DFA：

（1）置项目S→·S为初态集的核，计算Closure（{S→·S}）得到初态项目集，放入项目集规范族C中；(www.xing528.com)

（2）重复执行（3），直到C中项目集不再增加为止；

（3）for（C中的每个项目集I和每个文法符号X）

例5.10 构造识别下述拓广文法所有活前缀的DFA。

(0)S→E (4)A→d

(1)E→aA (5)B→cb

(2)E→bB (6)B→d

(3)A→c A

根据算法5.4构造的识别文法所有活前缀的DFA如图5-6所示。项目集规范族C中共有12个项目集，GOTO函数将其连接成一个DFA，其中I0为初态，I1为接受态。

图5-6　识别例5.10文法活前缀的DFA

4.有效项目

一个项目A→β1·β2称为对活前缀αβ1是有效的，当且仅当存在规范推导

其中，β1β2是规范句型的句柄，w是终结符号串。

若归约项目A→β·对活前缀αβ是有效的，则应将符号串β归约为A，即将活前缀αβ变成αA；若移进项目A→β1·β2对活前缀αβ1是有效的，则句柄尚未形成，下一步动作应该是移进。通常，同一个项目可能对好几个活前缀都是有效的。

文法G的一个活前缀γ的有效项目集，正是从识别活前缀的DFA开始状态出发，经由可以构成γ的路径所到达的项目集。直观上说，若I是对某个活前缀γ有效的项目集，则GOTO（I，X）就是对γX有效的项目集。

5.LR（0）分析表的构造

一个项目集中可能包含不同类型的项目，包括：

（1）移进和归约项目同时存在

项目集中含有形如A→α·aβ和B→γ·的产生式。由于，LR（0）分析不向前查看输入符号，所以不能确定应该将a移进分析栈，还是将γ归约为B。同时存在移进和归约项目的状态称为移进-归约冲突。

（2）归约和归约项目同时存在

项目集中含有形如A→α·和B→β·的产生式。这种情况下将无法确定归约为A还是规约为B。同时存在归约和归约项目的状态称为归约-归约冲突。

如果一个文法G的拓广文法G的活前缀识别自动机中的每个状态，即项目集中不存在移进-归约冲突和归约-归约冲突，则称G为LR（0）文法。

对于LR（0）文法，可直接从其项目集规范族C和识别活前缀的DFA中构造出LR（0）分析表，如算法5.5所示。

算法5.5 构造LR（0）分析表。

假定C={I0，I1，…，In}，为简便起见，直接用k表示项目集Ik对应的状态，令包含项目S→·S的状态为分析器的初态。

（1）若项目A→α·Xβ∈Ik且GOTO（Ik，X）=Ij，那么

①若X∈VT，则置ACTION[k，X]=Sj，即将（j，a）进栈；

②若X∈VN，则置GOTO[k，X]=j。

（2）若项目A→α·∈Ik，则对任何a∈VT（或结束符#），置ACTION[k，a]=rj（设A→α是文法G第j个产生式），即用A→α归约。

（3）若项目S→S·∈Ik，则置ACTION[k，#]=acc，即接受。

（4）分析表中凡不能用规则（1）～（3）填入的空白均置为“出错标志”。

由于LR（0）文法的项目集规范族的每个项目集不含冲突项目，因此，按上述方法构造的分析表的每个表项都是唯一的，即不含多重定义。如此构造的分析表称为LR（0）分析表，使用LR（0）分析表的分析器称作LR（0）分析器。

例5.11 构造例5.10文法的LR（0）分析表。

例5.10文法的项目集规范族和识别活前缀的DFA如图5-6所示。从图中可以看出，所有项目集均不含冲突项目，因此是LR（0）文法。根据算法5.5，得到如表5-12所示的LR（0）分析表。

表5-12　例5.10文法的LR（0）分析表

例5.12 构造表达式拓广文法的LR（0）分析表。

识别表达式文法活前缀的DFA如图5-7所示。注意，在这12个项目集里，I1、I2、I9中存在移进-归约冲突，因此，文法不是LR（0）文法，无法构造LR（0）分析表。

图5-7　识别例5.12文法表达式文法活前缀的DFA