主页 / user-16362086

n0nsense's questions

Martin Hope
NotAlfred
Asked: 2024-04-25 01:23:18 +0800 CST
  • 5

所以这个问题可能看起来太新手了，但我已经在读 Steven Muchnick 的《高级编译器设计和实现》一书，在优化的第一章中它讨论了常量折叠。

第一次尝试如下所示，但考虑到它需要类型类Integral和Bits.

data Value
  = BoolV Bool
  | IntegerV Integer
  | FloatV Double
  | StringV String
  deriving (Show, Eq)

data Expression
  = Const Value
  | Temp Label
  | List [Expression]
  | Call Label [Expression]
  | BinOp Operator Expression Expression
  deriving (Show, Eq)

rerunOverIR :: Expression -> Expression
rerunOverIR = \case
  Const constant -> Const constant
  Temp temporary -> Temp temporary
  List list -> List list
  Call label args -> Call label (map rerunOverIR args)
  BinOp operator lhs rhs ->
    case operator of
      Addition -> folder (+)
      Subtraction -> folder (-)
      Multiplication -> folder (*)
      Modulo -> folder mod
      Division -> folder div
      BitwiseAnd -> folder (.&.)
      BitwiseOr -> folder (.|.)
      BitwiseXor -> folder xor
      ShiftRight -> folder shiftR
      ShiftLeft -> folder shiftL
      Equal -> folder (==)
      NotEqual -> folder (/=)
      Greater -> folder (>)
      GreaterEqual -> folder (>=)
      Less -> folder (<)
      LessEqual -> folder (<=)
      LogicalAnd -> folder (&&)
      LogicalOr -> folder (||)
      _ -> error $ "this operator doesn't exist " ++ show operator
    where
      folder op =
        case lhs of
          Const c1 -> case rhs of
            Const c2 -> Const $ op c1 c2
            expr -> rerunOverIR $ BinOp operator (Const c1) (rerunOverIR expr)
          e1 -> case rhs of
            Const c2 -> rerunOverIR $ BinOp operator (rerunOverIR e1) (Const c2)
            e2 -> rerunOverIR $ BinOp operator (rerunOverIR e1) (rerunOverIR e2)

所以我这次尝试将表达式更改为下面的，但情况更糟。

data Expression
  = Bool Bool
  | Integer Integer
  | Float Double
  | String String
  | Temp Label
  | List [Expression]
  | Call Label [Expression]
  | BinOp Operator Expression Expression
  deriving (Show, Eq)

所以我的问题是，用 Haskell 编写的编译器或解释器如何在后期正确处理常量折叠？我很确定我走错了路......

haskell
Martin Hope
n0nsense
Asked: 2024-04-17 23:44:10 +0800 CST
  • 6

我正在尝试使用我自己在 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