haskell - 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 的流程是这样的:

试试 V <$> strParser . strParser以 tok "\"" 开头，但输入字符串不以 '"' 开头所以strParser失败。

试试 N <$> numParser . numParser成功解析数字 5，因此 Parsec 只返回 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 无法处理左递归语法。您必须设计解析器，使其在递归调用之前至少消耗一个 token 。一种常见的方法是“扁平化”你的语法:

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 - 一个解析单个 term s - 数字、字符串和带括号的表达式。对 expr 的递归调用现在可以了——里面的那个 expr只有在你解析了 term 之后才会发生(它总是消耗输入)和里面的一个 term只有在你解析了一个左括号之后才会发生。

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

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

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