parsec再帰的に簡単な式を解析する方法は？

Question

私はそのような文字列があります：***、**(*)*、****(**(**)*)**

をそして、私はそのようなデータ構造にそれを解析したい：Sが* ある

data Tree = Node [S] Tree Tree | Empty（*は、任意の文字にそれを意味するものではありません私は（私はmegaparsecを使用しますが、それはparsec習慣的に非常によく似ている）パーサを構築しようとしただけでスターシンボル）

です：

data Tree = Node [Char] Tree Tree | Empty deriving (Show) 

chain :: Parser Tree 
chain = do 
    line <- many $ char '*' 
    branch <- between (char '(') (char ')') chain 
    cont <- (eof >> return Empty) <|> chain 
    return $ Node line branch cont 

test = parseTest chain "****(*(*)***)*(*)**" 

しかし、動作しません。私は多くの方法を試みましたが、それと闘うことはできません。単純なテストケースと

Answer 1

ましょうスタート：最初の星を読んだ後にパースエラーがあることを

> parseTest chain "*" 
parse error at (line 1, column 2): 
unexpected end of input 
expecting "*" or "(" 

注意。入力は終了しましたが、パーサは別の星か括弧を読み込むことが予想されていました。

あなたのパーサを見てみると、それは明らかだ：

line <- many $ char '*' 

は星の最初の文字列を読み込むことで、成功しますが、次の行：

branch <- between (char '(') (char ')') chain 

は、入力中に開き括弧を必要とし、これは決して任意ではありません。

我々は、書面によりこれを修正することができます：

今

branch <- option Empty $ between (char '(') (char ')') chain 

を、パーサは"***"に大丈夫動作しますが、それは"**(*)*"にハングアップします。問題はラインです：

cont <- (eof >> return Empty) <|> chain 

これは、入力の終了を検出に基づいて解析する停止するタイミングを決定しようとしますが、これは唯一のトップレベルで現在のツリーの最後は終わりに対応chainコールに動作します再帰呼び出しでは、ツリーは入力が終了する前に終了することができますので、これは機能しません。

括弧内のツリーを解析するとき具体的には、テストケース"**(*)*"に、すなわち*、我々は、*にlineセットを取得Emptyに設定branch、そしてcontラインは、我々はの終わりではないことを見て入力（残りの入力がまだ読み取られているので、")*"はまだ読み込まれている）と再帰的にchainを呼び出します。この再帰呼び出しでは、lineが空文字列に設定され、branchはEmptyに設定され、cont行は再びchainへの再帰呼び出しを引き起こし、無限ループになります。

代わりに、のは、木のlineを解析するパーサtreeを書いてみましょう：

tree = do 
    line <- many $ char '*' 

となりまし、必要に応じて括弧内のtree（左側用）：

mleft <- optionMaybe $ between (char '(') (char ')') tree 

左辺がない場合は右辺もできません（自分自身を説得してください！） - カッコ内に左辺がない木を書くtはまだ空でない右手を持っており、あなたはそれを行うことができません表示されます）ので、私たちは完成です：

case mleft of 
    Nothing -> return $ Node line Empty Empty 

左辺がある場合は、右を読みます手元側（空かもしれないが、それは大丈夫です）ツリーとノードを返す：

Just left -> do 
     right <- tree 
     return $ Node line left right 

全体のパーサは、次のようになります。

tree :: Parser Tree 
tree = do 
    line <- many $ char '*' 
    mleft <- optionMaybe $ between (char '(') (char ')') tree 
    case mleft of 
    Nothing -> return $ Node line Empty Empty 
    Just left -> do 
     right <- tree 
     return $ Node line left right 

とうまくいけば、あなたは何を期待します：

> parseTest tree "*" 
Node "*" Empty Empty 
> parseTest tree "***" 
Node "***" Empty Empty 
> parseTest tree "**(*)*" 
Node "**" (Node "*" Empty Empty) (Node "*" Empty Empty) 
> parseTest tree "****(**(**)*)**" 
Node "****" (Node "**" (Node "**" Empty Empty) 
    (Node "*" Empty Empty)) (Node "**" Empty Empty) 

このパーサだけ無視し、末尾の入力：私はあなたが必要と疑う

treeOnly :: Parser Tree 
treeOnly = tree <* eof