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

mig*_*gou 5 grammar parsing

解析表达语法(PEG)中,是否有一种(简单的)方式来表达“无序序列”?诸如

Rule <- A B C
Run Code Online (Sandbox Code Playgroud)

要求A,B和C顺序匹配。诸如

Rule <- (A B C) / (B C A) / (C A B) / (A C B) / (C B A) / (B A C)
Run Code Online (Sandbox Code Playgroud)

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

是使用语法上宽松的规则(例如,

Rule <- (A / B / C){3}
Run Code Online (Sandbox Code Playgroud)

并在语义上检查每个规则仅匹配一次?

例如,Relax NG Compact Syntax具有一个“无序列表”运算符来解析XML的事实使我暗示没有明显的解决方案。

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

Ira*_*ter 2

语法规则精确地表达您想要的形式序列,无论您选择什么解析引擎(例如,PEG、LALR、LL(k)...)。

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

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

rule <- (A | B | C)* 
Run Code Online (Sandbox Code Playgroud)

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

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