对文法D→TL T→i T→f L→L,x L→x 构造LR项目集族(识别活前缀的自动机)
时间: 2023-10-25 17:26:04 浏览: 69
首先,我们先将文法转化为标准形式:
```
D -> T L
T -> i | f
L -> L , x | x
```
然后,我们按照LR文法的构造方法,逐步构造出自动机的状态和转移:
1. 首先,我们构造出初始状态 $I_0$,即项目集 $I_0 = \{[D' -> \cdot D, \$]\}$。
2. 然后,我们扩展 $I_0$,得到 $I_1$,即项目集 $I_1 = \{[D' -> D \cdot, \$], [D -> \cdot T L, \$]\}$。这里,我们使用了文法的增广形式,并且将 $D'$ 视为文法的起始符号。
3. 接着,我们继续扩展 $I_1$,得到 $I_2$,即项目集 $I_2 = \{[D -> T \cdot L, \$], [T -> \cdot i, L], [T -> \cdot f, L], [L -> \cdot L , x, \$], [L -> \cdot x, \$]\}$。
4. 然后,我们继续扩展 $I_2$,得到 $I_3$,即项目集 $I_3 = \{[T -> i \cdot, L], [T -> f \cdot, L]\}$。注意到这里 $T$ 只有一个符号,因此不需要继续扩展。
5. 接着,我们扩展 $I_2$,得到 $I_4$,即项目集 $I_4 = \{[L -> x \cdot, \$], [L -> L \cdot , x, \$]\}$。注意到这里 $L$ 的两个产生式都需要继续扩展。
6. 然后,我们扩展 $I_4$,得到 $I_5$,即项目集 $I_5 = \{[L -> L , \cdot x, \$], [L -> \cdot L , x, \$], [L -> \cdot x, \$]\}$。注意到这里出现了新的产生式 $L -> L , \cdot x, \$$。
7. 最后,我们继续扩展 $I_5$,得到 $I_6$,即项目集 $I_6 = \{[L -> L , x \cdot, \$]\}$。注意到这里 $L$ 只有一个符号,因此不需要继续扩展。
这样,我们就得到了自动机的所有状态和转移。最终的结果如下所示:
```
I0:
[D' -> .D, $]
I1:
[D' -> D., $]
[D -> .TL, $]
I2:
[D -> T.L, $]
[T -> .i, L]
[T -> .f, L]
[L -> .L,x,$]
[L -> .x,$]
I3:
[T -> i., L]
[T -> f., L]
I4:
[L -> x., $]
[L -> L.,x,$]
I5:
[L -> L, .x, $]
[L -> .L,x,$]
[L -> .x,$]
I6:
[L -> L,x., $]
```
其中,状态的编号即为对应的项目集的编号。每个状态中的项目使用点号表示当前扫描位置,$D'$ 表示文法的起始符号,$\$$ 表示输入串的结束符号。
阅读全文