对文法D→TL T→i T→f L→L,x L→x 构造LR项目集族(识别活前缀的自动机)
时间: 2023-10-25 11:06:55 浏览: 46
首先,我们需要将产生式转换为扩展文法:
```
D' -> D
D -> TL
T -> i
T -> f
L -> L,x
L -> x
```
然后,我们需要构造LR(0)项目集族。初始状态为闭包:
```
I0:
D' -> .D
D -> .TL
T -> .i
T -> .f
L -> .L,x
L -> .x
```
对于每个项目集,我们需要找到它的所有后继状态。后继状态可以通过将项目集中的每个项目的点向右移动一位来获得。如果点已经在产生式的末尾,则不需要移动。
对于每个后继状态,我们需要计算其闭包。闭包是从后继状态中的每个项目的点开始,添加能够推导出的所有项目的集合,以及它们的直接跟随符号。
重复这个过程,直到没有新的状态可以被添加为止。下面是完整的LR(0)项目集族:
```
I0:
D' -> .D
D -> .TL
T -> .i
T -> .f
L -> .L,x
L -> .x
I1:
D' -> D.
T -> .i
T -> .f
L -> .L,x
L -> .x
I2:
D -> T.L
L -> .L,x
L -> .x
I3:
T -> f.
I4:
L -> x.
I5:
L -> L.,x
L -> .L,x
L -> .x
I6:
D' -> D.
T -> .f
L -> .L,x
L -> .x
I7:
D -> TL.
I8:
L -> L,x.
I9:
D -> T.L
T -> .i
T -> .f
L -> .L,x
L -> .x
I10:
L -> L,x.
I11:
D -> TL.
I12:
L -> L,x.
I13:
D -> TL.
I14:
L -> L,x.
I15:
D -> TL.
```
其中,每个项目集中的每个项目都表示为 `A -> α . β` 的形式,其中 `A` 是一个非终结符,`α` 和 `β` 是符号串。点 `.` 表示当前解析位置。
在这个项目集族中,我们可以看到有些状态包含了相同的项目,但它们有不同的跟随符号,因此是不同的状态。例如,状态 I6 和状态 I1 包含相同的项目 `D -> .TL`,但状态 I6 的跟随符号是 `f`,状态 I1 的跟随符号是 `$`(输入的结束符号)。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)