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

Question

我读了几篇关于创建LR(1(项集的论文，但没有一篇与左递归语法有关，比如那些用于解析表达式的语法。如果我有以下语法，

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

如何创建LR(1(项目集？

Answer 1

左递归对于LR(1(解析器来说并不是一个固有的问题，而且无论语法是否有左递归，确定配置集和lookahead的规则都是相同的。

在您的情况下，我们首先用新的开始符号来扩充语法

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之前有一个点的作品。根据目前的情况，你知道如何做到这一点吗？