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

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

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

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

    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. В языке мощная статическая система типов, которая позволяет ловить ошибки сразу.

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

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) = p match {
        case e1 ~ op ~ e2 => BinOperation(e1, BinOperator(op), e2)
    }

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

Поскольку наше описание парсеров — это код, неоднозначные грамматики всё равно работают. В примере с парсингом 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, который снова ...

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

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

    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 парсеров ни к чему не обязывает, их можно комбинировать с обычными парсерами и наоборот.

Парсер готов

взято отсюда