суббота, 3 января 2009 г.

Тайна сия велика есть: парсеры на основе C++ шаблонов

Сегодня в ленте новостей пришла ссылка на статью об еще одном генераторе парсеров на основе C++ шаблонов: YARD - Yet Another Recursive Descent . Итого, полку парсеров, использующих для описания грамматик C++ шаблоны, прибыло. Теперь есть Boost.Spirit, YARD и PEGTL (Parsing Expression Grammar Template Library) (последняя использует возможности нового стандарта C++0x).

Когда я смотрю на эти парсеры, тайнами для меня являются несколько вещей.

Вот, например, когда я выбираю инструмент для какой-то задачи, я хочу выбрать наиболее мощный и удобный из доступных. Но как C++ библиотека, значительная часть работы которой выполняется в compile-time (т.е. когда разработчик вообще не имеет возможности вмешаться в ход происходящего), может быть мощнее специализированного инструмента вроде Coco/R или Antlr? Ведь отдельный инструмент может реализовывать сложные алгоритмы обработки грамматики, использовать различные стратегии оптимизации, иметь отличные диагностические возможности, генерировать различные вспомогательные представления (вроде средств визуализации процесса разбора, как в Antlr).

Разработчик YARD указывает следующие проблемы, которые, как он думает, присутствуют при использовании внешних генераторов парсеров (между строк мои саркастические комментарии):

* Code generators are complex pieces of software that have their own peculiar syntax and a steep learning curve.
Ну да, освоить Lex/Flex+Yacc/Bison или Coco/R, или Ragel, или Antlr значительно, значительно сложнее, чем написанную на грани возможностей языка библиотеки C++ шаблонов.

* Debugging the grammars and generated code is challenging.
Ну просто очевидно, что отлаживать сгенерированный Bison-ом или Antlr-ом код гораздо сложнее, чем трехэтажные шаблоны внутри YARD или Boost.Spirit.

* Converting from BNF form to an appropriate LR form is difficult.
Да просто ужас какая сложная задача - преобразовать BNF в Antlr-описание. Кошмар разработчика просто. Сделать то же самое, но вместо внятного синтаксиса использовать C++ шаблоны гораздо, гораздо проще.

* Separate passes and tools for lexing and parsing is inconvenient.
Ну что тут сказать? Может для Lex/Flex+Yacc/Bison это и представляет собой серьезную проблему, но уж для Coco/R, Antlr и Ragel это уж точно не так.

Ну и еще одна совершенно таинственная штука. Как может считаться читабельным описание грамматики, заданное в виде C++ шаблонов? Вот пример из статьи о YARD:

struct Element :
  Or<EmptyElemTag, Seq<STag, Content, ETag> >
{ };
struct STag :
  Seq<
    Char<'<'>,
    Name,
    Star<Seq<S, Attribute> >,
    Opt<S>,
    Char<'>'>
  >
{ };
struct Attribute :
  Seq<Name, Eq, AttValue>
{ };

Данный фрагмент сопровождается замечательной фразой:

Take notice of the close correspondence of the YARD grammar to the official XML specification.

Специально для того, чтобы почувствовать разницу, вот описание того же фрагмента грамматики из XML спецификации:

element    ::= EmptyElemTag
           |   STag content ETag
STag       ::= '<' Name (S Attribute)* S? '>'
Attribute  ::= Name Eq AttValue

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

Отправить комментарий