Flex (генератор лексического анализатора)
| Разработчик(и) | Верн Паксон |
|---|---|
| Первоначальный выпуск | около 1987 года [1] |
| Стабильная версия | 2.6.4
/ 6 мая 2017 г |
| Репозиторий | |
| Операционная система | Unix-подобный |
| Тип | лексического анализатора Генератор |
| Лицензия | Лицензия BSD |
| Веб-сайт | github |
Flex (быстрый генератор лексического анализатора ) — это с открытым исходным кодом бесплатная программная альтернатива lex . [2]
Это компьютерная программа , генерирующая лексические анализаторы (также известные как «сканеры» или «лексеры»). [3] [4]
Он часто используется как реализация lex вместе с Berkeley Yacc генератором анализатора в BSD (поскольку оба операционных системах, производных от lex и yacc являются частью POSIX ), [5] [6] [7] или вместе с GNU bison (версия yacc ) в портах *BSD [8] и в дистрибутивах Linux. В отличие от Bison, flex не является частью проекта GNU и не распространяется под лицензией GNU General Public License . [9] хотя руководство для Flex было подготовлено и опубликовано Фондом свободного программного обеспечения. [10]
История
[ редактировать ]Flex был написан на C примерно в 1987 году. [1] Верн Паксон , с помощью многих идей и большого вдохновения от Ван Джейкобсона . Оригинальная версия Джефа Посканцера . Быстрое табличное представление является частичной реализацией проекта Ван Джейкобсона. Реализация была выполнена Кевином Гонгом и Верном Паксоном. [11]
Пример лексического анализатора
[ редактировать ]Это пример сканера Flex для учебного языка программирования PL/0 .
Признаваемые токены: ' +', ' -', ' *', ' /', ' =', ' (', ' )', ' ,', ' ;', ' .', ' :=', ' <', ' <=', ' <>', ' >', ' >=';
цифры: 0-9 {0-9}; идентификаторы: a-zA-Z {a-zA-Z0-9} и ключевые слова: begin, call, const, do, end, if, odd, procedure, then, var, while.
%{
#include "y.tab.h"
%}
digit [0-9]
letter [a-zA-Z]
%%
"+" { return PLUS; }
"-" { return MINUS; }
"*" { return TIMES; }
"/" { return SLASH; }
"(" { return LPAREN; }
")" { return RPAREN; }
";" { return SEMICOLON; }
"," { return COMMA; }
"." { return PERIOD; }
":=" { return BECOMES; }
"=" { return EQL; }
"<>" { return NEQ; }
"<" { return LSS; }
">" { return GTR; }
"<=" { return LEQ; }
">=" { return GEQ; }
"begin" { return BEGINSYM; }
"call" { return CALLSYM; }
"const" { return CONSTSYM; }
"do" { return DOSYM; }
"end" { return ENDSYM; }
"if" { return IFSYM; }
"odd" { return ODDSYM; }
"procedure" { return PROCSYM; }
"then" { return THENSYM; }
"var" { return VARSYM; }
"while" { return WHILESYM; }
{letter}({letter}|{digit})* {
yylval.id = strdup(yytext);
return IDENT; }
{digit}+ { yylval.num = atoi(yytext);
return NUMBER; }
[ \t\n\r] /* skip whitespace */
. { printf("Unknown character [%c]\n",yytext[0]);
return UNKNOWN; }
%%
int yywrap(void){return 1;}
Внутренности
[ редактировать ]Эти программы выполняют анализ символов и токенизацию с помощью детерминированного конечного автомата (DFA). DFA — это теоретическая машина, принимающая обычные языки . Эти машины являются подмножеством коллекции машин Тьюринга . DFA эквивалентны машинам Тьюринга, движущимся вправо и доступным только для чтения . Синтаксис основан на использовании регулярных выражений . См. также недетерминированный конечный автомат .
Проблемы
[ редактировать ]Временная сложность
[ редактировать ]Лексический анализатор Flex обычно имеет временную сложность. по длине ввода. То есть он выполняет постоянное количество операций для каждого входного символа. Эта константа довольно мала: GCC генерирует 12 инструкций для цикла сопоставления DFA. [ нужна ссылка ] Обратите внимание, что константа не зависит от длины токена, длины регулярного выражения и размера DFA.
Однако использование макроса REJECT в сканере, который может сопоставлять очень длинные токены, может привести к тому, что Flex создаст сканер с нелинейной производительностью. Эта функция является необязательной. В этом случае программист явно сказал Flex «вернуться и повторить попытку» после того, как он уже сопоставил некоторые входные данные. Это заставит DFA вернуться назад, чтобы найти другие состояния принятия. Функция REJECT не включена по умолчанию, и из-за последствий для производительности ее использование не рекомендуется в руководстве Flex. [12]
Реентерабельность
[ редактировать ]По умолчанию сканер, созданный Flex, не является реентерабельным . Это может вызвать серьезные проблемы для программ, использующих сгенерированный сканер из разных потоков. Чтобы решить эту проблему, Flex предоставляет возможности для достижения повторного входа. Подробное описание этих опций можно найти в руководстве Flex. [13]
Использование в средах, отличных от Unix
[ редактировать ]Обычно сгенерированный сканер содержит ссылки на заголовочный файл unistd.h , специфичный для Unix . Чтобы избежать создания кода, включающего unistd.h , %option nounistd следует использовать . Другая проблема — вызов isatty (функции библиотеки Unix), которую можно найти в сгенерированном коде. % option Never-Interactive заставляет flex генерировать код, который не использует isatty . [14]
Использование flex из других языков
[ редактировать ]Flex может генерировать код только для C и C++ . Чтобы использовать код сканера, сгенерированный flex из других языков, инструмент привязки языка, такой как SWIG можно использовать .
Поддержка Юникод
[ редактировать ]Flex ограничен сопоставлением 1-байтовых (8-битных) двоичных значений и поэтому не поддерживает Unicode . [15] RE/flex и другие альтернативы поддерживают сопоставление Unicode.
Гибкий++
[ редактировать ]flex++ — аналогичный лексический сканер для C++ , который входит в состав пакета flex. Сгенерированный код не зависит от какой-либо среды выполнения или внешней библиотеки, за исключением распределителя памяти ( malloc или альтернативы, предоставляемой пользователем), если от него также не зависят входные данные. Это может быть полезно во встроенных и подобных ситуациях, когда традиционная операционная система или средства выполнения C могут быть недоступны.
Сканер C++, созданный flex++, включает файл заголовка. FlexLexer.h, который определяет интерфейсы двух классов, созданных C++.
См. также
[ редактировать ]
Ссылки
[ редактировать ]- ^ Перейти обратно: а б Левин, Джон (август 2009 г.). флекс и бизон . О'Рейли Медиа. п. 9. ISBN 978-0-596-15597-1 .
Примерно в 1987 году Верн Паксон из лаборатории Лоуренса в Беркли взял версию lex, написанную на ratfor (расширенном языке Fortran, популярном в то время), и перевел ее на C, назвав ее flex, что означает генератор лексического «быстрый анализатора» . '
- ^ Левин, Джон Р .; Мейсон, Тони; Браун, Дуг (1992). lex & yacc (2-е изд.). О'Рейли . п. 279. ИСБН 1-56592-000-7 .
Свободно доступная версия lex — flex .
- ^ Левин, Джон Р .; Мейсон, Тони; Браун, Дуг (1992). lex & yacc (2-е изд.). О'Рейли . стр. 1–2. ISBN 1-56592-000-7 .
- ^ Левин, Джон (август 2009 г.). флекс и бизон . О'Рейли Медиа. п. 304. ИСБН 978-0-596-15597-1 .
- ^ OpenBSD (11 декабря 2015 г.). "src/usr.bin/lex/" . Перекрестная ссылка BSD . Проверено 26 декабря 2015 г.
Это flex, быстрый генератор лексического анализатора.
- ^ "
flex(1)" . BSD * Справочные страницы . - ^ "
yacc(1)" . BSD * Справочные страницы . - ^ «bison-3.0.4 — генератор синтаксического анализатора GNU» . Порты OpenBSD . 15 ноября 2015 г. Проверено 26 декабря 2015 г.
- ^ Flex GNU или нет? , гибкий FAQ
- ^ «Flex — генератор сканеров — Содержание — Проект GNU — Фонд свободного программного обеспечения (FSF)» . ftp.gnu.org . Проверено 5 декабря 2019 г.
- ^ «Flex, версия 2.5. Быстрый генератор сканера. Издание 2.5, март 1995 г.» . Проверено 20 апреля 2019 г.
- ^ «Производительность — лексический анализ с помощью Flex для Flex 2.5.37» . Flex.sourceforge.net . Проверено 25 февраля 2013 г.
- ^ «Реентерабельность — лексический анализ с помощью Flex для Flex 2.5.37» . Flex.sourceforge.net . Проверено 25 февраля 2013 г.
- ^ «Параметры уровня кода и API — лексический анализ с помощью Flex для Flex 2.5.37» . Flex.sourceforge.net . Проверено 25 февраля 2013 г.
- ^ Томассетти, Габриэле (04 марта 2020 г.). «Почему не следует использовать (f)lex, yacc и bison» . Струмента . Проверено 26 октября 2022 г.
Дальнейшее чтение
[ редактировать ]- Левин, Джон (август 2009 г.). флекс и бизон . О'Рейли Медиа. ISBN 978-0-596-15597-1 .
- М. Е. Леск и Э. Шмидт, LEX - Генератор лексического анализатора
- Альфред Ахо, Рави Сетхи и Джеффри Ульман, Составители: принципы, методы и инструменты , Аддисон-Уэсли (1986). Описывает методы сопоставления с образцом, используемые flex (детерминированные конечные автоматы).