Наследование грамматик в 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
var id = identifier.Parse (» abc123 »); Assert.AreEqual («abc123», id); Совокупность всех правил, или грамматика языка, в Sprache обычно выглядит как статический класс с полями-парсерами. Более подробно о Sprache можно почитать в обзорной статье, для которой на хабре имеется перевод: Строим DSL на C# при помощи парсер-комбинаторов
Устройство калькулятора Наш калькулятор может работать в трех режимах: простой, научный и настраиваемый.Простой калькулятор поддерживает обычные арифметические операции над действительными числами с плавающей запятой, унарный минус и скобки. Научный режим добавляет поддержку двоичных и шестнадцатеричных чисел, экспоненциальную запись и вызовы любых функций из класса System.Math, а в настраиваемом режиме можно использовать параметры и регистрировать свои собственные функции (с возможностью перегрузки).
Каждый следующий режим поддерживает все возможности предыдущих режимов и добавляет новые. Точно так же будет устроена иерархия классов грамматик, описывающих входные языки выражений калькулятора. Парсер калькулятора представляет собой функцию, преобразовывающую входную строку в LINQ-выражение, которое можно скомпилировать в делегат и вызвать, как обычную функцию:
var expr = »4*(1/1–⅓+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
// Стало:
protected virtual Parser
Научный калькулятор
Поскольку научный калькулятор умеет как минимум все то же, что и обычный, его класс наследуется от грамматики простого калькулятора. Для поддержки двоичных и шестнадцатеричных чисел добавляем новые правила:
protected virtual Parser
protected virtual Parser
protected override Parser
protected virtual Parser
return Expression.Call (methodInfo, parameters); } Поскольку базовая грамматика ничего не знает о новых правилах, нужно их подключить в какое-нибудь правило базовой грамматики. Здесь подобрать подходящее правило не так легко, как в случае с константами. Подходящее правило будет определяться приоритетом операции вызова функции.Нетрудно заметить, что этот приоритет должен быть самый высокий — такой же, как операции взятия в скобки. Например, при вычислении выражения Sin (2) ^ Cos (3) сначала нужно вычислить значения функций, а затем выполнить операцию возведения в степень.
В базовой грамматике взятие в скобки фигурирует в правиле Factor, поэтому его нам и нужно переопределить:
protected override Parser
// в противном случае пробуем обратиться к System.Math return base.CallFunction (name, parameters); } Любую пользовательскую функцию для калькулятора можно представить в виде делегата Func. Именованные функции удобно хранить в словаре: Dictionary>. Чтобы разрешить перегрузку функций, достаточно к имени прицепить число параметров: «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
// вызвать this.CallCustomFunction (mangledName, double[]);
var callCustomFunction = new Func
// вызвать метод System.Math
return base.CallFunction (name, parameters);
}
Добавление параметров
Для поддержки параметров потребуется доработка грамматики: новое правило и обновление старых правил. Параметр — это просто идентификатор, который может встретиться там же, где константа или вызов функции:
protected virtual Parser
protected override Parser
Чтобы разрешить конфликт между параметрами и функциями, мы можем определить параметр как «Идентификатор, за которым не следует скобка». Такое правило не будет приводить к конфликту, поскольку оно устраняет неоднозначность. Выглядит оно так:
protected virtual Parser
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
// попробовать найти константу с таким именем в классе 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 нужно будет генерировать Expression, double>>. Вот как это может выглядеть:
var function = calc.ParseFunction («y/x»).Compile ();
var parameters = new Dictionary
// 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. Его удобно использовать, когда список допустимых параметров выражения фиксирован. Хотя это не имеет отношения к собственно разбору выражений, поясню, как устроен этот метод:
public Expression
return ParseExpression (text, paramList); } Два слова о юнит-тестах При разработке парсеров на Sprache очень удобно писать юнит-тесты параллельно с разработкой грамматик. Добавил новый парсер — сразу написал набор тестов к нему (приверженцы TDD сделают в обратном порядке). Поскольку библиотека Sprache никак не анализирует грамматику, она не может сообщить о проблемах вроде конфликтов или левой рекурсии (хотя простую левую рекурсию она может отследить на этапе выполнения), и набор юнит-тестов становится единственной опорой.Наследование грамматик взваливает на юнит-тесты дополнительную ответственность: для каждого класса нужно убедиться, что все унаследованные правила продолжают работать и нормально взаимодействуют с правилами, переопределенными в классах-потомках. Для этого можно использовать вспомогательный метод ForEachCalculator, который прогоняет тесты на всех вариантах калькулятора:
private void ForEachCalculator (Action
[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
