parsing - 为什么递归体面的解析器无法解析 aaaaaa EX(4.4.5) Ullman ravisethi

Question

语法 S -> a S a | aa 生成所有偶数长度的 a 字符串。我们可以为这个语法设计一个带有回溯的递归下降解析器。如果我们选择先通过产生式 S -> aa 展开，那么我们将只识别字符串 aa。因此，任何合理的递归下降解析器都会首先尝试 S -> aSa。

证明这个递归下降解析器可以识别输入 aa、aaaa 和 aaaaaaaa，但不能识别 aaaaaa。

Answer 1

我将从其他答案中解释一下自己。

它实际上是“单例匹配策略”的一个属性，通常在带有回溯的递归下降解析器的幼稚实现中。

引用Adrian Johnstone 博士的回答：

这里的诀窍是要意识到许多回溯解析器使用我们所说的单例匹配策略，其中只要规则的解析函数找到匹配项，它就会返回。通常，解析函数需要返回一组假定匹配。只需尝试完成它，您就会发现单格顿匹配解析器错过了一些可能的推导。

此外，此答案中可用的图像将帮助您可视化您举例说明的情况。

Answer 2

解析器将首先尝试调用match(a);S();match(a);，而不是match(a);match(a);如问题中所述。请注意，当您尝试S()在 block 内递归调用时match(a);S();match(a);，您只调用match(a)了一次，最后的“a”符号不会被消耗。