Введение

Существуют разные способы реализации синтаксических анализаторов для заданной грамматики. В статье рассматривается подход, называемый Комбинаторы синтаксического анализа, так же можно встретить название Парсер комбинаторы.

Когда я впервые познакомился с этим подходом, он произвел на меня сильное впечатление, потому что здесь без использования внешних фреймворков можно легко и быстро реализовать свою библиотеку, которая позволяет описывать парсеры в декларативном стиле. Парсер комбинаторы можно использовать для прототипирования или написания легко расширяемого синтаксического анализатора. В статье мы рассмотрим примеры реализации Парсер комбинаторов на языке 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<out A> представляет успешный или неуспешный результат разбора.

sealed interface ParseResult<out A> {
    data class Fail(val msg: String) : ParseResult<Nothing>
    data class Success<A>(val tail: String, val result: A) : ParseResult<A>
}

Обратите внимание, как мы используем Nothing для класса Fail - это возможно, потому что Nothing является наследником любого класса в Kotlin.

В классе Fail аттрибут msg - это сообщение об ошибке, а в классе Success аттрибуты:

tail - остаток строки, которую еще нужно разобрать;
result - результат работы парсера, это может что угодно, например символ типа Char или синтаксическое дерево разбора.

Интерфейс парсера определяется просто:

interface Parser<A> {
    fun parse(str: String): ParseResult<A>
}

При реализации комбинаторов часто придется выполнять шаблонное действие, такое, что если предыдущий парсер вернул Fail, то ничего не делать, а если Success, то выполнить некоторые действия и вернуть результат. Поэтому введем вспомогательную функцию map:

fun <T, R> ParseResult<T>.map(block: (ParseResult.Success<T>) -> ParseResult<R>) = 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<Char> {
    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<A>(private val a: A) : Parser<A> {
    override fun parse(str: String) = ParseResult.Success(str, 0, a)
}

Можно расширять набор элементарных парсеров и дальше, вводя, к примеру, такие как number(n), string(str) и так далее. Имея такие простые парсеры, можно конструировать анализаторы терминальных символов, но, как мы видели, в правилах грамматики присутствуют и нетерминалы, и комбинации терминалов и нетерминалов. Для построения более мощных анализаторов потребуются комбинаторы.

Комбинаторы

Alt и Seq

Вспомним, каким образом задаются правила грамматики, например, для правильной скобочной последовательности:

S -> (S)S
S -> ε

Глядя на эти правила становится ясно, что потребуются комбинаторы следования Seq и альтернативы Alt. Seq это комбинатор типа Parser<Pair<A, B>>, который принимает на вход два парсера pa: Parser<A>, pb: Parser<B> и применяет их последовательно, возвращая Pair<A, B>:

class Seq<A, B>(private val pa: Parser<A>, private val pb: Parser<B>) : Parser<Pair<A, B>> {
    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<A> конструирует парсер, возвращающий результат применения p1, а если он вернет Fail, то результат применения p2:

class Alt<A>(private val p1: Parser<A>, private val p2: Parser<A>) : Parser<A> {
    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 <A> ref(lazy: () -> Parser<A>) = object : Parser<A> {
    override fun parse(str: String) = lazy().parse(str)
}

Для того чтобы решить первую проблему, нужно ввести преобразователь типа парсера, который позволит из Parser<A> получить Parser<B>:

class Mapper<A, B>(private val p: Parser<A>, private val f: (A) -> B) : Parser<B> {
    override fun parse(str: String) = p.parse(str).map { ParseResult.Success(it.tail, f(it.result)) }
}

Теперь мы можем написать рабочий код, который превращает правильную скобочную последовательность в дерево разбора:

val `(` = symbol('(')
val `)` = symbol(')')

fun parens(): Parser<Tree> = 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<A>, преобразователь Mapper<A, B> и пару комбинаторов Alt<A>, Seq<A, B>. С таким набором инструментов можно разбирать КС-грамматики, но стоит признать, что код таким образом писать не удобно.

Введем несколько вспомогательных функций.

Вспомогательные функции alt, seq, optional, manyOf и someOf

Функция alt(p: Parser<A>, vararg ps: Parser<A>) будет принимать на вход набор парсеров, и возвращать комбинатор, который применяет эти парсеры к строке пока результат не будет Success. Реализуем ее с помощью свертки(fold)

fun <A> alt(p: Parser<A>, vararg ps: Parser<A>): Parser<A> = ps.fold(p) { x, xs -> Alt(x, xs) }

Функция seq будет так же, как и alt, принимать на вход набор парсеров и последним аргументом функцию преобразования, например, в случае для трех парсеров ее сигнатура будет иметь вид:

fun <X1, X2, X3, Y> seq(p1: Parser<X1>, p2: Parser<X2>, p3: Parser<X3>, f: (X1, X2, X3) -> Y): Parser<Y>

Для seq не получится сделать универсального решения, так как тип f зависит от типов предыдущих аргументов. Нам потребуются функции, которые преобразуют тип вида (X1, X2, X3, X4) -> Y в тип (Pair<X1, Pair<X2, Pair<X3, X4>>>) -> Y. Приведу пример для трех аргументов, а более подробно с кодом можно ознакомиться в репозитории:

fun <X1, X2, X3, X4, Y> args2tuple(f: (X1, X2, X3, X4) -> Y): (Pair<X1, Pair<X2, Pair<X3, X4>>>) -> Y =
    args2tuple { x1, x2, (x3, x4) -> f(x1, x2, x3, x4) }

fun <X1, X2, X3, Y> seq(p1: Parser<X1>, p2: Parser<X2>, p3: Parser<X3>, f: (X1, X2, X3) -> Y) =
    Mapper(Seq(p1, Seq(p2, p3)), args2tuple(f))

Нам будут также полезны комбинаторы:

optional(p: Parser<A>, a: A): Parser<A> - применяет парсер p и в случае неудачи возвращает значение a;
someOf(p: Parser<A>): Parser<List<A>> - ожидает, что при разборе входящей строки, p вернет Success хотя бы один раз;
manyOf(p: Parser<A>): Parser<List<A>> - пытается применить парсер p к входящей строке столько раз, сколько получится, если не получилось ни разу, то вернет пустой список.

Их реализация:

fun <A> optional(p: Parser<A>, a: A) = alt(p, Return(a))

fun <A> someOf(p: Parser<A>): Parser<List<A>> = seq(p, ref { manyOf(p) }) { x, xs -> listOf(x) + xs }

fun <A> manyOf(p: Parser<A>): Parser<List<A>> = optional(someOf(p), emptyList())

Нужно отметить, что приведенная выше реализация функций someOf и manyOf неоптимальная из-за рекурсивных вызовов, использовать такой код в реальных проектах нужно с осторожностью.

Используя вспомогательные функции, определенные выше, парсер parens() можно переписать в более удобном виде:

fun parens2(): Parser<Tree> = 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<Double> = ...

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<Double>, учитывая, что 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<A> и функцию bind: (A) -> Parser<B>, и позволяет осуществлять выбор о том, какой парсер нужно использовать далее на основе результата применения парсера p:

class Binder<A, B>(private val pa: Parser<A>, private val bind: (A) -> Parser<B>) : Parser<B> {
    override fun parse(str: String) = pa.parse(str).map {
        bind(it.result).parse(it.tail)
    }
}

fun <A, B> Parser<A>.then(bind: (A) -> Parser<B>): Parser<B> = Binder(this, bind)

Теперь попробуем применить Binder для разбора выражения printf("%s = %f", "2 + 2", 5). Я приведу пример парсера, который возвращает Success<Unit> если типы аргументов соответствуют спецификаторам формата, в противном случае, Fail без дополнительной информации, о том, где именно ошибка.
Мы рассмотрим два спецификатора:

%f - число
%s - строка

Код основного парсера:

fun printf(): Parser<Unit> = 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<Unit>) { types, type ->
            seq(types, type) { _, _ -> }
        }
    },
    `)`
) { _, _, _, _ -> }

Парсер quotedFrmStr(): Parser<List<Spec>> возвращает список спецификаторов в порядке следования, затем этот список отображается в соответствующие парсеры, далее список сворачивается с помощью комбинатора 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<String, Any>

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() можно автоматически сгенерировать документацию.

На этом я завершаю статью и желаю всем кода без ошибок! Спасибо за внимание.

Комбинаторы синтаксического анализа на Kotlin