parsing - 这个 peg 语法有什么问题？

Question

以下语法（来自 RFC 2396）：

domainlabel = 'a' / ('a' ('a' / '-')* 'a')

无法解析：

aa

为什么？

Answer 1

因为 PEG 不是 BNF。使用/而不是通常的 BNF 交替运算符|（如 RFC 2396 中所见）是故意避免混淆的尝试（尽管它没有帮助旧标准，如 RFC 822 也使用/）。

在 PEG 中，/是“有序选择”运算符。与 BNF 交替算子不同，/它不是对称的。如果第一个替代方案成功，则接受它。只有当第一个替代方案失败时，PEG 才会回溯并尝试第二个替代方案。

因此，当'a' / ('a' ('a' / '-')* 'a')应用于 时aa，第一个替代方案成功吸收了第一个替代方案a，而第二个替代方案从未尝试过。解析随后无法匹配整个字符串的事实并不重要；/只有在匹配第一个备选方案本身失败时才回溯，而不是在解析的某些后续部分失败时才回溯。

简而言之，如果您使用 PEG，则需要小心以正确的顺序编写您的交替。