LR解析表的实现是什么?

LR Parsing Tables 是一个二维数组,其中每个条目代表一个 Action 或 goto 条目。具有大量产生式的编程语言语法具有大量状态或项,即,I 0,I 1 ... ... I n

因此,由于更多的状态,将填充更多的 Actions 和 goto 条目,这需要大量内存。因此,一个二维数组不足以存储这么多的动作条目,因为每个条目至少需要 8 位进行编码。

因此,我们必须使用比二维数组更有效的编码来进行编码、Action 和 goto 字段。

例如,考虑语法。

E → E + T

E → T

T → T * F

T → (F)

F → (E)

F → 身份证

它的解析表将是

编码操作字段

动作表的某些行是相同的,即它们具有相同的动作条目。因此,它可以通过将每个状态的指针生成到一维数组中来存储多个空间。

要访问数组中的条目,我们可以为每个终端分配一个从 0 到 n-1 的序列号。该整数可用作访问特定终端的偏移量。可以通过创建一个配对列表来管理空间有效性

在给定的 Parsing Table 中,状态 0、4、6、7 具有相同的 Action 条目。它们可以表示为

象征行动
Ids5
(s4
any错误

状态 1有列表。

象征行动
+s6
$接受
any错误

在状态 2中,如果它可以用 r2 替换错误条目。因此,r2 将出现在除 * 之外的所有条目上。

象征行动
*s7
anyr2

状态 3 - 它只有 r4 条目和错误条目。如果它也可以用 r4 替换错误条目,那么所有条目都将由 r4 表示。

象征行动
anyr4

状态 5、10、11可以类似地求解。

状态 8

象征行动
+s6
)s11
any错误

状态 9

象征行动
*s7
anyr1

编码转到字段

goto table 也可以由列表编码。列表由一对当前状态,下一个状态)组成

∴ 转到 [当前状态,A] = 下一个状态

F 列- F 列有 10 个状态 7,所有其他条目要么是 3,要么是错误。我们可以将错误替换为 3。

当前状态下一个状态
710
any3

T 列

当前状态下一个状态
69
any2

在E 列中,我们可以选择 1 或 8 作为默认值。

当前状态下一个状态
48
any1

因此,保留这些列表显然会节省一些空间,即,与之前所占用的空间相比,占用的空间几乎减少了 10% 这些列表占用所有内存量。但是列表表示比矩阵表示慢。

以上是 LR解析表的实现是什么? 的全部内容, 来源链接: utcz.com/z/363410.html

回到顶部