В последнее время все большую популярность приобретают предметно-ориентированные языки (domain-specific languages - DSL). Вследствие этого одной из наиболее важных характеристик функциональных языков является их применимость для создания DSL. В этой статье Тед Ньювард рассказывает о синтаксическом анализе выражений, написанных на ранее рассмотренном DSL, и преобразовании их в AST для последующей интерпретации (AST и интерпретатор выражений были описаны в предыдущей статье). В статье будут также продемонстрированы возможности функциональных языков для создания "внешних" DSL. Синтаксический анализ текста и создание древовидной структуры данных будет реализовано при помощи так называемых комбинаторов парсеров , которые представляют собой стандартную библиотеку Scala, разработанную специально для этих целей.
На настоящий момент ситуация выглядит следующим образом: в процессе создания DSL (в нашем случае - простого языка арифметических выражений) мы определили структуру AST со следующими типами вершин:
- бинарные операторы сложения, вычитания, умножения и деления;
- унарный оператор смены знака (отрицания);
- числовые константы.
Был также создан интерпретатор, умеющий вычислять значение выражения, представленного в виде дерева. Кроме того, интерпретатор включает функцию для оптимизации выражений с целью уменьшения объема вычислений.
При этом код интерпретатора выглядит следующим образом (листинг 1).
Листинг 1. AST и интерпретатор языка выражений
package com.tedneward.calcdsl
{
private[calcdsl] abstract class Expr
private[calcdsl] case class Variable(name : String) extends Expr
private[calcdsl] case class Number(value : Double) extends Expr
private[calcdsl] case class UnaryOp(operator : String, arg : Expr) extends Expr
private[calcdsl] case class BinaryOp(operator : String, left : Expr, right : Expr)
extends Expr
object Calc
{
/**
* Function to simplify (a la mathematic terms) expressions
*/
def simplify(e : Expr) : Expr =
{
e match {
// Двойное отрицание не меняет значение операнда
case UnaryOp("-", UnaryOp("-", x)) => x
// Знак "+" не меняет значение операнда
case UnaryOp("+", x) => x
// Умножение x на 1 равно х
case BinaryOp("*", x, Number(1)) => x
// Умножение 1 на x равно х
case BinaryOp("*", Number(1), x) => x
// Умножение х на 0 равно 0
case BinaryOp("*", x, Number(0)) => Number(0)
// Умножение 0 на x равно 0
case BinaryOp("*", Number(0), x) => Number(0)
// Деление х на 1 равно х
case BinaryOp("/", x, Number(1)) => x
// Добавление х к 1 равно х
case BinaryOp("+", x, Number(0)) => x
// Добавление 1 к х равно х
case BinaryOp("+", Number(0), x) => x
// Других вариантов упрощения нет
case _ => e
}
}
def evaluate(e : Expr) : Double =
{
simplify(e) match {
case Number(x) => x
case UnaryOp("-", x) => -(evaluate(x))
case BinaryOp("+", x1, x2) => (evaluate(x1) + evaluate(x2))
case BinaryOp("-", x1, x2) => (evaluate(x1) - evaluate(x2))
case BinaryOp("*", x1, x2) => (evaluate(x1) * evaluate(x2))
case BinaryOp("/", x1, x2) => (evaluate(x1) / evaluate(x2))
}
}
}
}
|
Те из вас, кто прочитал предыдущую статью, помнят, что в качестве упражнения было предложено усовершенствовать оптимизацию, чтобы упрощение выражений выполнялось на произвольном уровне дерева, а не только на верхнем, как в листинге 1. Наиболее простой вариант был предложен Лексом Спуном (Lex Spoon). Он заключается в том, что функция simplify сначала вызывается рекурсивно для каждого из операндо, а затем выполняется упрощение самой операции на более высоком уровне (листинг 2).
Листинг 2. Усовершенствованная функция упрощения выражений
/*
* Вариант Лекса:
*/
def simplify(e: Expr): Expr = {
// сначала упрощаем подвыражения
val simpSubs = e match {
// упрощаем обе части выражения
case BinaryOp(op, left, right) => BinaryOp(op, simplify(left), simplify(right))
// упрощаем операнд
case UnaryOp(op, operand) => UnaryOp(op, simplify(operand))
// здесь нечего упрощать
case _ => e
}
// теперь упрощаем само выражение, считая,
// что все вложенные выражения уже упрощены
def simplifyTop(x: Expr) = x match {
// Двойное отрицание не меняет значение операнда
case UnaryOp("-", UnaryOp("-", x)) => x
// Знак "+" не меняет значение операнда
case UnaryOp("+", x) => x
// Умножение x на 1 равно х
case BinaryOp("*", x, Number(1)) => x
// Умножение 1 на x равно х
case BinaryOp("*", Number(1), x) => x
// Умножение х на 0 равно 0
case BinaryOp("*", x, Number(0)) => Number(0)
// Умножение 0 на x равно 0
case BinaryOp("*", Number(0), x) => Number(0)
// Деление х на 1 равно х
case BinaryOp("/", x, Number(1)) => x
// Добавление х к 1 равно х
case BinaryOp("+", x, Number(0)) => x
// Добавление 1 к х равно х
case BinaryOp("+", Number(0), x) => x
// Других вариантов упрощения нет
case _ => e
}
simplifyTop(simpSubs)
}
|
Спасибо, Лекс!
На данный момент перед нами стоит вторая часть задачи по созданию DSL - создание программного модуля, преобразующего выражение, заданное в текстовом виде, в AST. Этот процесс известен под именем " синтаксический разбор " и состоит из нескольких фаз: разбиение на токены , лексический анализ и синтаксический анализ.
Исторически существуют два способа создания программ для синтаксического разбора (парсеров):
- вручную;
- при помощи автоматизированных средств (генераторов парсеров).
Первый вариант заключается в том, что разработчик самостоятельно пишет код анализа каждого символа во входном потоке. При этом обработка символа, как правило, определяется не только самим символом, но и теми, которые были проанализированы до него (а может быть, - и после него). Этот метод успешно работает для простых языков, однако сопряжен с серьезными трудностями в случае языков с развитым синтаксисом.
Альтернативой служит использование генераторов парсеров. Исторически наибольшую популярность получили два генератора - lex (генератор лексических анализаторов) и yacc (Yet Another Compiler Compiler - генератор синтаксических анализаторов). Благодаря этим программам разработчикам парсеров не приходится создавать их вручную, достаточно передать на вход lex специальное описание лексики языка, после чего тот автоматически создаст самую низкоуровневую часть будущего парсера. Затем полученный лексический анализатор вместе с файлом, описывающим грамматические правила языка, передаются на вход yacc, который генерирует код парсера (грамматика языка определяет, в частности, список ключевых слов, правила описания блоков кода и т. д.).
Этот процесс подробно описан в учебниках по теории вычислительных наук, поэтому мы не будем углубляться в детали конечных автоматов и парсеров LARL- и LR-грамматик. Те из вас, кому интересны эти подробности, могут обратиться к статьям и книгам по данной тематике.
Далее мы перейдем к третьей возможности Scala, служащей для создания синтаксических анализаторов - комбинаторов парсеров . Эта возможность целиком относится к функциональной части Scala. Комбинаторы парсеров позволяют объединять различные части языка в компоненты, которые внешне напоминают спецификацию языка и решают задачу синтаксического разбора, не требуя при этом генерации кода.
Для понимания целей создания и возможностей комбинаторов парсеров желательно определенное знакомство с таким способом описания грамматики языка, как форма Бэкуса-Наура (Backus-Naur Form - БНФ). Например, наш язык арифметических выражений можно описать в БНФ следующим образом (листинг 3).
input ::= ws expr ws eoi;
expr ::= ws powterm [{ws '^' ws powterm}];
powterm ::= ws factor [{ws ('*'/'/') ws factor}];
factor ::= ws term [{ws ('+'/'-') ws term}];
term ::= '(' ws expr ws ')' / '-' ws expr / number;
number ::= {dgt} ['.' {dgt}] [('e'/'E') ['-'] {dgt}];
dgt ::= '0'/'1'/'2'/'3'/'4'/'5'/'6'/'7'/'8'/'9';
ws ::= [{' '/'\t'/'\n'/'\r'}];
|
В БНФ элемент в левой части каждого выражения задает имя для набора различных вариантов входных данных. Элементы в правой части представляют собой константы и выражения языка, а также их сочетания.
Одним из преимуществ описания языка в БНФ является то, что от БНФ легче перейти к комбинаторам парсеров в Scala. Обратите внимание на листинг 4, в котором показана упрощенная форма БНФ из листинга 3.
Листинг 4. Упрощенная грамматика языка
expr ::= term {'+' term / '-' term}
term ::= factor {'*' factor / '/' factor}
factor ::= floatingPointNumber / '(' expr ')'
|
В этой записи фигурные скобки ({}) обозначают возможность повторения (ноль или более раз), а вертикальная черта (/, также известная как "конвейерный символ") - отношение типа "или". Таким образом, в листинге 4 записано, что выражение factor может быть либо выражением типа floatingPointNumber (определение этого правила опущено), либо выражением типа expr, заключенным в круглые скобки.
Грамматику, записанную в такой форме, легко трансформировать в парсер на Scala (листинг 5).
package com.tedneward.calcdsl
{
object Calc
{
// ...
import scala.util.parsing.combinator._
object ArithParser extends JavaTokenParsers
{
def expr: Parser[Any] = term ~ rep("+"~term / "-"~term)
def term : Parser[Any] = factor ~ rep("*"~factor / "/"~factor)
def factor : Parser[Any] = floatingPointNumber / "("~expr~")"
def parse(text : String) =
{
parseAll(expr, text)
}
}
def parse(text : String) =
{
val results = ArithParser.parse(text)
System.out.println("parsed " + text + " as " + results + " which is a type "
+ results.getClass())
}
// ...
}
}
|
Преобразование фактически заключается в замене грамматических правил в БНФ на синтаксические конструкции комбинаторов: пробелы меняются на методы ~, обозначающие последовательность, повторы - на метод rep, а "или" по-прежнему представляются в виде /. Строковые константы также остаются без изменений.
Своим удобством данный подход частично обязан двум вещам: стандартному базовому классу JavaTokenParsers, от которого унаследован класс парсера, и комбинатору floatingPointNumber. Первый, в свою очередь, является наследником других классов, которые полезны в случае, если анализируемый язык не столь хорошо сочетается с синтаксическими конструкциями в Java. Второй же берет на себя детали разбора десятичной записи чисел с плавающей точкой.
Данная инфиксная грамматика достаточно проста (поэтому часто используется в качестве примера) и позволяет создавать парсеры любыми способами, в частности, несложно было бы разработать парсер вручную благодаря сходству между самой грамматикой и кодом создания парсера.
Принцип работы комбинатора парсеров
Для того чтобы понять принципы работы показанного выше парсера, необходимо ненадолго погрузиться в вопросы реализации комбинаторов. По своей природе каждый "парсер" представляет собой функцию (или case-класс), которая получает некоторые входные данные и возвращает объект-парсер. Например, комбинаторы самого нижнего уровня базируются на простых парсерах, которые принимают на вход объекты, считывающие элементы из входного потока (экземпляры Reader) и возвращающие объекты, обладающие некоторый высокоуровневой семантикой (экземпляры Parser). Пример показан в листинге 6.
Листинг 6. Пример простейшего парсера
type Elem type Input = Reader[Elem] type Parser[T] = Input => ParseResult[T] sealed abstract class ParseResult[+T] case class Success[T](result: T, in: Input) extends ParseResult[T] case class Failure(msg: String, in: Input) extends ParseResult[Nothing] |
Таким образом, Elem является абстрактным типом для представления любого вида входных данных, которые можно подвергнуть синтаксическому разбору. Как правило, таковыми являются текстовые строки или потоки. Тип Input представляет собой Elem, заключенный внутрь scala.util.parsing.input.Reader (квадратные скобки означают, что Reader является параметризованным типом данных, они играют роль, аналогичную угловым скобкам в C++ или Java). Наконец, Parser типа T - это такой тип данных, который принимает на вход экземпляр Input и возвращает результат типа ParseResult, который в конечном итоге может являться наследником одного из двух базовых типов - Success или Failure.
Разумеется, библиотека комбинаторов парсеров значительно более обширна, чем показано в листинге 6, в частности, реализация функций ~ и rep не совсем тривиальна. Тем не менее, теперь у вас должно быть базовое представление о том, как работают комбинаторы. Они "комбинируют" парсеры в целях повышения уровня абстракции и реализации нужной схемы синтаксического анализа (отсюда и название - "комбинаторы").
Но это еще не все. Приведенный в листинге 7 простой тест демонстрирует, что парсер возвращает не совсем то, что нам требуется для реализации остальных компонентов калькулятора.
Листинг 7. Первый же тест сигнализирует об ошибке
package com.tedneward.calcdsl.test
{
class CalcTest
{
import org.junit._, Assert._
// ...
@Test def parseNumber =
{
assertEquals(Number(5), Calc.parse("5"))
assertEquals(Number(5), Calc.parse("5.0"))
}
}
}
|
Данный тест завершится с ошибкой, потому что метод parseAll нашего парсера не возвращает экземпляр case-класса Number (этого можно было ожидать, так как нигде внутри парсера не задана связь между case-классами и грамматическими правилами). Он также не возвращает набор текстовых элементов (токенов) или чисел.
Вместо этого парсер возвращает результат типа Parsers.ParseResult, который, как вы теперь знаете, может быть либо экземпляром Parsers.Success (в случае успешного завершения разбора), либо экземпляром классов Parsers.NoSuccess, Parsers.Failure или Parsers.Error (все они говорят о том, что в процессе разбора возникли ошибки).
Если разбор завершился без ошибок, то результат можно получить при помощи метода get класса ParseResult. Таким образом, метод Calc.parse достаточно слегка видоизменить, как показано в листинге 8. После этого тест должен выполняться успешно.
Листинг 8. Второй вариант парсера на основе БНФ
package com.tedneward.calcdsl
{
object Calc
{
// ...
import scala.util.parsing.combinator._
object ArithParser extends JavaTokenParsers
{
def expr: Parser[Any] = term ~ rep("+"~term / "-"~term)
def term : Parser[Any] = factor ~ rep("*"~factor / "/"~factor)
def factor : Parser[Any] = floatingPointNumber / "("~expr~")"
def parse(text : String) =
{
parseAll(expr, text)
}
}
def parse(text : String) =
{
val results = ArithParser.parse(text)
System.out.println("parsed " + text + " as " + results + " which is a type "
+ results.getClass())
results.get
}
// ...
}
}
|
Все работает! Так ведь?
К сожалению, не совсем. Запустив тесты, вы увидите, что парсер по-прежнему возвращает результаты не тех типов, которые должны присутствовать в AST (еxpr и т. д.). Вместо этого возвращаемые значения представляют собой списки, строки и тому подобное. Разумеется, можно попросту анализировать эти результаты еще раз, преобразуя в экземпляры expr и производя последующие вычисления, но должен быть более легкий путь.
Легкий путь, разумеется, есть, но для того чтобы его найти, нам понадобится глубже разобраться с тем, как комбинаторы могут возвращать "нестандартные" результаты (т. е. не строки и не списки). Другими словами, как заставить парсер создавать объекты пользовательских типов, в нашем случае тех, которые используются в AST. Именно этим мы займемся в следующей статье, где рассмотрим основы реализации комбинаторов. Вы узнаете, как преобразовывать входной текст в AST для последующего вычисления значения (а также для компиляции).
|
Хотя главная цель (разбор и вычисление выражений) еще не достигнута, но мы уже реализовали базовую семантику парсера. Все, что осталось - это расширить парсер таким образом, чтобы он возвращал элементы типов, используемых в AST.
Если вам не терпится узнать, как решается проблема с типами, то прочитайте документацию Scaladoc по методу ^^ либо раздел книги " Программирование на Scala ", посвященный комбинаторам парсеров. Имейте в виду, что язык, рассматриваемый в нашей статье, немного более сложен, чем примеры, приводимые в этих ресурсах.
Разумеется, можно напрямую работать со строками и списками и полностью игнорировать AST. В частности, можно заново анализировать строки и списки, преобразуя в узлы AST. Однако какой во всем этом смысл, когда столько удобных средств можно найти в библиотеке комбинаторов?