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的代碼（這是我假設你將要執行的代碼）。

要開始，只需要一部分執行順序算術語句的語言。這將允許您弄清楚如何通過分析樹映射變量內存位置到語句。接下來添加一些循環讓跳轉工作。同樣添加條件。最後，你可以添加你的語言的最後部分。