4

問題

私は自己教育のために非決定論的パーサーを展開しています。次のようになります。

newtype Parser a b = P { runP :: [a] -> [(b, [a])] }

そして、次の形式のサブルーチンをドロップできるようにしたいと考えています : [a] -> [b]。これは、文字のバッファを取り、それを結果のリストに送信します。ここでの秘訣は、サブルーチン自体がステートフルな計算であり、呼び出しが成功するたびに状態を遷移することです (有限状態マシンと考えてください)。具体的には：

  1. サブルーチンが空の list を出力する場合[]、パーサーはもう 1 つの char をバッファーに挿入し、それをサブルーチンに渡します。サブルーチンは再び実行されます。
  2. サブルーチンが空でない list を出力する場合[b]、バッファは最初にフラッシュされ、パーサーはもう 1 文字をバッファに挿入し、それをサブルーチンに渡します。は[b]どこかに保管されている
  3. エスケープ条件に達するまで、ステップ 1 と 2 を繰り返し実行します。すべての中間結果は何らかの方法で組み合わせる必要があります。

  4. エスケープ条件に達すると、サブルーチンは結果bsをパーサーに戻し、残りのストリームと結合しますas。

    rs = fmap (flip (,) as) bs :: [(b,[a])]

したがって、署名を満たすrunP

関数には次の署名がある場合があります。withf :: ([a] -> [b]) -> Parser a b

重要なことは、withf gがパーサーでなければならないということ<*>です。関数シグネチャの提案gは純粋な関数であるため、正しい可能性は低いことに注意してください。

試した解決策

私はさまざまなコルーチン パッケージを使用してこれを実装しようとしましたが、私にとっては、パーサーをコルーチン計算コンテキストに変換する方が理にかなってliftおり、これもコンテキストに持ち上げられるトランスデューサーで構成されます。つまり、パーサーではなくなります。

withfまた、パーサー値コンストラクターにアクセスできるプリミティブ関数として実装しようとしました。基本的に手順 1..4 をコードに変換します。ここで私が抱えている最大の問題は、誰がどの情報を担当しているかということです。

  1. バッファの状態
  2. 中間結果の状態
  3. 中間結果を組み合わせる方法のロジック。
  4. エスケープ条件をどのように実装するか、またはより良い方法で構成する必要がありますwithf

また、パーサーに焼き付けられたさまざまな自作のコルーチン実装も試しましたが (Parser上記で定義した型は使用しません)、ほとんど成功しませんでした。

私を正しい方向に向けることができる人は誰でも大歓迎です。

4

2 に答える 2

3

まずはパーサーのMonadPlus代わりに使ってみましょう。[]これにより、より一般的になり、コードが少し明確になります (ネストされた s はそれほど多くありません[])。

newtype Parser a m b = P { runP :: [a] -> m (b, [a]) }

サブルーチンの署名を変更することをお勧めします。必要なことは次のとおりです。

  • サブルーチンがさらに入力を必要とするかどうかを通知し、
  • 状態をどこかに保持します。

これは、次の型シグネチャによって簡単に実現できます。

newtype Sub a b = Sub { runSub :: Either (a -> Sub a b) [b] }

サブルーチンは、結果を生成するか、新しい入力を要求して新しいサブルーチンを生成します。このようにして、返されたサブルーチンに渡すことで、必要な状態を維持できます。変換関数は次のようになります。

withf :: (MonadPlus m) => Sub a b -> Parser a m b
withf start = P $ f (runSub start)
  where
    f (Right bs) xs   = msum [ return (b, xs) | b <- bs ]
    f (Left r)   []   = mzero    -- No more input, can't proceed.
    f (Left r) (x:xs) = f (runSub (r x)) xs

更新:パーサーが実際にはStateTトランスフォーマーであり、その状態が[a]:

type Parser a m b = StateT [a] m b

runP :: (Monad m) => Parser a m b -> [a] -> m (b, [a])
runP = runStateT

確かに、runPまさにrunStateTです！

このようにして、無料でMonadインスタンスを取得しますParser。これで、タスクを小さなブロックに分割できます。まず、1 つの入力を消費するか失敗するパーサーを作成します。

receive :: (MonadPlus m) => Parser a m a
receive = get >>= f
  where
    f []        = mzero    -- No more input, can't proceed.
    f (x:xs)    = put xs >> return x

そして、それを使用して次のように記述しwithfます。

withf :: (MonadPlus m) => Sub a b -> Parser a m b
withf start = f (runSub start)
  where
    f (Right bs) = msum (map return bs)
    f (Left r)   = receive >>= f . runSub . r

if mis a MonadPlusthen もStateT s maMonadPlusであるため、直接mzeroおよびmsumwith を使用できることに注意してParserください。

于 2013-08-02T07:31:07.153 に答える
2

まず、解析の可能な結果を​​表す新しいデータ型を定義しましょう。

data Step r = Done | Fail | Succ r

パーサーは、 で終了するか、 でDone解析の失敗を示すか、 で解析済みの値をFail正常に返すことができます。rSucc r

Stepデータ型を型クラスのインスタンスにMonoidします

instance Monoid (Step r) where
    mempty = Done
    Done   `mappend` _ = Done
    Fail   `mappend` x = x
    Succ r `mappend` _ = Succ r

パーサーがDoneの場合、すぐに終了する必要があります。Aは、成功の可能性についてFail次の結果を確認する必要があることを意味します。もちろん、値の解析に成功したことを意味します。StepSucc r

次に、 a の型シノニムを定義しましょうParser。解析された結果を蓄積し ( Writer)、まだ消費されていない入力を表す純粋な状態を維持できる必要があります ( State)。

{-# LANGUAGE FlexibleContexts #-}                                                                   

import Control.Monad.State
import Control.Monad.Writer
import Data.List
import Data.Foldable

type Parser w s = WriterT w (State s)

evalParser :: Parser w s r -> s -> w
evalParser = evalState . execWriterT

これが実際のパーサーです

parser :: (MonadState [s] m, MonadWriter [w] m) => ([s] -> Step [w]) -> m ()
parser sub = do
    bufs <- gets inits
    -- try our subroutine on increasingly long prefixes until we are done,
    -- or there is nothing left to parse, or we successfully parse something
    case foldMap sub bufs of
         Done   -> return ()
         Fail   -> return ()
         Succ r -> do
            -- record our parsed result
            tell r
            -- remove the parsed result from the state
            modify (drop $ length r) 
            -- parse some more
            parser sub

そして簡単なテストケース

test :: String
test = evalParser (parse sub) "aabbcdde"
    where sub "aabb" = Succ "aabb"
          sub "cdd"  = Succ "cdd"
          sub "e"    = Done
          sub _      = Fail

-- test == "aabbcdd"
于 2013-08-02T04:15:05.123 に答える