5

私は attoparsec パーサーをコーディングしており、パーサーを再帰パーサーに変えたいパターンにぶつかっています (それらをモナド bind >>= 演算子と再​​帰的に結合します)。

そこで、次のようにパーサーを再帰パーサーに変換する関数を作成しました。

recursiveParser :: (a -> A.Parser a) -> a -> A.Parser a
recursiveParser parser a = (parser a >>= recursiveParser parser) <|> return a

次のような再帰的なデータ型がある場合に役立ちます

data Expression = ConsExpr Expression Expression | EmptyExpr

parseRHS :: Expression -> Parser Expression
parseRHS e = ConsExpr e <$> parseFoo

parseExpression :: Parser Expression
parseExpression = parseLHS >>= recursiveParser parseRHS
  where parseLHS = parseRHS EmptyExpr

もっと慣用的な解決策はありますか？recursiveParserある種の折り畳みのように思えます...sepByドキュメントでも見ましたが、この方法は私のアプリケーションにより適しているようです。

編集:ああ、実際に考えてみると、実際には似たようなものになるはずfixです...どうやってそれを忘れたのかわかりません。

EDIT2 : Rotsor は私の例に対する彼の代替案で良い点を指摘していますが、残念ながら、私の AST は実際にはそれよりも少し複雑です。実際にはもっと似ています（ただし、これはまだ単純化されています）。

data Segment = Choice1 Expression
             | Choice2 Expression
data Expression = ConsExpr Segment Expression 
                | Token String
                | EmptyExpr

ここで、文字列a -> bは右にc:dブラケット、左にブラケットし、:よりきつく結合します->。

つまり、次a -> bのように評価されます

(ConsExpr (Choice1 (Token "a")) (Token "b"))

とc:d評価されます

(ConsExpr (Choice2 (Token "d")) (Token "c"))

foldl一方と他方に使用できると思いますがfoldr、まだ複雑です。少し奇妙な方法で再帰的であるため、"a:b:c -> e:f -> :g:h ->"実際には有効な文字列ですが、そう"-> a"では"b:"ないことに注意してください。結局、私にfixはもっと簡単に思えました。再帰メソッドの名前を次のように変更しました。

fixParser :: (a -> A.Parser a) -> a -> A.Parser a
fixParser parser a = (parser a >>= fixParser parser) <|> pure a

ありがとう。

4

1 に答える 1

4

リストを解析して、後で必要なものに折りたたんでみませんか? 多分私は何かが欠けているかもしれませんが、これは私にとってより自然に見えます:

consChain :: [Expression] -> Expression
consChain = foldl ConsExpr EmptyExpr

parseExpression :: Parser Expression
parseExpression = consChain <$> many1 parseFoo

そしてそれも短いです。

ご覧のとおり、consChainは解析から独立しており、他の場所で役立つ可能性があります。また、結果の折りたたみを分離すると、やや直観的ではない再帰的な解析が、manyまたはmany1この場合に単純化されます。

manyの実装方法も参照してください。

many :: (Alternative f) => f a -> f [a]
many v = many_v
    where many_v = some_v <|> pure []
          some_v = (:) <$> v <*> many_v

それはあなたと多くの共通点がありますrecursiveParser:

  • some_vと類似していますparser a >>= recursiveParser parser
  • many_vと類似していますrecursiveParser parser

なぜ私があなたの再帰パーサー関数を直観的でないと呼んだのかと尋ねるかもしれません。これは、このパターンにより、パーサーの引数が解析動作に影響を与えることができるためです ( a -> A.Parser a、覚えていますか?)。これは便利かもしれませんが、明らかではありません (これの使用例はまだ見当たりません)。あなたの例がこの機能を使用していないという事実は、冗長に見えます。

于 2011-06-20T00:41:10.147 に答える