flex linux что это

Всем спасибо за внимание! Жду критики.

UPD. По просьбам в комментариях выкладываю скрины работы автодополнения и автоотступов, а также процесса компиляции (P.S. Ant’a я пока не прикрутил).

Компиляция…

Всё остальное…

Источник

Flex linux что это

GNU Flex позволяет описать лексический анализатор на простом языке Flex, перечислив регулярные выражения для отдельных токенов и указав код, исполняемый при сопоставлении каждого токена. Затем Flex генерирует код на языке C или C++. Полученный код использует детерминированный конечный автомат для разбора текста.

Содержание

Перед чтением этой статьи рекомендуется ознакомиться со статьёй об особенностях языка C

Опции командной строки

Философия UNIX гласит: пишите программы, которые делают что-то одно и делают это хорошо.

Задача: интерпретатор для управления роботом

Допустим, нам нужно написать простой интерпретатор, принимающий 6 команд:

Команды читаются из стандартного потока ввода std::cin последовательно как слова, вывод и ошибки печатаются в потоки std::cin и std::cout соответственно.

Реализация на C++ с помощью iostream

Ниже представлена реализация, использующая потоки для чтения отдельных слов. Далее мы попробуем дополнить эту реализацию сканером на GNU Flex, а пока что изучите исходный код примера:

Описание лексера на Flex

Flex получает описание лексического анализатора из входного файла на специальном языке. Этот файл состоит из трёх секций:

Обработчик правила — это вставка кода на языке C, которая будет помещена внутрь switch-case. Этот switch-case будет находиться в теле созданной генератором функции, выполняющей сканирование следующего токена. Внутри такой вставки можно выполнить return, чтобы функция вернула сопоставленную подстроку как токен, а можно ничего не делать, чтобы функция пропустила эту подстроку и продолжила выполнение.

GNU Flex предполагает, что набор типов токенов уже известен и предоставлен снаружи; дело в том, что этот набор обычно генерирует парсер контекстно-свободной грамматики, и он же проставляет числовое значение для каждого типа токена; генератору GNU Flex числовые значения типов токена безразличны. Ниже показан пример заголовка, определяющего типы токенов:

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

Генерация кода сканера с помощью GNU Flex

Для сборки потребуется запустить flex из командной строки с подходящими опциями (список возможных опций был показан ранее). Лучше всего написать скрипт, который автоматизирует запуск генератора кода и позволит не писать одни и те же команды повторно. Скрипт написан на языке Python:

Если скрип завершился успешно, откройте “RobotScanner.c” и исследуйте созданный код:

Код в “RobotScanner.c” довольно запутанный, и на деле его можно было написать проще на современном языке C, но GNU Flex рассчитан на работу в любых условиях, включая очень необычные компиляторы и операционные системы.

Подключение сканера в main

Добавляем обработку ошибок

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

Добавим два новых типа токена в enum Token :

Добавим два новых правила сканера в “RobotScanner.l”:

Модифицируем функцию ReadInputInLoop, чтобы обрабатывать TOKEN_ERROR. Обрабатывать TOKEN_UNEXPECTED_WORD в этой функции не надо, т.к. функция ExecuteCommand уже обрабатывает неопознанные команды.

После перекомпиляции и запуска программы введём “no. ” и получим:

Что делать дальше?

Поупражняйтесь с Flex: попробуйте описать правила для ключевых слов и операторов языка C, или сделать сканер для кода на Python. Не забывайте, что GNU Flex способен работать только с регулярными грамматиками, в которых нет рекурсивно определённых правил.

Для отладки правил сканера советуем использовать отладчики регулярных выражений, которые легко найти в поисковике по запросу “online regex debugger”.

Справку можно получить на stackoverflow по тегу flex-lexer: stackoverflow.com/questions/tagged/flex-lexer.

Избранные вопросы по интеграции GNU Flex в сборку проекта:

Источник

Flex linux что это

This is flex, the fast lexical analyzer generator.

flex is a tool for generating scanners: programs which recognize lexical patterns in text.

The flex codebase is kept in Git on GitHub. Source releases of flex with some intermediate files already built can be found on the github releases page.

Use GitHub’s issues and pull request features to file bugs and submit patches.

There are several mailing lists available as well:

Find information on subscribing to the mailing lists or search in the archive at: https://sourceforge.net/p/flex/mailman/ Note: Posting is only allowed from addresses that are subscribed to the lists.

The flex distribution contains the following files which may be of interest:

You need the following tools to build flex from the maintainer’s repository:

In cases where the versions of the above tools matter, the file configure.ac will specify the minimum required versions.

Once you have all the necessary tools installed, life becomes simple. To prepare the flex tree for building, run the script:

in the top level of the flex source tree.

This script calls the various tools needed to get flex ready for the GNU-style configure script to be able to work.

From this point on, building flex follows the usual routine:

This file is part of flex.

This code is derived from software contributed to Berkeley by Vern Paxson.

The United States Government has rights in this work pursuant to contract no. DE-AC03-76SF00098 between the United States Department of Energy and the University of California.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

Neither the name of the University nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED «AS IS» AND WITHOUT ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.

About

Источник

Lex и YACC в примерах

PowerDNS BV (bert hubert )

1. Введение

Здравствуй, дорогой читатель.

Эти программы чрезвычайно полезны, но как и для компилятора C, в их man-страницах не объясняется ни как ими пользоваться, ни описания языка использования. YACC удивительно полезен в сочетании с Lex, однако man-страница Bison не описывает, как интегрировать сгенерированный с помощью Lex код с вашей Bison-программой.

1.1. Чего НЕТ в этом документе

Документация, которая идет с Flex и BISON великолепна, но не является средством обучения. Однако хорошо дополняет мое HOW-TO. Эта документация также указана в конце статьи.

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

Не смотрите на примеры из этого HOW-TO как на примеры для подражания. Данные примеры намеренно упрощены, их можно написать куда лучше. Если знаете, как, пожалуйста, напишите мне.

1.2. Что нужно скачать

1.3. Лицензия

Copyright (c) 2001 by bert hubert. This material may be distributed only subject to the terms and conditions set forth in the Open Publication License, vX.Y or later (the latest version is presently available at http://www.opencontent.org/openpub/ ).

2. Чем Lex и YACC могут помочь

2.1. Чем занимается каждая программа

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

3. Lex

Программа Lex генерирует лексические анализаторы (lexer). Lexer принимает на входе поток символов, а когда встречает группу символов, совпадающих с некоторым шаблоном (ключом), выполняет определенное действие. Вот простейший пример:

В первой секции между парой скобок % < и %>мы включили текст, который напрямую попадет в итоговую программу. Это включение необходимо, потому что впоследствии мы используем подпрограмму printf, которая определена в заголовочном файле stdio.h

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

Помимо ‘stop’ мы также определили ключ ‘start’. Он делает почти то же самое.

Секция кода также заканчивается комбинацией ‘%%’.

Чтобы откомпилировать Пример 1, отдайте команды:

ЗАМЕЧАНИЕ. Если вы пользуетесь flex, а не lex, тогда возможно вам придется поменять параметр ‘-ll’ на ‘-lfl’, даже если вы вызываете ‘flex’ как ‘lex’. Так требуется в некоторых дистрибутивах.

Будет создан файл ‘example1’. Если теперь вы его запустите, программа будет ожидать ввода данных. Если введете что-либо, не совпадающее с определенными нами ключами (‘stop’ и ‘start’), то эти символы будут отображены еще раз. Если введете ‘stop’, будет выведено сообщение ‘Получена команда stop’.

Завершить работу с программой можно путем ввода EOF (^D).

3.1. Регулярные выражения в шаблонах

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

Шаблон WORD немного более сложное:

Откомпилируйте пример 2, аналогично примеру 1. С вашей новой программой может состояться вот такой диалог:

Man-страница по Flex подробно описывает работу с регулярными выражениями. Некоторые считают, что man-страница по регулярным выражениям Perl (man perlre) весьма полезна, хотя Flex не может реализовать все, что подвластно Perl.

3.2. Более сложный пример, синтаксис наподобие C

Допустим, нам нужно проанализировать файл следующего вида:

Ясно видим, что здесь встречаются следующие категории (токены):

Соответствующий Lex-файл приведен в примере 3:

Когда отдадим наш файл сгенерированной Lex-ом программе (с помощью скрипта example3.compile), мы получим:

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

На данном этапе нам здорово пригодится YACC.

3.3. Что мы увидели

Мы увидели, что Lex способен считывать символы из входного потока и группировать их в токены. Иначе это называется лексическим разбором.

4. YACC

YACC может проводить синтаксический анализ потока токенов с определенными значениями (атрибутами). Здесь явно видна связь между YACC и Lex. YACC совершенно не догадывается о том, что же такое «входной поток», ему требуются токены. Конечно, можно написать собственный лексический анализатор, но мы оставим эту задачу для Lex.

4.1. Простой контроллер термостата

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

Необходимо распознавать следующие токены: heat, on/off (состояние STATE), target, temperature и числа (NUMBER).

Lex-анализатор выглядит следующим образом (пример 4):

Отметим два важных изменения. Во-первых, мы подключили файл ‘y.tab.h’, во-вторых, мы больше ничего не печатаем, а лишь возвращаем имена токенов. Это изменение нужно потому, что мы будем отдавать поток токенов на вход YACC, которому неважно, что мы выводим на экран. В файле y.tab.h как раз находятся определения этих токенов.

Но откуда же берется файл y.tab.h? Он генерируется самим YACC из файла грамматики, который мы сейчас напишем. Наш язык очень прост, такой же простой будет и его грамматика:

Первая часть, я называю ее «корень». Она означает, что мы имеем «команды» (commands), и эти команды состоят из отдельных «команд» (command). Как нетрудно заметить, это определение рекурсивно, ведь оно содержит в себе само себя. Благодаря рекурсии, программа способна постепенно сокращать набор команд одну за одной. В разделе «Внутреннее устройство Lex и YACC» есть существенные замечания по рекурсии.

Правило heat_switch состоит из токена HEAT (это просто слово «heat»), после которого идет состояние (оно определено в Lex-файле как «on» или «off»).

Немного более сложным является последнее правило target_set, состоящее из токена TARGET (слово «target»), токена TEMPERATURE (слово «temperature») и числа.

Полный YACC-файл

В предыдущем разделе приведена лишь грамматическая часть YACC-файла, но это еще не все. Мы намеренно опустили этот заголовок:

Далее, есть функция main(), которая не делает ничего, только запускает наш механизм.

В последней строке определены используемые токены. На основе этой строки генерируется файл y.tab.h, если YACC вызван с ключом ‘-d’.

Компилируем и запускаем контроллер термостата

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

4.2. Обработка параметров термостата

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

Всякий раз, когда Lex распознает токен, текст этого токена помещается в строку «yytext». С другой стороны, YACC ожидает, что значение токена хранится в переменной «yylval». Пример 5 показывает очевидное решение этой проблемы:

Теперь нужно заставить YACC работать с этими переменными. То, что называется «yylval» в Lex, в YACC имеет совсем другое название. Давайте взглянем на новое правило для задания температуры:

Возможно, все станет ясно, когда вы увидите новое правило heat_switch:

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

4.3. Обрабатываем конфигурационный файл

Давайте повторим часть конфигурационного файла, упомянутого ранее:

Не забывайте, что лексический анализатор для этого файла у нас уже написан. Теперь нам надо составить YACC-грамматику, и модифицировать Lexer так, чтобы он возвращал значения в формате, понятном YACC.

Lex-файл примера 6 имеет следующий вид:

Если посмотрите внимательно, увидите, что порядок работы с yylval изменился. Теперь он является не целым числом, а строкой (указателем на char). В целях упрощения примера мы вызываем процедуру копирования строки strdup, и таким образом расходуется много памяти (память выделяется каждый раз при появлении токена типа WORD или FILENAME). Однако во многих случаях (особенно когда входные файлы маленькие) это не является острой проблемой, и можно обойтись этим примитивным решением.

Чтобы объяснить YACC о новом типе yylval, нужно добавить эту строку в заголовок нашей YACC-грамматики:

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

Содержимое зоны начинается с открывающей фигурной скобки (OBRACE), затем идут определения зоны, затем блок закрывается фигурной скобкой (EBRACE)

ВНИМАНИЕ. Грамматика не будет работать, если имя файла не содержит хотя бы одного символа ‘.’ или ‘/’.

Это обычное утверждение, обобщающее все утверждения, которые могут встретиться в блоке «zone». Опять же, видим рекурсию.

Здесь определяется блок, и внутри него утверждения (statements).

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

5. Написание парсера на C++

Хотя Lex и YACC появились раньше C++, тем не менее возможно создать парсер на языке C++. У Flex есть опция, позволяющая генерировать код лексического анализатора на C++, но мы не будем этим пользоваться, так как YACC не знает, как с ним напрямую работать.

В общем, нужно добавить в заголовок YACC-файла следующие строки:

Если хотите подсунуть модифицированную версию yydebug, нужно написать что-то вроде:

C++ запрещает несколько определений функции, поэтому мы так тут и пишем.

Возможно, придется повторить #define YYSTYPE в вашем Lex-файле, так как в C++ проверка типов данных более строгая.

Для компиляции программы введите:

6. Внутреннее устройство Lex и YACC

В YACC-файле можно указать свою собственную функцию main(), которая вызывает функцию yyparse(). Функция yyparse() создается автоматически с помощью YACC, и определяется в файле y.tab.c.

Функция yyparse() считывает поток токенов с атрибутами из yylex(), которую также нужно указать. Можно написать эту функцию самому вручную, или сгенерировать автоматически с помощью Lex. В наших примерах мы решаем задачу с помощью Lex.

yylex(), созданный Lex считывает символы из файла, которому соответствует файловый дескриптор FILE * yyin. Если yyin не установлен, тогда считывается стандартный ввод (stdin). Вывод программы производится в файл с дескриптором yyout, по умолчанию это стандартный вывод (stdout). Можно также модифицировать yyin в функции yywrap(), которая вызывается по достижении конца файла. Здесь можно открыть другой файл, и продолжить анализ.

Если это ваш случай, ваша реализация функции yywrap() должна вернуть 0. Если же вы действительно завершаете анализ, без открытия дополнительных файлов, возвращайте значение 1.

Каждый вызов функции yylex() возвращает целое значение, представляющее из себя тип токена. Таким образом YACC понимает, какого типа токен был считан. Этот токен может обладать значением (атрибутом), которое помещается в переменную yylval.

По умолчанию переменная yylval имеет тип int, но это можно переопределить ( #define YYSTYPE ) в одном из файлов, созданных YACC.

Лексический анализатор должен иметь доступ к переменной yylval. Для этого он должен быть объявлен в области видимости lexer как extern-переменная. Оригинальный YACC не дает сделать это через его средства, но вы сами можете сделать переопределение, добавив строку следом за #include :

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

6.1. Атрибуты токенов

Как уже было сказано, функция yylex() возвращает тип полученного токена, и помещает его значение в yylval. Всем токенам, перечисленным в строке с %token, назначаются численные номера, начиная с 256.

Поэтому все символы из стандартной таблицы ASCII (их коды 0-255) могут быть использованы в качестве токенов. Предположим, в процессе разработки программы-калькулятора, вы написали следующий лексический анализатор:

Соответствующая YACC-грамматика выглядит так:

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

Последняя точка соответствует всем символам, которые до сих пор не попали ни под одно правило.

Наша YACC-грамматика тогда будет выглядеть следующим образом:

Это намного короче и куда очевиднее. Нет необходимости объявлять эти ASCII-токены в заголовке %token, они заработают автоматически.

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

Это означает: команды (commands) либо пусты, либо состоит из нескольких команд (commands), за которыми следует еще одна команда (command). Таким образом, YACC может отцеплять от групп команд отдельные команды, и обрабатывать одна по одной.

Сравните такой подход с правой рекурсией, который почему-то на взгляд многих людей выглядит привлекательнее:

Однако этот вариант дороже обходится. Если это первое правило (с меткой %start), тогда YACC приходится держать все ваши команды на стеке, что занимает большой объем памяти. Поэтому для анализа больших выражений, например целых файлов, следует использовать левую рекурсию. Иногда трудно устранить правую рекурсию, но если ваши выражения малы по размеру, то можно обойтись и ею.

Если какой-либо символ завершает (и поэтому разделяет) список ваших команд, правая рекурсия на первый взгляд может выглядеть естественной, но она все такая же дорогая:

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

В ранних версиях этого HOW-TO ошибочно использовалась правая рекурсия. Маркус Триска (Markus Triska) любезно проинформировал меня об этом.

6.3. Продвинутый yylval: %union

На данный момент нам нужно определять тип переменной yylval. Однако это не всегда приемлемо. Бывают случаи, когда нужно работать с несколькими типами данных. Но вернемся к нашему гипотетическому термостату. Допустим, пользователь хочет выбирать, каким обогревателем он будет управлять, например так:

Пример 7 основан на примере 4. Начнем написание YACC-грамматики:

Мы определяем наш тип union, состоящий лишь из чисел и строк. Затем с помощью расширенного синтаксиса %token, мы объясняем YACC, к какой части union’а каждый токен должен иметь доступ.

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

Однако здесь появляется новый токен WORD, которому нужен тип данных «строка».

Lex-файл также слегка изменяется:

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

В файле example7.y вы найдете более подробное описание.

7. Отладка

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

Это приведет к созданию файла «y.output», содержащего сведения о том, как именно автомат парсера был создан.

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

7.1. Автомат

Внутри себя парсер YACC запускает так называемый «автомат». Автомат может находиться в нескольких состояниях. Также есть правила, при выполнении которых автомат переходит из одного состояния в другое. Начальным состоянием автомата является «корень», о котором я говорил раньше.

Рассмотрим часть файла y.output из примера 7:

По умолчанию, это состояние изменяется по правилу «commands». Как уже сказано выше, это рекурсивное правило определяет, что «commands» состоит из отдельных «command», после которых идет точка с запятой и, возможно, другие команды.

На первой строке имеется символ «.», описывающий наше текущее местонахождение: мы только что просмотрели ZONETOK и теперь ожидаем «quotedname». Ясно, что quotedname начинается с токена QUOTE, при появлении такового автомат переходит в состояние 4.

Если есть желание увидеть полное описание этого автомата, скомпилируйте пример 7 с флагами из раздела 7 (Отладка).

7.2. Конфликты: ‘сдвиг/вывод’, ‘вывод/вывод’

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

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

Для него мы описали следующую грамматику:

Вы, пожалуй, уже почуяли неладное. Автомат начинает считывать слово «delete», затем «heater», а затем решает, в какое состояние перейти на основе следующего токена. Следующий токен может быть «mode» (описывающий как именно удалять обогреватели), либо имя обогревателя, которое нужно удалить.

Проблема состоит в том, что для обеих команд следующим токеном является WORD. Поэтому YACC не знает, куда идти дальше. Это приводит к появлению предупреждения типа «вывод/вывод», при этом разбор delete_a_heater никогда не будет достигнут.

8. Дополнительные материалы

Man-страница Flex весьма полезна, если вы уже примерно знаете, чем занимается Flex. Flex Manual также доступен в интернете.

Прочтя настоящую статью, возможно, вы захотите узнать больше о Lex и YACC. Я не читал этих книг, но их названия звучат хорошо:

Bison-The Yacc-Compatible Parser Generator

Compilers : Principles, Techniques, and Tools

By Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman. The ‘Dragon Book’. Первое издание вышло в 1985, и книга до сих пор перепечатывается. Это классическая книга по конструированию компиляторов. Также на Amazon

9. Благодарности

Источник