Что такое Flex и Bison

Flex и Bison. это устаревшие утилиты Unix, которые помогают вам создавать очень быстрые парсеры для практически произвольных форматов файлов. Формально они реализуют синтаксический анализ не-неоднозначных контекстно-зависимых (в отличие от «естественного языка») грамматик Look-Ahead-Left-Right (в отличие от «рекурсивного спуска»).

Зачем вам изучать синтаксис паттернов Flex / Bison, когда вы можете просто написать свой собственный парсер? Ну, несколько причин. Во-первых, Flex и Bison сгенерируют парсер, который фактически гарантированно будет работать быстрее, чем все, что вы могли бы написать вручную за разумное время. Во-вторых, обновление и исправление исходных файлов Flex и Bison намного проще, чем обновление и исправление пользовательского кода анализатора. В-третьих, у Flex и Bison есть механизмы для обработки и восстановления ошибок, что вы определенно не хотите пытаться внедрить в собственный анализатор. Наконец, Flex и Bison существуют уже давно, поэтому они гораздо свободнее от ошибок, чем более новый код.

Предполагается, что эта веб-страница будет учебным пособием для новичков, которым необходимо использовать Flex и Bison для какого-то реального проекта. Я написал это, когда изучал их, так что, надеюсь, это объясняет все правильно, так как вам нужно знать их. (Учебные пособия по Flex и Bison, которые я обнаружил в Googling, обычно были очень сложными в теории и загадочных деталях.) Однако, чтобы по-настоящему изучить эти инструменты, вам следует взглянуть на несколько книг:

  • сгибать Зубр от Джона Левина. Это окончательный текст для изучения этих инструментов.
  • Эффективный Flex Зубр, который охватывает сложные темы и хорошую практику.

lex vs. flex, yacc против бизонов

В дополнение к слухам о «flex and bison», вы также услышите о «lex and yacc». «lex и yacc». оригинальные инструменты; «flex and bison». их почти полностью совместимые новые версии. Только очень старый код использует lex и yacc; большая часть мира перешла на Flex и Bison.

Все четыре из вышеперечисленных являются инструментами на основе C; они написаны на C, но важнее их вывод на C-код. Тем не менее, мой проект был на C так что это также руководство по использованию C с Flex и Bison.

что мы будем делать!

Давайте создадим парсер Flex / Bison для глупого формата, который я назову «snazzle». Файлы Snazzle имеют четыре основных раздела:

  • заголовок, который просто говорит «sNaZZle», за которым следует номер версии,
  • раздел, который объявляет имена типов, такие как «type foo» и «type bas»,
  • раздел с фактическими данными, состоящими ровно из 4 чисел и одного из названных выше названий типов,
  • и нижний колонтитул, который просто говорит «конец».

(У меня нет конкретного формата файла или программы, я просто придумываю это.) Вот пример нашего глупого формата:

Для создания парсеров вы хотите начать с высокого уровня, потому что именно так Бизон думает о них. К счастью, мы уже начали на высоком уровне, говоря, что «snazzlefile» состоит из четырех основных частей; мы назовем их «header», «typedefs», «body» и «footer». Затем мы разбиваем эти четыре основные части на составляющие их части и так далее, пока не пройдем весь путь до того, что называется терминальные символы. Терминальные символы являются наименьшими единицами вашей грамматики. для нашего примера здесь целые числа, такие как «15», являются одним из наших терминальных символов. (Но не отдельные символы «1» и «5», которые составляют его.) Терминальные символы. это граница между Flex и Bison: Flex видит отдельные символы «1» и «5», но объединяет их в «15», прежде чем передать его Bison ,

Для наших глупых файлов мы сделаем 3 типа терминальных символов: NUMBER, который в основном является целым числом, FLOAT, который является числом с плавающей запятой (который нам нужен только для версии), и STRING, который является почти всем остальным. Кроме того, поскольку это учебное пособие, давайте продемонстрируем мощь Flex, создав программу, которая просто обрабатывает наш ввод без использования Bison для его анализа. Вот первый удар:

Файлы Flex и Bison имеют три раздела:

  1. первая. это своего рода «контрольная» информация,
  2. второе. это фактические определения токенов (Flex) или грамматики (Bison),
  3. последний. это код C, который нужно дословно скопировать в выходной файл.

Эти разделы делятся на %%, который вы видите в строках 7 и 12. Давайте рассмотрим эту строку построчно.

  • Строки 1 (и 5) являются разделителями, которые сообщают Flex, что строки со 2 по 4 являются кодом C, который нужно скопировать непосредственно в сгенерированный лексер.
  • Линии 2 и 3 должны получить доступ к Cout.
  • Строка 4 должна объявить функцию yylex, которую мы собираемся вызвать позже. Функция yylex. это то, что генерирует Flex, поэтому она волшебным образом появляется, когда мы запускаем наш snazzle.l через Flex. Обратите внимание, что смешение C и C имеет несколько деликатных моментов, одним из которых является «манипулирование именами». компиляция C функции с именем yylex приведет к символу с именем что-то вроде _Z5yylexv. Это нормально, если все, кто вызывает yylex, также скомпилированы в режиме C , так что их связь аналогичным образом искажается. Однако, если вы хотите скомпилировать какую-либо его часть в режиме C, вам, вероятно, придется отключить преобразование имен для этого следующим образом:
    • объявить с помощью extern «C» int yylex ();
    • определить его с помощью #define YY_DECL extern «C» int yylex ()
    Что такое Flex и Bison
  • Строка 6. это удобная опция Flex, которая не позволяет искать (или пытаться использовать) функцию yywrap. Здесь мы вообще не будем использовать yywrap, и я не хочу добавлять «-lfl» к компиляции, просто чтобы добавить пустое определение по умолчанию.
  • Строка 7%%, что означает, что мы закончили с разделом управления и переходим к разделу токенов. Обратите внимание, что в нашем разделе управления нет ничего особенного. раздел управления Bison получает гораздо больше использования, чем Flex.
  • Строки 8-11 имеют одинаковый (простой) формат: регулярное выражение (отдельная тема, которую я совсем не касаюсь в конце этой страницы) и действие. Когда Flex читает входной файл и может соответствовать одному из регулярные выражения, он выполняет действие. Регулярное выражение не Идея Perl о регулярном выражении, поэтому вы не можете использовать «\ d», но все нормальные вещи доступны. действие это просто код C, который копируется в возможный вывод flex; соответственно, вы можете иметь одно утверждение или фигурные скобки с целой кучей утверждений. Некоторые особенности формата файла, который я обнаружил: действие должно быть выровнено по левому краю (если есть пробел, начинающий строку, где ожидается шаблон, строка считается комментарием!); разделение между шаблоном и действием. просто пробел (подойдет только один пробел); действие не ограничивается одной строкой, если вы используете фигурные скобки.
  • Строка 12. еще один разделитель %%, означающий, что мы закончили со вторым разделом и можем перейти к третьему.
  • Строки 13-16 являются третьим разделом, который предназначен исключительно для скопированного кода C. (Обратите внимание, что, в отличие от контрольной секции вверху, нет «%<" or "%>Msgstr «. Обычно нам не нужно помещать что-либо в этом разделе для файла Flex. но для этого примера, если мы поместим сюда функцию main (), тогда весь наш код будет в одном файле, а затем мы не будем не нужно связывать отдельный main.o.

Этот пример можно скомпилировать, запустив это: Это создаст файл «lex.yy.c», который мы затем можем скомпилировать с помощью g :

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

Довольно круто! Обратите внимание, что восклицательный знак в самом конце просто повторяется: когда Flex находит что-то, что не соответствует ни одному из регулярных выражений, он выводит его в STDOUT. Обычно это хороший признак того, что ваши определения токенов недостаточно полны, но чтобы избавиться от них на данный момент, вы можете просто добавить. ; в раздел токенов. это будет соответствовать любому одному символу («.») и ничего не делать с ним (пустой оператор C «;»).

Теперь немного подробнее о синтаксисе для среднего раздела. В общем, это действительно так просто, как «совпадение с регулярным выражением», за которым следует «что с ним делать». «Что с ним делать» может сильно различаться. например, большинство анализаторов полностью игнорируют пробелы, что можно сделать, просто сделав «действие» точкой с запятой: Большинство анализаторов также хотят отслеживать номер строки, что вы бы сделали, перехватывая все возвраты каретки и увеличивая счетчик строк. Однако вы хотите, чтобы возврат каретки сам по себе игнорировался, как если бы это был пробел, поэтому даже если у вас есть действие, выполненное здесь, вы хотите не добавьте туда выражение return: почти все остальное понадобится, чтобы вернуть токен Bison, но об этом позже.

чтение из файла

ОК, первое большое обновление: чтение из файла. Прямо сейчас мы читаем из STDIN, что немного раздражает, потому что большую часть времени вы действительно хотите выбрать файл для чтения. Flex считывает свои данные из глобального указателя на переменную C FILE с именем yyin, которая по умолчанию имеет значение STDIN. Все, что вам нужно сделать, это установить этот указатель на свой собственный дескриптор файла, и он будет читать оттуда. Это меняет наш пример следующим образом (различия в смелый):

Вот как запустить наш новый код, хотя нет ничего потрясающего:

Первое, что мы должны сделать в нашем глупом парсере, это начать определять терминальные токены; для нас это целые, поплавки и строки. Несмотря на то, что Flex вычисляет и возвращает токены по типу, определение этих типов выполняется в файле Bison. Кроме того, давайте переместим main () в третий раздел («скопированный C-код») файла Bison:

Теперь, когда в файле Bison объявлены типы терминалов (% token s), мы можем реализовать их в файле Flex:

Поскольку файл Flex теперь должен включать в себя #include файл, сгенерированный Bison (snazzle.tab.h), мы должны сначала запустить Bison. Также обратите внимание, что bison должен быть запущен с.d, чтобы создать для нас файл.h.

Вы заметите, что ввод отражается в обратном направлении! Это связано с тем, что для каждого из определяемых вами правил Bison не выполняет действие пока это не соответствует полному правило. В приведенном выше примере все рекурсивные правила были праворекурсивными (то есть они выглядели как «foo: bar foo», а не «foo: foo bar»). Право-рекурсивный поиск выведет вывод в обратном направлении, так как он должен соответствовать ВСЕМУ, прежде чем он сможет начать выяснять, что к чему, И у него есть еще один существенный недостаток: если ваш ввод достаточно большой, праворекурсивные правила переполнят внутренний стек Bison! Так что лучшей реализацией грамматики Бизона была бы левая рекурсия:

(Обратите внимание, что нам также пришлось изменить 1 доллар в cout на 2 доллара, поскольку то, что мы хотели распечатать, теперь является вторым элементом в правиле.) Это дает нам результат, на который мы надеемся:

Теперь, когда все готово, мы наконец можем определить настоящий формат файла в файле Bison. Сначала мы создадим простые токены во Flex: те, которые используются для представления константных строк, таких как SNAZZLE, TYPE и END, соответственно, представляющих строки «sNaZZle», «type» и «end». Затем мы конкретизируем действительные правила в грамматике бизонов и в итоге получаем этот красивый предмет искусства:

04 Использование Bison и Flex вместе

Это скомпилировано и работает так же, как и другие:

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

Makefile

Когда вы, наконец, устали от ручного перезапуска Flex и Bison, а также забыли, в каком порядке это делать, я от всей души рекомендую создать make-файл. Вот образец, который я сделал:

принуждение к возврату каретки

Следующая настройка: вы заметите, что это полностью игнорирует пробелы, так что вы можете поместить весь файл snazzle в одну строку, и все будет хорошо. Вы можете хотеть или не хотеть этого поведения, но давайте предположим, что это плохо, и потребуем, чтобы после строк были строки, такие же, как в примере файла «in.snazzle». Для этого нам нужно сделать две вещи: распознать токен ‘\ n’ (flex) и добавить его в грамматику (bison):

Но когда мы запускаем его, мы получаем ошибку разбора:

Зачем?? Что ж, получается, что у in.snazzle есть дополнительный возврат каретки в конце:

И если мы удалим это, snazzle будет счастлив:

Но это на самом деле не лучшее решение, так как требовать, чтобы все входные файлы имели ровно один возврат каретки после данных, это немного необоснованно. Нам нужно сделать это более общим. В частности, мы должны разрешить любое количество возвратов каретки между строками, что мы сделаем, определив правило ENDLS, которое соответствует одному или нескольким токенам ENDL, и переключив нашу грамматику на использование ее вместо непосредственного использования ENDL:

Обратите внимание, что для этого не потребовалось никаких изменений в файле flex. базовые токены не изменились, как мы их использовали. И, к счастью, это прекрасно работает:

номера строк

Следующий небольшой трюк: не было бы неплохо, если бы эта ошибка синтаксического анализа дала нам строку, на которую мы должны смотреть, чтобы нам не приходилось угадывать и проверять грамматику? К сожалению, у Flex нет гарантированного способа получения номера строки (ну, есть yylineno, но он почти полностью ручной, и в некоторых ситуациях ваш синтаксический анализатор работает очень медленно, так что вы можете просто сделать это самостоятельно). Лучший способ отслеживать номер строки. иметь глобальную переменную, которую вы обновляете всякий раз, когда видите возврат каретки:

Что довольно круто, когда вы делаете определение «type oops» в середине тела вместо того, где оно должно быть:

Конечно, «синтаксическая ошибка» не очень полезна, но по крайней мере у вас есть номер строки. 🙂

прямой возврат терминальных символов

Если у вас есть отдельные символы, которые также являются терминальными символами, вы можете заставить Flex возвращать их напрямую, вместо того, чтобы создавать для них токен%: вы также можете перечислить их несколько в одну строку с помощью этого ярлыка:

На стороне зубров, вы также можете использовать их напрямую:

действия до конца грамматики

Самая крутая вещь, которую я обнаружил о Бизоне. это то, что вы можете делать действия в середине грамматики а не только в конце. Это означает, что вы можете получить информацию, как только она будет прочитана, что я считаю очень полезным. Например, вызов функции C может выглядеть следующим образом: вы всегда можете добавить действия в конце строки, например так: Но затем вы получите имя функции после вычисления ‘body’, что означает, что все было проанализировано до Вы узнаете, что это было! Тем не менее, вы можете встроить блок кода в середину грамматики, и он будет запущен до того, как будет вычислено «тело»:

пробелы в файлах flex / bison

Я обнаружил, что в отличие от большинства инструментов Unix, Flex и Bison удивительно мягки в отношении пробелов. Это действительно хорошо, потому что достаточно сложно понять их синтаксис без возможности переопределения вещей. Следующее все эквивалентны:

избежать проблем с.lfl и связью с yywrap

Если вы знаете, что хотите анализировать только один файл за раз (обычно это хорошее предположение), вам не нужно предоставлять собственную функцию yywrap, которая будет просто возвращать 1. Внутри вашего flex-файла вы можете сказать% option noyywrap, и сгенерированный вывод определит yywrap как локальный макрос, возвращающий 1. Это дает дополнительный бонус от удаления требования связываться с библиотеками flex, поскольку они нужны только для получения yywrap по умолчанию определяется как функция, возвращающая 1.

переименование идентификаторов

Flex и Bison генерируют код, который использует глобальное пространство имен, что означает, что если вы когда-нибудь попытаетесь использовать более одного в одной программе, у вас будут конфликты идентификаторов. Чтобы обойти это, вы можете сказать и Flex, и Bison префикс их идентификаторов с помощью заданной вами пользовательской строки.

Во Flex вы можете использовать любой параметр командной строки -P foo или синтаксис опции % option prefix = «foo» в первом разделе файла.

В Bison вы можете использовать любой параметр командной строки -р фу или синтаксис опции % name-prefix «foo».

движущийся выход

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

Во Flex вы можете указать либо -o lex.foo.cc в командной строке (это должно быть перед вашим входным файлом!) или % option outfile = «lex.foo.cc» в первом разделе.l файла.

В Bison вы можете указать либо -o «foo.tab.cc» в командной строке или % output «foo.tab.cc» в первом разделе.y файла. Тем не менее, Bison обычно в любом случае называет свой вывод после его ввода; входной файл с именем «foo.y» уже будет генерировать «foo.tab.c».

зависание в Windows

Я слышал от лояльного читателя (о, привет, Алена), что запуск этих примеров из Windows представляет собой логистическую проблему. Visual C запускает его в своем собственном терминале, и когда программа завершается, он сразу же закрывает терминал, так что вы можете ‘ не вижу никакого выхода.

Рекомендуется добавить вызов в программу приостановки Windows, которая останавливается, пока вы не нажмете клавишу ввода. Таким образом, добавьте это в вашу основную функцию после yylex / yyparse и перед возвращением:

стартовые состояния

В грамматике Flex / Bison практически невозможно разрешить многострочные комментарии, такие как C / /. Что вам действительно нужно, так это чтобы парсер перешел в своего рода состояние «игнорировать все», когда он видит «/ », и возвращается в нормальное состояние, когда он видит « /». Ясно, что вы не захотите, чтобы Bison делал это, иначе вам придется ставить необязательные цели ‘comment’ по всем элементам в вашем синтаксисе; Вы можете увидеть, как упал Flex, чтобы реализовать какой-то способ сделать это.

Flex позволяет указать стартовые состояния, которые являются просто шаблонными правилами регулярных выражений, как и любые другие но они совпадают, только если вы находитесь в определенном состоянии. Синтаксис для шаблона, который должен соответствовать, только если мы находимся в состоянии ‘FOO’, выглядит следующим образом:

Обратите внимание, что вы придумать названия состояний. они не предопределены или что-то еще. Хотя, когда вы создаете состояние, вы должны объявить его в разделе управления вашего файла Flex (это первый раздел перед первым «%%»):

Так как вы попали в государство? Существует специальная конструкция Flex (я думаю, что в конечном итоге это макрос C), которая входит в любой обычный блок кода: а как насчет возврата из этого состояния и возврата туда, где вы были изначально? Вместо чего-то очевидного (скажем, «END ()»?) Они решили сделать состояние по умолчанию «INITIAL». Предполагается, что любой шаблон сопоставления Flex, у которого нет состояния перед ним, находится в НАЧАЛЬНОМ состоянии. Чтобы вернуться к этому, просто перейдите к нему: обратите внимание, что BEGIN для всех намерений и целей является нормальным кодом C, несмотря на тот факт, что это не так. 🙂 Это означает, что вы можете обращаться с ним как с кодом и размещать его где угодно. вы даже можете сделать его условным:

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

Обратите внимание, что вы также можете иметь Flex-соответствие, относящееся к множественный утверждает, перечисляя их всех:

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

чтение введенных данных

Это на удивление довольно просто. Основная идея состоит в том, чтобы фильтровать вход Flex через libz. libz очень хорош, потому что он пропустит, без изменений, любой ввод, который не заархивирован. поэтому нам не нужно проверять, является ли ввод заархивированным, и обрабатывать его по-другому!

сгибать бизон || برنامجك الأول

Для справки, API для libz доступен здесь (последнее, что я смотрел). Я постоянно удивляюсь тому, как легко использовать libz напрямую, чтобы избежать глупых взломов, таких как «popen» ing «gunzip.c» и перенаправление его вывода. Слава команде libz!

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

Что такое Flex и Bison

Так или иначе (я помещаю его в мои файлы верхнего уровня, потому что он не должен входить в исходный код Flex / Bison), вам нужно определить свою функцию ввода. Моя выглядит так:

Затем вместо fopen вы используете libz:

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

Идея оболочки о регулярных выражениях не совсем точна с «реальным» определением регулярных выражений, но, по крайней мере, идея та же самая. Здесь мы говорим ls перечислить все файлы, которые имеют asdf где-то в имени. Мы могли бы попросить только файлы начало с asdf, говоря «asdf », или все файлы, заканчивающиеся asdf на « asdf». Звездочка в основном означает «что-нибудь может пойти сюда».

Регулярные выражения. это просто научная деконструкция такого сопоставления с образцом. На самом деле есть целая книга О’Рейли, посвященная им, если вы действительно хотите увидеть, о чем они все. (Мне бы очень хотелось сделать чудак о том, что он хорош для бессонницы, но сейчас он занимает 5,076 место в рейтинге продаж Amazon. Думаю, это не может быть слишком невыносимо!)

С учетом вышесказанного мой небольшой обзор здесь явно не будет исчерпывающим, но должен дать вам общее представление. Регулярные выражения Flex состоят из «символов» и «метасимволов». «Символы» интерпретируются буквально как реальный текст, тогда как «метасимволы» изменяют работу поиска. Например, перечисление «foo» в качестве регулярного выражения будет соответствовать ровно одной строке, то есть «foo». Но если вы добавите метасимвол «» (что означает «один или несколько из предыдущего символа») после «f», чтобы получить «f oo», он будет соответствовать «foo», «ffoo» и «ffffffffffffffffoo» , Таблица метасимволов следующая: