4

我正在学习递归体面解析，并提出了一些我认为算法不起作用的场景。其中之一是，考虑到这个简单的语法：

S→E；
E → 标识 | 身份证+身份证

那么这个字符串id + id;在这个语法的语言中是有效的。但是，如果我们执行递归下降算法，它会从S到E然后到id，这是第一个匹配的终端。现在输入在+，我们又回到了S尝试匹配;然后失败的地方；但没有其他规则可供选择S。

我认为语法没有歧义，因为语言中只有 2 个字符串id;和id + id;，每个字符串都有一个唯一的解析树。这里的一般问题是非终结符具有相同前缀的产生式，并且可能会做出在递归中更深层次匹配的选择，但会为更浅层次创建无效输入。

我已经阅读了诸如左递归之类的递归下降的典型问题，但在任何地方都没有发现上述问题。那么这真的是一个问题还是我错过了什么？

我从书中找到了一个权威的答案，Parsing Techniques: A Practical Guide p.182-188它将上述方法归类为朴素递归体面，并强调了同样的问题。有两种解决方案始终适用于没有前瞻的一般情况（因为通常所需的前瞻长度随着前缀长度的增加而增加）：需要使用延续的穷举递归下降和广度优先递归下降。

4

3 回答 3

1

我对此很生疏，以至于我可能要发布垃圾了，但是这不能通过前瞻来解决吗？就像是：

func recogniseS
    expect(E)
    expect(semicolon)

fund recogniseE
    expect(id)

    if nextTokenIs(plus) then 
        expect(plus)
        expect(id)
    endif

或者，类似地，您可以重新表述为：

S → id [+ id];

即本质就是+可选的。因此，只要可以处理任何可选的情况，就可以处理这种情况。

于 2014-12-17T15:01:54.187 回答
1

就可以像这样考虑语法而言，这不是问题（第一个替代项为E'空）：

S → E ;
E → id E'
E' → | + id

对于E'，如果下一个标记是 ，我们预测第一个替代方案，如果下一个标记是 ，我们预测第二个替代;方案+。

于 2014-12-17T15:02:01.747 回答
1

从某种意义上说，如果您编写这样的 PEG 语法，它就行不通，这是一个问题。这是一个已知问题，有时被描述为 PEG 解析的问题，但我认为将编写无法处理的语法的人归咎于 PEG 是不公平的——其他解析形式也不能幸免。

如果它不是 PEG 语法而是普通的旧 CFG，那么应该没有问题，除非您使用的工具很傻或有问题。它应该能够将其转换为工作解析器，无论它是使用递归下降还是其他算法。如果它使用递归下降，它可能会使用前瞻，这将摆脱这种情况。

于 2014-12-17T15:07:35.237 回答