1

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

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

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

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

我在http://pegjs.org/online上使用 peg.js并解决了 (1) (lookahead) 和 (2)，但 (3) 让我无法理解。有什么建议么？

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

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

_ = [ \t]*
4

2 回答 2

1

感谢 peg.js 的强大功能，如果元素列表s是一组元素的组合S（不允许重复），提供一个返回 true（并使用输入）的检查函数并不难。基本思想是计算 的幂集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 = !.
于 2016-05-10T11:40:41.510 回答
0

真正唯一的可能性是列出所有六个可能的顺序，因为 PEG 没有“无序排列”运算符。（传统的上下文无关文法也不行，因此需要大致相同的程序。

例如，您可以使用：

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

但这显然是为大量替代方案构建的乏味。

通过接受任意的, , ... 列表，然后检查语义动作中的重复，通常更容易解决“以任何顺序但没有重复的x, , ... 列表”等。这不仅使语法更容易编写，而且允许更有意义的错误消息。yxy

于 2016-05-09T19:07:56.070 回答