О чём гайд

Этот гайд является машинным переводом документации парсера Kudzu с правками и некоторыми вольностями:

  • версия в грэдле заменена на текущую (на момент 05.03.24)
  • в листингах программ приведён полный текст рабочего кода, включая имя пакета (оно у вас будет своё)

Установка

repositories {
    mavenCentral()
}

// for plain JVM or Android projects
dependencies {
    implementation("io.github.copper-leaf:kudzu-core:5.1.0")
}

// for multiplatform projects
kotlin {
    sourceSets {
        val commonMain by getting {
            dependencies {
                implementation("io.github.copper-leaf:kudzu-core:{{site.version}}")
            }
        }
    }
}

Основное использование

Смотрите тесты для примера использования каждого включенного анализатора. Далее приведен базовый пример синтаксического анализа и оценки в нескольких различных форматах.

Объединение нескольких парсеров

package com.github.KuzyaGlebkin

import com.copperleaf.kudzu.parser.ParserContext
import com.copperleaf.kudzu.parser.chars.CharInParser
import com.copperleaf.kudzu.parser.chars.DigitParser
import com.copperleaf.kudzu.parser.many.AtLeastParser
import com.copperleaf.kudzu.parser.mapped.MappedParser
import com.copperleaf.kudzu.parser.maybe.MaybeParser
import com.copperleaf.kudzu.parser.sequence.SequenceParser

fun main() {
    val intLiteralParser = MappedParser(
        SequenceParser(
            MaybeParser(
                CharInParser('-')
            ),
            AtLeastParser(
                DigitParser(),
                minSize = 1
            )
        )
    ) { it.text.toInt() }

    val (node, remainingText) = intLiteralParser.parse(ParserContext.fromString("-123"))
    val parsedValue: Int = node.value
    println(parsedValue==-123)
}

Найти и заменить структурированные последовательности текстом

package com.github.KuzyaGlebkin

import com.copperleaf.kudzu.parser.ParserContext
import com.copperleaf.kudzu.parser.SourcePosition
import com.copperleaf.kudzu.parser.chars.CharInParser
import com.copperleaf.kudzu.parser.choice.PredictiveChoiceParser
import com.copperleaf.kudzu.parser.many.ManyParser
import com.copperleaf.kudzu.parser.mapped.MappedParser
import com.copperleaf.kudzu.parser.sequence.SequenceParser
import com.copperleaf.kudzu.parser.text.IdentifierTokenParser
import com.copperleaf.kudzu.parser.text.ScanParser

fun main() {
    val variableMap = mapOf(
        "asdf" to "first",
        "qwerty" to "second",
    )

    val patternToReplace = MappedParser(
        SequenceParser(
            CharInParser('#'),
            CharInParser('{'),
            IdentifierTokenParser(),
            CharInParser('}'),
        )
    ) {
        val (_, _, identifier, _) = it.children
        variableMap[identifier.text]
    }

    val findAndReplaceParser = ManyParser(
        PredictiveChoiceParser(
            patternToReplace,
            ScanParser(patternToReplace),
        )
    )

    val (node, remainingText) = findAndReplaceParser.parse(ParserContext.fromString("the value of #{asdf} is 1, but #{qwerty} is 2"))
    println(node.text)
}

Построение и вычисление выражений с помощью пользовательских операторов

package com.github.KuzyaGlebkin

import com.copperleaf.kudzu.parser.ParserContext
import com.copperleaf.kudzu.parser.expression.ExpressionParser
import com.copperleaf.kudzu.parser.expression.Operator
import com.copperleaf.kudzu.parser.value.IntLiteralParser

fun Int.pow(exponentVal: Int): Int {
    val base = this
    var exponent = exponentVal
    var result: Int = if (exponentVal >= 0) { 1 } else { 0 }

    while (exponent > 0) {
        result *= base
        exponent -= 1
    }

    return result
}

fun main() {
    val expressionParser = ExpressionParser<Int>(
        termParser = { IntLiteralParser() },

        // precedence — приоритет
        Operator.Infix(op = "+", precedence = 40) { l, r -> l + r },
        Operator.Infix(op = "-", precedence = 40) { l, r -> l - r },
        Operator.Infix(op = "*", precedence = 60) { l, r -> l * r },
        Operator.Infix(op = "/", precedence = 60) { l, r -> l / r },

        Operator.Prefix(op = "-", precedence = 80) { r -> -r },
        Operator.Infixr(op = "^", precedence = 70) { l, r -> l.pow(r) },
    )

    val (node, remainingText) = expressionParser.parse(ParserContext.fromString("2 ^ ((4 - 2) * 2) + 2 ^ (-3)", skipWhitespace = true))
    val value = expressionParser.evaluator.evaluate(node)
    println(value == 16)
}

Детали реализации

В Kudzu синтаксический анализатор - это класс, который расширяет Parser и реализует 2 метода: predict, и parse. predict это метод, который проверяет, способен ли анализатор использовать следующий символ, и parse фактически реализует логику синтаксического анализа и возвращает Node.

Существует два типа узлов (нод), TerminalNode и NonTerminalNode. TerminalNode обычно содержит необработанный текст, который был распарсен из входных данных, в то время как a NonTerminalNode содержит другие узлы. Таким образом, нетерминальные узлы составляют внутренние узлы дерева синтаксического анализа1, в то время как терминальные узлы составляют листья дерева синтаксического анализа.

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

API-интерфейсы разработаны таким образом, что каждый шаг полностью изолирован, так что код для одного шага можно легко заменить или повторно использовать по мере необходимости, обеспечивая большую гибкость, сохраняя при этом код для каждой фазы чистым и легким для понимания. Общий процесс синтаксического анализа и оценки текста с помощью Kudzu заключается в следующем:

  1. String
  2. ParserContext
  3. Parser.parse(ParserContext) -> Pair<Node, ParserContext>
  4. Node.visit([Visitor]) -> Unit
  1. Текстовая строка, которая должна быть проанализирована.
  2. Предоставляет единый API для синтаксических анализаторов, позволяющий использовать отдельные символы. Отслеживает позицию источника.
  3. Каждая грамматика имеет единственное корневое правило, которое определяется как простой экземпляр Parser. Результатом является единственный корневой узел и ParserContext, представляющий текст, который остается неиспользованным. Ожидается, что успешный синтаксический анализ вернет пустой ParserContext. Этот корневой анализатор будет рекурсивно вызывать тот же метод для других объектов анализатора, каждый из которых создает узлы в дереве и продвигает позицию в ParserContext.
  4. Узел может посещать любое количество объектов-посетителей (Visitor objects), которые распознают и оценивают отдельные узлы в дереве синтаксического анализа.
1

в оригинале — parse tree, в отличии от термина abstract syntax tree обозначает дерево, которое содержит все символы, которые были в тексте, например тут видно, что it.children возвращает всех потомков, а не только нужный нам идентификатор val (_, _, identifier, _) = it.children

Создание парсеров

Хотя вы можете создавать собственные подклассы парсера (Parser), которые реализуют вашу логику синтаксического анализа, обычно лучше использовать встроенные примитивы парсера, предоставляемые Kudzu. Ниже приведен базовый пример построения парсера, который распознает либо полное слово, либо число:

Update

Автор ответил по поводу ChoiceParser

package com.github.KuzyaGlebkin

import com.copperleaf.kudzu.parser.ParserContext
import com.copperleaf.kudzu.parser.chars.DigitParser
import com.copperleaf.kudzu.parser.chars.LetterParser
import com.copperleaf.kudzu.parser.many.ManyParser
import com.copperleaf.kudzu.parser.sequence.SequenceParser
import com.copperleaf.kudzu.parser.text.OptionalWhitespaceParser
import com.copperleaf.kudzu.parser.choice.ChoiceNParser

fun main() {
    val wordParser = ManyParser(LetterParser())
    val numberParser = ManyParser(DigitParser())
    // в оригинале — ChoiceParser, но я его в пакете не нашёл
    val tokenParser = ExactChoiceParser(
        wordParser,
        numberParser
    )
    val statement = ManyParser(
        SequenceParser(
            tokenParser,
            OptionalWhitespaceParser()
        )
    )
    val output = statement.parse(ParserContext.fromString("one two 1234 asdf 56 qwerty 7890"))
    println(output)
}

Эта простая грамматика будет соответствовать входной строке типа one two 1234 asdf 56 qwerty 7890 и демонстрирует, насколько сложными могут быть парсеры. Парсеры могут быть построены из более мелких, и представляет несколько важных доступных встроенных парсеров. Ниже приведено описание некоторых из этих типов парсеров (просмотрите исходный код для всех доступных парсеров)

  • LetterParser: Использует одну букву из входных данных, распознается при помощи предоставляемого Котлином char.isLetter()
  • DigitParser: Потребляет одну цифру из входных данных, распознается при помощи предоставляемого Котлином char.isDigit()
  • ManyParser: Принимает другой парсер и повторно использует его на входных данных до тех пор, пока этот парсер может их обрабатывать. Поскольку он сам по себе является Parser и принимает Parser в качестве входных данных, полная грамматика теперь определяется рекурсивно и использует прогностический (predictive*) подход для определения, может ли продолжаться следующая итерация его парсера. Вы можете передать ManyParser любой другой парсер, а не только парсеры символьного типа, и поэтому сколь угодно сложные вложенные грамматики можно повторять по мере необходимости. Вы заметите, что мы дали парсеру name. Это имя привязывается к создаваемым им узлам, так что при оценке дерева синтаксического анализа мы можем искать узлы с именем word или number и соответственно выполнять различные действия.
  • PredictiveChoiceParser: Получает список парсеров и предикативно (predicatively*) выбирает один из них для продолжения синтаксического анализа.
  • SequenceParser: Получает список парсеров и выполняет каждый из них по порядку один раз.
  • OptionalWhitespaceParser: Принимает и удаляет пробелы, если они существуют. Поскольку пробелы необязательны входные данные, такие как two1234, все равно будут совпадать и будут проанализированы правильно.
  • LazyParser: Некоторые грамматики имеют производственные правила (production rules), которые сами по себе являются рекурсивными, например, A := B A. LazyParser Действует как заполнитель (placeholder), просто делегируя его другому парсеру. Рекурсивные правила должны быть построены с использованием этих ленивых типов, поскольку нам нужен конкретный экземпляр для передачи другим парсерам. Этот ленивый парсер позволяет нам создавать ссылку на парсер, передавая ее тем парсер, которым это нужно, и на более позднем этапе заполнять детали парсер по мере необходимости.
  • Прогностическая грамматика (predictive grammar) проверяет, можно ли использовать парсер, предварительно вызвав его predict метод. Ожидается, что этот метод проверит, способен ли он использовать следующий символ, и если он не может использовать следующий символ, то весь парсер не сможет продолжить работу. Для парсеров типа many эта предсказуемость используется для определения того, когда следует прекратить выполнение итерации. Для парсеров типа choice это определяет, какой субпродукт будет выбран: будет использоваться первый субпарсер, для которого predict возвращает true, и другие правила тестироваться не будут. Это сделано для повышения производительности и предотвращения бесконечной рекурсии.

Вычисление деревьев синтаксического анализа

После создания полного анализатора и преобразования текста в AST1 мы можем теперь оценить его. Оценка AST состоит из Visitor.Callback или простого обратного вызова лямбды. Ниже приведен базовый пример использования вымышленной грамматики:

val parser = constructParser()

val (node, _) = parser.parse(input)

// simple visiting, such as finding all nodes of a particular type and not caring about the structure
node.visit { node ->
    // do something with each node as it is entered in the tree
}

// alternatively, visit with a full set of callbacks to also introspect the parse-tree's structure
node.visit(object : Visitor.Callback {
    var depth: Int = 0
    override fun enter(node: Node) {
        depth++
    }
    override fun exit(node: Node) {
        depth--
    }
    override fun onStart() { }
    override fun onFinish() { }
})

А вот уже мой пример, который использует грамматику из прошлых примеров. Носколько такой пример корректен — не знаю.

package com.github.KuzyaGlebkin

import com.copperleaf.kudzu.node.Node
import com.copperleaf.kudzu.visitor.Visitor
import com.copperleaf.kudzu.parser.ParserContext
import com.copperleaf.kudzu.parser.expression.ExpressionParser
import com.copperleaf.kudzu.parser.expression.Operator
import com.copperleaf.kudzu.parser.value.IntLiteralParser
import com.copperleaf.kudzu.visit

fun Int.pow(exponentVal: Int): Int {
    val base = this
    var exponent = exponentVal
    var result: Int = if (exponentVal >= 0) { 1 } else { 0 }

    while (exponent > 0) {
        result *= base
        exponent -= 1
    }

    return result
}
fun constructParser() : ExpressionParser<Int> {
    return ExpressionParser<Int>(
        termParser = { IntLiteralParser() },

        // precedence — приоритет
        Operator.Infix(op = "+", precedence = 40) { l, r -> l + r },
        Operator.Infix(op = "-", precedence = 40) { l, r -> l - r },
        Operator.Infix(op = "*", precedence = 60) { l, r -> l * r },
        Operator.Infix(op = "/", precedence = 60) { l, r -> l / r },

        Operator.Prefix(op = "-", precedence = 80) { r -> -r },
        Operator.Infixr(op = "^", precedence = 70) { l, r -> l.pow(r) },
    )
}

fun main() {
    val parser = constructParser()
    val input = ParserContext.fromString("2 ^ ((4 - 2) * 2) + 2 ^ (-3)", skipWhitespace = true)

    val (node, _) = parser.parse(input)

// simple visiting, such as finding all nodes of a particular type and not caring about the structure
    node.visit { node ->
        println(node)
    }

// alternatively, visit with a full set of callbacks to also introspect the parse-tree's structure
    node.visit(object : Visitor.Callback {
        var depth: Int = 0
        override fun enter(node: Node) {
            depth++
        }
        override fun exit(node: Node) {
            depth--
        }
        override fun onStart() { }
        override fun onFinish() { }
    })
}
1

До этого говорилось, что Кудзу не создает абстрактное синтаксическое дерево, что тут имелось в виду спрошу у автора. Update Автор сказал, что обновит документацию в следующим релизе.