如何使用解析器组合器解析一元表达式？

Question

我正在尝试解析 Haskell 中的表达式。我已经可以使用在 dhall 项目中找到的下面的代码解析二进制表达式，但我没有正确理解它。这是：

makeOperator :: Parser Operator -> Parser Expression -> Parser Expression
makeOperator parseOperator parseValue = do
  l0 <- parseValue
  fs <- many do
    operator <- do
      _ <- wsP
      parseOperator
    _ <- wsP
    r <- parseValue
    pure $ \l -> BinaryOperation l operator r
  pure $ foldl (\l f -> f l) l0 fs

我尝试通过编写下面的代码来复制 dhall 代码，但似乎此代码消耗了输入，并且不允许优先级较低的解析器完成其工作。

makeOperatorUnary :: Parser Operator -> Parser Expression -> Parser Expression
makeOperatorUnary parseOperator parseValue = UnaryOperation <$> parseOperator <*> parseValue

如果有人能解释 dhall 代码的确切工作原理并引导我走向正确的方向，我会很高兴。

谢谢你

Answer 1

makeOperator

组合器的工作方式，您为它提供一个解析器

parseOperator

，用于您感兴趣的一组相等优先级、左关联二元运算符（例如，

+

和

-

同时使用二元运算符）优先级），以及用于解析更高优先级级别的表达式（例如乘法和除法）的解析器

parseValue

，并且它通过将每个

parseValue

优先级表达式解析为连接的自包含单元来实现优先级由当前优先级的

parseOperator

运算符执行。

因此，要解析二进制

+

和

-

表达式，您需要使用类似以下内容：

parseAddSub :: Parser Expression
parseAddSub = makeOperator parseBinaryPlusOrMinusOperator parseMulDiv

其中

parseBinaryPlusOrMinusOperator

负责解析

+

和

-

运算符，而

parseMulDiv

是下一个最高优先级表达式解析器，它将确保

1*2

和

3*4

被解析为单位，因此当在表达式

+

中加入

1*2+3*4

时，结果将最终等于

(1*2)+(3*4)

，正确实现优先级。

您的

makeOperatorUnary

组合器类似。它需要一个用于感兴趣的一元运算符的解析器，例如

-

，然后它需要一个用于 higher 优先级表达式的解析器。这意味着如果你写：

parseUnaryMinus = makeOperatorUnary parseUnaryMinusOperator parseAddSub

那么你就会遇到问题了。如果您尝试解析

-3+4

，此版本的

parseUnaryMinus

将解析一元

-

运算符，然后将整个

3+4

表达式解析为更高优先级的

parseAddSub

表达式，这将给出

 的等价物-(3+4)

，这是错误的优先级。

您可能想在

parseAddSub

和

parseMulDiv

之间添加一元减号，如下所示：

parseAddSub = makeOperator parseBinaryPlusOrMinusOperator parseUnaryMinus

parseUnaryMinus = makeOperatorUnary parseUnaryMinusOperator parseMulDiv

parseMulDiv = ...

这将接受类似

1+-3*4

等价于

1+(-(3*4))

的内容，这可能就是您想要的。

您还需要

makeOperatorUnary

来 可选地 解析运算符，就像

parseAddSub

检查但不要求二进制

+

和

-

运算符一样。因此，不要尝试上面的定义，而是尝试：

makeOperatorUnary parseOperator parseValue
  =   UnaryOperation <$> parseOperator <*> parseValue
  <|> parseValue

这是一个没有空格处理的简化示例来说明设计：

import Data.Void
import Text.Megaparsec
import Text.Megaparsec.Char

type Parser = Parsec Void String

data UnaryOperator = UnaryMinus
  deriving (Show)

data Operator = Plus | Minus | Times | Divide
  deriving (Show)

data Expression
  = Literal Int
  | BinaryOperation Expression Operator Expression
  | UnaryOperation UnaryOperator Expression
  deriving (Show)

makeOperator :: Parser Operator -> Parser Expression -> Parser Expression
makeOperator parseOperator parseValue = do
  l0 <- parseValue
  fs <- many $ do
    operator <- do
      parseOperator
    r <- parseValue
    pure $ \l -> BinaryOperation l operator r
  pure $ foldl (\l f -> f l) l0 fs

makeUnaryOperator :: Parser UnaryOperator -> Parser Expression -> Parser Expression
makeUnaryOperator parseOperator parseValue
  =   UnaryOperation <$> parseOperator <*> parseValue
  <|> parseValue


parseAddSub, parseUnaryMinus, parseMulDiv, parseFactor :: Parser Expression

parseAddSub = makeOperator (Plus <$ char '+' <|> Minus <$ char '-') parseUnaryMinus

parseUnaryMinus = makeUnaryOperator (UnaryMinus <$ char '-') parseMulDiv

parseMulDiv = makeOperator (Times <$ char '*' <|> Divide <$ char '/') parseFactor

parseFactor = Literal . read <$> some digitChar
  <|> between (char '(') (char ')') parseAddSub

main = do
  parseTest parseAddSub "1+-2*3"