6

さまざまなライブラリで正規表現のように動作する、たとえばBNFのパーサーがないように見える理由を長い間疑問に思っていました。

確かに、ANTLR、Yacc 、およびCFGを解析できるコードを生成する他の多くのものがありますが、中間ステップなしでそれを実行できるライブラリはないようです。

私はPackrat パーサーを作成して、正規表現に関連するネストされた括弧の癖をすべて起動することに興味があります (そして、おそらく、そのスポーツのためにさらにそうです) が、どういうわけか、私はちょうど歩いているような気がします別の停止問題のような沼地のクラス。

これらのパーサーには技術的/理論的な制限がありますか、それとも何か不足していますか?

4

8 に答える 8

4

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

于 2009-04-29T18:08:20.560 に答える
2

Boost.Spiritは、あなたが求めるもののように見えます。

独自のものを探している場合は、最新のコンパイラ プロジェクトにBNFCを使用しており、独自の実装で使用される文法を提供しています。これは良い出発点かもしれません...

于 2009-04-29T18:27:57.143 に答える
1

Pyparsing ( http://pyparsing.wikispaces.com ) には packrat 解析の組み込みサポートがあり、純粋な Python であるため、実際の実装を確認できます。

于 2009-09-11T03:00:31.780 に答える
0

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

于 2009-04-29T18:17:46.683 に答える
0

本格的な文脈自由文法は、複雑でわかりにくい構文がなくても十分に混乱するため、さらに混乱を招くのでしょうか?

あなたが何を求めているのかを知るのは難しいです。正規表現のようなものを作成しようとしていますが、文脈自由文法のためですか? 同様に、(Perl で) を使用して、またはまたは?$var =~ /expr = expr + expr/を一致させます。これの制限の 1 つは構文にあると思います。約 3 つ以上の規則があると、「文法式」が現代の正規表現よりもさらに読みにくくなります。"1 + 1""1 + 1 + 1""1 + 1 + 1 + 1 + 1 + ..."

于 2009-04-29T18:08:11.900 に答える
0

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

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

于 2009-04-29T18:12:30.377 に答える
0

tcllibには、 Parse Expression Grammarsと TCLを我慢できれば、そのようなものがあります。Perl があなたのものなら、CPAN にはParse::Earleyがあります。 これは有望に見える純粋な Perl のバリエーションです 。PLYは Python のもっともらしい解決策のようです

于 2009-04-29T18:26:22.077 に答える