LR(0)项目

爱被打了一巴掌 2022-02-02 02:17 262阅读 0赞

### 文章目录 ###

*  项目的概念
 *  增广文法
 *  文法中的项目
 *   *  后继项目
     *  LR自动机

# 项目的概念 #

右部某位置标有圆点的产生式称为相应文法的一个 ·**`LR(0)`项目（简称为项目）**。

例如：`$S \rightarrow{bBB}$`

1.  `$S \rightarrow{·bBB}$`为**移进项目**
2.  `$S \rightarrow{b·BB}$`、`$S \rightarrow{bB·B}$`为**待约项目**。
3.  `$S \rightarrow{bBB·}$`为**规约项目**

注：

1.  **项目描述了句柄识别的状态**。
2.  产生式`$A \rightarrow{\epsilon}$`只生成一个项目`$A\rightarrow{·}$`

# 增广文法 #

如果`G`是一个以`S`为开始符号的文法，则`G`的**增广文法**`$G^{'}$`就是在`G`上加上新开始符号`$S^{'}$`和产生式`$S^{'}\rightarrow{S}$`而得到的文法。

![image][]

**引入这个新的开始产生式的目的是是的文法开始符号仅出现在一个产生式的左边，从而是的分析器只有一个接受状态。**

# 文法中的项目 #

假设现在有一个文法，它包含5个产生式，如下：  
![image][image 1]

则每个文法的项目如下：  
![image][image 2]

注：

1.  **若是将这15个项目作为状态机的状态，那么状态数就太多了。**
2.  **凡是圆点后面存在非终结符的时候就存在等价项目**
3.  **可以把所有等价的项目组成一个项目集`(I)`，称为项目集闭包，每个项目集闭包对应着自动机的一个状态。**

## 后继项目 ##

*  **同属于一个产生式**的项目，但**圆点的位置只相差一个符号**，则称后者是前者的后继项目
 *  A→α· Xβ的后继项目是A→αX·β

## LR自动机 ##

![image][image 3]

[image]: http://note.youdao.com/yws/res/11066/36E5872CB9AF477BBD895FA6F14D8722
[image 1]: http://note.youdao.com/yws/res/11076/622DDEE208C1424591F6418E64E02344
[image 2]: http://note.youdao.com/yws/res/11080/282E5F076C45448B96EA1113A84DF799
[image 3]: https://note.youdao.com/src/92512ECA2E174EEE8506C054FF1A08A0