Статьи

Генерация байт-кода

Октябрь 25, 2018

В этом посте мы увидим, как генерировать байт-код для нашего языка. До сих пор мы видели, как создать язык для выражения того, что мы хотим, как проверить этот язык, как создать редактор для этого языка, но все же мы не можем фактически запустить код. Время это исправить. Благодаря компиляции для JVM наш код сможет работать на любых платформах. Это звучит довольно здорово для меня!

jvm_bytecode_write_your_own_compiler

Серия по созданию собственного языка

Предыдущие сообщения:

  1. Построение лексера
  2. Сборка парсера
  3. Создание редактора с подсветкой синтаксиса
  4. Создайте редактор с автозаполнением
  5. Отображение дерева разбора на абстрактное синтаксическое дерево
  6. Преобразование модели в модель
  7. Проверка

Код доступен на GitHub под тегом 08_bytecode

Добавление выписки

Прежде чем перейти к генерации байт-кода, давайте просто добавим оператор печати к нашему языку. Это довольно просто: нам просто нужно изменить несколько строк в определениях лексера и парсера, и мы готовы идти дальше.

1
2
3
4
5
6
7
8
9
// Changes to lexer
PRINT              : 'print';
  
// Changes to parser
statement : varDeclaration # varDeclarationStatement
          | assignment     # assignmentStatement
          | print          # printStatement ;
  
print : PRINT LPAREN expression RPAREN ;

Общая структура нашего компилятора

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

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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()
}

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

Использование ASM для генерации байт-кода

Теперь давайте погрузимся в забавную часть. Метод компиляции JvmCompiler — это место, где мы производим байты, которые позже мы сохраним в файле класса. Как мы производим эти байты? С некоторой помощью ASM, которая является библиотекой для создания байт-кода. Теперь мы можем сами сгенерировать массив байтов, но дело в том, что он будет включать в себя некоторые скучные задачи, такие как генерация структур классов ASM делает это для нас. Нам все еще нужно иметь некоторое представление о том, как устроена JVM, но мы можем выжить, не будучи экспертами в мельчайших деталях.

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
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()
    }
  
}

О типах

Хорошо, мы видели, что наш код использует типы. Это необходимо, потому что в зависимости от типа нам нужно использовать разные инструкции. Например, чтобы поместить значение в целочисленную переменную, мы используем ISTORE, а для помещения значения в двойную переменную мы используем DSTORE . Когда мы вызываем System.out.println для целого числа, нам нужно указать сигнатуру (I) V, а когда мы вызываем его для печати двойного числа, мы указываем (D) V.

Для этого нам нужно знать тип каждого выражения. В нашем супер, супер простом языке мы сейчас используем только int и double . На реальном языке мы можем захотеть использовать больше типов, но этого будет достаточно, чтобы показать вам принципы.

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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)
    }
}

Выражения

Как мы уже видели, JVM — это стековая машина. Поэтому каждый раз, когда мы хотим использовать значение, мы помещаем его в стек, а затем выполняем некоторые операции. Давайте посмотрим, как мы можем поместить значения в стек

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
// 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

Мы также можем создать задачу gradle для компиляции исходных файлов.

1
2
3
4
    main = "me.tomassetti.sandy.compiling.JvmKt"
    args = "$sourceFile"
    classpath = sourceSets.main.runtimeClasspath
}

Выводы

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

Ссылка: Генерация байт-кода от нашего партнера JCG
61
Share: