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

Question

我阅读了几篇关于创建 LR(1) 项集的论文，但其中 none 与左递归文法有关，例如用于解析表达式的文法。如果我有以下语法，

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 可能在这里的内容，这样做的规则与 non-left-recursive 的情况相同：我们列出 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 [$] 的上下文中扩展 Ts，我们通过列出 T 的所有产生式，然后列出 [=25= 的内容来实现]后面跟着in 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 之前有一个点的产品。根据目前的情况，您知道如何做到这一点吗？

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

LR(1) item sets for left recursive grammar

parsing

lr1

lr