Scala: parser combinators на примере парсера формул03.04.2017 07:33

Время от времени у меня возникает желание придумать свой собственный маленький язык программирования и написать интерпретатор. В этот раз я начал писать на scala, узнал про библиотеку parser combinators, и был поражён: оказывается, можно писать парсеры легко и просто. Чтобы не превращать статью в пособие по «рисованию совы», ниже приведёна реализация разбора и вычисления выражений типа "1 + 2 * sin(pi / 2)".


Сам парсинг и вычисление выражения занимают всего лишь 43 непустых строчки — не то чтобы я сильно стремился сократить их количество, но выглядит это реально просто и лаконично. Проект на github.


Для сравнения:


  • длинный пример на java
  • короткий, но непонятный пример на C#

Итак, если вам не терпится увидеть результат:


Ответственный за парсинг кусочек кода
object FormulaParser extends RegexParsers with PackratParsers {

    def id: Parser[Id] = "[a-zA-Z][a-zA-Z0-9_]*".r ^^ Id

    def number: Parser[Number] = "-" ~> number ^^ (n => Number(-n.value)) |
        ("[0-9]+\\.[0-9]*".r | "[0-9]+".r) ^^ (s => Number(s.toDouble))

    def funcCall: Parser[FuncCall] = id ~ ("(" ~> expression <~ ")") ^^ (pair => FuncCall(pair._1, pair._2))

    def value: Parser[Expression] = number | funcCall | id | ("(" ~> expression <~ ")")

    lazy val term: PackratParser[Expression] = term ~ ("*" | "/") ~ value ^^ binOperation | value

    lazy val expression: PackratParser[Expression] = expression ~ ("+" | "-") ~ term ^^ binOperation | term
    ...
}

Посмотрите на следущую строчку: 


def value: Parser[Expression] = number | funcCall | id | ("(" ~> expression <~ ")")

Она подозрительно похожа на описание грамматики, но это валидный код, в котором среда разработки может сразу же обнаружить и подсветить большинство ошибок.


Это возможно по следующим причинам:


  1. В scala разрешено давать методам замечательные названия типа "~", "~>", "<~", "|", "^^". Комбинация парсеров p и q записывается как p~q, а возможность выбрать один из них: p|q. Читается намного лучше, чем p.andThen(q) или p.or(q)
  2. Благодаря неявным преобразованиям (implicits) и строчка "abc" и регулярное выражение "[0-9]+".r при необходимости превращаются в парсеры.
  3. В языке мощная статическая система типов, которая позволяет ловить ошибки сразу.

Думаю, мне удалось Вас заинтересовать, поэтому дальше всё будет по порядку.



Оглавление:


  1. Pegex Parsers
  2. Packrat Parsers
  3. код парсера целиком
  4. вычисление выражений
  5. заключение

Parser Combinators.


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


Regex parsers


Итак, самое простое — RegexParsers. Добавляют неявные преобразования из строк и регулярных выражений в парсеры.


object SimpleExample extends RegexParsers {
    def boolTrue: Parser[Boolean] = "true" ^^ (_ => true)
    // если читаем строчку "true", то вызывается функция, которая преобразует строчку в истинное значение boolean

    def bool: Parser[Boolean] = ("true" | "false") ^^ (_ == "true")
    // можно сгруппировать парсеры и применить функцию к результату

    def alternativeBool: Parser[Boolean] = "true" ^^ (_ => true) | "false" ^^ (_ => false)
    // или преобразовать каждый результат по отдельности

    def int: Parser[Int] = "[0-9]+".r ^^ (_.toInt)
    // парсим последовательность цифр и преобразуем в число.
    // метод .r создаёт регулярное выражение из строки

    def id: Parser[Id] = "[a-zA-Z][a-zA-Z0-9_]*".r ^^ Id
    // Id - функция, которая делает из строки объект типа Id
}

Кстати, значок ~ обозначает не только метод у парсера, но и имя case класса, хранящего пару значений. Кусочек кода из Parsers.scala: 


case class ~[+a, +b](_1: a, _2: b) {
    override def toString = "("+ _1 +"~"+ _2 +")"
}

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


def intInBrackets: Parser[Int] = "(" ~ int ~ ")" ^^ (p => p._1._2)

Что произойдёт?


  1. "(" неявно из строки превращается в парсер, который возвращает String
  2. парсер int возвращает Int
  3. "(" ~ int создаёт парсер для ~[String, Int]
  4. "(" ~ int ~ ")" создаёт парсер, который возвращает ~[~[String, Int], String]
  5. у парсера будет вызван метод ^^
  6. в метод передаётся функция, которая принимает аргумент p с типом ~[~[String, Int], String] и возвращает Int

В данном случае скобки не несут никакой полезной информации. Можно сделать так: 


def intInBrackets: Parser[Int] = "(" ~>  int <~ ")"

В этот раз скобки будут отброшены.


  • "(" ~> int создаёт парсер, который парсит скобку и потом Int, но возвращает только Int
  • int <~ ")" работает аналогично, но для левого аргумента

Выражения с оператором <~ советуют заключать в скобки, так как у него не очень высокий приоритет.


def funcCall: Parser[FuncCall] = id ~ ("(" ~> expression <~ ")") ^^ (pair => FuncCall(pair._1, pair._2))

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


def number: Parser[Number] = "-" ~> number ^^ (n => Number(-n.value)) |
        ("[0-9]+\\.[0-9]*".r | "[0-9]+".r) ^^ (s => Number(s.toDouble))
        // s.toDouble преобразует строку в число.

def value: Parser[Expression] = number | funcCall | id | ("(" ~> expression <~ ")")

private def binOperation(p: ~[~[Expression, String], Expression]) =
        BinOperation(p._1._1, BinOperator(p._1._2), p._2)

Я немножко поленился и превращаю строку в число стандартными методами. Время надо экономить)


Поскольку наше описание парсеров — это код, неоднозначные грамматики всё равно работают. В примере с парсингом number | funcCall | id мы пытаемся распарсить number, в случае неудачи — вызов функции и т.д. Порядок может быть важным, например (id | funcCall) при попытке распарсить «sin (x)» радостно распарсит Id("sin"), и парсер funcCall не будет вызван. Для корректной работы лучше написать (funcCall | id).


Packrat Parsers


Допустим, мы хотим распарсить последовательность единичек: 


object Ones extends RegexParsers {
    def ones: Parser[Any] =  ones ~ "1" | "1"
}

Парсинг ones начинается с того, что мы вызываем парсинг ones, который снова …


3c963a2177f34437bc213931d9ee3e22.jpg

Попытка распарсить единички приведёт к переполнению стека.


В данном случае можно изменить описание так, чтобы каждый раз «поглощалось» что-нибудь. Например: 


def ones: Parser[Any] =  "1" ~ ones | "1"

Но не всегда грамматику легко переписать. Выражния типа 3-2-1 должны распознаваться именно как (3-2)-1, вариант 3-(2-1) не подойдёт. С делением будет аналогичная проблема. Как это сделать без усложнения грамматики?


Нас спасут packrat — парсеры. Их идея заключается в том, что парсер может хранить «для себя» некоторую информацию о вызовах. Например, чтобы сохранять результат работы и не парсить одно и то же дважды… или чтобы корректно работать в случаях с рекурсией. 


object Ones extends RegexParsers with PackratParsers{
    lazy val ones: PackratParser[Any] =  ones ~ "1" | "1"
}

в трейте PackratParsers содержится неявное преобразование строчек и прочего в парсеры «нужного» типа.


PackratParser лучше создавать только один раз и хранить в переменной. Кроме того, если парсер p использует q, а q использует p, стоит использовать ленивую инициализацию.


    lazy val term: PackratParser[Expression] = term ~ ("*" | "/") ~ value ^^ binOperation | value

    lazy val expression: PackratParser[Expression] = expression ~ ("+" | "-") ~ term ^^ binOperation | term

Думаю, теперь понятно, как можно легко и непринуждённо распарсить 3–2–1 как (3–2)-1.


Возможно, у вас возникает вопрос: где парсер хранит информацию? Если её хранить прямо внутри PackratParser, то вызов парсера для другого ввода может дать некорректные результаты. Так вот, необходимая информация хранится вместе с «входными» данными парсера. Можно заглянуть в код библиотеки и убедиться в этом: 


class PackratReader[+T](underlying: Reader[T]) extends Reader[T] { outer =>

    private[PackratParsers] val cache = mutable.HashMap.empty[(Parser[_], Position), MemoEntry[_]]
    ...
}

Поэтому парсер принимает на вход не строку, а new PackratReader(new CharSequenceReader(string))


def apply(code: String): Either[LexerError, Expression] =
    parse(expression, new PackratReader(new CharSequenceReader(code))) match {
        case Success(result, next) => Right(result)
        case NoSuccess(msg, next) => Left(LexerError(msg))
    }

Что самое крутое — использование packrat парсеров ни к чему не обязывает, их можно комбинировать с обычными парсерами и наоборот.


Парсер готов


Код целиком: 


object FormulaParser extends RegexParsers with PackratParsers {

    def id: Parser[Id] = "[a-zA-Z][a-zA-Z0-9_]*".r ^^ Id

    def number: Parser[Number] = "-" ~> number ^^ (n => Number(-n.value)) |
        ("[0-9]+\\.[0-9]*".r | "[0-9]+".r) ^^ (s => Number(s.toDouble))

    def funcCall: Parser[FuncCall] = id ~ ("(" ~> expression <~ ")") ^^ (pair => FuncCall(pair._1, pair._2))

    def value: Parser[Expression] = number | funcCall | id | ("(" ~> expression <~ ")")

    lazy val term: PackratParser[Expression] = term ~ ("*" | "/") ~ value ^^ binOperation | value

    lazy val expression: PackratParser[Expression] = expression ~ ("+" | "-") ~ term ^^ binOperation | term

    private def binOperation(p: ~[~[Expression, String], Expression]) =
        BinOperation(p._1._1, BinOperator(p._1._2), p._2)

    def apply(code: String): Either[ParserError, Expression] =
        parse(expression, new PackratReader(new CharSequenceReader(code))) match {
            case Success(result, next) => Right(result)
            case NoSuccess(msg, next) => Left(ParserError(msg))
        }

    case class ParserError(msg: String)
}

sealed trait Expression

case class BinOperator(operator: String)

case class Number(value: Double) extends Expression
case class Id(name: String) extends Expression
case class BinOperation(left: Expression, op: BinOperator, right: Expression) extends Expression
case class FuncCall(funcName: Id, argument: Expression) extends Expression

Результат парсинга — либо дерево, либо сообщение об ошибке.


case классы — просто классы-обёртки над значениями, они все реализуют интерфейс Expression. слово sealed обозначает, что реализующие этот интерфейс классы должны содержаться в том же самом файле. Это позволяет с уверенностью говорить, что Expression может быть одного из четырёх типов.


Вычисление выражений


Код, который вычисляет выражения, тоже прост.
Я предполагаю, что на вход подаются корректные выражения.


object Evaluator {
    def apply(expression: Expression,
              variables: (String) => Double = Map.empty,
              functions: (String) => (Double) => Double = Map.empty): Double = {

        def eval(exp: Expression) = this (exp, variables, functions)

        expression match {
            case Number(value) => value
            case Id(name) => variables(name)
            case BinOperation(left, op, right) => operator2func(op)(eval(left), eval(right))
            case FuncCall(funcId, expr) => functions(funcId.name)(eval(expr))
        }
    }

    def operator2func(binOperator: BinOperator): (Double, Double) => Double =
        binOperator.operator match {
            case "+" => (a, b) => a + b
            case "-" => (a, b) => a - b
            case "*" => (a, b) => a * b
            case "/" => (a, b) => a / b
        }
}

Фишечки скалы — можно объявить функцию eval внутри функции apply для повышения читаемости кода. Вторая фишечка — в качестве аргумента по-умолчанию мы подсовываем Map.empty. Она пустая, поэтому может быть любого типа, она неизменяемая, поэтому она останется пустой, и реально мы получим ссылки на один и тот же объект — синглтон. Map.empty имеет метод apply(a: In):Out — мы можем считать её функцией.


Почти всё


Парсинг и вычислени выражений готовы. Посчитаем получившиеся строки кода (непустые):


  1. Парсер: 17 строк
  2. case-классы для описания AST: 6
  3. вычисление выражений: 20 строк.

И всё — причём код легко читается, его легко изменять и он практчиески не содержит ничего лишнего. Красота!


А оно работает?


Об этом стоит подумать ещё на этапе написания парсера, но проверяющий код ни на что не влияет, потому приведён только только сейчас. (конечно, можно написать тестики…, но эта статья о написании парсеров, а не тестов, поэтому я сделал как можно проще)


Код, который проверяет работу
object Main extends App {
    def eval(code: String,
             variables: (String) => Double = Map.empty,
             functions: (String) => (Double) => Double = Map.empty) = {
        val parsed = FormulaParser(code)
        parsed.left.foreach(error => println(s"\'$code\' parsing error: $error"))
        parsed.right.map(expr => Evaluator(expr, variables, functions)).foreach(d => println(s"\'$code\' = $d"))
    }

    eval("1")
    eval("0.1")
    eval("1.")
    eval("  1  ")
    eval("-0.1")

    eval("1+2")
    eval("2-1")
    eval("2*3")
    eval("4/2")

    val vars = Map(
        "pi" -> math.Pi,
        "e" -> math.E)

    val funcs: (String) => (Double) => Double = Map(
        "sin" -> math.sin,
        "cos" -> math.cos,
        "inc" -> { d: Double => d + 1 }
    )

    eval("pi", vars)
    eval("inc(e)", vars, funcs)

    eval("2+2*2")
    eval("1+2*(3+4*5)")
    eval("8/2/2")
    eval("8-1-2")

    eval("1. + 2.0 * sin(pi / 2)", vars, funcs)
}

Заключение


Для серьёзных целей существуют генераторы парсеров и прочие штуки.


Но если Вам хочется парсить что-нибудь относительно простое, экспериментировать и получать мгновенную обратную связь — можно использовать описанный выше подход. Информации на русском почти нет, да и на английском тоже не очень много. Я надеюсь, что статья поможет кому-нибудь.


Полезные ссылочки:


  1. библиотека на github
  2. Пример парсинга DSL
  3. «Programmin in scala» 2nd edition, глава «parser combinators».

Приведённый выше код я выложил на github


Как запустить

Используется система сборки sbt. Достаточно установить её, перейти в папку с проектом и набрать в консоли «sbt run»


P.S. У меня всё ещё есть цель дописать свой интерпретатор lua-подобного языка с шахматами и поэтессами. Я вроде бы продумал синтаксис языка, потом в процессе написания парсера наткнулся на противоречия — пришлось отказаться от пары поэтесс и заменить шахматы на шашки, но результат всё равно получается довольно интересным.

Комментарии (2)

  • 3 апреля 2017 в 04:55

    +1

    ↑

    ↓

    А почему взяли именно встроенную в скала библиотеку, а не сторонние парсеры? Parboiled2 или FastParse например.

  • 3 апреля 2017 в 06:29

    +1

    ↑

    ↓

    Не обязательно покупать второе издание Programming in Scala, чтоб почитать про парсеры — в первом почти то же самое, но доступно совершенно свободно. Programming in Scala/Combinator Parsing

    Вызывать методы _N вручную все-таки не стоит. Предполагается их использовать следующим образом: 

        private def binOperation(p: Expression ~ String ~ Expression) = p match {
        case e1 ~ op ~ e2 => BinOperation(e1, BinOperator(op), e2)
    }

    Вместо PackratParser можно использовать rep1, слегка усложнив метод binOperation.

© Habrahabr.ru