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，秒差距的过程是这样的：

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 - 以及解析单个数字，字符串和括号表达式的单个文件。expr的递归调用现在可以 - expr内部的调用仅在您解析了term（总是消耗输入）并且term内部的调谐发生在您解析了左括号后才发生。

请注意，expr有一个类似列表的结构：它解析一个单一的东西可能后面有很多事情。一般而言，您应该考虑使用线性输入流的输入令牌的解析器，因此列表形解析器往往比树形解析器更有效也就不足为奇了。

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

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

Answer 2

的类型是骗你：当你定义一个递归解析器p，你没有真正允许使用p本身，无论你想要的！您需要首先输入部分输入内容，以确保您正在取得进展。否则，Haskell确实会很乐意进入一个无限循环。

这个问题一般通过定义表达式的不同“层”来解决，只允许“简单”或括号 - 在左递归位置中包含“更复杂”的一个（因为匹配一个开括号会迫使你使通过部分输入字符串的方式）。

E.g.为您的表达式语法就会变成（从最简单到最复杂的）：

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

这是一个总的语言眼前一亮：因为类型必须是当它涉及到终端完全诚实的，就根本不可能编写这些表现不好的左递归分析器。 typechecker告诉你，你必须找到另一种方式来识别你的语言条款。

例如在不动点组合子fix我在总解析器组合库的使用不具有类型(a -> a) -> a而是（忽略搞笑括号内）(□ a → a) → a这正是阻止你使用递归调用你已经取得了一些进展之前。你仍然可以写一个parser for Expr，但类型检测者在这里警告你当你非法移动。