Наследование грамматик в Sprache (или еще один настраиваемый калькулятор выражений для .NET)

Статья демонстрирует технику создания парсеров с использованием наследования грамматик. Наследование позволяет описывать новые грамматики на основе уже существующих путем добавления новых правил или переопределения унаследованных, что существенно упрощает реализацию новых парсеров. Изменения в базовой грамматике автоматически становятся доступными во всех порожденных грамматиках. Основная область применения такой техники — поддержка нескольких диалектов или версий языков.

Поддержка наследования грамматик есть в некоторых генераторах парсеров (например, в ANTLR, Nitra), и автоматически доступна в инструментах, использующих объектно-ориентированные языки в качестве DSL-языков описания грамматик (например, Sprache и Irony).

В качестве примера приложения для статьи взята настраиваемая библиотека-калькулятор выражений с поддержкой пользовательских функций и переменных. Калькулятор компилирует строки в LINQ-выражения, которые легко преобразуются в строго типизированные делегаты. В отличие от интерпретирующих калькуляторов вроде NCalc, скомпилированные выражения по скорости работы никак не отличаются от методов, написанных на C#. Пример использования готового калькулятора:

// выражение с переменными
var expr = calc.ParseExpression("Sin(y/x)", x => 2, y => System.Math.PI);
var func = expr.Compile();
Console.WriteLine("Result = {0}", func());

// пользовательские функции
calc.RegisterFunction("Mul", (a, b, c) => a * b * c);
expr = calc.ParseExpression("2 ^ Mul(PI, a, b)", a => 2, b => 10);
Console.WriteLine("Result = {0}", func.Compile()());

Краткий обзор Sprache

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

Я бы сказал, что Sprache — превосходный инструмент, отлично подходящий для достаточно широкого круга задач и обладающий особой притягательностью, поскольку поощряет пошаговую разработку грамматик и TDD. Конечно, у комбинаторных парсеров есть определенные недостатки (например, сложности с диагностикой и восстановлением после ошибок), однако подобные детали несущественны для темы этой статьи.

Парсер в Sprache — это функция, которая трансформирует входную строку в какой-нибудь другой объект. В отличие от большинства инструментов построения компиляторов, в Sprache не используется генерация кода. Парсеры определяются прямо в тексте программы, и их сразу же можно использовать для разбора текста. Это позволяет параллельно с описанием парсеров писать для них юнит-тесты, что очень удобно. Вот пример простого парсера, который принимает строчку из повторяющихся букв A:

var parseA = Parse.Char('A').AtLeastOnce();

Простые парсеры комбинируются в более сложные парсеры. Для комбинации парсеров в Sprache определена масса extension-методов (например, Or, And, Many и так далее), однако особенно впечатляет определение парсеров как LINQ-запросов:

Parser<string> identifier =
    from leading in Parse.WhiteSpace.Many()
    from first in Parse.Letter.Once()
    from rest in Parse.LetterOrDigit.Many()
    from trailing in Parse.WhiteSpace.Many()
    select new string(first.Concat(rest).ToArray());

var id = identifier.Parse(" abc123  ");
Assert.AreEqual("abc123", id);

Совокупность всех правил, или грамматика языка, в Sprache обычно выглядит как статический класс с полями-парсерами. Более подробно о Sprache можно почитать в обзорной статье, для которой на хабре имеется перевод:

Строим DSL на C# при помощи парсер-комбинаторов

Устройство калькулятора

Наш калькулятор может работать в трех режимах: простой, научный и настраиваемый.

Простой калькулятор поддерживает обычные арифметические операции над действительными числами с плавающей запятой, унарный минус и скобки. Научный режим добавляет поддержку двоичных и шестнадцатеричных чисел, экспоненциальную запись и вызовы любых функций из класса System.Math, а в настраиваемом режиме можно использовать параметры и регистрировать свои собственные функции (с возможностью перегрузки).

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

var expr = "4*(1/1-1/3+1/5-1/7+1/9-1/11+1/13-1/15+1/17-1/19+10/401)";
var func = calc.ParseExpression(expr).Compile();
var result = func();

Простой калькулятор

В качестве основы для простого калькулятора взят пример из поставки Sprache — сверхкомпактный LinqyCalculator. Грамматика разбита на правила так, чтобы максимально упростить создание LINQ-выражений во время компиляции:

Expr ::= Term ("+"|"-" Term)*
Term ::= InnerTerm ("*"|"/"|"%" InnerTerm)*
InnerTerm ::= Operand ("^" Operand)
Operand ::= NegativeFactor | Factor
NegativeFactor ::= "-" Factor
Factor ::= "(" Expr ")" | Constant
Constant ::= Decimal

Обычно парсеры Sprache объявляются как статические лямбда-функции. Нам это не подходит, потому что их нельзя переопределять в классах-потомках, так что правила будем объявлять как виртуальные свойства.

// Было:
public static readonly Parser<Expression> ExpressionInParentheses =
	from lparen in Parse.Char('(')
	from expr in Expr
	from rparen in Parse.Char(')')
	select expr;

// Стало:
protected virtual Parser<Expression> ExpressionInParentheses
{
	get
	{
		return
			from lparen in Parse.Char('(')
			from expr in Expr
			from rparen in Parse.Char(')')
			select expr;
	}
}

После такой переделки грамматика немного увеличивается в размерах, зато теперь любые правила можно переопределять в классах-потомках. Чтобы можно писать юнит-тесты для каждого правила, придется объявлять свойства-парсеры как public или protected internal.

Я не буду приводить полный текст грамматики простого калькулятора, его можно посмотреть на гитхабе. В своей содержательной части он практически повторяет стандартный пример LinqyCalculator из поставки Sprache.

Научный калькулятор

Поскольку научный калькулятор умеет как минимум все то же, что и обычный, его класс наследуется от грамматики простого калькулятора. Для поддержки двоичных и шестнадцатеричных чисел добавляем новые правила:

protected virtual Parser<string> Binary
{
	get
	{
		return Parse.IgnoreCase("0b").Then(x =>
			Parse.Chars("01").AtLeastOnce().Text()).Token();
	}
}

protected virtual Parser<string> Hexadecimal
{
	get
	{
		return Parse.IgnoreCase("0x").Then(x =>
			Parse.Chars("0123456789ABCDEFabcdef").AtLeastOnce().Text()).Token();
	}
}

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

Обратите внимание: парсеры Binary и Hexadecimal возвращают string, а парсер Constant — LINQ-выражение. Понадобятся вспомогательные методы, которые преобразуют строки в Expression.Constant(double). Готовый парсер Constant с поддержкой десятичных, двоичных и шестнадцатеричных чисел примет такой вид:

protected override Parser<Expression> Constant
{
	get
	{
		return
			Hexadecimal.Select(x => Expression.Constant((double)ConvertHexadecimal(x)))
			.Or(Binary.Select(b => Expression.Constant((double)ConvertBinary(b))))
			.Or(base.Constant);
	}
}

Для поддержки функций в выражениях понадобятся еще два правила:

protected virtual Parser<string> Identifier
{
	get { return Parse.Letter.AtLeastOnce().Text().Token(); }
}

protected virtual Parser<Expression> FunctionCall
{
	get
	{
		return
			from name in Identifier
			from lparen in Parse.Char('(')
			from expr in Expr.DelimitedBy(Parse.Char(',').Token())
			from rparen in Parse.Char(')')
			select CallFunction(name, expr.ToArray());
	}
}

Вспомогательный метод CallFunction просто формирует LINQ-выражение для вызова статического из класса System.Math с указанным именем:

protected virtual Expression CallFunction(string name, Expression[] parameters)
{
	var methodInfo = typeof(Math).GetMethod(name, parameters.Select(e => e.Type).ToArray());
	if (methodInfo == null)
	{
		throw new ParseException(string.Format("Function '{0}({1})' does not exist.",
			name, string.Join(",", parameters.Select(e => e.Type.Name))));
	}

	return Expression.Call(methodInfo, parameters);
}

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

Нетрудно заметить, что этот приоритет должен быть самый высокий — такой же, как операции взятия в скобки. Например, при вычислении выражения Sin(2) ^ Cos(3) сначала нужно вычислить значения функций, а затем выполнить операцию возведения в степень.

В базовой грамматике взятие в скобки фигурирует в правиле Factor, поэтому его нам и нужно переопределить:

protected override Parser<Expression> Factor
{
	get { return base.Factor.XOr(FunctionCall); }
}

Добавление пользовательских функций

Для самой навороченной версии калькулятора создадим новый класс на базе научного калькулятора. Добавление пользовательских функций, очевидно, не потребует введения новых правил грамматики, потому что синтаксис выражений остается прежним. Поменяется только метод, который занимается вызовом функций. Псевдокод:

override Expression CallFunction(string name, Expression[] parameters)
{
	если есть пользовательская функция с именем name,
	{
		возвращаем выражение для вызова этой функции с параметрами parameters;
	}

	// в противном случае пробуем обратиться к System.Math 
	return base.CallFunction(name, parameters);
}

Любую пользовательскую функцию для калькулятора можно представить в виде делегата Func<double[], double>. Именованные функции удобно хранить в словаре: Dictionary<string, Func<double[], double>>. Чтобы разрешить перегрузку функций, достаточно к имени прицепить число параметров:

"Min:2" — функция Min с двумя параметрами
"Min:5" — функция Min с пятью параметрами

В результате приведенный выше псевдокод превратится в что-то типа такого:

protected override Expression CallFunction(string name, Expression[] parameters)
{
	// попробовать найти пользовательскую функцию
	var mangledName = name + ":" + parameters.Length;
	if (CustomFuctions.ContainsKey(mangledName))
	{
		return Expression.Call(...); // вызвать функцию с этим именем
	}

	// вызвать метод System.Math
	return base.CallFunction(name, parameters);
}

Определенную сложность представляет выражение Expression.Call, которое нужно сгенерировать для вызова пользовательской функции. Дело в том, что Expression.Call может вызывать только существующие методы, в число которых пользовательские функции, очевидно, не входят. Чтобы выкрутиться в этой ситуации, достаточно определить в классе калькулятора такой метод:

protected virtual double CallCustomFunction(string mangledName, double[] parameters)
{
	return CustomFuctions[mangledName](parameters);
}

Этот метод и будет вызывать выражение Expression.Call, которое мы сформируем при компиляции. Нам останется только преобразовать список параметров в один параметр-массив:

protected override Expression CallFunction(string name, Expression[] parameters)
{
	// попробовать найти пользовательскую функцию
	var mangledName = name + ":" + parameters.Length;
	if (CustomFuctions.ContainsKey(mangledName))
	{
		// подготовить параметры
		var newParameters = new List<Expression>();
		newParameters.Add(Expression.Constant(mangledName));
		newParameters.Add(Expression.NewArrayInit(typeof(double), parameters));

		// вызвать this.CallCustomFunction(mangledName, double[]);
		var callCustomFunction = new Func<string, double[], double>(CallCustomFunction).Method;
		return Expression.Call(Expression.Constant(this), callCustomFunction, newParameters.ToArray());
	}

	// вызвать метод System.Math
	return base.CallFunction(name, parameters);
}

Добавление параметров

Для поддержки параметров потребуется доработка грамматики: новое правило и обновление старых правил. Параметр — это просто идентификатор, который может встретиться там же, где константа или вызов функции:

protected virtual Parser<Expression> Parameter
{
	get { return Identifier; }
}

protected override Parser<Expression> Factor
{
	get { return Parameter.Or(base.Factor); }
}

Здесь мы впервые встречаем конфликт. Дело в том, что в правиле Factor теперь есть две альтернативы, которые обе начинаются с идентификатора: параметр и функция. Если парсер встретил идентификатор, он не может определить, параметр перед ним или функция, пока не заглянет вперед. Если за идентификатором идет скобка "(", значит это функция, в противном случае — параметр.

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

Чтобы разрешить конфликт между параметрами и функциями, мы можем определить параметр как «Идентификатор, за которым не следует скобка». Такое правило не будет приводить к конфликту, поскольку оно устраняет неоднозначность. Выглядит оно так:

protected virtual Parser<Expression> Parameter
{
	get
	{
		// identifier not followed by a '(' is a parameter reference
		return
			from id in Identifier
			from n in Parse.Not(Parse.Char('('))
			select GetParameterExpression(id);
	}
}

Парсер Parse.Not подобен отрицательному предпросмотру (negative lookahead) в регулярных выражениях: он не меняет указатель текущего символа и срабатывает успешно, если переданный ему парсер, в данном случае Parse.Char('('), терпит неудачу.

Как и в случае с вызовом функций, нам нужно как-то сгенерировать выражение, возвращающее значение параметра. Настало время принять решение о том, как в калькулятор будут передаваться параметры. На первый взгляд, мы можем поступить с параметрами так же как с пользовательскими функциями: регистрировать их в специальном словаре Dictionary<string, double>, который хранится в калькуляторе:

calc.Parameters["MyPI"] = 355/113d;
calc.Parameters["MyE"] = 2.718d;

Компиляция обращения к такому параметру будет устроена аналогично вызову пользовательской функции. Калькулятор сгенерирует вызов метода GetParameterExpression, передав ему имя параметра. Если параметр не определена, можно попытаться найти его среди констант класса System.Math:

protected virtual Expression GetParameterExpression(string id)
{
	// попробовать взять значение параметра, если оно определено
	if (Parameters.ContainsKey(id))
	{
		// вызвать this.GetParameterValue(id)
		var getParameterValue = new Func<string, double>(GetParameterValue).Method;
		return Expression.Call(Expression.Constant(this), getParameterValue, Expression.Constant(id)) as Expression;
	}

	// попробовать найти константу с таким именем в классе System.Math
	var systemMathConstants = typeof(System.Math).GetFields(BindingFlags.Public | BindingFlags.Static);
	var constant = systemMathConstants.FirstOrDefault(c => c.Name == id);
	if (constant == null)
	{
		throw new ParseException(string.Format("Parameter or constant '{0}' does not exist.", id));
	}

	// вернуть значение константы System.Math
	return Expression.Constant(constant.GetValue(null));
}

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

calc.Parameters["P"] = 3.14d;
calc.Parameters["R"] = 10;
var func1 = calc.ParseExpression("2*P*R").Compile();
var result1 = func1();

var func2 = calc.ParseExpression("R+P").Compile();
calc.Parameters["P"] = 123;
var result2 = func2();

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

Другой способ передачи параметров

Логично будет привязать список параметров не к калькулятору, а к выражению. Для этого потребуется изменить тип выражения-результата калькулятора: вместо Expression<Func> нужно будет генерировать Expression<Func<Dictionary<string, double>, double>>. Вот как это может выглядеть:

var function = calc.ParseFunction("y/x").Compile();
var parameters = new Dictionary<string, double>{ { "x", 2 }, { "y", 4 } };
var result = function(parameters);

Для такой схемы потребуется не такая уж большая переделка. Вместо вызова this.GetParameterValue нужно всего лишь сгенерировать обращение к словарю параметров: parameters[name]. Индексатор в C# компилируется в вызов метода get_Item, поэтому доступ к параметру будет выглядеть так:

var getItemMethod = typeof(Dictionary<string, double>).GetMethod("get_Item");
return Expression.Call(ParameterExpression, getItemMethod, Expression.Constant(name));

Чтобы не усложнять выражение, мы не будем проверять, есть ли в словаре параметр с указанным именем. Если параметра нет, класс Dictionary и сам пожалуется на это. Вот полный метод для компиляции параметров:

protected virtual Expression GetParameterExpression(string name)
{
	// try to find a constant in System.Math
	var systemMathConstants = typeof(System.Math).GetFields(BindingFlags.Public | BindingFlags.Static);
	var constant = systemMathConstants.FirstOrDefault(c => c.Name == name);
	if (constant != null)
	{
		// return System.Math constant value
		return Expression.Constant(constant.GetValue(null));
	}

	// return parameter value: Parameters[name]
	var getItemMethod = typeof(ParameterList).GetMethod("get_Item");
	return Expression.Call(ParameterExpression, getItemMethod, Expression.Constant(name));
}

Синтаксический сахар для параметров

В начале статьи приведен пример использования калькулятора для вычисления выражения с параметрами:

var expr = calc.ParseExpression("Sin(y/x)", x => 2, y => System.Math.PI);

Такой синтаксис читается значительно лучше, чем создание и заполнение Dictionary<string, double>. Его удобно использовать, когда список допустимых параметров выражения фиксирован. Хотя это не имеет отношения к собственно разбору выражений, поясню, как устроен этот метод:

public Expression<Func<double>> ParseExpression(string text, params Expression<Func<double, double>>[] parameters)
{
	var paramList = new Dictionary<string, double>();
	foreach (var p in parameters)
	{
		var paramName = p.Parameters.Single().Name;
		var paramValue = p.Compile()(0);
		paramList[paramName] = paramValue;
	}

	return ParseExpression(text, paramList);
}

Два слова о юнит-тестах

При разработке парсеров на Sprache очень удобно писать юнит-тесты параллельно с разработкой грамматик. Добавил новый парсер — сразу написал набор тестов к нему (приверженцы TDD сделают в обратном порядке). Поскольку библиотека Sprache никак не анализирует грамматику, она не может сообщить о проблемах вроде конфликтов или левой рекурсии (хотя простую левую рекурсию она может отследить на этапе выполнения), и набор юнит-тестов становится единственной опорой.

Наследование грамматик взваливает на юнит-тесты дополнительную ответственность: для каждого класса нужно убедиться, что все унаследованные правила продолжают работать и нормально взаимодействуют с правилами, переопределенными в классах-потомках. Для этого можно использовать вспомогательный метод ForEachCalculator, который прогоняет тесты на всех вариантах калькулятора:

private void ForEachCalculator(Action<SimpleCalculator> fact)
{
	foreach (var calc in new[] { new SimpleCalculator(), new ScientificCalculator(), new XtensibleCalculator() })
	{
		fact(calc);
	}
}

[Fact]
public void ExprCombinesTermsWithAddSubOperators()
{
	ForEachCalculator(calc =>
	{
		Assert.Equal(4d, calc.Expr.Parse("2+2").Execute());
		Assert.Equal(2d, calc.Expr.Parse("2*3-4*1").Execute());
		Assert.Throws<ParseException>(() => calc.Expr.Parse("+"));
	});
}

Однако более изящное решение, которое и используется в юнит-тестах калькулятора, состоит в наследовании тестов. В базовом классе тестов определен виртуальный метод CreateCalculator, который создает калькулятор для тестирования. Базовый класс тестов создает и тестирует SimpleCalculator, его потомок создает тестирует ScientificCalculator, наследуя все тесты базового класса, но выполняя их уже для калькулятора-потомка, и так далее.

Резюме

Итак, мы получили три варианта калькулятора, отличающихся набором возможностей и синтаксисом входных выражений. Благодаря наследованию, большинство правил базовой грамматики повторно используются в грамматиках-потомках, что позволяет фокусировать разработку на отличиях от базовой версии. Полный исходный текст проекта калькулятора доступен на github.

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

Автор: yallie

Источник