PEG 语法，它接受三个任意顺序的可选元素

Question

假设我们有三个元素 a b 和 c。

一个有效的表达式使用这三个元素（和可选的空格）。

这三个要素中至少有一个必须存在。
所有三个元素都是可选的（只要至少存在其他两个元素之一，请参见 1）。
提供这三个元素的顺序并不重要。

是否有一种惯用的方法来编写满足这三个要求的 PEG 语法？

我在 http://pegjs.org/online 玩过 peg.js 并解决了 (1)（前瞻）和 (2)，但 (3) 没有解决。有什么建议吗？

e = &(a / b / c) (a? b? c?) 

a = 'a' _
b = 'b' _
c = 'c' _

_ = [ \t]*

Answer 1

真正唯一的可能是列出所有六个可能的顺序，因为 PEG 没有 "unordered permutation" 运算符。（传统的上下文无关文法也没有，所以大致相同的过程是必要的。

例如，您可以使用：

a (b c? / c b?)? / b (a c? / c a?)? / c (a b? / b a?)?

但是为更多的备选方案构建显然是乏味的。

通过接受 x、y、...的任意列表，然后检查语义动作中的重复，通常更容易解决 "a list of x, y, ... in any order but without repetitions" 等问题。这不仅使语法更容易编写，而且允许更有意义的错误消息。

Answer 2

感谢 peg.js 的强大功能，如果元素列表 s 是一些元素集 S 的组合（不允许重复）。基本思想是计算 S 的幂集并将 s 的每个元素映射到一个素数。 S 的每个元素映射到其对应元素的素数乘积，即 S 的幂集的每个元素映射到唯一的数字。集合 s 是 S 中元素的组合，当且仅当 s 中相应素数的乘积在从 S 计算的素数乘积中。（我想，执行此检查的方法不止一种 :-)）。下面是 peg.js 的解决方案，其中包含 5 个元素，我认为它非常有效。（使用 & { predicate } 时的一个小问题：内部的 javascript 是用参数对象中的所有命名表达式调用的，因此 (a / b /c /d /e)+ 必须有一个名称，例如 el:(a / b /c /d /e)+ ）。

{
    // array of elements (expressions)
    var data = ['a','b','c', 'd', 'e'];

    // map elements to primes
    var primemap = {
       a: 2,
       b: 3,
       c: 5,
       d: 7,
       e: 11
    };

    // powerset of an array
    function powerset(arr) {
        var ps = [ [] ];
        for (var i=0; i < arr.length; i++) {
            for (var j = 0, len = ps.length; j < len; j++) {
                ps.push(ps[j].concat(arr[i]));
            }
        }
        return ps;
    }

    // compute the product of primes corresponding to each element of an array arr
    function primeprod(arr) {
       return arr.reduce( function(p,c) { return p * primemap[c] }, 1 );  
    }

    // compute powerset and remove empty set at index 0 of the powerset
    var ps = powerset(data);
    ps.splice(0,1);
    // map elements of powerset to products of primes
    var prods = ps.map( function(el) { return primeprod(el); });

    // returns true if an arr is a combination of the elements
    function isCombination(arr) {
       return prods.indexOf(primeprod(arr)) !== -1
    }
}

expr =  exp / blankline;

exp = (el:(a / b / c / d / e)+ &{ return isCombination(Array.prototype.slice.call(arguments)[0]); } {return el; } ) rest*

a = _ a:'a' {return a; }
b = _ b:'b' {return b; }
c = _ c:'c' {return c; }
d = _ d:'d' {return d; }
e = _ e:'e' {return e; }

rest = [^abcde]

blankline =
    [ \t]* ("\n" / eof) { return []; }

_ = [ \t]*
eof = !.

PEG 语法，它接受三个任意顺序的可选元素

PEG grammar which accepts three optional elements in any order

grammar

parsing

peg

antlr4

pegjs