Блог

Я пишу компилятор для небольшого императивного языка. Целевым языком является байт-код Java, а компилятор реализован на Haskell.

Я написал интерфейс для языка — то есть у меня есть лексер, анализатор и средство проверки типов. У меня возникли проблемы с пониманием того, как выполнять генерацию кода.

Я сохраняю структуру данных, представляющую стек локальных переменных. Я могу запросить эту структуру с именем локальной переменной и получить ее позицию в стеке. Эта структура данных передается по мере того, как я хожу по синтаксическому дереву, а переменные выталкиваются при входе в новые области и выходе из них.

С чем у меня возникли проблемы, так это с тем, как выдавать байт-код. Выдача строк на терминалах и объединение их на более высоких уровнях кажется плохим решением как с точки зрения ясности, так и с точки зрения производительности.

tl; dr Как мне выдавать байт-код при обработке синтаксического дерева?

Моим первым проектом в Haskell несколько месяцев назад было написание компилятора c, и результатом стал довольно наивный подход к генерации кода, о котором я расскажу здесь. Пожалуйста, не рассматривайте это как пример хорошего дизайна для генератора кода, а скорее рассматривайте это как быстрый и грязный (и в конечном счете наивный) способ получить что-то, что работает довольно быстро с приличной производительностью.

Я начал с определения промежуточного представления LIR (Lower Intermediate Representation), которое в точности соответствовало моему набору команд (в моем случае 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 ):

 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 за раз.

Если вы не делали этого раньше, вы можете сделать это небольшими проходами: 1) для каждого оператора создайте некоторый байтовый код (без правильно адресованных ячеек памяти) 2) после этого, если у вас есть циклирование, goto и т.д., Введите реальные адреса (вы их знаете теперь, когда у вас все разложено) 3) замените выборки / хранилища памяти правильными расположениями 4) выгрузите это в файл JAR

Обратите внимание, что это очень упрощено и не пытается выполнить какую-либо оптимизацию производительности. Это даст вам функциональную программу, которая будет выполняться. Это также предполагает, что вы знаете коды для JVM (я предполагаю, что именно там вы собираетесь ее выполнить.)

Для начала просто найдите подмножество языка, которое выполняет последовательные арифметические операции. Это позволит вам выяснить, как сопоставлять переменные ячейки памяти с операторами через дерево синтаксического анализа. Затем добавьте несколько циклов, чтобы заставить переходы работать. Аналогичным образом добавьте условные обозначения. Наконец, вы можете добавить заключительные части вашего языка.