一个简单的CFG声称没有等效的PEG，似乎无论如何都有

Question

In"Packrat解析：一种具有回溯的实用线性时间算法"；在第30页，作者指出上下文无关语法(CFG(：

S -> a S a | a S b | b S a | b S b | a

似乎没有相应的解析表达式语法(PEG(。

上述CFG相当于：

S -> (a | b) S (a | b) | a

并且可以概括为"；a和b的奇数，中间有一个"a"；。然而，将其翻译成PEG:

S <- (a / b) S (a / b) / a

似乎工作得很好，并且为相同的语言编写代码。

您可以使用peg.js(将语法输入为S = ('a' / 'b') S ('a' / 'b') / 'a'(在网上自己尝试一下。

是作者错了还是我误解了什么？

Answer 1

您只是测试不够。尝试由奇数个as组成的输入。所有输入都与语法匹配，但PEG只接受长度为2^k−1的输入，用于某个整数k。