Haskell中编译器的代码生成

Question

我正在编写一个小型命令式语言的编译器.目标语言是Java字节码,编译器在Haskell中实现.

我已经写了一个语言的前端 - 即我有一个词法分析器,解析器和类型检查器.我无法弄清楚如何进行代码生成.

我保留了一个表示局部变量堆栈的数据结构.我可以使用局部变量的名称查询此结构并获取其在堆栈中的位置.当我遍历语法树时传递这个数据结构,并在我进入和退出新范围时弹出和推送变量.

我弄清楚的是如何发出字节码.在终端发出字符串并将它们连接在更高的级别似乎是一个糟糕的解决方案,无论是清晰度还是性能方面.

tl; dr如何在使用语法树时发出字节码？

Answer 1

几个月前，我在 Haskell 中的第一个项目是编写 ac 编译器，结果是一种相当幼稚的代码生成方法，我将在这里介绍它。请不要将此视为代码生成器良好设计的示例，而应将其视为一种快速而肮脏（最终是幼稚）的方法，以获得运行速度相当快且性能良好的东西。

我首先定义了一个与我的指令集（在我的例子中为 x86_64）紧密对应的中间表示 LIR（较低的中间表示）：

data LIRInst = LIRRegAssignInst LIRReg LIRExpr
             | LIRRegOffAssignInst LIRReg LIRReg LIRSize LIROperand
             | LIRStoreInst LIRMemAddr LIROperand
             | LIRLoadInst LIRReg LIRMemAddr
             | LIREnterInst LIRInt
             | LIRJumpLabelInst LIRLabel
             | LIRIfInst LIRRelExpr LIRLabel LIRLabel -- false, then true
             | LIRCallInst LIRLabel LIRLabel -- method label, return label
             | LIRCalloutInst String
             | LIRRetInst [LIRLabel] String -- list of successors, and the name of the method returning from
             | LIRLabelInst LIRLabel
             deriving (Show, Eq, Typeable)

State Monad接下来是一个 monad，它将在整个翻译过程中处理交错状态（当时我很高兴没有意识到我们的朋友）：

newtype LIRTranslator a = LIRTranslator
    { runLIR :: Namespace -> (a, Namespace) }

instance Monad LIRTranslator where
    return a = LIRTranslator (\s -> (a, s))
    m >>= f = LIRTranslator (\s ->
        let (a, s') = runLIR m s
        in runLIR (f a) s')

以及将“线程”通过各个翻译阶段的状态：

data Namespace = Namespace
    { temp         :: Int                       -- id's for new temporaries
    , labels       :: Int                       -- id's for new labels
    , scope        :: [(LIRLabel, LIRLabel)]    -- current program scope
    , encMethod    :: String                    -- current enclosing method
    , blockindex   :: [Int]                     -- index into the SymbolTree
    , successorMap :: Map.Map String [LIRLabel]
    , ivarStack    :: [(LIRReg, [CFGInst])]     -- stack of ivars (see motioned code)
    }

为了方便起见，我还指定了一系列翻译器单元函数，例如：

-- |Increment our translator's label counter
incLabel :: LIRTranslator Int
incLabel = LIRTranslator (\ns@(Namespace{ labels = l }) -> (l, ns{ labels = (l+1) }))

然后，我继续逐个片段地递归地对 AST 进行模式匹配，产生了以下形式的许多函数：

translateBlock :: SymbolTree -> ASTBlock -> LIRTranslator [LIRInst]
translateBlock st (DecafBlock _ [] _) = withBlock (return [])
translateBlock st block =
    withBlock (do b <- getBlock
                  let st' = select b st
                  declarations <- mapM (translateVarDeclaration st') (blockVars block)
                  statements <- mapM (translateStm st') (blockStms block)
                  return (concat declarations ++ concat statements))

（用于翻译目标语言代码块）或

-- | Given a SymbolTree, Translate a single DecafMethodStm into [LIRInst]
translateStm st (DecafMethodStm mc _) =
    do (instructions, operand) <- translateMethodCall st mc
       final <- motionCode instructions
       return final

（用于翻译方法调用）或

translateMethodPrologue :: SymbolTree -> DecafMethod -> LIRTranslator [LIRInst]
translateMethodPrologue st (DecafMethod _ ident args _ _) =
    do let numRegVars = min (length args) 6
           regvars = map genRegVar (zip [LRDI, LRSI, LRDX, LRCX, LR8, LR9] args)
       stackvars <- mapM genStackVar (zip [1..] (drop numRegVars args))
       return (regvars ++ stackvars)
  where
    genRegVar (reg, arg) =
        LIRRegAssignInst (symVar arg st) (LIROperExpr $ LIRRegOperand reg)
    genStackVar (index, arg) =
        do let mem = LIRMemAddr LRBP Nothing ((index + 1) * 8) qword -- ^ [rbp] = old rbp; [rbp + 8] = ret address; [rbp + 16] = first stack param
                                  return $ LIRLoadInst (symVar arg st) mem

有关实际生成一些 LIR 代码的示例。希望这三个例子能给您一个良好的起点；最终，您需要慢慢地进行，一次专注于 AST 中的一个片段（或中间类型）。