用解析表达式语法解析无序序列

Question

有没有一种(简单的)方法，在parsing expression grammar内(PEG)，表达“无序序列”？诸如

之类的规则

Rule <- A B C

要求A、B、C按顺序匹配。规则如

Rule <- (A B C) / (B C A) / (C A B) / (A C B) / (C B A) / (B A C)

允许它们以任何顺序匹配(这正是我们想要的)，但在序列中存在更多术语的实践中，它很麻烦且不适用。

是使用语法上更宽松的规则的唯一解决方案，例如

Rule <- (A / B / C){3}

并从语义上检查每个规则是否仅匹配一次？

事实上，例如，Relax NG Compact Syntax 有一个 "unordered list" operator解析 XML 让我暗示没有明显的解决方案。

最后一个问题:您认为增加这样一个运算符是否会给PEG带来歧义？

Answer 1

无论您选择哪种解析引擎(例如 PEG、LALR、LL(k) 等)，语法规则都可以准确表达您想要的形式序列。

表达您想要使用 BNF 规则的某事物的所有可能序列的唯一方法是您提出的丑陋的大规则。

标准解决方案是简单地定义:

rule <- (A | B | C)* 

(或者您的解析器生成器接受的列表语法)并且从语义上看只提供了 3 种形式并且它们是唯一的。

构建解析器生成器的人们通常会添加特殊的“扩展 BNF”符号来让他们描述特殊情况；您给出了一个使用 {3} 作为特殊语法的示例，这意味着您只需要“3 of”，假设解析器生成器接受此表示法并执行适当的强制操作。人们可以想象一种扩展符号{unique}来让您描述您的情况。我从未见过实现该想法的解析器生成器。