Здравствуйте. Я учусь на последнем курсе бакалавриата и уже через месяц с небольшим буду защищать свою выпускную квалификационную работу (или же дипломную). Мне захотелось рассказать про неё здесь, чем я сейчас и займусь.
Меня давно интересуют инструменты для обеспечения работы языков программирования - лексеры, парсеры, интерпретаторы, компиляторы и всякое такое. Настолько интересуют, что уже в конце первого курса я решила, что в конце обучения буду защищать свой маленький язык программирования. Увы, создание собственного языка оказалось делом довольно сложным, из-за чего пришлось искать новую тему. Примерно на третьем курсе мы изучали в университете 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 из моей статьи перебрался в репозиторий на Гитхабе, можете тоже глянуть.
