1

私が読んだすべてのことは、正規表現のようなTreetopのバックトラックを示唆していますが、それを機能させるのに苦労しています。

次の文法があるとします。

grammar TestGrammar
  rule open_close
    '{' .+ '}'
  end
end

これは文字列と一致しません{abc}。.+それは、手紙a以降のすべてを消費しているからだと思います。つまり、消費abc}したいだけのときに消費しますabc。

これは、同様の正規表現が行うこととは異なるように見えます。正規表現/{.+}/は一致し{abc}ます。これが可能であるのは、正規表現エンジンがの}一部としてクロージングを消費した後.+、一致しなかったためにバックトラックするためであると私は理解しています。

では、Treetopはそのようなバックトラックを実行できますか？もしそうなら、どのように？

}否定を使用して「 。以外のもの」と一致させることができることを私は知っています。しかし、それは私の意図ではありません。文字列と一致させたいとします{ab}c}。その場合に必要なトークンは、開始{、中間の文字列ab}c、および終了}です。これは不自然な例ですが、のようなネストされた式を操作する場合に非常に関連性が高くなり{a b {c d}}ます。

4

1 に答える 1

2

Treetopは、ParsingExpressionGrammarパーサーの実装です。PEGの利点の1つは、柔軟性、速度、およびメモリ要件の組み合わせです。ただし、このバランスを取る行為にはいくつかのトレードオフがあります。

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

ゼロ以上、1つ以上、およびオプションの演算子は、それぞれ、サブ式eのゼロ以上、1つ以上、またはゼロまたは1つの連続した繰り返しを消費します。ただし、文脈自由文法や正規表現とは異なり、これらの演算子は常に貪欲に動作し、可能な限り多くの入力を消費し、バックトラックすることはありません。[…]最初の部分が2番目の部分に一致するaを残すことは決してない(a* a)ため、式は常に失敗します。(a*)

（エンファシスマイン。）

つまり、特定のPEGオペレーターは別のルートをたどろうとしてバックトラックできますが、+オペレーターはできません。

代わりに、ネストされた部分式を一致させるために、区切られた部分式（最初にチェックされた）とそれに続く非式文字の間に交互を作成する必要があります。（未テスト）のようなもの：

grammar TestGrammar
  rule open_close
    '{' contents '}'
  end
  rule contents
    open_close / non_brackets
  end
  rule non_brackets
    # …
  end
end
于 2012-10-17T05:04:49.690 に答える