OMeta: нисходящий рекурсивный парсер с откатами

предыдущая серия

Рассмотрим простейший пример встроенного языка калькулятора. По большому счёту, арифметические вычисления не должны входить в правильный чистый язык — их лучше определять дополнительным DSL, что добавляет огромную гибкость вычислительной системе. Сейчас мы это продемонстрируем.

Существуют две реализации OMeta для Windows (.NET) — OMeta# и IronMeta. Последний более-менее развивается, хотя и не особо активно, но пожалуй главный его технический недостаток — потребность в пакете NuGet. В инженерном же аспекте мета-язык IronMeta существенно расширяет оригинальный OMeta, причём в направлении поддержки синтаксиса .NET, что в некотором смысле не только плюс, но и минус.

OMeta# не развивается уже давно, однако смотрится более целостным и «олдскульным», причём не требует никаких дополнительных пакетов. Оригинальное решение с гитхаба, формально ориентированное на VS2008, без проблем собирается в Visual Studio 2010. Существенный недостаток OMeta# (впрочем, как и самой оригинальной OMeta) в отсутствии внятной документации, а набор примеров OMeta# действительно полностью демонстрационный: предлагается обёртка консольной программы, нативно понимающая синтаксис созданного DSL. Такой подход удобен для демонстрации возможностей OMeta, но очевидно совсем не годится для использования в реальных проектах.

Мы рассмотрим простой способ быстрого подключения OMeta# в произвольный проект C# — например, в стандартное оконное приложение Windows Forms.

1. Создадим новый пустой проект и включим в список ссылок библиотеки OMetaCS и OMetaSharp.

2. Файл с описанием нашего языка необходимо оттранслировать в cs-файл, который будет включён в наш проект и определениями из которого (в частности, парсером) мы будем непосредственно пользоваться. Для этого обычно создаётся отдельная утилита, которая перестраивает некоторую подключаемую библиотеку (предварительно перегенерив код одного из её файлов) при изменении исходной грамматики. Для наглядности мы упростим этот технический момент: будем генерировать cs-файл, например, при нажатии на кнопку А, а затем включим его в проект вручную.

Вот как выглядит код генерации парсера:

var contents = File.ReadAllText(@"ПУТЬ_К_ФАЙЛУ_ГРАММАТИКИ\gramm.ometacs");
var result = Grammars.ParseGrammarThenOptimizeThenTranslate
<OMetaParser, OMetaOptimizer, OMetaTranslator>
(contents,
p => p.Grammar,
o => o.OptimizeGrammar,
t => t.Trans);
File.WriteAllText(@"ПУТЬ_К_ВЫХОДНОМУ_ФАЙЛУ\parser.cs", result);

После его срабатывания файл parser.cs надо включить в проект.

3. Использование нашего парсера не менее просто. Например, в файле gramm.ometacs был определён класс парсера Calculator. После включения в проект файла parser.cs определим такую функцию:

protected T Parse<T>(string text, Func<Calculator, Rule<char>> ruleFetcher)
{
return Grammars.ParseWith(text, ruleFetcher).As<T>();
}

С помощью этого генерика мы будем получать результат исполнения программы на нашем языке с применением подходящего типа.

var result = Parse<string>("(2+2)*2", x => x.Expr);   

Expr — это название финального терма нашей грамматики.

После исполнения данной команды (например, по нажатию на кнопку Б) в переменную result запишется значение 8.

Рассмотрим простейший пример грамматики калькулятора. Она сочетает элементы синтаксиса C# с оригинальным PEG-синтаксисом OMeta.
Текст этой грамматики запишем например в файл gramm.ometacs, который транслируется в cs-файл вышеприведённой функцией.

Грамматика охватывается общим блоком с таким синтаксисом:

ometa OMetaSharp.Examples.Calculator<char, int> : Parser<char> {

}

ometa — ключевое слово, Examples — произвольное пространство имён C#, Calculator — название класса нашего парсера. На вход он получает поток из символов, на выходе возвращает целое значение.

Строго говоря, PEG — это не столько описание грамматики, сколько описание стратегии разбора грамматики! PEG, можно сказать, описывает нисходящий рекурсивный парсер с откатами. Сама эта стратегия и задаёт грамматику, только уже по факту. Гарантируется, что можно придумать такую стратегию, которая будет разбирать текст за линейное время от его длины.

Описание стратегии состоит из именованных правил разбора, перечисленных через запятую. Каждое правило состоит из имени (левая часть), символа «=» и типа структуры (правая часть). Вместо оператора перечисления BNF в PEG используется оператор приоритетного выбора «|», который так же часто применяется и для перечисления.

Первое наше правило — определение цифры:

dig = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9',

В данном случае все варианты равноправны, хотя в первую очередь всегда будет сопоставляться первый вариант (‘0’), и т. д.

Число описывается с помощью управляющего правила «+», означающего циклическое повторение разбора один или более раз:

num = dig+,

Правила применяются в порядке их записи, поэтому если мы хотим учесть приоритет операций, отдельно надо выделить операции умножения и деления и операции сложения и вычитания:

fac = fac '*' num | fac '/' num | num,
exp = exp '+' fac | exp '-' fac | fac

Четырьмя правилами мы описали арифметическую грамматику. Однако с её помощью наш парсер сможет лишь выполнять сопоставление — никаких семантических действий данная грамматика пока не выполняет.

Наполнение её вычислительной семантикой будет нашим следующим шагом.

Поделиться статьей ...Share on Facebook0Share on Google+0Tweet about this on TwitterShare on LinkedIn0Share on VKPrint this page

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *