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现在可以正常 - expr只有在你解析了一个term(它总是消耗输入)并且term只有在你解析了一个左括号之后才会发生内部的一个.

请注意,它expr具有类似列表的结构:它解析一个可能后跟很多东西的东西.一般来说,您应该考虑解析器使用输入令牌的线性输入流,因此列表形解析器往往比树形解析器更有效并不奇怪.

该Text.Megaparsec.Expr模块包含打包此模式的函数,并使用任意优先级和固定规则解析表达式.

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