对文法D→TL T→i T→f L→L,x L→x 构造LR项目集族(识别活前缀的自动机)
时间: 2024-06-08 13:12:15 浏览: 71
首先,我们列出文法的所有产生式的项目:
D' → .D
D → .TL
T → .i
T → .f
L → .L,x
L → .x
然后,我们按照LR算法的步骤,构造项目集:
I0:
D' → .D
D → .TL
T → .i
T → .f
L → .L,x
L → .x
I1:
D' → D.
L → L.,x
I2:
D → T.L
T → .i
T → .f
L → .L,x
L → .x
I3:
L → x.
L → L.,x
I4:
T → i.
I5:
T → f.
现在我们需要构造自动机,其中每个状态都对应于一个项目集。我们定义转移函数goto(I, X)来计算从项目集I通过X符号转移到的新的项目集。我们还定义action(I, a)和goto(I, A)函数用于填写分析表。
状态0的自动机如下所示:
```
+--------+ i +--------+
| |------------->| 4 |
| 0 | +--------+
| |
+--------+ f +--------+
| |------------->| 5 |
| D' | +--------+
| |
+--------+
| | T | |
| D |------------->| 2 |
| | | |
+--------+
| | L | |
| T |------------->| 2 |
| | | |
+--------+
| | x | |
| L |------------->| 3 |
| | | |
+--------+ , +--------+
|
|
v
+--------+
| |
| L |
| |
+--------+
```
状态1的自动机如下所示:
```
+--------+ x +--------+
| |------------->| 3 |
| 1 | +--------+
| |
+--------+ , +--------+
|
|
v
+--------+
| |
| L |
| |
+--------+
```
状态2的自动机如下所示:
```
+--------+ i +--------+
| |------------->| 4 |
| 2 | +--------+
| |
+--------+ f +--------+
| |------------->| 5 |
| T | +--------+
| |
+--------+
| | x | |
| L |------------->| 3 |
| | | |
+--------+ , +--------+
|
|
v
+--------+
| |
| L |
| |
+--------+
```
状态3的自动机如下所示:
```
+--------+ x +--------+
| |------------->| 3 |
| 3 | +--------+
| |
+--------+ , +--------+
|
|
v
+--------+
| |
| L |
| |
+--------+
```
状态4的自动机如下所示:
```
+--------+ $ +--------+
| |------------->| accept |
| 4 | +--------+
| |
+--------+
```
状态5的自动机如下所示:
```
+--------+ $ +--------+
| |------------->| accept |
| 5 | +--------+
| |
+--------+
```
最后,我们可以填写LR分析表:
| | i | f | x | , | T | L | D |
|---|---|---|---|---|---|---|---|
| 0 | s4| s5| | | 2 | 2 | 1 |
| 1 | | | | | | | |
| 2 | s4| s5| | | 6 | 2 | |
| 3 | | | | r2| | | |
| 4 | | | | | | | |
| 5 | | | | | | | |
| 6 | | | s3| s7| | | |
| 7 | | | | r4| | | |
其中,s表示移进操作,r表示归约操作,数字表示要转移到的状态或要归约的产生式的编号。例如,(0, i) = s4 表示在状态0读取输入符号i时,应该将其移进状态4。(2, T) = 6 表示在状态2读取输入符号T时,应该转移到状态6。(3, ,) = r2 表示在状态3读取输入符号,时,应该使用产生式L → x进行归约。
阅读全文