Работающий программист

Комбинаторы синтаксических анализаторов

Тэд Ньюард

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

Постановка задачи

Мой клиент по шею погружен в мир научных исследований в области нейро-оптики и попросил меня поработать с ним над новым проектом, который должен упростить проведение экспериментов со светочувствительной тканью (optical tissue). Конкретно я работаю над программной системой, управляющей специальным оборудованием микроскопа, которое контролирует различные стимулирующие устройства (LED, источники световых сигналов и др.), а те инициируют ответную реакцию от светочувствительной ткани; после этого собираются результаты, измеренные оборудованием, которое следит за светочувствительной тканью.

Если все это смутно напоминает вам «Matrix-y», то вы не одиноки. Когда я впервые услышал об этом проекте, первой моей реакцией было: «Ух ты, круто!».

Так или иначе, одна из главных особенностей аппаратной оснастки в том, что у нее будет довольно сложная конфигурация в каждой серии экспериментов, и это требует от нас придумать, как указывать эту конфигурацию. С одной стороны, вроде бы очевидно, что это должен быть XML-файл. Однако, люди, управляющие оборудованием, не собираются становиться программистами — это ученые и лаборанты, а значит, было бы странновато ожидать, что они будут писать синтаксически корректные XML-файлы (и делать это правильно перед каждой серией экспериментов). Мысль создать некую разновидность системы конфигурирования с GUI-интерфейсом сразу же показалась нам слишком заумной.

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

Некоторые соображения

Средство синтаксического разбора, или синтаксический анализатор (parser), решает две интересные и полезные задачи: преобразует текст в некую другую, более понятную форму и проверяет текст на соответствие определенной структуре (которая отчасти помогает преобразовать его в более понятную форму). Возьмем, к примеру, телефонный номер, который, хоть и является последовательностью цифр, все же имеет свою структуру, требующую проверки. Формат варьируется в разных странах, но цифры остаются цифрами. По сути, телефонный номер — отличный пример того случая, где «более понятная форма» не является целочисленным значением: цифры — это не целочисленное значение, а символьное представление того, что обычно лучше представляется как тип предметной области (domain type). (Интерпретируя их просто как числа, вы, например, затрудняете себе извлечение кода страны или добавочного номера.)

Если телефонный номер состоит из цифр, как и другие числа (величина заработной платы, идентификаторы сотрудников и т. д.), тогда в коде, где мы разбираем и проверяем цифры, будет некоторое дублирование, если только мы каким-то образом не расширим синтаксический анализатор. А это подразумевает, что любой создаваемый нами синтаксический анализатор должен быть открытым, позволяющим другим лицам расширять средство разбора/библиотеку самыми разными способами (например, для обработки канадских почтовых индексов) без модификации самого источника. Этот вариант известен под названием «открыто-замкнутый принцип» (open-closed principle): программные сущности должны быть открыты для расширения, но закрыты для модификации.

Решение: генеративное метапрограммирование

Одно из решений — традиционный подход «lex/yacc»¹, более формально называемый генератором синтаксических анализаторов (parser generator). Это влечет за собой необходимость указания синтаксиса для конфигурационного файла в некоем абстрактном формате. Обычно это делается с использованием какой-либо вариации синтаксиса/грамматики формы Бэкуса-Наура (Backus-Naur form, BNF), применяемой для описания формальной грамматики (как в большинстве языков программирования), и последующим запуском утилиты, которая генерирует код для разбиения строкового ввода на части и формирования в результате того или иного дерева структур/объектов. Этот сложный в целом процесс разделяется на два этапа — лексический анализ («lexing») и синтаксический анализ (parsing). При этом лексический анализатор (lexer) сначала преобразует строковый ввод в лексемы (tokens), попутно проверяя, что символы действительно образуют допустимые лексемы. Затем лексемы принимаются синтаксическим анализатором, и он проверяет, что лексемы появляются в правильном порядке, содержат допустимые значения и т. д., а потом обычно преобразует лексемы в некое абстрактное дерево структур для последующего анализа.

¹ Lex (сокращение от lexer) — лексический анализатор, а yacc (Yet Another Compiler Compiler) — генератор синтаксических анализаторов. — Прим. ред.

Проблемы с генераторами синтаксических анализаторов — те же, что и при любом подходе с применением генеративного метапрограммирования: сгенерированный код придется генерировать заново в случае изменения синтаксиса. Но для подобных сценариев важнее тот факт, что код будет генерироваться компьютером со всеми сопутствующими прелестями в именовании переменных (кто-нибудь готов мириться с такими переменными, как integer431 и string$$x$y$z?), что затрудняет отладку.

Решение: функциональное программирование

В какой-то мере синтаксический анализатор является фундаментально функциональным: он принимает ввод, выполняет какую-то операцию над ним и выдает результат. Крайне важно понимать, что синтаксический анализатор может быть создан из множества небольших синтаксических анализаторов, каждый из которых разбирает крошечную часть строкового ввода, возвращает лексему и другую функцию для разбора следующей крошечной части строкового ввода. Эти методики, которые, насколько мне известно, были введены в языке Haskell, формально называются комбинаторами синтаксических анализаторов (parser combinators) — это элегантное решение для «среднемасштабных» задач синтаксического анализа. Эти анализаторы не обязательно должны быть такими же сложными, как в языках программирования и могут быть чем-то, чуть посложнее String.Split (или серией регулярных выражений).

В случае комбинаторов синтаксических анализаторов требование открытости для расширения выполняется созданием небольших функций с последующим использованием приемов функционального программирования для их «комбинирования» в более крупные функции (отсюда и произошло название «комбинаторы»). Более крупные синтаксические анализаторы могут составляться кем угодно с навыками, достаточными для понимания композиции функций. Эта универсальная методика сама по себе заслуживает детального исследования, но я отложу эту интересную тему для будущей статьи.

Как оказалось, для Microsoft .NET Framework доступно несколько библиотек комбинаторов синтаксических анализаторов, большинство которых основано на модуле Parsec, написанном на Haskell, который является своего рода стандартом для библиотек комбинаторов синтаксических анализаторов. Две такие библиотеки — FParsec, написанная на F#, и Sprache, написанная на C#. Каждая из них является проектом с открытым исходным кодом и сравнительно хорошо документирована, поэтому они служат двум целям: их можно использовать либо в готовом виде, либо как модель для изучения проектировочных решений. Рассказ о FParsec я тоже оставлю для будущей статьи.

Sprache

Sprache, доступная на code.google.com/p/sprache, описывается как «простая, облегченная библиотека для конструирования синтаксических анализаторов непосредственно в коде на C#», которая «не пытается конкурировать с коммерческими языковыми средами разработки. Она располагается где-то между регулярными выражениями и полнофункциональными инструментальными наборами вроде ANTLR». (ANTLR — генератор синтаксических анализаторов, подпадающий под категорию генеративного метапрограммирования подобно lex/yacc.)

Приступить к работе со Sprache несложно: скачайте код, скомпилируйте проект, а затем скопируйте сборку Sprache.dll в каталог зависимостей вашего проекта и добавьте ссылку на нее в проект. С этого момента вся работа по определению синтаксических анализаторов сводится к объявлению экземпляров Sprache.Parser и комбинированию их определенным образом для создания экземпляров Sprache.Parser, которые в свою очередь могут при необходимости (обычно такая необходимость возникает) возвращать объекты предметной области, содержащие некоторые или все разобранные значения.

Простой пример с использованием Sprache

Начнем с синтаксического анализатора, которому известно, как разбирать вводимые пользователем телефонные номера в экземпляры типа предметной области PhoneNumber. Для большей простоты я буду придерживаться формата, принятого в США: (nnn) nnn-nnnn. Но нам нужно специфически распознавать деление на междугородные коды, префикс и строку, а также допускать подстановку букв вместо цифр (чтобы при желании можно было вводить телефонный номер как «(800) EAT-NUTS»). В идеале, тип PhoneNumber должен осуществлять преобразования между буквенными и всеми числовыми формами по требованию, но реализацию этой функциональности я оставлю читателям в качестве упражнения (что по большому счету означает, что мне просто неохота возиться с этим).

(Педант, сидящий во мне, требует отметить, что простое преобразование всех букв в числа, между прочим, не является полным решением. В колледже в моем кругу друзей было очень модно придумывать впечатляющие телефонные номера — один из моих бывших соседей по комнате все еще ждет, когда освободится номер 1-800-CTHULHU, чтобы навсегда стать победителем в этой знаменитой игре².)

² Имеется в виду популярная компьютерная игра «Call of Cthulhu: Dark Corners of the Earth». — Прим. ред.

Проще всего начать с типа предметной области PhoneNumber:

Если бы это был «реальный» тип предметной области, то в свойствах AreaCode, Prefix и Line присутствовал бы код проверки в их методах set, но это привело бы к повторению кода между синтаксическим анализатором и классом предметной области (что, кстати, мы обязательно исправим).

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

Определение numberParser весьма прямолинейно. Начинаем с примитивного анализатора Digit (экземпляра Parser<T>, определенного в классе Sprache.Parse) и описываем, что мы хотим минимум одну цифру в потоке ввода, неявно используя все цифры до тех пор, пока этот поток не пересохнет или пока анализатор не встретит нецифровой символ. Метод Text преобразует поток разобранных результатов в единую строку для последующего использования.

Проверить, как это работает, легко — скормите этому анализатору строку и поглядите как он ее раздраконит:

При выполнении в результат сохраняется «101». Если методу Parse подается строка ввода «abc», возникает исключение. (Если вы предпочитаете, чтобы исключения не генерировались, в Sprache также есть метод TryParse, возвращающий объект Result, который можно опросить на предмет успеха или неудачи.)

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

Синтаксический анализатор Numeric принимает символ и, если это число, переходит к следующему символу. Метод Then принимает функцию (в форме лямбда-выражения) для выполнения. Метод Return собирает каждый результат в единую строку и, как подразумевает его имя, использует ее в качестве возвращаемого значения (рис. 1).

Рис. 1. Разбор телефонного номера

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

Однако теперь нам нужно обрабатывать левые и правые скобки, дефис и преобразовывать все в объект PhoneNumber. Это может показаться неуклюжим, учитывая то, что вы видели на данный момент, но смотрите, что будет дальше, как показано на рис. 2.

Рис. 2. Преобразование ввода в объект PhoneNumber

К этому времени пользоваться синтаксическим анализатором становиться весьма легко:

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

Концепция комбинаторики

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

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

Ted Neward is an architectural consultant with Neudesic LLC. He has written more than 100 articles and authored or coauthored a dozen books, including “Professional F# 2.0” (Wrox, 2010). He’s a C# MVP and speaks at conferences around the world. He consults and mentors regularly—reach him at ted@tedneward.com or Ted.Neward@neudesic.com if you’re interested in having him come work with your team, or read his blog at blogs.tedneward.com.

Thanks to the following technical expert for reviewing this article: Luke Hoban