Здравствуйте. Я учусь на последнем курсе бакалавриата и уже через месяц с небольшим буду защищать свою выпускную квалификационную работу (или же дипломную). Мне захотелось рассказать про неё здесь, чем я сейчас и займусь.
Меня давно интересуют инструменты для обеспечения работы языков программирования - лексеры, парсеры, интерпретаторы, компиляторы и всякое такое. Настолько интересуют, что уже в конце первого курса я решила, что в конце обучения буду защищать свой маленький язык программирования. Увы, создание собственного языка оказалось делом довольно сложным, из-за чего пришлось искать новую тему. Примерно на третьем курсе мы изучали в университете Kotlin, который быстро запал мне в душу и стал моим любимцем (после Lua). Мне захотелось написать дипломную именно на нём, поэтому я стала думать, что бы такое написать. Так как меня интересовал геймдев, я подумала: "Почему бы не создать свой движок для текстовых квестов как альтернативу Ren'Py?". Подумала и написала простой движок. Увы, в нём не было научной новизны, да и писать под него было неудобно, ну хоть получила опыт создания язычков, когда дала жизнь своему Av, про который писала в прошлой статье.
В университете мне сказали, что подобная тема совершенно не подходит для защиты, после чего я снова задумалась, что бы написать. Вспомнила, что довольно неплохо знакома с ANTLR, и решила написать DSL, который позволит превращать классы, которые сгенерировал ANTLR, в AST Kotlin. Эта мысль возникла довольно внезапно, но мне быстро стало интересно, во что она может превратиться. Как писать такой DSL, а главное, зачем? Как я объясняла нашей завкафедрой, подобный инструмент позволит автоматически переводить кодовые базы с разных языков на один - мой любимый Котлин. Кроме того, это поможет поддержать авторов новых языков программирования, поскольку он позволяет не писать свой рантайм, а положиться на уже существующий JVM, ведь Котлин исполняется на нём.
Официально тема моей дипломной работы называется так: "DSL ASTra для описания транспайлеров из классов, сгенерированных ANTLR, в AST Kotlin". Почему ASTra? Потому что [AS]T [Tra]nspiler. Теперь расскажу, как работает мой DSL и как можно его использовать, в качестве примера возьму транспайлер STLC => Kotlin.
Работа фактически состоит из двух частей:
Ядро, которое позволяет описывать транспайлеры
Около трёх сотен классов, которые описывают типизированное AST Kotlin версии 1.9.22
Ядро состоит из следующих классов:
TranspilationRule
RuleBuilder
RuleHolder
RuleHolderBuilder
RuleVisitor
DefaultRule
RuleLogger
TranspilationRule<P, A> - это класс, который позволяет описывать правила транспиляции. Мы сопоставляем семантику P:ParseTree и A:KotlinAst между собой, чтобы в дальнейшем RuleVisitor мог искать правила и преобразовывать дерево разбора в AST.
Как выглядит использование билдера TranspilationRule:
val rX = rule<XContext, KSimpleIdentifier>("x") {
from(XContext::class)
how {ctx: XContext ->
ctx.ID().text.id
}
}В данном случае можно опустить типовые параметры функции rule, поскольку они выведутся самостоятельно без всяких проблем, но я обычно указываю их везде. Функция rule вызывает type-safe builder, который позволяет поэтапно настраивать наше правило.
XContent - это класс, сгенерированный ANTLR, KSimpleIdentifier - класс, описывающий простые идентификаторы в AST Kotlin. Функция how описывает, как именно XContent становится KSimpleIdentifier. Существуют ещё howCtx, где ctx становится ресивером, и howFixed, где с помощью комбинатора фиксированной точки сама how становится рекурсивной, за счёт чего можно вызывать себя же без поиска среди правил. Можно также не задавать имя сразу, а вызвать name("name") внутри rule {}, но мне удобнее сразу задавать имя.
Пример посложнее:
val rConditional = rule("conditional") {
from(ConditionalContext::class)
how {ctx: ConditionalContext ->
val tToExp = lookup<TContext, KExpression>()
?: error("ASTra doesn't know how to get KExpression from T")
tToExp(ctx.pred).ifElse(
tToExp(ctx.if_true).block,
tToExp(ctx.if_false).block
)
}
}Здесь уже можно увидеть вызов функции lookup. Это довольно интересная часть, поскольку мы просто ищем правило с такой сигнатурой, не интересуясь его именем и не привязываясь к нему хардкодно.
По факту весь DSL состоит из объявления правил, показывающих, как семантика некоего формального языка соответствует семантике Котлина. Есть, конечно, вспомогательные функции, но в целом это всё. Разве что стоит отметить возможность настройки логирования перед вызовом правила и после, а также существование defaultRule, которое будет выполняться, если для узла дерева разбора не будет найдено правило.
Вот пример defaultRule:
default {
println("default for $it")
"TODO".id()
}Пример транспайлера STLC => Kotlin целиком
val stlcRuleHolder=rules<StlcLexer,StlcParser> {
default {
println("default for ${it::class.simpleName}")
"TODO".id()
}
val rX=
rule("x") {
from(XContext::class)
how {ctx:XContext-> ctx.ID().text.id}
}
val rVariable=
rule("variable") {
from(VariableContext::class)
how {ctx:VariableContext-> rX(ctx.x())}
}
val rTrue=
rule("true") {
from(Constant_trueContext::class)
how {true.ast}
}
val rFalse=
rule("false") {
from(Constant_falseContext::class)
how {false.ast}
}
val rParenthesis=
rule("parenthesis") {
from(ParenthesisContext::class)
how {ctx:ParenthesisContext->
val tToExp=lookup<TContext,KExpression>()
?: error("ASTra doesn't know how to get KExpression from Parenthesis")
tToExp(ctx.t()).paren
}
}
val rConditional=
rule("conditional") {
from(ConditionalContext::class)
how {ctx:ConditionalContext->
val tToExp=lookup<TContext,KExpression>()
?: error("ASTra doesn't know how to get KExpression from T")
tToExp(ctx.pred).ifElse(
tToExp(ctx.if_true).block,
tToExp(ctx.if_false).block
)
}
}
val rT=
rule("t") {
from(TContext::class)
how {ctx:TContext->
when(ctx)
{
is VariableContext->rVariable(ctx)
is AbstractionContext->
lookup<AbstractionContext,KFunctionLiteral>()?.invoke(ctx)
?: error("ASTra doesn't know how to get KLambdaLiteral from Abstraction")
is ApplicationContext->
lookup<ApplicationContext,KExpression>()?.invoke(ctx)
?: error("ASTra doesn't know how to get KExpression from ApplicationContext")
is Constant_trueContext->rTrue(ctx)
is Constant_falseContext->rFalse(ctx)
is ConditionalContext->rConditional(ctx)
is ParenthesisContext->rParenthesis(ctx)
else->error("ASTra doesn't know how to get KExpression from ${ctx::class.simpleName}")
}
}
}
val rApplication=
rule<ApplicationContext,KExpression>("application") {
from(ApplicationContext::class)
how {ctx->
val exp=ctx.t(1)
ctx.t(0).let(rT)(rT(exp))
}
}
val rType=
rule("type") {
from(TypeContext::class)
howFixed {rType->
{ctx:TypeContext->
val boolify={name:String->
if(name=="Bool") "Boolean" else name
}
when(ctx)
{
is Flat_typeContext->boolify(ctx.ID().text).type
is Abstraction_typeContext->
boolify(ctx.ID().text).type
.functionTypeParameters
.leadsTo(rType(ctx.type()))
.type
else->error("ASTra doesn't know how to get other KType from ${ctx::class.simpleName}")
}
}
}
}
val rAbstraction=
rule<AbstractionContext,KLambdaLiteral>("abstraction") {
from(AbstractionContext::class)
how {ctx->
rX(ctx.x()).variableDecl(rType(ctx.type()))
.lambdaParams
.literal(rT(ctx.t()).stat)
}
}
}Думаю, с первой частью всё более-менее понятно, перехожу ко второй. IDEA говорит, что у интерфейса KotlinAst 282 наследника. Я не буду считать вручную, сколько их на самом деле, а поверю ей.
Почему так много классов? Я следовала официальной грамматике и упрощала её там, где это было возможно, но в целом мне пришлось описать её целиком, кроме лишних частей.
Как обычно, начну с "Hello, world!":
"println".id("Hello, world!".ast)Как можно заметить, здесь println является идентификатором, а "Hello, world!" - строкой в AST. Благодаря перегрузке функции-оператора invoke можно вызвать println.id как обычную функцию, что очень удобно.
val x = "x".idЗдесь мы просто сослались на некоторое свойство "x".
Пример посложнее:
val exp: KBinaryExpression = 1.ast + 2.ast Здесь выражение имеет тип KBinaryExpression, объединяющий в себе KAdditiveExpression и KMultiplicativeExpression. Путём добавления постфикса ast к литералу целого числа мы превращаем его в KIntegerLiteral.
"obj"["prop".id]Здесь мы берём свойство "prop" у объекта "obj".
val declaration = kval("x", 10.ast)Здесь мы создаём объявление свойства. Как можно заметить, оно создаётся необычайно просто, при этом доступна более полная кастомизация:
val declaration1 = kval("x") {
+Lateinit // import EMemberModifier.Lateinit
+Override // import EMemberModifier.Override
isVar
+10.ast
}
// Объявления равнозначны
val declaration2 = kval("x") {
mods(Lateinit, Override)
isVal(false)
expr(10.ast)
}Но это ладно, всё выглядит достаточно просто. Для примера возьму прям большой кусок кода и покажу, как он выглядит на Котлине и моём DSL.
Оригинал
abstract class Character(val name: String, var health: Int)
{
abstract fun attack(target: Character)
fun isAlive(): Boolean = health > 0
open fun takeDamage(amount: Int)
{
health -= amount
println("$name получил $amount урона. Осталось $health HP.");
if (health <= 0) println("$name пал в бою...")
}
}
abstract class Hero(
name: String,
health: Int,
val power: Int
):Character(name, health)
{
override fun attack(target: Character)
{
println("$name атакует ${target.name}!")
target.takeDamage(power)
}
}
class Monster(
name: String,
health: Int,
val damage: Int
):Character(name, health)
{
override fun attack(target: Character)
{
println("$name кусает ${target.name}!")
target.takeDamage(damage);
}
}
fun main()
{
val hero = Hero("Алиса", 100, 20)
val goblin = Monster("Гоблин", 100, 20)
println("⚔️ Битва начинается!")
while(hero.isAlive()&&goblin.isAlive())
{
hero.attack(goblin)
if(goblin.isAlive()) goblin.attack(hero)
println()
}
println("🏁 Битва окончена!")
}На DSL
kotlinFile {
+kclass("Character",EInheritanceModifier.Abstract) {
primaryConstructor {
"name" ofType "String"
"health" init {
isVar
type("Int")
}
}
classBody {
function("attack") {
+EInheritanceModifier.Abstract
"target" ofType "Character"
}
function("isAlive") {
type("Boolean".type)
exprBody("health".id greater 0.ast)
}
function("takeDamage") {
+EInheritanceModifier.Open
"amount" ofType "Int"
blockBody {
+"health".id.subAssign("amount".id)
+"println".id(
stringLiteral {
ref("name")
text(" получил ")
ref("amount")
text(" урона. Осталось ")
ref("health")
text(" HP.")
}
)
+"health".id
.lessEq(0.ast)
.ifTrue("println".id("\$name пал в бою...".ast).stat)
}
}
}
}
+kclass("Hero",EInheritanceModifier.Abstract) {
primaryConstructor {
"name" init {
notMine // isn't val/var, just sends to parent constructor
type("String")
}
"health" init {
notMine
type("Int")
}
"power" ofType "Int"
}
delegationSpecifiers {
"Character".id.simpleUserType.userType constructorInvocation
listOf("name".id.valueArg, "health".id.valueArg)
}
classBody {
function("attack") {
+Override
"target" ofType "Character"
blockBody {
+"println".id(
stringLiteral {
ref("name")
text(" атакует ")
expr("target".id["name".id])
text("!")
}
)
+"target"["takeDamage".id]("power".id)
}
}
}
}
+kclass("Monster") {
primaryConstructor {
"name" init {
notMine
type("String")
}
"health" init {
notMine
type("Int")
}
"damage" ofType "Int"
}
delegationSpecifiers {
"Character".id.simpleUserType.userType constructorInvocation
listOf("name".id.valueArg, "health".id.valueArg)
}
classBody {
function("attack") {
+Override
"target" ofType "Character"
blockBody {
+"println".id(
stringLiteral {
ref("name")
text(" кусает ")
expr("target".id["name".id])
text("!")
}
)
+"target"["takeDamage".id]("damage".id)
}
}
}
}
+kfun("main") {
blockBody {
+kval("hero", "Hero".id("Алиса".ast, 100.ast, 20.ast))
+kval("goblin", "Monster".id("Гоблин".ast, 100.ast, 20.ast))
+"println".id("⚔️ Битва начинается!".ast)
+("hero"["isAlive".id]() and "goblin"["isAlive".id]()).kwhile {
+"hero"["attack".id]("goblin".id)
+"goblin"["isAlive".id]().ifTrue(
"goblin"["attack".id]("hero".id).stat
)
+"println".id()
}
+"println".id("🏁 Битва окончена!".ast)
}
}
}Что здесь происходит? Мы объявляем абстрактный класс Character, от которого наследуются классы Hero и Monster. Оба умеют драться и получать урон. Ниже в функции main мы загоняем их на арену и заставляем драться не на жизнь, а на смерть. Код полностью рабочий, если интересно, кто из них выживет, можете запустить в IDE или в онлайн-песочнице.
Как можно заметить, я активно использую type-safe builders и перегрузки функций-операторов, благодаря чему у меня получается относительно компактная и удобная запись.
Использование when тоже относительно удобно:
kwhen("x".id) {
"Int".type caseIs "Int".ast
"String".type caseIs "String".ast
"Unknown".ast.stat.caseElse
}Стоит также отметить, что для преобразования моего AST в исходный код я создала интерфейс Emitter<E>, который может реализовать любой эмиттер, в том числе и KotlinEmitter, который есть в проекте.
Чем отличается от kastree, kotlinx.ast, kotlinpoet? Тем, что у меня именно DSL для генерации AST, он не работает в качестве шаблонизатора, как kotlinpoet, и позволяет описывать AST более лаконично и компактно за счёт удобных билдеров и свойств-расширений. Плюс он создан мной для дипломной работы, да.
Пожалуйста, если примеров не хватило, пишите в комментариях или смотрите в репозитории, там как раз ещё есть пример транспайлера Lisp => Kotlin, где игрушечный Лисп превращается в Котлин по щелчку пальца. Прошу прощения за небрежно оформленный код, я займусь им, когда будет время.
P. S. Av из моей статьи перебрался в репозиторий на Гитхабе, можете тоже глянуть.