18-12-19 プログラミング言語を作ろう（遅刻）

正直どこまで書くか無茶苦茶迷いました。

端折るためにかなりガバガバな作りです。（特にコンパイル部分）

前置き

宗教戦争（言語）の話から「いっそのこと自分で言語作って創始しようぜ」につなげる予定でしたが、その記事がなくなったので特に言うことはありません。

プログラミング言語の作り方

色々あるんですけど、今回は

1. 構文解析

2. ASTオブジェクト化

3. コンパイル、バイトコード生成

4. バイトコードロード

5. 実行

という流れで行きますです。

定義

これをしなくちゃ始まらない。

まずは文法。今回は一先ず

code: MyLang

func main() {

puts("Hello, World")

}

という文を実行できるようにしましょう。

トップレベルとmain関数のどちらにも式を許してしまうと、コードがとっちらかって美しくないので

トップレベルにはトップレベルオブジェクトのみを許可するようにします。

一先ずトップレベルオブジェクトは関数のみとします。

関数には任意個の式を許します。

式は関数呼び出しとリテラル（String）だけ。

間違っても標準出力だからといって専用の構文を用意しないようにしましょう（1敗）

以上のことからEBNFは

code: ebnf

program

: topLevelObject+

topLevelObject

: function

function

: "func" ID functionParameters block

functionParameters

: "(" ID{COMMA} ")"

functionCall

: ID "(" expression{COMMA} ")"

block

: "{" statements "}"

statements

: statement*

statement

: expression semi

expression

: literal

: block

: functionCall

literal

: stringLiteral

stringLiteral

: STRING

semi

: SEMI

: NL

STRING

: "\".*\""

ID

SEMI

: ";"

COMMA

: ","

NL

: "\\n"

で、ASTオブジェクトは

code: AST.kt

sealed class AST

data class Program(val program: List<AST>)

object Skip : AST()

data class Variable(val name: String) : AST()

data class StringNode(val value: String) : AST()

data class Block(val statements: List<AST>) : AST()

open class FunctionDeclaration(open val name: String, val parameters: List<AST>, val body: Block) : AST()

data class UnresolvedFunction(override val name: String, val paramSize: Int) : FunctionDeclaration(name, (0..paramSize).map { Skip }, Block(

emptyList()))

data class FunctionCall(val functionDeclaration: FunctionDeclaration, val parameters: List<AST>) : AST()

で！いいんじゃあないでしょうか

それじゃあ早速作っていきますよ！

作る

準備編

Intelli JのPluginでKotlin入れておいてください。

File>New>Project > Gradle > Kotlin(Java)にチェックを入れてNext

GroupIdとArtifactIdは自由で。わからない人はそれぞれ

でいいと思います。

後はそのままNext>Finishで大丈夫だと思います。プロジェクト名とか変えたい場合は自由で。

Gradleプロジェクトは無茶苦茶初期化長いので気長に待ってください。

code: build.gradle

plugins { id 'org.jetbrains.kotlin.jvm' version '1.3.11' }

group 'com.github.sobreera.myParser'

version '1.0-SNAPSHOT'

repositories {

mavenCentral()

}

dependencies {

compile "org.jetbrains.kotlin:kotlin-stdlib-jdk8"

implementation('com.github.h0tk3y.betterParse:better-parse-jvm:0.4.0-alpha-3')

implementation(group: 'org.ow2.asm', name: 'asm', version: '5.0.3')

}

compileKotlin { kotlinOptions.jvmTarget = "1.8" }

compileTestKotlin { kotlinOptions.jvmTarget = "1.8" }

実装編

AST>解析器>コンパイラの順で作っていきますよ。

ASTオブジェクト

code: AST.kt

sealed class AST

data class Program(val program: List<AST>)

object Skip : AST()

data class Variable(val name: String) : AST()

data class StringNode(val value: String) : AST()

data class Block(val statements: List<AST>) : AST()

open class FunctionDeclaration(open val name: String, val parameters: List<AST>, val body: Block) : AST()

data class UnresolvedFunction(override val name: String, val paramSize: Int) : FunctionDeclaration(name, (0..paramSize).map { Skip }, Block(

emptyList()))

data class FunctionCall(val functionDeclaration: FunctionDeclaration, val parameters: List<AST>) : AST()

構文解析器

とりあえずサクッとコードを

code: MyParser.kt

import com.github.h0tk3y.betterParse.combinators.*

import com.github.h0tk3y.betterParse.combinators.zeroOrMore

import com.github.h0tk3y.betterParse.grammar.Grammar

import com.github.h0tk3y.betterParse.grammar.parser

import com.github.h0tk3y.betterParse.parser.Parser

object MyParser : Grammar<Program>() {

private val STRING by token("\".*\"")

private val FUNC by token("func\\b")

private val LBRC by token("\\{")

private val RBRC by token("}")

private val LPAR by token("\\(")

private val RPAR by token("\\)")

private val COMMA by token(",")

private val SEMI by token(";")

private val NL by token("\\n", ignore = true)

private val WS by token("\\s", ignore = true)

private val semi by SEMI or NL

private val stringLiteral by STRING use { StringNode(text.removeSurrounding("\"", "\"")) }

private val literal: Parser<AST> by stringLiteral

private val expression by literal or parser(::block) or parser(::functionCall)

private val statement by expression * -semi

private val statements: Parser<List<AST>?> by zeroOrMore(statement)

private val block by -LBRC * statements * -RBRC map { Block(it ?: emptyList()) }

private val functionParameters by -LPAR * separatedTerms(ID, COMMA, acceptZero = true) * -RPAR map {

it.map { v -> Variable(v.text) }

}

private val functionCall: Parser<FunctionCall> by ID * -LPAR * separatedTerms(expression, COMMA, acceptZero = true) * -RPAR map { (name, args) ->

FunctionCall(UnresolvedFunction(name.text, args.size), args)

}

private val function by -FUNC * ID * functionParameters * block map { (name, param, block) ->

FunctionDeclaration(name.text, param, block)

}

private val topLevelObject by function

private val program: Parser<Program> by oneOrMore(topLevelObject) map { Program(it) }

override val rootParser: Parser<Program> by program

}

無茶苦茶分かりづらいですね！

流石にちょっとだけ解説します。

この時点で

code: kotlin

val CODE = """

func main() {

puts("Hello, World")

}

""".trimIndent()

val result = MyParser.parseToEnd(CODE)

println(result)

みたいなコードを実行すると

Program(program=[com.github.sobreera.myParser.FunctionDeclaration@1c655221])

みたいなASTオブジェクトの結果が返ってきます。

Q. なんでEBNFと逆順で書いてるのか

依存順の処理のためです。

例えばなんですけど、関数Aで使う変数を定義するのって、関数Aより上ですか？下ですか？

当然関数Aより上で宣言しないと使えませんよね、そういう理由です。

コンパイラ

まずはコードを

code: Compiler.kt

import org.objectweb.asm.ClassWriter

import org.objectweb.asm.Opcodes.*

class Compiler : ClassLoader() {

companion object {

fun compile(program: Program) {

val className = "MyLang"

val cw = ClassWriter(ClassWriter.COMPUTE_MAXS)

cw.visit(V1_5,

ACC_PUBLIC + ACC_SUPER,

className,

null,

"java/lang/Object",

null)

cw.visitSource("$className.java", null)

cw.visitMethod(ACC_PUBLIC, "<init>", "()V", null, null).apply {

visitVarInsn(ALOAD, 0)

visitMethodInsn(INVOKESPECIAL, "java/lang/Object", "<init>", "()V", false)

visitInsn(RETURN)

visitMaxs(-1, -1)

visitEnd()

}

val mainFunc = program.program.filter { it is FunctionDeclaration && it.name == "main" }.firstOrNull() as FunctionDeclaration?

if(mainFunc != null){

cw.visitMethod(ACC_PUBLIC + ACC_STATIC, mainFunc.name, "([Ljava/lang/String;)V", null, null).apply {

visitCode()

visitFieldInsn(GETSTATIC, "java/lang/System", "out", "Ljava/io/PrintStream;")

val putString = mainFunc.body.statements.filter { it is FunctionCall && it.functionDeclaration.name == "puts" }.firstOrNull() as FunctionCall?

if(putString != null && putString.parameters.first() is StringNode) {

visitLdcInsn((putString.parameters.first() as StringNode).value)

visitMethodInsn(INVOKEVIRTUAL, "java/io/PrintStream", "println", "(Ljava/lang/String;)V")

visitInsn(RETURN)

visitMaxs(2,1)

visitEnd()

}

}

}

cw.visitEnd()

val code = cw.toByteArray()

val loader = Compiler()

val klass = loader.defineClass(className, code, 0, code.size)

klass.getMethod("main", Array<String>::class.java).invoke(null, arrayOf(""))

}

}

}

ここの説明どこまでするかで遅れが発生しました。

えぇ…と思われるかもしれないですけど、ここ真面目に説明しようとするとJVMのStackの話から始めないとだめで、もうそれカレンダー1つ埋めれるよねってレベルになるのでやりません。

これ書く前にBoostNoteで説明の部分下書きしてたんですけどまだ完成してませんし、もはや僕自身どこで切ればいいのかわかってないので気になる人は調べてください。

気が向いたら書きます。

最後の4行で生成したバイトコードを読み込んで実行しています。

実行

では実行してみましょう。

code: MyLangTest.kt

fun main(args: Array<String>) {

val CODE = """

func main() {

puts("Hello, World")

}

""".trimIndent()

val result = MyParser.parseToEnd(CODE)

Compiler.compile(result)

}

反省

これパーサ部分で記事1つ使うべきだったよね。