LR(0)分析表的构造

男娘i 2022-01-27 09:15 535阅读 0赞

### 文章目录 ###

*  文法规范句型的活前缀
 *  LR(0)项目
 *  构造识别文法所有规范举行活前缀DFA的方法
 *   *  定义闭包函数（CLOSURE）
     *  定义状态转移函数（GO）
     *  构造识别文法规范语句活前缀DFA的方法
     *  LR(0)分析表的构造

# 文法规范句型的活前缀 #

*  字符串的前缀是指字符串的任意首部，例如字符串"abc"的前缀有 ϵ \\epsilon ϵ、`a`、`ab`、`abc`。
 *  **规范语句活前缀是指规范语句的前缀**，这种前缀不包括句柄右边的任何符号

**在LR分析工作过程中的任何时刻，栈中的文法符号应是某一规范句型的活前缀**。这是因为一旦句型句柄在栈的顶部形成，就会立即被规约，因此只要输入串已扫描过得部分保持可规约成一个活前缀，那就意味着所扫描过的部分是正确的。这样一来，**我们对句柄的识别就变成对规范句型活前缀的识别**。

# LR(0)项目 #

活前缀与句柄之间的关系存在三种情况：

1.  活前缀中已经含有句柄的全部符号，表明此时某一规则 A → α A\\rightarrow\{\\alpha\} A→α的右部符号串 α \\alpha α已经出现在栈顶，其相应的分析动作使用此规则进行规约
2.  活前缀中只含有句柄的一部分符号，此时意味着形如 A → α 1 α 2 A\\rightarrow\{\\alpha\_1\\alpha\_2\} A→α1α2规则的右部子串 α 1 ! \\alpha\_1! α1!已出现在栈顶，正期待着从剩余的输入串中进行规约得到 α 2 \\alpha\_2 α2
3.  活前缀中全然不含有句柄的任何符号，此时意味着期望从剩余输入串中能看到由某规则 A → α A\\rightarrow\{\\alpha\} A→α的右部 α \\alpha α所推出的符号串

**为了刻画在分析过程中，文法的一个规则右部符号串已有多大一部分被识别，我们可在文法中每个规则右部适当位置加一个圆点来表示**。针对上述3中情况，标有圆点的规则分别为：

A → α ⋅ A \\rightarrow\{\\alpha·\} A→α⋅  
 A → α 1 ⋅ α 2 A \\rightarrow\{\\alpha\_1·\\alpha\_2\} A→α1⋅α2  
 A → ⋅ α A \\rightarrow\{·\\alpha\} A→⋅α

**文法G中右部标有圆点的规则称为`G`的一个LR(0)项目**

注：规则 A → ϵ A\\rightarrow\{\\epsilon\} A→ϵ仅有LR(0)项目 A → ⋅ A\\rightarrow\{·\} A→⋅

不同的LR(0)项目反映了在分析过程中栈顶的不同情况，因此，可以根据圆点后是终结符还是非终结符，将一个文法的全部LR(0)项目进行分类：

1.  规约项目：形如 A → α ⋅ A \\rightarrow\{\\alpha·\} A→α⋅，其中 α ∈ ( V N ∪ V T ) ∗ \\alpha \\in (V\_N \\cup V\_T)^\* α∈(VN∪VT)∗，即圆点在最右端的项目，它表示**一个规则的右部已经分析完成，句柄已形成**，应该按此规则进行规约。
2.  移进项目：形如 A → α ⋅ a β A \\rightarrow\{\\alpha·a\\beta\} A→α⋅aβ，其中 α ， β ∈ ( V N ∪ V T ) ∗ \\alpha，\\beta \\in (V\_N \\cup V\_T)^\* α，β∈(VN∪VT)∗， a ∈ V T a \\in V\_T a∈VT，即圆点后面为终结符的项目，它表示**期待从输入串中移入一个符号，以待形成句柄。**
3.  待约项目：形如 A → α ⋅ B β A \\rightarrow\{\\alpha·B\\beta\} A→α⋅Bβ，其中 α ， β ∈ ( V N ∪ V T ) ∗ \\alpha，\\beta \\in (V\_N \\cup V\_T)^\* α，β∈(VN∪VT)∗， B ∈ V N B \\in V\_N B∈VN，即圆点后面为非终结符的项目，它表示**期待从剩余的输入串中进行规约而得到`B`，然后才能继续分析`A`的右部**。
4.  接受项目：形如 S ′ → S ⋅ S^\{&\#x27;\}\\rightarrow\{S·\} S′→S⋅，其中 S ′ S^\{&\#x27;\} S′为文法的开始符号，即文法开始符号的规约项目。 S ′ S^\{&\#x27;\} S′为左部的规则仅有一个，它是规约项目的特殊情况，它表示整个句子已经分析完毕，可以接受。

# 构造识别文法所有规范举行活前缀DFA的方法 #

构成识别文法规范句型活前缀DFA的每一个状态是由若干个LR(0)项目所组成的集合，称为LR(0)项目集。

在这个项目集中，所有的LR(0)项目识别的活前缀**是相同的**。**可以利用闭包函数(CLOSURE)来求DFA一个状态的项目集。**

## 定义闭包函数（CLOSURE） ##

设`I`是拓广文法 G ′ G^\{&\#x27;\} G′的一个LR(0项目集，`I`的闭包`CLOSURE(I)`的定义如下：

1.  `I`中的任何一个项目都属于`CLOSURE(I)`
2.  若 A → α ⋅ B β A\\rightarrow\{\\alpha·B\\beta\} A→α⋅Bβ属于`CLOSURE(I)`，则每一形如 B → ⋅ r B\\rightarrow\{·r\} B→⋅r的项目也属于`CLOSURE(I)`。
3.  重复第二步直到`CLOSURE(I)`不再增大为止。

## 定义状态转移函数（GO） ##

设`I`是拓广文法 G ′ G^\{&\#x27;\} G′的任一项目集，`X`为一文法符号，定义状态转移函数`GO(I,X)`如下：

G O ( I , X ) = C L O S U R E ( J ) GO(I,X) = CLOSURE(J) GO(I,X)=CLOSURE(J)

J = \{ A → α X ⋅ β ∣ A → α ⋅ X β ∈ I \} J = \\\{A \\rightarrow\{\\alpha X·\\beta\} | A \\rightarrow\{\\alpha·X\\beta\} \\in I\\\} J=\{ A→αX⋅β∣A→α⋅Xβ∈I\}

## 构造识别文法规范语句活前缀DFA的方法 ##

1.  求 C L O S U R E ( \{ S ′ → ⋅ S \} ) CLOSURE(\\\{S^\{&\#x27;\} \\rightarrow\{·S\}\\\}) CLOSURE(\{ S′→⋅S\})，得到**初态项目集**
2.  对初态项目集或其他已构造的项目集，应用状态转移函数`GO(I,X)`求出新的项目集（后继状态）
3.  重复第二步制导不出现新的项目集为止

**构成识别一个文法活前缀的DFA的状态（项目集）的全体称为这个文法的LR(0)项目集规范族。**

## LR(0)分析表的构造 ##

用整数0、1、2、…、n分别表示状态 I 0 , I 1 , I 2 , . . . , I n I\_0,I\_1,I\_2,...,I\_n I0,I1,I2,...,In，令包含 S ′ → ⋅ S S^\{&\#x27;\} \\rightarrow\{·S\} S′→⋅S项目的集合 I k I\_k Ik的下标为分析器的初始状态。

1.  若项目 A → α ⋅ x β A \\rightarrow\{\\alpha·x\\beta\} A→α⋅xβ属于 I k I\_k Ik，且转换函数 G O ( I k , x ) = I j GO(I\_k,x) = I\_j GO(Ik,x)=Ij，当`x`为终结符时，则置 A C T I O N \[ k , x \] = S j ACTION\[k,x\] = S\_j ACTION\[k,x\]=Sj
2.  若项目 A → α ⋅ A \\rightarrow\{\\alpha·\} A→α⋅属于 I k I\_k Ik，\*\*则对任何终结符和结束符 （ 统 一 记 为 a ） 置 （统一记为a）置 （统一记为a）置ACTION\[k,a\]=r\_j ∗ ∗ （ 假 定 \*\*（假定 ∗∗（假定A \\rightarrow\{\\alpha\}$为文法的第j条规则）
3.  若 G O ( I k , A ) = I j GO(I\_k,A) = I\_j GO(Ik,A)=Ij，`A`为非终结符，则置`GOTO[k,A] = j`
4.  若项目 S ′ → S ⋅ S^\{&\#x27;\}\\rightarrow\{S·\} S′→S⋅属于 I k I\_k Ik，则置`ACTION[k,$] = acc`

根据这种方法构造的LR(0)分析表不含多重定义时，称这样的分析表为LR(0)分析表，能构造LR(0)分析表的文法称为LR(0)文法。（**同一个项目集中不存在移进项目和规约项目同时并存或多个规约项目同时并存**）