Scala または Haskell 用の成熟したパーサー ライブラリを探しています。最も重要な点は、ライブラリがあいまいさを処理できることです。式があいまいである場合、式に一致するすべての可能な抽象構文ツリーが必要です。簡単な例: 式a ⊗ b ⊗ cは(a ⊗ b) ⊗ cまたはa ⊗ (b ⊗ c)と見なすことができ、両方の変形が必要です。ありがとう！
1014 次
4 に答える
13
私は、Comprehending Monads (do 記法の前身) のような Walder の論文が刺激的で新しいものだった時代を思い出す老人のように感じます。アイデアは、（引用すると）失敗を成功のリストに置き換えることです。つまり、可能なすべての解析のリストを維持します。最後は通常は最初の試合だけを取りますが、このセットアップではすべてを取ることができます。
これらは、決定論的パーサーにとってそれほど効率的ではないため、あまり流行っていませんが、必要なものです。
polyparse、特にText.ParserCombinators.HuttonMeijerandを見てくださいText.ParserCombinators.HuttonMeijerWallace。
(Hutton & Meijer はパーサー ライブラリを (Gofer から) Haskell に変換し、Wallace は追加機能を追加しました。)
"aaaa"で解析するような単純なケースでそれをチェックアウトしてください
testP = do
a <- many $ char 'a'
b <- many $ char 'a'
return (a,b)
求めるセマンティクスがあるかどうかを確認します。
あなたは成熟を求めました。これらのライブラリは、純粋な関数型プログラミングの遺産の一部です! そうは言っても、若いとはいえ、パーセクはより成熟していると言えます。
(憶測: parsec はあなたが望むことはできないと思います。その標準的な選択コンビネータは決定論的です。私はその動作を微調整したり置き換えたりすることを検討していません。
于 2012-11-08T02:12:22.283 に答える
4
この質問はすぐに私にYacc が死んでいることを思い出させました/いいえ、それは 2010 年末からの議論ではありません。Yacc は死んでいるという論文の著者は、 Scala (メンテナンスされていません)、Haskell、および Racket でライブラリを提供しています。Yacc is alive応答で、Russ Cox は、あいまいな文法のためにコードが指数関数的に実行されることを指摘しています。
であいまいな文法を解析できることはよく知られていますがO(n^3)、解析ツリーが指数関数的に多く存在する場合、すべての解析ツリーを列挙するのに指数関数的な時間がかかることは明らかですx1 + x2 + x3 ... + xn。bisonそうするGLRアルゴリズムを実装します。残念ながら、bison確かに成熟していますが (実際には瀕死ではないにしても)、Haskell でも Scala でも書かれていません。
Daniel Spiewak は Scala IIRC に GLL パーサーを実装しましたが、前回見たときはパフォーマンスの問題がいくつかありました。ですから、それが成熟していると言えるかどうかもわかりません。
于 2012-11-08T15:53:38.130 に答える
3
最後に、ここ では sdf テーブル ジェネレーターを使用し、パーサー ジェネレーターとしてJSGLRを使用する Syntax Definition Formalism ( SDF2 ) を選択しました。
于 2013-01-29T11:04:23.470 に答える
3
それがどれほど成熟しているかについて話すことも、使用例を示すこともできませんが、scala gll-combinatorsライブラリをタブで数日間開いています。あいまいな文法を処理し、かなり気の利いたように見えます。
于 2012-11-08T15:11:53.223 に答える