11

次の最小限の Peg.js 文法を定義しました。

start  =  "A1" / "A123"

サンドボックスで試すことができます。

「A1」と「A123」が一致すると予想していました (バックトラッキングの仕組みに関する私の考えによると)。しかし、そうではありません: 文法は "A1" を認識しますが、"A123" は認識しません。

注:関連する質問How to transform a simple grammar into something that works in PEG.js (expected "a" but "a" found) のように、「用語の順序を逆にする」というアドバイスは探していません。むしろ、私が見ている動作と、この場合に Peg.js のバックトラッキングが適用されない理由を理解しようとしています。用語の順序を逆にしても効果がない理由については、以下のより現実的な例を参照してください。

より現実的な例として、単位の解析を考えてみましょう。文法は、メートル法単位 (「m」、「mol」など) を、「mm」、「mm​​ol」などのオプションの接頭辞とともに認識し、「yr」、「week」、または「mo」などの非メートル法単位も認識する必要があります。

次の Peg.js 文法は、「mo」を消費してつまずいてバックトラックしないため、「mol」を認識しません。(用語の順序を変更しても意味がありません。むしろ、「mol」または「mmol」を犠牲にして「mo」が認識されるようになります。)

start  =  nonmetric / metric / prefix metric
metric = "mol" / "l" / "m" / "g"
nonmetric = "yr" / "mo" / "week" / "day" / "hour"
prefix = "m" / "k" / "c"

私はAntlrで同様のことをうまくやることができます:

grammar units;
start  :  nonmetric | metric | prefix metric;
metric : 'mol' | 'l' | 'm' | 'g';
nonmetric : 'yr' | 'mo' | 'week' | 'day' | 'hour';
prefix : 'm' | 'k' | 'c';
4

2 に答える 2

15

問題はbacktrackingの概念にあります。PEG パーサーは、他の再帰降下パーサーやPrologのようにバックトラックしません。むしろ、選択を迫られると、PEG パーサーはいずれかが成功するまですべてのオプションを試します。成功すると、ルールがどのように呼び出されたかに関係なく、コミットされます。

ウィキペディアの記事から：

ただし、文脈自由文法や正規表現とは異なり、これらの演算子は常に貪欲に動作し、可能な限り多くの入力を消費し、バックトラックすることはありません。

複雑なケースであなたが求めることは、この質問で求められることと同じです。これまでのところ、答えはイエスです。たとえ結果がやや醜い文法であっても、常に最も長いオプションが最初に一致するように、PEG 文法のルールを微調整する必要があります。

PEG 文法を微調整する 1 つの方法は、先読みを使用することです (これが先読みが PEG で機能する主な理由の 1 つです)。

start  =  nonmetric / metric / prefix metric
metric = "mol" / "l" / !"mo" "m" / "g"
nonmetric = "yr" / !"mol" "mo" / "week" / "day" / "hour"
prefix = !("mol"/"mo") "m" / "k" / "c"
于 2014-07-17T17:09:02.983 に答える
3

これは仕様によるものです。マッチングに使用する正しい順序やルールを指定するのはあなた次第です。

元のホワイト ペーパーからの引用:

もちろん、これらのツールによって言語の構文設計が容易になるわけではありません。CFG 内の 2 つの可能な選択肢があいまいであるかどうかを判断する必要がある代わりに、PEG は言語設計者に、言語に影響を与えずに「/」式の 2 つの選択肢を並べ替えることができるかどうかを判断するという同様の課題を提示します。この問題はしばしば自明ですが、そうでない場合もあり、一般的には決定できません。ただし、CFG のあいまいさを発見する場合と同様に、一般的な状況で保守的に順序の感度または非感度を識別する自動アルゴリズムを見つけることが期待されています。

この単純なケースでは、PEG.js はもう少し賢く、指定したルールがあいまいであることを認識できます。作者に聞いてみる価値はあると思います。

于 2014-08-06T05:10:24.483 に答える