Flex и Bison: классика жанра сомнительных достоинств

Как-то никогда раньше не приходилось писать парсеры. Хоть я и был в курсе темы в общих чертах и заклинаниями LALR(n) и БНФ меня не запугать, но на практике я эти знания никогда не применял. Но все когда-нибудь случается в первый раз.

Нужно иметь веские основания, чтобы писать свой парсер с нуля; в качестве таковых в голову приходят практика в теории компиляторов, маниакальная оптимизация, шибко изощренный контекстно-зависимый язык — или просто мазохизм. В данном случае это все не ко мне, так что я решил использовать какой-нибудь генератор. В первую очередь я обратился к классическим генераторам lex и yacc, вернее, к их современным реинкарнациям Flex и Bison. Первый генератор служит для создания лексического анализатора (преобразует набор символов исходного текста в последовательность более нагруженных смыслом токенов), второй — синтаксического анализатора (построение синтаксического дерева из токенов на основании некоторой грамматики). Еще их часто называют на английский манер, токенайзер (tokenizer) и парсер (parser).

Попробовал я с этими генераторами пожить, но очень быстро запросил пощады. Анализатор, сгенерированный Flex, долго не хотел компилироваться, а под C++ (ни mingw, ни msvc) он у меня так и не скомпилировался. При включенном режиме совместимости с Bison (%option bison-bridge) отказался компилироваться вообще. Flex не знает о существовании Unicode, так что парсить не ASCII на Flex — тот еще изврат. Выданный исходник просто жуткий, многослойный торт из макросов и сплошные глобальные переменные. Хоть и заявляется (вроде как экспериментальная) поддержка C++, но этот вариант у меня тоже не компилировался ни в какую.

Такой гембель и вопиющая кривизна ради всего-навсего токенайзера? Я лучше напишу свой лексический анализатор за пару часов без всего этого бубнотрясения. Это несложно. Вот синтаксический разбор по грамматике — другое дело. Но Bison сильно под lex заточен, и вообще, говорят, не менее крив и жуток, чем Flex, так что я решил поискать альтернативный вариант. После Flex настроения корячиться дальше не осталось.

Поиски привели меня к генератору парсеров LEMON, который был создан в рамках разработки sqlite. Этот парсер мне очень понравился, с его помощью я и решил свою задачу. Тем не менее, с Flex и Bison я рекомендую познакомиться. Какая-никакая, но классика жанра. По этой причине многие книги и статьи для иллюстрации своих идей используют именно Bison. Кроме того, справку по LEMON будет сложно понять без знания Bison, поскольку она пестрит отсылками вида «а это мы делаем как в yacc». Из всех встреченных мною материалов мне больше всего понравился замечательный тутор одного доброго человека, который сэкономил мне массу часов гугления и курения мануалов. Если захочется пощупать Flex и Bison под Windows, можно воспользоваться уже готовыми программами, так что с этим вопросом возиться не нужно.

Имея представление о Bison с LEMON разобраться не составит большого труда. Отмечу некоторые моменты, на которые нужно обратить внимание.

Bison сам вызывает токенайзер (лексический анализатор), в то время как LEMON ожидает быть вызванным. Имхо, так оно много правильнее, т.к. парсеру не нужно лезть во все щели вашей программы, можно ограничиться только предоставлением простого API для вызова. В случае с LEMON, который есть парсер для грамматик типа LALR(1) и поэтому в любом случае анализирует токены по одному, API получается предельно простым: создать парсер, в цикле скормить токены из лексера, удалить парсер.

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

Формат для файла описания грамматики у LEMON, имхо, симпатичнее чем у Bison. Особенно использование именованных подстановок вместо $1, $2 и т.п. радует. Но следует иметь в виду, что синтаксис определения грамматических правил в Bison гораздо нагляднее и поддерживает синтаксис для грамматических правил, максимально приближенный к БНФ, в то время как LEMON понимает только правила в виде простой последовательности терминальных и нетерминальных символов. Парсер от этого не особо страдает в функциональности, но правила, конечно, теряют в выразительности при чтении исходника грамматики. Например, рассмотрим такое правило:

В грамматике по правилам LEMON его можно записать следующим образом:

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

Как итог, парсером LEMON я остался доволен. Делает что нужно, чего не нужно — не делает, генерируемый код вполне внятный, компилируется без особых проблем. Ну и то, что эта программа от авторов sqlite, внушает определенный оптимизм по поводу качества кода.

  3 comments for “Flex и Bison: классика жанра сомнительных достоинств

  1. lex
    02.11.2013 at 10:44

    boost::spirit !?

    • mgsxx
      02.11.2013 at 11:24

      boost::spirit — мегакомбайн, что не всегда нужно, и с зависимостью от boost, что тем более не всегда нужно. А LEMON — один C файл без зависимостей. Но как вариант, говорят, spirit неплох. Сам не пробовал. Подозреваю, что будет лучше, чем Bison 😉

  2. lexxmark
    09.12.2013 at 10:34

    Под windows есть http://sourceforge.net/projects/winflexbison/
    Вроде всё работает, и для C++, и в связке flex+bison, и реентерабельность там есть, если покопать

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