Generación de código para el compilador en Haskell

Question

Estoy escribiendo un compilador para un lenguaje pequeño e imperativo. El idioma de destino es bytecode de Java, y el compilador se implementa en Haskell.

He escrito un frontend para el idioma, es decir, tengo un lexer, un analizador y un contador de letras. Tengo problemas para averiguar cómo hacer la generación de código.

Guardo una estructura de datos que representa la pila de variables locales. Puedo consultar esta estructura con el nombre de una variable local y obtener su posición en la pila. Esta estructura de datos se transmite a medida que recorro el árbol de sintaxis, y las variables se abren y se presionan al ingresar y salir de nuevos ámbitos.

Lo que tengo problemas para averiguar es cómo emitir el bytecode. Emisión de cadenas en los terminales y la concatenación de ellas en los niveles superiores parece una mala solución, tanto claridad- y en cuanto al rendimiento.

tl; dr ¿Cómo puedo emitir bytecode mientras muevo el árbol de sintaxis?

Answer 1

Mi primer proyecto en Haskell hace unos meses era escribir un compilador C, y lo que resultó fue un enfoque bastante ingenuo como para la generación de código, lo que voy a caminar por aquí. Por favor, haga no toman esto como un ejemplo de buen diseño para un generador de código, sino más bien lo ven como una manera rápida y sucia (y en última instancia ingenuo) para conseguir algo que funciona bastante rápidamente con un rendimiento decente.

empecé mediante la definición de una representación intermedia LIR (Intermedio Bajo Representación), que estrechamente correspondió al conjunto de instrucciones (x86_64 en mi caso):

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) 

Después vino una mónada que se ocuparía de intercalado de Estado en todo el traducción (yo estaba felizmente inconscientes de nuestro amigo el State Monad -en el tiempo):

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') 

junto con el estado que serían 'rosca' a través de las distintas fases de traducción:

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) 
    } 

Para mayor comodidad, también especifica una serie de funciones monádicos traductor, por ejemplo:

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

Entonces procedí a recursivamente patrón-fósforo mi AST, fragmento por fragmento, resultando en muchos funciones de la forma:

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)) 

(para la traducción de un bloque de código de la lengua de destino) o

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

(para la traducción de una llamada de método) o

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 

para un ejemplo de generar realmente algún código LIR. Espero que estos tres ejemplos te den un buen punto de partida; en última instancia, querrás ir despacio, centrándote en un fragmento (o tipo intermedio) dentro de tu AST a la vez.

Answer 2

Si no ha hecho esto antes, puede hacerlo en pequeños pasos: 1) para cada declaración producir algún código de bytes (con fuera abordado adecuadamente las posiciones de memoria) 2) después de que se hace, si tiene bucle, gotos, etc., ingrese las direcciones reales (ya las conoce ahora que lo tiene todo) 3) reemplace las ubicaciones/almacenes de memoria con las ubicaciones correctas 4) cárguelo en un archivo JAR

Tenga en cuenta que esto es muy simplificado y no trata de hacer cualquier optimización del rendimiento. Le dará un programa funcional que se ejecutará. Esto también supone que conoce los códigos para la JVM (que es donde estoy suponiendo que va a ejecutarlo.)

Para empezar, sólo hay un subconjunto del lenguaje que hace declaraciones aritméticas secuenciales. Esto le permitirá descubrir cómo asignar ubicaciones de memoria variable a las declaraciones a través del árbol de análisis sintáctico. A continuación, agregue algunos bucles para hacer que los saltos funcionen. Del mismo modo, agregue condicionales. Finalmente, puede agregar las partes finales de su idioma.