左递归语法的 LR(1) 项集

Question

我读过几篇关于创建 LR(1) 项集的论文，但没有一篇涉及左递归语法，例如用于解析表达式的语法。如果我有以下语法，

E -> E + T | T
T -> T * F | F
F -> (E) | NUMBER

我将如何创建 LR(1) 项目集？

Answer 1

对于 LR(1) 解析器来说，左递归本质上并不是一个问题，并且无论您的语法是否具有左递归，确定配置集和前瞻的规则都是相同的。

在您的例子中，我们首先使用新的开始符号增强语法：

S -> E
E -> E + T | T
T -> T * F | F
F -> (E) | NUMBER

我们的初始配置集对应于查看生产 S -> E，前瞻为 $。最初，这给我们带来了以下结果：

(1)
    S -> .E     [$]

我们现在需要扩展 E 的范围。这给了我们这些新项目：

(1)
    S -> .E     [$]
    E -> .E + T [$]
    E -> .T     [$]

现在，让我们看看项目 E ->; .E + T [$]。我们需要扩展 E 可能在这里，这样做的规则与非左递归情况相同：我们列出 E 的所有产生式点在前面，前瞻由产生式 E ->; 中 E 后面的内容给出。 .E + T [$]。在本例中，我们正在寻找具有 + 前瞻的 E，因为这就是产生式中的内容。这添加了这些项目：

(1)
    S -> .E     [$]
    E -> .E + T [$]
    E -> .T     [$]
    E -> .E + T [+]
    E -> .T     [+]

从这里开始，我们展开了 T 之前有一个点的所有情况，这给出了以下内容：

(1)
    S -> .E     [$]
    E -> .E + T [$]
    E -> .T     [$]
    E -> .E + T [+]
    E -> .T     [+]
    T -> .T * F [$]
    T -> .F     [$]
    T -> .T * F [+]
    T -> .F     [+]

我们现在必须展开 T在 T -> 的上下文中.T * F [$]，我们通过列出 T 的所有产生式来做到这一点，然后列出 T 后面跟在 T 中的内容 - > .T * F [$]（即*）。这给了我们以下结果：

(1)
    S -> .E     [$]
    E -> .E + T [$]
    E -> .T     [$]
    E -> .E + T [+]
    E -> .T     [+]
    T -> .T * F [$]
    T -> .F     [$]
    T -> .T * F [+]
    T -> .F     [+]
    T -> .T * F [*]
    T -> .F     [*]

从这里开始，我们将扩展 F 之前有一个点的产生式。根据目前的情况，你知道如何做到这一点吗？