このParsecパーサはなぜ無限ループに入るのですか？

Question

次のパーサーは、任意の入力に対して無限ループを入力します。

data Ast 
    = Number Int 
    | Identifier String 
    | Operation Ast BinOp Ast 
    deriving (Show, Eq) 

data BinOp = Plus | Minus 
    deriving (Show, Eq, Enum) 

number = Number <$> read <$> many1 digit 

identifier = Identifier <$> many1 letter 

operator = choice $ mkParser <$> [(Plus, '+'), (Minus, '-')] 
    where mkParser (f, c) = f <$ char c 

operation = Operation <$> ast <*> operator <*> ast 

ast :: Parser Ast 
ast = operation <|> number <|> identifier 

問題は操作パーサーのどこかにあります。私はそれが代替構文解析に関係していると仮定しますが、私はそれを理解しません。

問題の原因を説明できますか？

ありがとうございます！

Answer 1

問題は実際に無限再帰にあります。 astパーサは、最初にoperationパーサーを呼び出します。しかし、operationパーサーはastを再度呼び出します。等々。 <*>解析の演算子もパーサーを実行します。 <|>との相違点の説明：<*><|>が最初のパーサーを実行するかどうかを順番にパーサーを1つずつ順番に実行し、失敗した場合にのみ2番目に実行します。

operation = Operation <$> ast <*> operator <*> ast 
ast  = operation <|> number <|> identifier 

基本的に、パーサーを並べ替えても、アプローチは機能しません。説明については、この回答を参考にしてください。Megaparsec: Not able to parse arithmetic string