Haskell编译器的代码生成

Question

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

我写了一个语言的前端 - 即我有一个词法分析器，解析器和类型检查器。我无法弄清楚如何做代码生成。

我保留一个数据结构来表示局部变量的堆栈。我可以用一个局部变量的名字查询这个结构并获得它在堆栈中的位置。当我走过语法树时，这个数据结构会被传递，随着我进入和退出新的作用域，变量会被弹出和推送。

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

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

Answer 1

几个月前，我在Haskell的第一个项目是编写一个c编译器，结果是一个相当幼稚的代码生成方法，我将在这里介绍。请做而不是将此作为代码生成器的良好设计示例，而是将其视为一种快速而肮脏（并且最终是天真）的方式，以便能够以相当快的速度运行，并且具有良好的性能。

我开始通过定义一个中间表示LIR（下中间表示），它紧密对应于我的指令集（在我的情况x86_64的）：

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 -at的时间）：

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中的一个片段（或中间类型）。

Answer 2

如果你还没有这样做之前，你能做到在小关： 1）每个语句产生一些字节码（以出妥善解决内存位置） 2）之后做到这一点，如果你有循环，gotos等，放在真实的地址（你知道他们现在已经把它们全部排好了） 3）用正确的位置替换内存提取/存储 4）将它转储到JAR文件

请注意，这是非常简化的，不会尝试做任何性能优化。它会给你一个执行的功能程序。这也假设你知道JVM的代码（这是我假设你将要执行的代码）。

要开始，只需要一部分执行顺序算术语句的语言。这将允许您弄清楚如何通过分析树映射变量内存位置到语句。接下来添加一些循环让跳转工作。同样添加条件。最后，你可以添加你的语言的最后部分。