文法左因式分解

Question

我正在准备期中考试，所以我找到了一些问题，并试图解决它。

但是我的回答和给出的答案不一样。

问题：

Consider The Following Grammar, Which Generates Email Addresses:

Addr → Name@Name.id
Name → id | id.Name

This grammar, as written, is not LL(1).  Rewrite the grammar to eliminate all LL(1) conflicts.

根据我的理解，这个问题要求我们消除LL(1)冲突，它可以通过左因式分解来消除。

因此，我的答案是

Addr → Name@Name.id
Name → idName'
Name' → epsilon | .Name

然而，给出的答案是

Addr → Name@Name.id
Name → idName'
Name' → epsilon | .idName'

我的理解有错吗？如对此职位有任何建议，敬请见谅。

谢谢

Answer 1

据我所见，无论是你的解还是你给出的答案，都不是LL(1)。然而，给出的答案更准确地反映了左因子分解过程.您的解决方案留下了伪Name -> id Name'，它现在没有任何用途；将语法中的Name扩展到它的唯一产品可以消除不必要的派生步骤。(实际上，您可以以相同的方式消除Name的两个实例。)

但是如果问题是要你想出一个LL(1)语法，那么给出的答案是行不通的。

以一个简单的地址me@example.com为例，想象解析器一直运行到example之后，这是一个id。此时，解析器需要一个Name'，它要么是空的，要么是以.开头的东西。(在语法中，东西是'.' Name，在您引用的解决方案中，它是'.' id Name，但无论哪种方式，预期的下一个令牌都是.。)因此，解析器需要在空的生产和以.开始的生产之间作出决定。由于展望是.，解析器当然可以选择从.开始的产品。但是选择空置的产品呢？在这种情况下，下一个令牌将匹配Addr -> Name @ Name . id中的第二个.之后的任何内容，后者也是一个.。换句话说，查看.，解析器有两个明显有效的选项:空的生产或以.开头的生产。不管是用你的语法还是解决方案的语法，这都是真的。

最简单的解决方案(这不是很普遍)是重新排列Addr规则。Addr希望在@之后至少有两个id，这也可以通过以下方式实现：

Addr -> Name @ id . Name

你仍然需要离开因素Name来完成这个任务，但是现在Name的跟随集没有问题；它不能再被.所遵循，example之后的决定也是被迫的。