Megaparsec：无法解析递归算术字符串

我正在使用 Megaparsec 开发一个小型解析器并尝试解析算术。

-- Arithmetic expressions
data Aexp = N Num 
            | V Var 
            | Mult Aexp Aexp
            | Add Aexp Aexp 
            | Sub Aexp Aexp 
             deriving (Show, Eq, Read)


arithParser :: Parser Aexp
arithParser = V <$> strParser
            <|> N <$> numParser
            <|> Mult <$> arithParser <* tok "*" <*> arithParser
--boolParser :: Parser Bexp


strParser :: Parser Var
strParser = tok "\"" *> some (noneOf ("\n\r\"=[]{},:")) <* tok "\""

numParser :: Parser Num
numParser = (some (oneOf ['0' .. '9']) >>= return . read) <* whitespace

如果我运行命令Parse arithParser "5*5" "5*5"它只是返回Right (N 5)，它应该返回的地方Mult(N 5) (N 5)。因为 arithParser 中的优先级。但如果我改变顺序，它似乎会进入无限循环并崩溃。

不确定我在这里做错了什么，任何帮助将不胜感激。

秒差距尝试左边的替代方案<|>在它尝试正确的方法之前。如果左边的选择成功了，那么它就不会再打扰右边的选择了。所以在这种情况下，当输入输入时5*5，Parsec 的过程如下所示：

1. Try V <$> strParser. strParser开始于tok "\""，但输入字符串不以'"' so strParser fails.
2. Try N <$> numParser. numParser成功解析数字 5，因此 Parsec 只是返回N 5.
3. 完毕！无需尝试第三种选择。

所以我们可以尝试通过移动来修补这个解析器Mult选项到顶部，包裹在try这样它就可以回溯并尝试numParser or strParser如果输入结果不是乘法。

arithParser :: Parser Aexp
arithParser = try (Mult <$> arithParser <* tok "*" <*> arithParser)
            <|> N <$> numParser
            <|> V <$> strParser

这个解析器还有另一个更微妙的问题。让我们逐步完成上述步骤。

1. Try try (Mult <$> arithParser <* tok "*" <*> arithParser)。这个解析器开始于arithParser，所以递归调用arithParser.
2. Try try (Mult <$> arithParser <* tok "*" <*> arithParser)。这个解析器开始于arithParser，所以递归调用arithParser.
3. Try try (Mult <$> arithParser <* tok "*" <*> arithParser)。这个解析器开始于arithParser，所以递归调用arithParser.
4. ...

这是一个无限循环。 Parsec 无法处理左递归语法。您必须设计您的解析器，以便它在递归调用之前至少消耗一个标记。一种常见的方法是“扁平化”你的语法：

expr, term :: Parser AExp
expr = do
    n <- term
    rest <- optional $ tok "*" *> expr
    return $ maybe n (Mult n) rest
term = N <$> numParser
    <|> V <$> strParser
    <|> parenthesised expr

parenthesised = between (char '(') (char ')')

在这里，我将解析器分成一个解析任意的expr - a term可选地后跟乘法符号和被乘数expr- 以及一个解析单个的terms - 数字、字符串和括号表达式。递归调用expr现在还好 - 里面的那个expr仅在您解析之后才会发生term（总是消耗输入）和里面的term仅在解析左括号后才会发生。

注意expr具有类似列表的结构：它解析一个事物，可能后面跟着很多事物。一般来说，您应该考虑解析器消耗输入标记的线性输入流，因此列表形解析器往往比树形解析器更有效也就不足为奇了。

The Control.Monad.Combinators.Expr https://hackage.haskell.org/package/parser-combinators-1.3.0/docs/Control-Monad-Combinators-Expr.html模块包含打包此模式并以任意优先级和固定规则解析表达式的函数。

expr = makeExprParser term [[InfixR $ tok "*" $> Mult]]