Written by Federico Tomassetti
in Language Engineering

    Adding a print statement

    Before jumping in the bytecode generation let’s just add a print statement to our language. It is fairly easy: we just need to change a few lines in the lexer and parser definitions and we are good to go.

    // Changes to lexer
    PRINT              : 'print';
    
    // Changes to parser
    statement : varDeclaration # varDeclarationStatement
              | assignment     # assignmentStatement
              | print          # printStatement ;
    
    print : PRINT LPAREN expression RPAREN ;

    The general structure of our compiler

    Let’s start from the entry point for our compiler. We will either take the code from the standard input or from a file (to be specified as the first parameter). Once we get the code we try to build an AST and check for lexical and syntactical errors. If there are none we validate the AST and check for semantic errors. If still we have no errors we go on with the bytecode generation.

    fun main(args: Array<String>) {
        val code : InputStream? = when (args.size) {
            0 -> System.`in`
            1 -> FileInputStream(File(args[0]))
            else -> {
                System.err.println("Pass 0 arguments or 1")
                System.exit(1)
                null
            }
        }
        val parsingResult = SandyParserFacade.parse(code!!)
        if (!parsingResult.isCorrect()) {
            println("ERRORS:")
            parsingResult.errors.forEach { println(" * L${it.position.line}: ${it.message}") }
            return
        }
        val root = parsingResult.root!!
        println(root)
        val errors = root.validate()
        if (errors.isNotEmpty()) {
            println("ERRORS:")
            errors.forEach { println(" * L${it.position.line}: ${it.message}") }
            return
        }
        val bytes = JvmCompiler().compile(root, "MyClass")
        val fos = FileOutputStream("MyClass.class")
        fos.write(bytes)
        fos.close()
    }

    Note that in this example we are always producing a class file named MyClass. Probably later we would like to find a way to specify a name for the class file, but for now this is good enough.

    Using ASM to generate bytecode

    Now, let’s dive in the funny part. The compile method of JvmCompiler is where we produce the bytes that later we will save into a class file. How do we produce those bytes? With some help from ASM, which is a library to produce Bytecode. Now, we could generate the bytes array ourselves, but the point is that it would involve some boring tasks like generating the classpool structures. ASM does that for us. We still need to have some understanding of how the JVM is structured but we can survive without being experts on the nitty-gritty details.

    class JvmCompiler {
    
        fun compile(root: SandyFile, name: String) : ByteArray {
            // this is how we tell ASM that we want to start writing a new class. We ask it to calculate some values for us
            val cw = ClassWriter(ClassWriter.COMPUTE_FRAMES or ClassWriter.COMPUTE_MAXS)
            // here we specify that the class is in the format introduced with Java 8 (so it would require a JRE >= 8 to run)
            // we also specify the name of the class, the fact it extends Object and it implements no interfaces
            cw.visit(V1_8, ACC_PUBLIC, name, null, "java/lang/Object", null)
            // our class will have just one method: the main method. We have to specify its signature
            // this string just says that it takes an array of Strings and return nothing (void)
            val mainMethodWriter = cw.visitMethod(ACC_PUBLIC or ACC_STATIC, "main", "([Ljava/lang/String;)V", null, null)
            mainMethodWriter.visitCode()
            // labels are used by ASM to mark points in the code
            val methodStart = Label()
            val methodEnd = Label()
            // with this call we indicate to what point in the method the label methodStart corresponds
            mainMethodWriter.visitLabel(methodStart)
    
            // Variable declarations:
            // we find all variable declarations in our code and we assign to them an index value
            // our vars map will tell us which variable name corresponds to which index
            var nextVarIndex = 0
            val vars = HashMap<String, Var>()
            root.specificProcess(VarDeclaration::class.java) {
                val index = nextVarIndex++
                vars[it.varName] = Var(it.type(vars), index)
                mainMethodWriter.visitLocalVariable(it.varName, it.type(vars).jvmDescription, null, methodStart, methodEnd, index)
            }
    
            // time to generate bytecode for all the statements
            root.statements.forEach { s ->
                when (s) {
                    is VarDeclaration -> {
                        // we calculate the type of the variable (more details later)
                        val type = vars[s.varName]!!.type
                        // the JVM is a stack based machine: it operated with values we have put on the stack
                        // so as first thing when we meet a variable declaration we put its value on the stack
                        s.value.pushAs(mainMethodWriter, vars, type)
                        // now, depending on the type of the variable we use different operations to store the value
                        // we put on the stack into the variable. Note that we refer to the variable using its index, not its name
                        when (type) {
                            IntType -> mainMethodWriter.visitVarInsn(ISTORE, vars[s.varName]!!.index)
                            DecimalType -> mainMethodWriter.visitVarInsn(DSTORE, vars[s.varName]!!.index)
                            else -> throw UnsupportedOperationException(type.javaClass.canonicalName)
                        }
                    }
                    is Print -> {
                        // this means that we access the field "out" of "java.lang.System" which is of type "java.io.PrintStream"
                        mainMethodWriter.visitFieldInsn(GETSTATIC, "java/lang/System", "out", "Ljava/io/PrintStream;")
                        // we push the value we want to print on the stack
                        s.value.push(mainMethodWriter, vars)
                        // we call the method println of System.out to print the value. It will take its parameter from the stack
                        // note that we have to tell the JVM which variant of println to call. To do that we describe the signature of the method,
                        // depending on the type of the value we want to print. If we want to print an int we will produce the signature "(I)V",
                        // we will produce "(D)V" for a double
                        mainMethodWriter.visitMethodInsn(INVOKEVIRTUAL, "java/io/PrintStream", "println", "(${s.value.type(vars).jvmDescription})V", false)
                    }
                    is Assignment -> {
                        val type = vars[s.varName]!!.type
                        // This code is the same we have seen for variable declarations
                        s.value.pushAs(mainMethodWriter, vars, type)
                        when (type) {
                            IntType -> mainMethodWriter.visitVarInsn(ISTORE, vars[s.varName]!!.index)
                            DecimalType -> mainMethodWriter.visitVarInsn(DSTORE, vars[s.varName]!!.index)
                            else -> throw UnsupportedOperationException(type.javaClass.canonicalName)
                        }
                    }
                    else -> throw UnsupportedOperationException(s.javaClass.canonicalName)
                }
            }
    
            // We just says that here is the end of the method
            mainMethodWriter.visitLabel(methodEnd)
            // And we had the return instruction
            mainMethodWriter.visitInsn(RETURN)
            mainMethodWriter.visitEnd()
            mainMethodWriter.visitMaxs(-1, -1)
            cw.visitEnd()
            return cw.toByteArray()
        }
    
    }

    About types

    Ok, we have seen that our code use types. This is needed because depending on the type we need to use different instructions. For example to put a value in an integer variable we use ISTORE while to put a value in a double variable we use DSTORE. When we call System.out.println on an integer we need to specify the signature (I)V while when we call it to print a double we specify (D)V.

    To be able to do so we need to know the type of each expression. In our super, super simple language we use just int and double for now. In a real language we may want to use more types but this would be enough to show you the principles.

    interface SandyType {
        // given a type we want to get the corresponding string used in the JVM
        // for example: int -> I, double -> D, Object -> Ljava/lang/Object; String -> [Ljava.lang.String;
        val jvmDescription: String
    }
    
    object IntType : SandyType {
        override val jvmDescription: String
            get() = "I"
    }
    
    object DecimalType : SandyType {
        override val jvmDescription: String
            get() = "D"
    }
    
    fun Expression.type(vars: Map<String, Var>) : SandyType {
        return when (this) {
            // an int literal has type int. Easy :)
            is IntLit -> IntType
            is DecLit -> DecimalType
            // the result of a binary expression depends on the type of the operands
            is BinaryExpression -> {
                val leftType = left.type(vars)
                val rightType = right.type(vars)
                if (leftType != IntType && leftType != DecimalType) {
                    throw UnsupportedOperationException()
                }
                if (rightType != IntType && rightType != DecimalType) {
                    throw UnsupportedOperationException()
                }
                // an operation on two integers produces integers
                if (leftType == IntType && rightType == IntType) {
                    return IntType
                // if at least a double is involved the result is a double
                } else {
                    return DecimalType
                }
            }
            // when we refer to a variable the type is the type of the variable
            is VarReference -> vars[this.varName]!!.type
            // when we cast to a value, the resulting value is that type :)
            is TypeConversion -> this.targetType.toSandyType()
            else -> throw UnsupportedOperationException(this.javaClass.canonicalName)
        }
    }
    
    

    Expressions

    As we have seen the JVM is a stack-based machine. So every time we want to use a value we push it on the stack and then do some operations. Let’s see how we can push values into the stack

    // Convert, if needed
    fun Expression.pushAs(methodWriter: MethodVisitor, vars: Map<String, Var>, desiredType: SandyType) {
        push(methodWriter, vars)
        val myType = type(vars)
        if (myType != desiredType) {
            if (myType == IntType && desiredType == DecimalType) {
                methodWriter.visitInsn(I2D)
            } else if (myType == DecimalType && desiredType == IntType) {
                methodWriter.visitInsn(D2I)
            } else {
                throw UnsupportedOperationException("Conversion from $myType to $desiredType")
            }
        }
    }
    
    fun Expression.push(methodWriter: MethodVisitor, vars: Map<String, Var>) {
        when (this) {
            // We have specific operations to push integers and double values
            is IntLit -> methodWriter.visitLdcInsn(Integer.parseInt(this.value))
            is DecLit -> methodWriter.visitLdcInsn(java.lang.Double.parseDouble(this.value))
            // to push a sum we first push the two operands and then invoke an operation which
            // depend on the type of the operands (do we sum integers or doubles?)
            is SumExpression -> {
                left.pushAs(methodWriter, vars, this.type(vars))
                right.pushAs(methodWriter, vars, this.type(vars))
                when (this.type(vars)) {
                    IntType -> methodWriter.visitInsn(IADD)
                    DecimalType -> methodWriter.visitInsn(DADD)
                    else -> throw UnsupportedOperationException("Summing ${this.type(vars)}")
                }
            }
            is SubtractionExpression -> {
                left.pushAs(methodWriter, vars, this.type(vars))
                right.pushAs(methodWriter, vars, this.type(vars))
                when (this.type(vars)) {
                    IntType -> methodWriter.visitInsn(ISUB)
                    DecimalType -> methodWriter.visitInsn(DSUB)
                    else -> throw UnsupportedOperationException("Summing ${this.type(vars)}")
                }
            }
            is DivisionExpression -> {
                left.pushAs(methodWriter, vars, this.type(vars))
                right.pushAs(methodWriter, vars, this.type(vars))
                when (this.type(vars)) {
                    IntType -> methodWriter.visitInsn(IDIV)
                    DecimalType -> methodWriter.visitInsn(DDIV)
                    else -> throw UnsupportedOperationException("Summing ${this.type(vars)}")
                }
            }
            is MultiplicationExpression -> {
                left.pushAs(methodWriter, vars, this.type(vars))
                right.pushAs(methodWriter, vars, this.type(vars))
                when (this.type(vars)) {
                    IntType -> methodWriter.visitInsn(IMUL)
                    DecimalType -> methodWriter.visitInsn(DMUL)
                    else -> throw UnsupportedOperationException("Summing ${this.type(vars)}")
                }
            }
            // to push a variable we just load the value from the symbol table
            is VarReference -> {
                val type = vars[this.varName]!!.type
                when (type) {
                    IntType -> methodWriter.visitVarInsn(ILOAD, vars[this.varName]!!.index)
                    DecimalType -> methodWriter.visitVarInsn(DLOAD, vars[this.varName]!!.index)
                    else -> throw UnsupportedOperationException(type.javaClass.canonicalName)
                }
            }
            // the pushAs operation take care of conversions, as needed
            is TypeConversion -> {
                this.value.pushAs(methodWriter, vars, this.targetType.toSandyType())
            }
            else -> throw UnsupportedOperationException(this.javaClass.canonicalName)
        }
    }

    Gradle

    We can also create a gradle task to compile source files

    task compileSandyFile(type:JavaExec) {
        main = "me.tomassetti.sandy.compiling.JvmKt"
        args = "$sourceFile"
        classpath = sourceSets.main.runtimeClasspath
    }
    

    Conclusions

    We did not go in any detail and we sort of rush through the code. My goal here is just to give you an overview of what is the general strategy to use to generate bytecode. Of course if you want to build a serious language you will need to do some studying and understand the internals of the JVM, there is no escape from that. I just hope that this brief introduction was enough to show you that this is not as scarying or complicate and most people think.

    Download the guide with 68 resources on Creating Programming Languages

    Receive the guide to your inbox to read it on all your devices when you have time

    Powered by ConvertKit
     
    Creating a Programming Language

    Learn to Create Programming Languages

    Subscribe to our newsletter to get the FREE email course that teaches you how to create a programming language