主页 / coding / 问题 / 78342257
Accepted
n0nsense
Asked: 2024-04-17 23:44:10 +0800 CST

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

  • 772

我正在尝试使用我自己在 Haskell 中手写的解析器组合库来解析表达式。我已经可以使用在 dhall 项目中找到的下面的代码来解析二进制表达式，但我没有正确理解它。

这就是我定义表达式的方式：

data Expression
  = BinaryOperation Expression Operator Expression
  | UnaryOperation Operator Expression
  deriving (Show, Eq)

这是我从 dhall 项目中获取的函数。你可以在这里阅读更多 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 代码，但似乎此代码消耗了输入，并且不允许优先级较低的解析器完成其工作。例如+2 + 2将成为+2解析器+ 2的剩余字符串。

makeOperatorUnary :: Parser Operator -> Parser Expression -> Parser Expression
makeOperatorUnary parseOperator parseValue = do
  operator <- parseOperator
  value <- parseValue
  pure $ UnaryOperation operator value

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

谢谢

parsing

1 个回答

  1. Best Answer

    组合器的工作方式是makeOperator，您为它提供一个解析器，parseOperator用于解析您感兴趣的一组相等优先级、左关联二元运算符（例如，相同优先级的二元运算符），以及一个解析器，+用于解析位于更高的优先级（例如，乘法和除法），并且它通过将每个优先级表达式解析为由当前优先级的运算符连接的自包含单元来实现优先级。-parseValueparseValueparseOperator

    因此，要解析二进制文件+和-表达式，您需要使用以下内容：

    parseAddSub :: Parser Expression
parseAddSub = makeOperator parseBinaryPlusOrMinusOperator parseMulDiv

    whereparseBinaryPlusOrMinusOperator负责解析+和-运算符，并且parseMulDiv是下一个最高优先级表达式解析器，它将确保1*2和被解析为单元，因此当在表达式 中3*4加入 by 时，结果将最终等于，正确实现优先。+1*2+3*4(1*2)+(3*4)

    你的makeOperatorUnary组合器是相似的。它需要一个解析器来解析感兴趣的一元运算符，例如-，然后它需要一个解析器来解析更高优先级的表达式。这意味着如果你写：

    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"
    • 0

相关问题