На настоящий момент ситуация выглядит следующим образом: в процессе создания 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).
