LR解析表的实现是什么？

LR Parsing Tables 是一个二维数组，其中每个条目代表一个 Action 或 goto 条目。具有大量产生式的编程语言语法具有大量状态或项，即，I ₀，I ₁ ... ... 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 条目。它们可以表示为

状态 1有列表。

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

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

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

状态 8

状态 9

编码转到字段

goto table 也可以由列表编码。列表由一对_（当前状态，下一个状态）组成

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

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

T 列

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

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