構文解析と異なる構造の分離

Question

私は異なったパーサーを持っているとしましょう。p1, ..., pk。私は関数pk :: Parser ([t1], ..., [tk])を定義したいと思っています。pi :: Parser tiです。 P のいずれかに一致する文字列のコレクション（次々）... P _Kを解析し、対応するリストにそれらを分離します

。簡単にするために、2つのパーサーに一致する文字列はないものとします。

私はそれを行うことができましたが、私は実際にはエレガントな方法（多くの場合、または他の組み込みparsecパーサーを使用して）を見つけるのに苦労しています。

Answer 1

最初のステップは、大きなタイプのパーサにあなたのパーサのそれぞれを有効にすることです：

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'] 

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

Answer 2

パーサをリストとして表すと、これは簡単です。使い方：

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

私たちは書くことができ

を：それは1つのリストにそれらすべてをバンドルとして

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

これは、かなり右ではありません。のは、一意の識別子と、各パーサを関連付けてみましょう：

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。

これは、すべてのパーサーの結果タイプが同じである必要があるため、それぞれの結果を、pの場合はCons <$> pのデータ型にラップする必要があります。その後、各リストからコンストラクタをアンラップできます。確かに、これはかなり醜いですが、それをタプルで不均一にするには、醜い型クラスのハッキングが必要です。

具体的な使用例については、より簡単な解決策があるかもしれませんが、これは一般的に私が考えることができる最も簡単な方法です。

Answer 3

残念ながら、タイプレベルの細かいことがない限り、これを完全に一般的に行うことはできません。しかし、Daniel Wagnerの提案に沿ったアプローチは、多態的なコンビネータといくつかの既存の再帰的インスタンスを使用してDIYスタイルで構築することができます。デモンストレーションするための簡単な例を紹介します。

まず、でテストするには、いくつかのsimplemindedパーサ：

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) 

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

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

新しいコンビネータでパーサーを組み合わせるのは簡単で、結果の種類はわかりやすいものです。

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

我々はタプルを再帰的にMonoidインスタンスと複数の行を結合するためのリストのための通常のインスタンスに頼っています。 Right ([123,8],([True,False],(["acdf","qq"],Nil)))として成功し解析し

runTest = parseTest parseMulti testInput 

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

：今、それが機能することを示すために、簡単なテストを定義します。