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

Question

我正在使用 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" 它只是 returns Right (N 5)，它应该 return Mult(N 5) (N 5)。由于 arithParser 中的优先级。但是，如果我更改顺序，它似乎会进入无限循环并崩溃。

不确定我在这里做错了什么，我们将不胜感激。

Answer 1

Parsec 在尝试 <|> 的左选项之前先尝试右选项。如果左边的选择成功，那么它就不会理会右边的选择。所以在这种情况下，当输入 5*5 时，Parsec 的过程如下所示：

尝试V <$> strParser。 strParser 以 tok "\"" 开头，但输入字符串不是以 '"' 开头，因此 strParser 失败。
尝试N <$> numParser。 numParser 成功解析数字 5，所以 Parsec 只是 returns N 5.
完成！无需尝试第三种选择。

所以我们可以尝试通过将 Mult 选项移到顶部来修补此解析器，将其包裹在 try 中，以便它可以回溯并尝试 numParser 或 strParser 如果输入结果不是乘法。

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

这个解析器还有另一个更微妙的问题。让我们按照上面的步骤走一遍。

尝试try (Mult <$> arithParser <* tok "*" <*> arithParser)。此解析器以 arithParser 开头，因此递归调用 arithParser.
尝试try (Mult <$> arithParser <* tok "*" <*> arithParser)。此解析器以 arithParser 开头，因此递归调用 arithParser.
尝试try (Mult <$> arithParser <* tok "*" <*> arithParser)。此解析器以 arithParser 开头，因此递归调用 arithParser.
...

这是一个无限循环。 Parsec 无法处理左递归文法。您必须设计解析器，使其在递归调用之前至少使用一个标记。一种常见的做法是 "flatten out" 你的语法：

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 - 一个 term 可选地后跟一个乘法符号和一个被乘数 expr - 一个解析单个 terms - 数字、字符串和带括号的表达式。对 expr 的递归调用现在可以了 - expr 中的调用仅在您解析了 term（它始终消耗输入）并且 term 中的调用发生后才会发生只有在你解析了左括号之后。

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

Text.Megaparsec.Expr 模块包含封装此模式并解析具有任意优先级和固定规则的表达式的函数。

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

Answer 2

类型在骗你：当你定义一个递归解析器 p 时，你实际上不允许在任何你想使用的地方使用 p 本身！你需要先咀嚼部分输入，以保证你正在取得进步。否则Haskell确实会愉快地陷入死循环。

这个问题通常通过定义不同的 "tiers" 表达式来解决，并且在左递归位置只允许 "simpler" 表达式或圆括号包裹的 "more complex" 表达式（因为匹配一个开括号确实会迫使您通过输入字符串的一部分。

例如您的表达式的语法将变成（从最简单到最复杂）：

<Literal> ::= [0-9]+
<Var>     ::= [a-zA-Z]+
<Base>    ::= '(' <Expr> ')' | <Var> | <Literal>
<Factor>  ::= <Base> | <Base> '*' <Factor>
<Expr>    ::= <Factor> | <Factor> '+' <Expr> | <Factor> '-' <Expr>

这就是整体语言的闪光点：因为类型在终止时必须完全诚实，所以编写这些行为不佳的左递归解析器实际上是不可能的。类型检查器告诉您必须找到另一种方法来识别您的语言术语。

例如定点组合器 fix I use in my total parser combinators library doesn't have type (a -> a) -> a but rather (ignoring the funny brackets) (□ a → a) → a which precisely prevents you from using the recursive call before you've made some progress. You can still write a parser for Expr 但类型检查器会在您进行非法移动时警告您。

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

Megaparsec: Unable to parse recursive arithmetic string

haskell

megaparsec