Статьи

Начало работы с компиляторами Scala Parser

Декабрь 9, 2017

Scala предоставляет очень простой способ создать свой собственный язык программирования, используя свою библиотеку синтаксического анализатора. Это делает создание вашего собственного предметно-ориентированного языка (например, DSL) или интерпретируемого языка проще, чем вы могли себе представить. В качестве учебника давайте напишем парсер, который анализирует простые математические выражения, такие как «1 + 9 * 8» и «4 * 6 / 2-5».

Для тех из вас, кто знаком с языковым дизайном, грамматика EBNF для этого языка будет выглядеть примерно так:

digit ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
number ::= digit | digit number
operator ::= "+" | "-" | "*" | "/"
expr ::= number (operator expr)?

Чтобы начать писать синтаксический анализатор с библиотекой синтаксического анализа Scala, мы пишем класс, который расширяет  черту Parsers  . Вот пример класса, который расширяет  RegexParsers, который является субтитром Parsers  .

class ExprParser extends RegexParsers {
    val number = "[1-9][0-9]+".r

    def expr: Parser[Any] = number ~ opt(operator ~ expr )

    def operator: Parser[Any] = "+" | "-" | "*" | "/"
}

Единственные различия между определением действительных токенов в Scala и определением в грамматике EBNF заключаются в следующем:

  • Scala использует «~» между каждым токеном
  • Вместо использования «?» Как и в грамматике EBNF, Scala использует ключевое слово «opt»

Чтобы выполнить наш анализатор, мы просто вызываем унаследованный   метод анализа, который является частью  черты Parsers .

def main(args : Array[String]) {

    val parser = new ExprParser

    val result = parser.parseAll(parser.expr, "9*8+21/7")

    println(result.get)
}

Результатом этого println будет:

((Некоторые из них ((+ Некоторые из них ((/ ~ (7 ~ отсутствует))))))))) 9 ~ Некоторые из них ((* ~ 8 ~ ~ (21 ~)

Были сделаны! Ну не совсем. Прямой вывод — это способ, которым Scala видит результат наших операций синтаксического анализатора. Чтобы сделать наш язык более значимым, давайте добавим немного кода Scala для вычисления арифметической операции и вывода результата в вывод.

Давайте начнем наш квест, чтобы вычислить результат, изучив что «(9 ~ Некоторые ((* ~ (8 ~ Некоторые ((+ ~ (21 ~ Некоторые) ((/ ~ (7 ~ Нет)))))))))) действительно означает в мире Скала. Давайте посмотрим на подмножество этой строки, «(9 ~ Some ((* ~ (8 ~ None))))». Это результат разбора «9 * 8». Первая часть, которая выглядит интересной, это «9 ~ Some (…)». В нашем парсере мы определили следующее правило:

def expr: Parser[Any] = number ~ opt(operator ~ expr)

Ясно, что «число» оценивается как «9», а «~» печатается дословно, что, как вы должны помнить, используется в синтаксических анализаторах Scala для объединения частей грамматики. Тем не менее, что происходит с «Некоторые (…)»? Что ж, всякий раз, когда Scala анализирует оператор opt (x), он будет оценивать его как Some (…) или None, оба из которых являются подклассами Option. Это имеет смысл … оператор opt (x) оценивает Option.

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

def expr: Parser[Any] = number ~ opt(operator ~ expr)

Нам нужно изменить это определение синтаксического анализатора, чтобы оно возвращало Int вместо Any. Нам также нужно вычислить результат арифметической операции. Наше правило грамматики допускает либо одно число, либо число, за которым следует арифметический оператор и другое число. Если мы имеем дело с одним числом, нам нужно сказать парсеру преобразовать результат в Int. Чтобы сделать это, мы вносим следующую модификацию в наше правило синтаксического анализатора:

def expr: Parser[Int] = (number ^^ { _.toInt }) { }

^^ просто говорит парсеру выполнить следующий за ним код, содержащийся в {…}. Все, что мы делаем, это конвертируем его в Int.

Затем нам нужно сообщить парсеру, что делать, когда он встречает число или когда он встречает число, за которым следует оператор и другой номер. Для этого нам нужно определить целочисленную операцию для каждой ситуации (одно целочисленное значение, сложение двух значений, вычитание двух значений, деление двух значений и умножение двух значений).

def expr: Parser[Int] = (number ^^ { _.toInt }) ~ opt(operator ~ expr ) ^^ {
    case a ~ None => a
    case a ~ Some("*" ~ b) => a * b
    case a ~ Some("/" ~ b) => a / b
    case a ~ Some("+" ~ b) => a + b
    case a ~ Some("-" ~ b) => a - b
}

Есть пять случаев, которые мы рассматриваем. Первая — это ситуация, когда у нас есть только одно целое число (~ None). Когда у нас есть Int с None после него, мы просто оцениваем целочисленное значение как есть. Вторая ситуация, когда у нас есть целое число, умноженное на другое целое число (a ~ Some («*» ~ b)). В этом случае мы просто выполняем a * b. Затем мы переходим к определению правил деления, сложения и вычитания.

Ключевые выводы из этого урока:

  • Вы определяете тип, который ваше правило синтаксического анализа возвращает в скобках определения Parser []. В этом примере это Int.
  • Вы можете добавить собственный код Scala для работы с результатами парсера с помощью ^^ {…}

Теперь, когда мы заложили основу для комбинаторов синтаксического анализатора Scala, мы можем использовать эти функции для создания полнофункционального интерпретируемого языка, который содержит условия if-else, циклы и даже вызовы функций.

Вот статья о том, как создать полнофункциональный интерпретируемый язык с помощью этого подхода:  https://dzone.com/articles/create-a-programming-language-with-scala-parser-co

30
Share: