3

私が異なるパーサーを持っているとしましょう。関数を定義したいのですが、.p1, ..., pkpk :: Parser ([t1], ..., [tk])pi :: Parser ti

これは、 p 1 ...p kのいずれかに一致する文字列のコレクションを (次々に) 解析し、対応するリストでそれらを分離します。簡単にするために、どの文字列も 2 つのパーサーに一致しないと仮定します。

私はなんとかそれを行うことができましたが、エレガントな方法を見つけるのに本当に苦労しています（できれば、多くのまたは他の組み込みパーセックパーサーを使用してください）。

4

3 に答える 3

6

最初のステップは、各パーサーを大きな型のパーサーに変えることです。

p1 :: Parser t1
p2 :: Parser t2
p3 :: Parser t3
p1 = undefined
p2 = undefined
p3 = undefined

p1', p2', p3' :: Parser ([t1], [t2], [t3])
p1' = fmap (\x -> ([x], [], [])) p1
p2' = fmap (\x -> ([], [x], [])) p2
p3' = fmap (\x -> ([], [], [x])) p3

ここで、これらの最後のパーサーから繰り返し選択し、最後に結果を連結します。

parser :: Parser ([t1], [t2], [t3])
parser = fmap mconcat . many . choice $ [p1', p2', p3']

Monoidサイズ 5 までのタプルのインスタンスがあります。それを超えて、ネストされたタプルまたはより適切なデータ構造を使用できます。

于 2012-01-06T14:38:45.147 に答える
5

パーサーをリストとして表すと、これが簡単になります。使用：

choice :: [Parser a] -> Parser a
many :: Parser a -> Parser [a]

私たちは書くことができます：

combineParsers :: [Parser a] -> Parser [a]
combineParsers = many . choice

すべてを1つのリストにまとめているため、これは正しくありません。各パーサーを一意の識別子に関連付けましょう。

combineParsers' :: [(k, Parser a)] -> Parser [(k, a)]
combineParsers' = many . choice . combine
  where combine = map (\(k,p) -> (,) k <$> p)

次に、これをリスト形式に戻すことができます。

combineParsers :: [Parser a] -> Parser [[a]]
combineParsers ps = map snd . sortBy fst <$> combineParsers' (zip [0..] ps)

combineParsers' :: [(k, Parser a)] -> Parser (Map k [a])代わりに、たとえばを使用して書くことで、これをより効率的にすることができますcombine = map $ \(k,p) -> fmap (\a -> Map.insertWith (++) k [a]) p。

Cons <$> pこれには、すべてのパーサーが同じ結果タイプを持っている必要があるため、各パーサーの各結果をforeachpのデータ型にラップする必要があります。次に、各リストからコンストラクターをアンラップできます。確かに、これはかなり醜いですが、タプルで異種的にそれを行うには、さらに醜い型クラスのハックが必要になります。

特定のユースケースにはもっと簡単な解決策があるかもしれませんが、これは私が考えることができる一般的な方法です。

于 2012-01-06T13:33:04.273 に答える
5

残念ながら、型レベルのトリッキーなしでは、これを完全に一般的に行うことはできません。ただし、Daniel Wagner の提案に沿ったアプローチは、ポリモーフィック コンビネータといくつかの既存の再帰インスタンスを使用して、DIY スタイルで構築できます。簡単な例を示して説明します。

最初に、いくつかの単純なパーサーでテストします。

type Parser = Parsec String ()

parseNumber :: Parser Int
parseNumber = read <$> many1 digit

parseBool :: Parser Bool
parseBool = string "yes" *> return True
        <|> string "no" *> return False

parseName :: Parser String
parseName = many1 letter

次に、可能性の終わりを示す「基本ケース」型を作成し、入力なしで常に成功するパーサーを与えます。

data Nil = Nil deriving (Eq, Ord, Read, Show, Enum, Bounded)
instance Monoid Nil where 
    mempty = Nil
    mappend _ _ = Nil

parseNil :: Parser Nil
parseNil = return Nil

もちろん、これは と同等です。()実際に を解析したい場合に備えて、あいまいさを解消するために新しい型を作成しているだけです()。次に、パーサーを連結するコンビネーター:

infixr 3 ?|>
(?|>) :: (Monoid b) => Parser a -> Parser b -> Parser ([a], b)
p1 ?|> p2 = ((,) <$> ((:[]) <$> p1) <*> pure mempty)
        <|> ((,) <$> pure [] <*> p2)

ここで何が起こっているかというと、 p1 ?|> p2tryp1が成功した場合、それをシングルトン リストにラップしmempty、タプルの 2 番目の要素を埋めます。失敗した場合p1は、空のリストを埋めp2て 2 番目の要素を使用します。

parseOne :: Parser ([Int], ([Bool], ([String], Nil)))
parseOne = parseNumber ?|> parseBool ?|> parseName ?|> parseNil

パーサーと新しいコンビネーターの組み合わせは簡単で、結果の型は一目瞭然です。

parseMulti :: Parser ([Int], ([Bool], ([String], Nil)))
parseMulti = mconcat <$> many1 (parseOne <* newline)

Monoid複数の行を結合するために、タプルの再帰インスタンスとリストの通常のインスタンスに依存しています。ここで、それが機能することを示すために、簡単なテストを定義します。

runTest = parseTest parseMulti testInput

testInput = unlines [ "yes", "123", "acdf", "8", "no", "qq" ]

として正常に解析されRight ([123,8],([True,False],(["acdf","qq"],Nil)))ます。

于 2012-01-06T15:14:23.557 に答える