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

Перевод статьи Николаса Блумхардта, известного .NET разработчика, автора IoC/DI контейнера Autofac. В этой статье Николас показывает на реальном примере как с наименьшими усилиями написать парсер предметно-ориентированного языка программирования с помощью Sprache, библиотеки парсер-комбинаторов.


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

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

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


Ссылка на пример в виде солюшена для VS2010.

Трудности

Во многом дизайн системы обусловлен тем фактом, что набор возможных типов аккаунтов (и, следовательно, различных анкет) неограничен. Создание новых анкет должно быть возможно без переразвертывания приложения. Кроме того состав анкет должен быть легко изменяем, возможно, самими конечными пользователями.

Есть много возможных путей представления анкет:

• Отобразить доменную модель анкет на реляционные таблицы базы данных
• Создать формат анкет основанный на XML
• Использовать Windows Workflow Foundation с его слишком общими XAML файлами
• Читать анкеты из CSV файлов или других таблиц

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

В этой статье мы рассмотрим другой привлекательный вариант: создание удобного мини-языка описания анкет.

Язык описания анкет

Возможно, вы читали некоторые обсуждения различий между внутренними и внешними DSL.

Внутренний DSL представляет собой специально построенный API на языке общего назначения (таком как C#), который при использовании читается больше как описание проблемы, нежели как программа, которая её решает.

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

Пример DSL анкеты выглядит так:

identification  "Personal Details"
[
	name        "Full Name"
	department  "Department"
]

employment "Current Employer"
[
	name        "Your Employer"
	contact     "Contact Number"
	#months     "Total Months Employed"
]

Это двух шаговый опросник собирающий личные данные и подробности трудоустройства.

• Каждый раздел имеет свой идентификатор, название и список вопросов.
• Каждый вопрос имеет идентификатор и некий текст запроса.
• Объявление идентификатора вопроса (например, #months) может иметь префикс из символа, который указывает на тип собираемых данных – символ решетки в данном случае обозначает натуральное число.

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

Подходы к разбору описаний анкет

Разбор это процесс принятия текста на исходном языке, таком как анкета выше и преобразование его в некое представление, обычно в какую-то объектную модель, с которой программа может работать. Для программиста на C# есть несколько путей достижения этой цели.

Парсеры написанные вручную

Как самые простые, так и самые сложные парсеры зачастую пишутся вручную. Простые пишутся, когда решение очевидно (например, «разбить строку, находя запятые в цикле»). Самые сложные парсеры пишутся, когда программисту необходим чрезвычайный уровень контроля (например, компилятор C#). Разбор чего-нибудь промежуточного вручную обычно не стоит затраченных сил, если конечно вы не профессионал в этой области, точно знающий, что он делает (это определенно не про меня!)

Регулярные выражения

Это удобный способ сопоставления и извлечения шаблонов из текста. .NET включает встроенный класс System.Text.Regex для эффективной работы с регулярными выражениями, поэтому они обычно являются первым вариантом для рассмотрения, когда кто-то сталкивается с задачей разбора. Несмотря на довольно простую грамматику, регулярные выражения быстро становится трудно читать и поддерживать. Это, пожалуй, самый большой их недостаток. Кроме того, есть много грамматик, которые регулярные выражения не в состоянии проанализировать (начиная с тех, которые допускают вложенность).

Генераторы парсеров

Генераторы парсеров, «языковые тулкиты», позволяют задать грамматику в декларативном формате. Тулкит включает в себя средства, работающие во время сборки проекта, которые генерируют классы на целевом языке (таком как C#) способные разбирать грамматику. Использование таких инструментов требует времени для изучения их работы и интеграции их в процесс сборки проекта. Для небольших задач разбора это может быть излишним, но для чего-то значительно более сложного или требующего высокой скорости разбора, изучение и использование таких инструментов настоятельно рекомендуется.

Парсер-комбинаторы

Эта основанная на функциях техника часто используется по умолчанию в функциональных языках, таких как Haskell и F#, оба из которых имеют высококачественные библиотеки парсер-комбинаторов. C# так же имеет молодую библиотеку комбинаторов Sprache, разработанную вашим покорным слугой и используемую далее в статье. Sprache позволяет очень легко написать и поддерживать простые парсеры без крутой кривой изучения или встраивания в процесс сборки. Она хорошо сочетается с процессом разработки через тестирование. К текущим недостаткам можно отнести производительность и, иногда, качество сообщений об ошибках – ни один из них не является большой проблемой для разбора небольших DSL. [Обновление: с тех пор как эта статья была написана, скорость разбора и обработка ошибок в Sprache были значительно улучшены.]

Приступая к работе

Для начала, скачайте Sprache.dll. Эта статья организована таким образом, чтобы вы могли следовать тексту, создавая и тестируя парсеры в Visual Studio с NUnit.

Грамматики строятся снизу вверх. Сначала анализаторы создаются для низкоуровневых синтаксических элементов, таких как идентификаторы, строки и числа. Затем мы постепенно поднимаемся выше, комбинируя эти простые части в более сложные, пока не получим завершенный язык.

Разбор идентификатора

В нашем языке описания анкет наиболее вложенным значащим элементом является вопрос:

name    "Full Name"

Основные части здесь – идентификатор и некоторый текст в кавычках. Первой задачей для нашего парсера будет разбор идентификатора, в данном случае 'name'.

[Test]
public void AnIdentifierIsASequenceOfCharacters()
{
    var input = "name";
    var id = QuestionnaireGrammar.Identifier.Parse(input);
    Assert.AreEqual("name", id);
}

Парсеры в Sprache это статические методы класса, представляющие грамматики. QuestionnaireGrammar.Identifier типа Parser<string>, т.е. он возвращает значения типа string.

Определение парсера:

public static readonly Parser<string> Identifier = Parse.Letter.AtLeastOnce().Text().Token();

Этот код читается довольно хорошо – мы собираемся анализировать непустую последовательность букв и вернуть их текстовое представление. Вот элементы парсера:

Parse.Letter – в Sparche класс Parse содержит вспомогательные методы и свойства для выполнения общих задач синтаксического анализа. Letter это простой парсер типа Parser<char>, который читает с входа букву и возвращает её как char. Если символ на входе не буква, этот парсер не будет ему соответствовать.

AtLeastOnce() – все созданные с помощью Sprache парсеры поддерживают повторение. AtLeastOnce() принимает парсер одного элемента типа T и возвращает новый парсер, который будет разбирать последовательность таких элементов, возвращая IEnumerable<T>.

Text() – модификатор AtLeastOnce() берет наш Parser<char> и превращает его в парсер с типом Parser<IEnumerable<char>>. Вспомогательная функция Text() берет парсер типа Parser<IEnumerable<char>> и конвертирует его в Parser<string>, для более удобной работы.

Token() – модификатор, принимающий, а затем отбрасывающий начальные и конечные пробельные символы.

Просто?

Есть еще несколько интересных тестов на парсер идентификатора.

[Test]
public void AnIdentifierDoesNotIncludeSpace()
{
    var input = "a b";
    var parsed = QuestionnaireGrammar.Identifier.Parse(input);
    Assert.AreEqual(“a”, parsed);
}

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

[Test]
public void AnIdentifierCannotStartWithQuote()
{
    var input = "\"name";
    Assert.Throws<ParseException>(() => QuestionnaireGrammar.Identifier.Parse(input));
}

Метод расширения Parse() бросает исключение ParseException, если парсер не подходит. Вы так же можете использовать не бросающий исключений TryParse().

После того как мы обрадовались корректно распарсеному идентификатору, можем тронуться дальше.

Разбор текста в кавычках

Разбор текста в кавычках не намного сложнее разбора идентификатора – наша простая версия не поддерживает экранированные символы или что-нибудь затейливое.

Посмотрим снова на входную строку:

name    "Full Name"

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

1. Открывающие кавычки
2. Всё, за исключением других кавычек
3. Закрывающие кавычки

Сами по себе кавычки нам не особо интересны, поэтому мы будем возвращать только текст между ними.

Тест для парсера будет выглядеть вот так:

[Test]
public void QuotedTextReturnsAValueBetweenQuotes()
{
    var input = "\"this is text\"";
    var content = QuestionnaireGrammar.QuotedText.Parse(input);
    Assert.AreEqual("this is text", content);
}

Перейдем прямо к анализатору:

public static readonly Parser<string> QuotedText =
    (from open in Parse.Char('"')
     from content in Parse.CharExcept('"').Many().Text()
     from close in Parse.Char('"')
     select content).Token();

Такое удобное переиспользование синтаксиса LINQ запросов впервые было описано (насколько мне известно) Luke Hoban из команды F#. Операции from разбивают отдельные единицы синтаксиса, а select трансформирует их в возвращаемое значение всего парсера.

Парсим вопрос

Возможно, вы уже заметили, что парсеры строго типизированы: парсер для символа возвращает char, а парсер для текста возвращает string. Парсер для вопроса будет возвращать Question!

public class Question
{
    public Question(string id, string prompt)
    {
        Id = id;
        Prompt = prompt;
    }

    public string Id { get; private set; }
    public string Prompt { get; private set; }
}

Это большое преимущество анализа на основе комбинаторов. Как только семантическая модель задачи построена, парсер может транслировать входные данные прямо в неё.

public static readonly Parser<Question> Question =
    from id in Identifier
    from prompt in QuotedText
    select new Question(id, prompt);

Юнит тест для вопроса теперь проходит:

[Test]
public void AQuestionIsAnIdentifierFollowedByAPrompt()
{
    var input = "name \"Full Name\"";
    var question = QuestionnaireGrammar.Parse(input);
    Assert.AreEqual("name", question.Id);
    Assert.AreEqual("Full Name", question.Prompt);
}

Разбор раздела

Разбор раздела такой же как разбор вопроса: сначала мы строим семантическую модель, а затем, используя существующие парсеры переводим в неё исходный текст.

Напомню, раздел выглядит вот так:

identification "Personal Details"
[
    name        "Full Name"
    department  "Department"
]

Мы можем представить его в объектной модели так:

public class Section
{
    public Section(string id, string title, IEnumerable<Question> questions)
    {
        Id = id;
        Title = title;
        Questions = questions;
    }

    public string Id { get; private set; }
    public string Prompt { get; private set; }
    public IEnumerable<Question> Questions { get; private set; }
}

Разработка парсера так же проста как разработка объектной модели:

public static readonly Parser<Section> Section =
    from id in Identifier
    from title in QuotedText
    from lbracket in Parse.Char('[').Token()
    from questions in Question.Many()
    from rbracket in Parse.Char(']').Token()
    select new Section(id, title, questions);

Для завершения примера у нас есть еще один класс модели:

public class Questionnaire
{
    public Questionnaire(IEnumerable<Section> sections)
    {
        Sections = sections;
    }

    public IEnumerable<Section> Sections { get; private set; }
}

Соответствующий парсер (на этот раз без разбора синтаксиса):

public static Parser<Questionnaire> Questionnaire =
        Section.Many().Select(sections => new Questionnaire(sections)).End();

Модификатор .End() требует, чтобы все входные данные были разобраны (т.е. в конце не осталось мусора).

Это все, что нам нужно для примера, без квалификаторов типов данных.

Поддержка типов данных ответа

Последним штрихом нашей грамматики будет поддержка квалификаторов типов ответа.

#months "Total Months Employed"

Для их представления мы можем использовать перечисление всех возможных типов.

public enum AnswerType
{
    Natural,
    Number,
    Date,
    YesNo
}

Это довольно ограниченный набор, так что с помощью перебора мы проверим каждый возможный квалификатор.

public static Parser<AnswerType> AnswerTypeIndicator =
    Parse.Char('#').Return(AnswerType.Natural)
        .Or(Parse.Char('$').Return(AnswerType.Number))
        .Or(Parse.Char('%').Return(AnswerType.Date))
        .Or(Parse.Char('?').Return(AnswerType.YesNo));

Класс Question изменен для принятия AnswerType в качестве параметра конструктора. Простая модификация парсера вопросов завершает нашу работу.

public static Parser<Question> Question =
    from at in AnswerTypeIndicator.Or(Parse.Return(AnswerType.Text))
    from id in Identifier
    from prompt in QuotedText
    select new Question(id, prompt, at);

Резюме

Законченный анализатор представляет собой всего лишь шесть правил в 25 хорошо оформленных строках кода.

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