11

Haskell の Parsec 構文解析ライブラリを使用して Java のサブセットを再帰降下パーサーとして解析し、Happy のような従来のパーサー ジェネレーター ソリューションに代わるものとして検討してきました。Parsec は非常に使いやすいようで、解析速度は私にとって重要な要素ではありません。しかし、Parsec を使用して「バックアップ」を実装することが可能かどうかは疑問に思っています。これは、使用する正しいプロダクションを 1 つずつ順番に試して見つける手法です。簡単な例として、JLS Java 文法の最初の部分を考えてみましょう。

Literal:
    IntegerLiteral  
    FloatingPointLiteral

解析を成功させるために、これら 2 つのルールをどのように順序付ける必要があるかを理解する必要がないようにしたいと考えています。現状では、次のような単純な実装です。

literal = do {
    x <- try (do { v <- integer; return (IntLiteral v)}) <|>
         (do { v <- float; return (FPLiteral v)});
    return(Literal x)
}

機能しません...「15.2」のような入力により、最初に整数パーサーが成功し、次に「。」で全体がチョークします。シンボル。この場合、もちろん、2 つのプロダクションを並べ替えることで問題を解決できることは明らかです。ただし、一般的なケースでは、このようなものを見つけるのは悪夢であり、いくつかのケースを見逃す可能性が非常に高い. 理想的には、Parsec にこのようなことを理解してもらう方法が欲しいです。これは可能ですか、それとも単にライブラリを使いすぎているのでしょうか? Parsec のドキュメントには、「文脈依存の無限先読み文法を解析する」ことができると書かれているので、ここで何かできるはずだと思われます。

4

2 に答える 2

8

これを行う 1 つの方法は、tryコンビネーターを使用することです。これにより、パーサーが入力を消費し、解析全体を失敗させることなく失敗させることができます。

もう 1 つは、 を使用するText.ParserCombinators.ReadPことです。これは、 が証明されている対称選択演算子を実装しているa +++ b = b +++ aため、実際にはどの順序でも問題ありません。は最小限ですが、本当にReadP強力なパーサーを構築するために必要なものを提供します。

于 2010-03-23T17:42:22.303 に答える
2

Parsec を使用して、トークン セパレーターまでのすべてnotFollowedByを消費するようにするか (このアプローチは、ほとんどの場合、任意のシナリオに対応します)、考えられるすべての解析の代替手段を探索するパーサー コンビネーターを調べます。integer最初に頭に浮かぶのはUU_Parsingライブラリです。

于 2010-03-22T21:40:20.183 に答える