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 -> .E + T [$]。在这种情况下，我们正在寻找一个E带有前瞻的，+因为这就是生产中的内容。这增加了这些项目：

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

从这里开始，我们扩展了 a 之前有一个点的所有情况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在 的上下文中扩展 s T -> .T * F [$]，我们通过列出所有的 产生式，T然后列出Tin 后面的内容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. 根据迄今为止的情况，您是否看到如何做到这一点？