Комбинаторы синтаксического анализа на Kotlin
Введение
Существуют разные способы реализации синтаксических анализаторов для заданной грамматики. В статье рассматривается подход, называемый Комбинаторы синтаксического анализа, так же можно встретить название Парсер комбинаторы.
Когда я впервые познакомился с этим подходом, он произвел на меня сильное впечатление, потому что здесь без использования внешних фреймворков можно легко и быстро реализовать свою библиотеку, которая позволяет описывать парсеры в декларативном стиле. Парсер комбинаторы можно использовать для прототипирования или написания легко расширяемого синтаксического анализатора. В статье мы рассмотрим примеры реализации Парсер комбинаторов на языке Kotlin. Напишем синтаксические анализаторы для арифметических выражений и функций вида printf("%s = %f", "2 + 2", 5)
, в которых типы аргументов определяются строкой формата. Код, используемый в статье, доступен в репозитории.
Вспомним несколько понятий из теории формальных языков
Формальный язык — это множество слов над конечным множеством символов — алфавитом. Чтобы выделить из всего множества слов некоторое его подмножество, используют формальные грамматики. Грамматику можно задать набором правил вида: L -> R
, где L
— непустая последовательность терминалов и нетерминалов, содержащая хотя бы один нетерминал, а R
— любая последовательность терминалов и нетерминалов. Терминал — это объект, состоящий только из символов алфавита, а нетерминал — объект обозначающий какую-либо сущность языка.
Рассмотрим пример задания грамматики правильной скобочной последовательности:
S -> (S)S
S -> ε
где (
, )
— терминальные символы, S
— нетерминальный символ, ε — пустая строка.
Для классификации грамматик используют иерархию, предложенную Ноамом Хомским.
По иерархии Хомского грамматики делятся на 4 типа, каждый последующий является более ограниченным подмножеством предыдущего и легче поддается анализу:
тип 0. неограниченные грамматики — возможны любые правила;
тип 1. контекстно-зависимые грамматики — левая часть может содержать один нетерминал, окруженный «контекстом» — последовательность символов, в том же виде присутствующая в правой части;
тип 2. контекстно-свободные грамматики — левая часть состоит из одного нетерминала;
тип 3. регулярные грамматики.
В статье в качестве примеров будем рассматривать анализаторы, соответствующие только контекстно-свободным (КС) и контекстно-зависимым (КЗ) грамматикам. К примеру, языки, порождаемые КС-грамматиками это — правильные скобочные последовательности (пример грамматики был выше) или арифметические выражения. В качестве языков, порождаемых КЗ-грамматиками можно рассмотреть, например, протоколы передачи данных, в которых сообщение состоит из заголовка, содержащего длину сообщения, а дальше следует само сообщение. Также интересный пример встречается в современных IDE, которые умеют подсвечивать ошибки в случае, когда типы аргументов не соответствуют спецификаторам:
printf("%s = %f", "2 + 2", 5)
Для того чтобы разобрать КС-грамматику, достаточно автомата с магазинной памятью (МП-автомат), а вот для разбора КЗ-грамматики потребуется линейно-ограниченный автомат, более мощный формализм с точки зрения вычислимости по сравнению с МП-автоматом.
Комбинаторы синтаксического анализа
Парсер комбинаторы занимают уникальное место в области синтаксического анализа, они позволяют писать выражения, повторяющие структуру грамматических правил, то есть задают удобный DSL для написания парсеров.
Я познакомился с этой концепцией в статье Еруна Фокера. Впервые о парсер комбинаторах начали говорить в 1980 годах, а на текущий момент для разных языков программирования существуют удобные библиотеки для работы с ними.
Итак, комбинаторы парсеров — это конструкторы, которые на основе одних парсеров создают другие, более сложные, например, комбинатор альтернативы Alt(p1, p2)
применит к строке сначала парсер p1
и если разбор завершится с ошибкой, то применит p2
. Или комбинатор следования Seq(p1, p2)
, применяющий последовательно p1
и p2
, и возвращающий скомбинированный результат.
Tип Parser и элементарные синтаксические анализаторы.
Parser и ParseResult
Начнем с определения интерфейса Parser
и результата работы парсера ParseResult
.
Запечатанный интерфейс ParseResult
представляет успешный или неуспешный результат разбора.
sealed interface ParseResult {
data class Fail(val msg: String) : ParseResult
data class Success(val tail: String, val result: A) : ParseResult
}
Обратите внимание, как мы используем Nothing
для класса Fail
— это возможно, потому что Nothing
является наследником любого класса в Kotlin.
В классе Fail
аттрибут msg
— это сообщение об ошибке, а в классе Success
аттрибуты:
tail
— остаток строки, которую еще нужно разобрать;result
— результат работы парсера, это может что угодно, например символ типаChar
или синтаксическое дерево разбора.
Интерфейс парсера определяется просто:
interface Parser {
fun parse(str: String): ParseResult
}
При реализации комбинаторов часто придется выполнять шаблонное действие, такое, что если предыдущий парсер вернул Fail
, то ничего не делать, а если Success
, то выполнить некоторые действия и вернуть результат. Поэтому введем вспомогательную функцию map
:
fun ParseResult.map(block: (ParseResult.Success) -> ParseResult) = when (this) {
is ParseResult.Fail -> this
is ParseResult.Success -> block(this)
}
Парсер TakeIf
Теперь все готово, чтобы написать наш первый парсер TakeIf
. Он будет проверять — соответствует ли первый символ строки предикату.
class TakeIf(private val description: String, private val predicate: (Char) -> Boolean) : Parser {
override fun parse(str: String) = when {
str.isEmpty() -> ParseResult.Fail("Input string is empty")
!predicate(str.first()) -> ParseResult.Fail("Symbol '${str.first()}' does not satisfy predicate: $description")
else -> ParseResult.Success(str.drop(1), str.first())
}
}
Думаю, код не требует пояснений.
Дополнительно введем функцию, которая возвращает парсер, проверяющий соответствие первого символа строки заданному набору символов, она нам пригодится в будущем:
fun symbol(c: Char, vararg cs: Char) =
TakeIf("in [${(cs + c).joinToString { it.toString() }}]") { it in cs + c }
Результат работы парсера:
println(symbol('a').parse("abc")) // output: Success(tail=bc, pos=1, result=a)
println(symbol('b').parse("abc")) // output: Fail(msg=Symbol 'a' does not satisfy predicate: in [b])
Парсер Return
Парсер Return
всегда возвращает заданное значение, и он пригодится нам в будущем:
class Return(private val a: A) : Parser {
override fun parse(str: String) = ParseResult.Success(str, 0, a)
}
Можно расширять набор элементарных парсеров и дальше, вводя, к примеру, такие как number(n)
, string(str)
и так далее. Имея такие простые парсеры, можно конструировать анализаторы терминальных символов, но, как мы видели, в правилах грамматики присутствуют и нетерминалы, и комбинации терминалов и нетерминалов. Для построения более мощных анализаторов потребуются комбинаторы.
Комбинаторы
Alt и Seq
Вспомним, каким образом задаются правила грамматики, например, для правильной скобочной последовательности:
S -> (S)S
S -> ε
Глядя на эти правила становится ясно, что потребуются комбинаторы следования Seq
и альтернативы Alt
. Seq
это комбинатор типа Parser
, который принимает на вход два парсера pa: Parser
, pb: Parser
и применяет их последовательно, возвращая Pair
:
class Seq(private val pa: Parser, private val pb: Parser) : Parser> {
override fun parse(str: String) = pa.parse(str).map { it1 ->
pb.parse(it1.tail).map { it2 ->
ParseResult.Success(it2.tail, it1.result to it2.result)
}
}
}
Комбинатор Alt
на основе парсеров p1, p2: Parser
конструирует парсер, возвращающий результат применения p1
, а если он вернет Fail
, то результат применения p2
:
class Alt(private val p1: Parser, private val p2: Parser) : Parser {
override fun parse(str: String) = when (val r = p1.parse(str)) {
is ParseResult.Fail -> p2.parse(str)
is ParseResult.Success -> r
}
}
Преобразователь парсеров Mapper и «ленивость»
Если бы мы сейчас решили реализовать парсер для разбора правильной скобочной последовательности, то написали бы такой код:
val `(` = symbol('(')
val `)` = symbol(')')
fun parens() : Parser* Как тип указать?*/> = Alt(
Seq(`(`, Seq(parens(), Seq(`)`, parens()))),
Return(Unit)
)
fun main() {
parens().parse("(()())")
}
Это нерабочий код, в нем есть две проблемы. Первая — это невозможность вычислить тип парсера, возвращаемый функцией parens()
, а вторая — это рекурсивный вызов функцией самой себя. Со второй проблемой легко справиться, добавив «ленивости» нашим парсерам:
fun ref(lazy: () -> Parser) = object : Parser {
override fun parse(str: String) = lazy().parse(str)
}
Для того чтобы решить первую проблему, нужно ввести преобразователь типа парсера, который позволит из Parser
получить Parser
:
class Mapper(private val p: Parser, private val f: (A) -> B) : Parser {
override fun parse(str: String) = p.parse(str).map { ParseResult.Success(it.tail, f(it.result)) }
}
Теперь мы можем написать рабочий код, который превращает правильную скобочную последовательность в дерево разбора:
val `(` = symbol('(')
val `)` = symbol(')')
fun parens(): Parser = Alt(
Mapper(
Seq(
`(`,
Seq(
ref { parens() },
Seq(
`)`,
ref { parens() }
)
)
)
) { (_, a) -> Tree.Node(a.first, a.second.second) },
Return(Tree.Leaf)
)
fun main() {
println(parens().parse("(()())")) //output: Success(tail=, pos=6, result=Node(left=Node(left=Leaf, right=Node(left=Leaf, right=Leaf)), right=Leaf))
}
Подведем промежуточный итог.
Мы реализовали пару элементарных парсеров TakeIf
и Return
, преобразователь Mapper
и пару комбинаторов Alt
, Seq
. С таким набором инструментов можно разбирать КС-грамматики, но стоит признать, что код таким образом писать не удобно.
Введем несколько вспомогательных функций.
Вспомогательные функции alt, seq, optional, manyOf и someOf
Функция alt(p: Parser, vararg ps: Parser)
будет принимать на вход набор парсеров, и возвращать комбинатор, который применяет эти парсеры к строке пока результат не будет Success
. Реализуем ее с помощью свертки (fold
)
fun alt(p: Parser, vararg ps: Parser): Parser = ps.fold(p) { x, xs -> Alt(x, xs) }
Функция seq
будет так же, как и alt
, принимать на вход набор парсеров и последним аргументом функцию преобразования, например, в случае для трех парсеров ее сигнатура будет иметь вид:
fun seq(p1: Parser, p2: Parser, p3: Parser, f: (X1, X2, X3) -> Y): Parser
Для seq
не получится сделать универсального решения, так как тип f
зависит от типов предыдущих аргументов. Нам потребуются функции, которые преобразуют тип вида (X1, X2, X3, X4) -> Y
в тип (Pair
. Приведу пример для трех аргументов, а более подробно с кодом можно ознакомиться в репозитории:
fun args2tuple(f: (X1, X2, X3, X4) -> Y): (Pair>>) -> Y =
args2tuple { x1, x2, (x3, x4) -> f(x1, x2, x3, x4) }
fun seq(p1: Parser, p2: Parser, p3: Parser, f: (X1, X2, X3) -> Y) =
Mapper(Seq(p1, Seq(p2, p3)), args2tuple(f))
Нам будут также полезны комбинаторы:
optional(p: Parser, a: A): Parser
— применяет парсерp
и в случае неудачи возвращает значениеa
;someOf(p: Parser): Parser
— ожидает, что при разборе входящей строки,- >
p
вернетSuccess
хотя бы один раз;manyOf(p: Parser): Parser
— пытается применить парсер- >
p
к входящей строке столько раз, сколько получится, если не получилось ни разу, то вернет пустой список.
Их реализация:
fun optional(p: Parser, a: A) = alt(p, Return(a))
fun someOf(p: Parser): Parser> = seq(p, ref { manyOf(p) }) { x, xs -> listOf(x) + xs }
fun manyOf(p: Parser): Parser> = optional(someOf(p), emptyList())
Нужно отметить, что приведенная выше реализация функций someOf
и manyOf
неоптимальная из-за рекурсивных вызовов, использовать такой код в реальных проектах нужно с осторожностью.
Используя вспомогательные функции, определенные выше, парсер parens()
можно переписать в более удобном виде:
fun parens2(): Parser = optional(
seq(`(`, ref { parens2() }, `)`, ref { parens2() }) { _, left, _, right -> Tree.Node(left, right) },
Tree.Leaf
)
fun main() {
println(parens2().parse("(()())")) // output: Success(tail=, result=Node(left=Node(left=Leaf, right=Node(left=Leaf, right=Leaf)), right=Leaf))
}
Теперь мы готовы приступить к написанию синтаксического анализатора арифметических выражений.
Разбор арифметических выражений
В этом разделе мы опишем парсер, который разбирает и сразу же вычисляет арифметическое выражение:
fun exp(): Parser = ...
println(exp().parse("3+4*(1/(2*3*4)-1/(4*5*6)+1/(6*7*8)-1/(8*9*10)+1/(10*11*12))")) // output: Success(tail=, result=3.1427128427128426)
Грамматика арифметических выражений задается следующим образом:
op1 -> '+' | '-'
op2 -> '*' | '/'
exp -> exp op1 term | term
term -> term op2 factor | factor
factor -> number | '(' exp ')' | -factor
Для того чтобы написать анализатор по правилам грамматики, нужно каждый терминальный и нетерминальный символы заменить на соответствующий парсер. Если мы сделаем это для приведенных выше правил, то получится примерно следующий код:
fun exp() = seq(ref { exp() }, op1(), term()) {...}
Если применить парсер exp
к строке, то он будет вызывать сам себя пока не кончится память. Это происходит из-за того, что правила содержат непосредственную левую рекурсию. Для того чтобы исключить левую рекурсию, нужно правило вида A -> A a | b
преобразовать к правилам вида:
A -> b A' | b
A' -> a A | a
Подробнее об алгоритме устранения левой рекурсии можно почитать в статье. Преобразуем правила в соответствии с этим алгоритмом:
op1 -> '+' | '-'
op2 -> '*' | '/'
exp -> term exp1 | term
exp1 -> op1 term exp1 | op1 term
term -> factor term1 | factor
term1 -> op2 factor term1 | op2 factor
factor -> number | '(' exp ')' | -factor
Не буду приводить полный код для разбора арифметических выражений, его можно посмотреть в репозитории, но хочу обсудить типы промежуточных парсеров exp1(), term1()
, потому, что они могут казаться не совсем обычными. Ясно, что тип fun factor(): Parser
, учитывая, что op2
— это по сути парсер бинарного оператора, имеющий тип fun op2(): Parser<(Double, Double) -> Double>
, тогда получаем, что тип fun term1(): Parser<(Double) -> Double>
. В коде это выглядит следующим образом:
// term1 -> op2 factor term1 | op2 factor
fun term1(): Parser<(Double) -> Double> = alt(
seq(op2(), factor(), ref { term1() }) { op, b, t -> { a -> t(op(a, b)) } },
seq(op2(), factor()) { op, b -> { a -> op(a, b) } }
)
Такие же рассуждения можно провести и для exp1()
.
Ограничения комбинаторов Seq и Alt
Вспоминая, что КС-грамматика описывается правилами, левые части которых состоят только из одного нетерминального объекта, то интуитивно понятно, что с помощью комбинаторов seq
и alt
можно описать анализатор любой КС-грамматики. Для КЗ-грамматики, правила которой могут иметь вид a A b -> a w b
, приведенных выше комбинаторов недостаточно.
Рассмотрим КЗ-язык:
{anbncn: n ≥ 0}
Слова этого языка состоят из трех групп символов одинаковой длины, например aabbcc
. Думаю, что если бы мы решили сформировать правила грамматики с одним нетерминальным символом слева, то получился бы бесконечный набор правил. Если хочется узнать как выглядит грамматика этого языка, то можно подсмотреть, например, в википедии.
Но вот если бы у нас был способ выбора парсера на основе результата предыдущего разбора, то мы смогли бы написать синтаксический анализатор этого языка.
Комбинатор связывания и анализ КЗ-грамматики
Многие компиляторы и IDE умеют показывать предупреждения, если в функции форматного вывода, например printf("%s = %f", "2 + 2", 5)
, порядок типов спецификаторов не соответствует порядку типов аргументов. Грамматика, разбирающая выражения такого вида, является контекстно-зависимой, так как парсеры, разбирающие аргументы, зависят от строки со спецификацией формата вывода. То есть нам нужно научить нашу библиотеку комбинаторов выбирать на этапе разбора.
Комбинатор связывания и пример разбора КЗ-грамматики
Приведем комбинатор Binder
, который принимает на вход парсер p: Parser
и функцию bind: (A) -> Parser
, и позволяет осуществлять выбор о том, какой парсер нужно использовать далее на основе результата применения парсера p
:
class Binder(private val pa: Parser, private val bind: (A) -> Parser) : Parser {
override fun parse(str: String) = pa.parse(str).map {
bind(it.result).parse(it.tail)
}
}
fun Parser.then(bind: (A) -> Parser): Parser = Binder(this, bind)
Теперь попробуем применить Binder
для разбора выражения printf("%s = %f", "2 + 2", 5)
. Я приведу пример парсера, который возвращает Success
если типы аргументов соответствуют спецификаторам формата, в противном случае, Fail
без дополнительной информации, о том, где именно ошибка.
Мы рассмотрим два спецификатора:
%f
— число%s
— строка
Код основного парсера:
fun printf(): Parser = seq(
string("printf"),
`(`,
quotedFrmStr().then {
it.map { spec ->
when (spec) {
Spec.STR -> seq(comma(), strType()) { _, _ -> }
Spec.INT -> seq(comma(), numType()) { _, _ -> }
}
}.fold(Return(Unit) as Parser) { types, type ->
seq(types, type) { _, _ -> }
}
},
`)`
) { _, _, _, _ -> }
Парсер quotedFrmStr(): Parser
возвращает список спецификаторов в порядке следования, затем этот список отображается в соответствующие парсеры, далее список сворачивается с помощью комбинатора >
seq
.
Результат работы:
println(printf().parse("printf(\"%s = %f\",\"2 + 2\",2+2)")) // output: Success(tail=, result=kotlin.Unit)
println(printf().parse("printf(\"%f = %s\",\"2 + 2\",5)")) // output: Fail(...)
Обратите внимание, что в первой строке во втором аргументе используется арифметическое выражение, которое также нужно еще разобрать и вычислить. Но из-за однообразия способов комбинирования наших парсеров мы спокойно можем использовать результат из раздела «Анализ арифметических выражений»:
fun numType() = seq(exp()) { _ -> }
Мы закончили с комбинаторами и давайте подведем итог.
Заключение
В статье мы увидели, как с помощью комбинаторов можно строить лексические анализаторы. С использованием комбинаторов seq
и alt
мы можем построить синтаксические анализаторы, разбирающие КС-грамматики. Преимущество такого подхода в декларативном стиле и в том, что структура этих деклараций повторяет структуру правил грамматики. Если требуется разобрать КЗ-грамматику, то нужно использовать комбинатор связывания Binder
или then
, тогда класс разбираемых грамматик расширяется, но сложность компоновки парсеров увеличивается.
Использование комбинаторов не ограничивается только парсерами, например, похожий подход можно использовать для построения валидаторов.
val item: Map
sealed interface PromoAction {
data class PromoCode(...): PromoAction
data class Sale(...): PromoAction
}
fun extractPromo() = alt(
seq(extractId(), extractPromoCode()) {id, code -> PromoCode(id, code)},
seq(extractId(), extractSale()) {id, saleValue -> Sale(id, saleValue)}
)
extractPromo().run(item) // output: Success(PromoCode) or Success(Sale)
Пример кода выше проверяет корректность данных и конструирует на основе этих данных соответствующие data-классы. Преимущество такого подхода в его декларативном стиле, например по extractPromo()
можно автоматически сгенерировать документацию.
На этом я завершаю статью и желаю всем кода без ошибок! Спасибо за внимание.