7

我正在使用 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 中的优先级。但是，如果我更改顺序，那么它似乎会进入无限循环并崩溃。

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

4

2 回答 2

11

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

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

因此，我们可以尝试通过将Mult选项向上移动到顶部来修补此解析器，包裹在 a 中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只有在你解析了 a term（它总是消耗输入）之后才会发生，而里面的调用只有在你term解析了一个左括号之后才会发生。

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

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

expr = makeExprParser term [[InfixR $ tok "*" $> Mult]]
于 2017-04-08T19:25:27.190 回答
1

这些类型在骗你：当你定义一个递归解析器时p，你实际上不允许在p任何你想要的地方使用它自己！您需要先咀嚼部分输入，以保证您正在取得进展。否则 Haskell 确实会很高兴地进入无限循环。

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

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

<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 编写解析器，但类型检查器会在您进行非法移动时向您发出警告。

于 2017-07-04T23:28:21.323 回答