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"，它只返回Right (N 5)，在那里它应该返回Mult(N 5) (N 5)。因为arithParser中的优先级。但是，如果我改变顺序，它似乎进入一个无限循环并崩溃。

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

Answer 1

Parsec先尝试<|>的左选项，然后再尝试右边的选项。如果左边的选择成功了，那么它就不会为右边的选择费心了。因此，在本例中，当输入5*5时，Parsec的流程如下所示：

1. 试试V <$> strParser。strParser以tok "\""开头，但输入字符串不以'"'开头，因此strParser失败。
2. 试试N <$> numParser。numParser成功地解析了数字5，所以Parsec只返回N 5。
3. 完成了！没有必要尝试第三种选择。

因此，我们可以尝试修补这个解析器，方法是将Mult选项移到顶部，包装在一个try中，这样如果输入结果不是乘法，它就可以回溯并尝试numParser或strParser。

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

这个解析器还有另一个更微妙的问题。让我们走完这些台阶，就像上面一样。

1. 试试try (Mult <$> arithParser <* tok "*" <*> arithParser)。这个解析器以arithParser开头，因此递归地调用arithParser。
2. 试试try (Mult <$> arithParser <* tok "*" <*> arithParser)。这个解析器以arithParser开头，因此递归地调用arithParser。
3. 试试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的解析器--一个可选的term后面跟着一个乘法符号和一个乘法和expr --以及一个解析单个terms --数字、字符串和括号表达式的解析器。现在，对expr的递归调用是可以的--只有在解析了term (它总是使用输入)之后，expr中的调用才会发生，而term中的调用只有在解析了括号后才会发生。

请注意，expr有一个类似列表的结构:它解析单个事物，可能后面跟着很多东西。通常，您应该考虑解析器使用输入令牌的线性输入流，因此列表型解析器往往比树型解析器更有效，这并不奇怪。

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

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

Answer 2

这些类型都在欺骗您:当您定义递归解析器p时，实际上不允许您在任何地方使用p本身！您需要先咀嚼部分输入，以保证您正在取得进展。否则，哈斯克尔会很高兴地进入一个无限的循环。

这个问题通常通过定义不同的表达式“层”来解决，并且只允许在左侧递归位置使用“简单”或括号包装的“更复杂的”表达式(因为匹配打开的括号确实会迫使您通过部分输入字符串)。

例如，表达式的语法将转化为(从最简单到最复杂)：

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

这就是整个语言的闪光点:因为类型在终止时必须是完全诚实的，因此编写这些行为糟糕的左递归解析器几乎是不可能的。打字员告诉你，你必须找到另一种方式来识别你的语言的术语。

例如，我在总解析器组合器库中使用的不动点组合器修复没有(a -> a) -> a类型，而是(忽略有趣的括号) (□ a → a) → a类型，这正好阻止您在取得一些进展之前使用递归调用。您仍然可以编写一个Expr解析器，但打字机在这里警告您时，您是非法的行动。