parsing - 左递归语法的 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 + T [$] 中 E 后面的内容给出。在本例中，我们正在寻找具有 + 前瞻的 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 * F [$] 的上下文中扩展 T，为此我们列出了T 后跟 T -> .T * F [$] 中 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 * F [*]
    T -> .F     [*]

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