オンラインパーサーが正規表現で止まっているように見えるのはなぜですか?

StackOverflow https://stackoverflow.com/questions/803515

質問

私は長い間、なぜ次のようなパーサーが存在しないのか疑問に思っていました。 BNF, 、さまざまなライブラリの正規表現のように動作します。

確かに、次のようなことはあります アントラー, ヤック そして他の多くの コードを生成する これにより、 CFG, しかし、中間ステップなしでそれを行うことができるライブラリはないようです。

を書くことに興味があります Packrat パーサー, 、正規表現に関連する入れ子になった括弧の癖をすべて起動するためです (そしておそらく、スポーツのためならさらにそうです) が、どういうわけか、別の停止問題、つまり沼のようなクラスに足を踏み入れているだけのような気がします。

これらのパーサーには技術的/理論的な制限があるのでしょうか、それとも単に何かが足りないのでしょうか?

役に立ちましたか？

解決

それは文化的なものだと思います。文脈自由文法の使用は、ほとんどの場合コンパイラーに限定されており、コンパイラーは通常、各生成規則に関連付けられたコードを持っています。一部の言語では、コールバックをシミュレートするよりもコードを出力する方が簡単です。他には、パーサーライブラリがあります。たとえば、Haskellのパーサーコンビネーターです。一方、正規表現はgrepなどのツールで広く使用されており、ユーザーが新しい正規表現を指定するたびにCコンパイラを実行するのは不便です。

他のヒント

Boost.Spirit は、あなたが望んでいるように見えます。

自分で作成したい場合は、最新のコンパイラプロジェクトのBNFC は、独自の実装で使用される文法。これは良い出発点かもしれません...

技術的/理論的な制限は影に隠れています。なぜもっと普及していないのかはわかりませんが、あなたが求めているこの種の「オンライン」解析を提供するライブラリを少なくとも 1 つ知っています。

シンプルパース は、複雑な EBNF 文法をプログラムに貼り付けるだけで、それを使用してすぐに解析できる Python ライブラリです。中間の手順は必要ありません。私は、カスタム入力言語が必要だったものの、正式なビルド プロセスにコミットしたくなかったいくつかのプロジェクトでこれを使用してきました。

私の頭の中に浮かんだ小さな例を次に示します。

decl = r"""
    root := expr
    expr := term, ("|", term)*
    term := factor+
    factor := ("(" expr ")") / [a-z]
"""
parser = Parser(decl) 
success, trees, next = parser.parse("(a(b|def)|c)def")

Haskell と Scala のパーサー コンビネータ ライブラリを使用すると、パーサーを使用するコードの同じチャンク内でパーサーの文法を表現することもできます。ただし、たとえば、実行時にユーザーに文法を入力させることはできません (いずれにせよ、これは文法を理解するのに役立つソフトウェアを作成している人にしか興味がないかもしれません)。

Pyparsing（ http://pyparsing.wikispaces.com ）には、packratの解析とそれは純粋なPythonなので、実際の実装を見ることができます。

本格的なコンテキストフリー文法は、さらに複雑にするために、不可解なほど密集した理解できない構文がないため、十分に混乱しているのですか？

あなたが何を求めているのかを知るのは難しいです。コンテキストフリーの文法のために、正規表現のようなものを作成しようとしていますか？同様に、 $ var =〜/ expr = expr + expr / （Perlで）を使用して、＆quot; 1 + 1＆quot; または＆quot; 1 + 1 + 1＆quot; または＆quot; 1 + 1 + 1 + 1 + 1 + ...＆quot; ？これの制限の1つは構文になると思います。約3つ以上のルールがあると、「文法式」が作成されます。現代の正規表現よりもさらに読みにくい。

サイド効果は、私があなたを得るものだと私が見る唯一のものです。ほとんどのパーサージェネレーターには処理用の埋め込みコードが含まれており、それを機能させるにはevalが必要です。

それを回避する1つの方法は、アクションに名前を付けてから「アクション」を作成することです。実行するアクションの名前とそれを実行する引数を受け取る関数。

理論的には、C ++の Boost Spirit を使用して実行できますが、主に静的文法用に作成されています。これが一般的ではない理由は、CFGが正規表現ほど一般的に使用されていないためだと思います。コンパイラの構築を除き、文法を使用する必要はありませんでしたが、正規表現を何度も使用しました。通常、CFGは正規表現よりもはるかに複雑なので、YACCやANTLRなどのツールを使用して静的にコードを生成することは理にかなっています。

tcllib には、構文解析文法およびTCL。 PerlがあなたのものならCPANには Parse :: Earley があります。 こちらは、有望に見える純粋なPerlのバリエーションです。 PLY はPythonにとってもっともらしい解決策のようです

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top