一个简单的 CFG 声称没有等效的 PEG，但它似乎有一个
A simple CFG claimed to have no equivalent PEG, that seems to have one anyway
在第 30 页的 "Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking" 中，作者声明上下文无关文法 (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
似乎工作正常并且为相同的语言编写代码。
You can try this out yourself online using peg.js（输入语法为S = ('a' / 'b') S ('a' / 'b') / 'a'）。
是作者错了还是我理解错了什么？
你只是测试不够。尝试由奇数个 a 组成的输入。所有匹配语法，但 PEG 只接受长度为 2k−1 的整数 k。
在第 30 页的 "Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking" 中，作者声明上下文无关文法 (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
似乎工作正常并且为相同的语言编写代码。
You can try this out yourself online using peg.js（输入语法为S = ('a' / 'b') S ('a' / 'b') / 'a'）。
是作者错了还是我理解错了什么？
你只是测试不够。尝试由奇数个 a 组成的输入。所有匹配语法，但 PEG 只接受长度为 2k−1 的整数 k。