1

と の 3 つの要素があるa bとしcます。

有効な式は、これら 3 つの要素 (およびオプションの空白) を使用します。

  1. これらの 3 つの要素の少なくとも 1 つが存在する必要があります。
  2. 3 つの要素はすべてオプションです (他の 2 つの要素の少なくとも 1 つが存在する限り、1 を参照してください)。
  3. これら 3 つの要素が提供される順序は重要ではありません。

これら 3 つの要件を満たす PEG 文法を記述する慣用的な方法はありますか?

http://pegjs.org/onlineで peg.js をいじって(1) (先読み) と (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、 の要素の組み合わせです。SsS. （このチェックを実行する方法は複数あると思います:-)）。以下は、私がかなり効率的だと考える 5 つの要素を持つ peg.js のソリューションです。( を使用するときのちょっとした& { 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 には「順序付けられていない順列」演算子がないため、実際には 6 つの可能な順序をすべてリストすることが唯一の方法です。(また、従来の文脈自由文法もそうではないため、ほぼ同じ手順が必要です。

たとえば、次のように使用できます。

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

しかし、それは明らかに多数の代替案を構築するのが面倒です。

通常、「x, , ... の任意の順序で、繰り返しなしのリスト」などを解決するには、, y, ... の任意のリストを受け入れ、セマンティック アクションで繰り返しをチェックする方が簡単です。これにより、文法が書きやすくなるだけでなく、より意味のあるエラー メッセージが可能になります。xy

于 2016-05-09T19:07:56.070 に答える