Время от времени у меня возникает желание придумать свой собственный маленький язык программирования и написать интерпретатор. В этот раз я начал писать на scala, узнал про библиотеку parser combinators, и был поражён: оказывается, можно писать парсеры легко и просто. Чтобы не превращать статью в пособие по "рисованию совы", ниже приведёна реализация разбора и вычисления выражений типа "1 + 2 * sin(pi / 2)".
Сам парсинг и вычисление выражения занимают всего лишь 43 непустых строчки — не то чтобы я сильно стремился сократить их количество, но выглядит это реально просто и лаконично. Проект на github.
Для сравнения:
Итак, если вам не терпится увидеть результат:
Ответственный за парсинг кусочек кода
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 <~ ")")
Она подозрительно похожа на описание грамматики, но это валидный код, в котором среда разработки может сразу же обнаружить и подсветить большинство ошибок.
Это возможно по следующим причинам:
- В scala разрешено давать методам замечательные названия типа
"~", "~>", "<~", "|", "^^". Комбинация парсеров p и q записывается как p~q, а возможность выбрать один из них: p|q. Читается намного лучше, чем p.andThen(q) или p.or(q)
- Благодаря неявным преобразованиям (implicits) и строчка
"abc" и регулярное выражение "[0-9]+".r при необходимости превращаются в парсеры.
- В языке мощная статическая система типов, которая позволяет ловить ошибки сразу.
Думаю, мне удалось Вас заинтересовать, поэтому дальше всё будет по порядку.
Читать полностью »
