ПЭГ-грамматика, которая принимает три необязательных элемента в любом порядке

Question

Предположим, у нас есть три элемента: ab и c.

В действительном выражении используются эти три элемента (и необязательные пробелы).

1. Должен присутствовать хотя бы один из этих трех элементов.
2. Все три элемента являются необязательными (если присутствует хотя бы один из двух других элементов, см. 1).
3. Заказ, в котором эти три элемента поставлены, не имеет значения.

Есть ли идиоматический способ написать грамматику ПЭГ, которая отвечает этим трем требованиям?

Я играл с peg.js на http://pegjs.org/online и решил (1) (смотреть) и (2), но (3) ускользнул от меня. Какие-либо предложения?

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

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

_ = [ \t]* 

Answer 1

Действительно единственная возможность перечислить все шесть возможных заказы, потому что ПЭГ не имеет «неупорядоченные перестановки» оператор. (И ни делать традиционные контекстные свободные грамматики, поэтому примерно такая же процедура необходима

Например, вы можете использовать:..

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

, но это, очевидно, утомительно построить для большего числа альтернатив

Это, как правило, легче решить «список x, y ... в любом порядке, но без повторений» и тому подобное, принимая произвольный список x, y ..., а затем проверка повторов в семантическое действие. Это не только делает грамматика легче писать, она позволяет более значимые сообщения об ошибках.

Answer 2

Благодаря удивительности peg.js, не слишком сложно предоставить функцию проверки, которая возвращает true (и потребляет вход), если список элементов s представляет собой комбинацию некоторого набора элементов S (без повторений). Основная идея состоит в том, чтобы вычислить набор параметров S и сопоставить каждый элемент s с расчетом. Каждый элемент S отображается на произведение простых чисел его соответствующих элементов, то есть каждый элемент набора команд S отображается на уникальный номер. Набор s представляет собой комбинацию элементов в S тогда и только тогда, когда произведение соответствующих простых чисел в s входит в число простых чисел, рассчитанных с S. (На мой взгляд, существует более одного способа выполнить эту проверку :-)). Ниже приведено решение для peg.js с 5 элементами, которые я считаю довольно эффективными. (Немного gotcha при использовании & { predicate }: внутри JavaScript вызывается все именованные выражения в объекте arguments, поэтому (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 = !.