Разработчик (и) | Верн Паксон |
---|---|
Первый выпуск | около 1987 г.; 33 года назад (1987) |
Стабильный выпуск | 2.6.4 / 6 мая 2017 г.; 3 года назад (06.05.2017) |
Репозиторий | |
Операционная система | Unix-подобная |
Тип | Лексический анализатор генератор |
Лицензия | Лицензия BSD |
Веб-сайт | github.com / westes / flex |
Flex (быстрый лексический анализатор генератор) - это бесплатная программа с открытым исходным кодом, альтернатива lex. Это компьютерная программа, которая генерирует лексические анализаторы (также известные как «сканеры» или «лексеры»). Он часто используется как реализация lex вместе с Berkeley Yacc генератором парсера в операционных системах, производных от BSD (как и lex
, и yacc
являются частью POSIX ) или вместе с GNU bison (версия yacc ) в * портах BSD и в дистрибутивах Linux. В отличие от Bison, flex не является частью проекта GNU и не выпускается под Стандартной общественной лицензией GNU, хотя руководство по Flex было разработано и опубликовано Free Software Foundation.
Flex был написан на C около 1987 года. Автор: Верн Паксон, с помощью многих идей и вдохновения Ван Якобсона. Оригинальная версия автора Jef Poskanzer. Быстрое табличное представление - это частичная реализация дизайна, разработанного Ван Якобсоном. Реализация была выполнена Кевином Гонгом и Верном Паксоном.
Это пример сканера Flex для учебного языка программирования PL / 0.
Токены распознаются: '+
', '-
', '*
', '/
', '=
',' (
',' )
',' ,
',' ;
',' .
',' : =
',' <
',' <=
',' <>
',' >
',' >=
'; числа: 0-9 {0-9}
; идентификаторы: a-zA-Z {a-zA-Z0-9}
и ключевые слова: begin
, call
, const
, do
, end
, if
, нечетный
, процедура
, затем
, var
, пока
.
% {#include "y.tab.h"% } цифра [0-9] буква [a-zA-Z] %% "+" {return PLUS; } "-" {return MINUS; } "*" {ВРЕМЯ возврата; } "/" {return SLASH; } "(" {return LPAREN;} ")" {return RPAREN; } ";" {вернуть SEMICOLON; } "," {return COMMA; } "." {ПЕРИОД возврата; } ": =" {возвращение СТАНОВИТСЯ; } "=" {return EQL; } "<>" {вернуть NEQ; } "<" { return LSS; } ">" {вернуть GTR; } "<=" { return LEQ; } ">=" {вернуть GEQ; } "начало" {return BEGINSYM; } "вызов" {return CALLSYM; } "const" {return CONSTSYM; } "делать" {возвращать ДОСИМ; } "конец" {return ENDSYM; } "если" {вернуть IFSYM; } "нечетный" {return ODDSYM; } "процедура" {return PROCSYM; } "затем" {return THENSYM; } "var" {return VARSYM; } "в то время как" {return WHILESYM; } {буква} ({буква} | {цифра}) * {yylval.id = strdup (yytext); вернуть IDENT; } {цифра} + {yylval.num = atoi (yytext); вернуть НОМЕР; } [\ t \ n \ r] / * пропускать пробелы * /. {printf ("Неизвестный символ [% c] \ n", yytext [0]); вернуть НЕИЗВЕСТНО; } %% int yywrap (void) {return 1;}
Эти программы выполняют синтаксический анализ и токенизацию символов с помощью детерминированного конечного автомата (DFA). DFA - это теоретическая машина, принимающая обычные языки. Эти машины являются частью коллекции машин Тьюринга. DFA эквивалентны доступным только для чтения машинам Тьюринга, движущимся вправо. Синтаксис основан на использовании регулярных выражений. См. Также недетерминированный конечный автомат.
Лексический анализатор Flex обычно имеет временную сложность в длине ввода. То есть он выполняет постоянное количество операций для каждого входного символа. Эта константа довольно мала: GCC генерирует 12 инструкций для цикла сопоставления DFA. Обратите внимание, что константа не зависит от длины токена, длины регулярного выражения и размера DFA.
Однако использование макроса REJECT в сканере с потенциалом сопоставления очень длинных токенов может заставить Flex создать сканер с нелинейной производительностью. Эта функция не является обязательной. В этом случае программист явно сказал Flex «вернуться и попробовать еще раз» после того, как он уже сопоставил некоторый ввод. Это заставит DFA вернуться в поисках других состояний приема. Функция REJECT не включена по умолчанию, и из-за ее влияния на производительность ее использование не рекомендуется в руководстве по Flex.
По умолчанию сканер, созданный Flex, не повторно входим. Это может вызвать серьезные проблемы для программ, использующих сгенерированный сканер из разных потоков. Чтобы решить эту проблему, Flex предоставляет варианты для достижения повторного входа. Подробное описание этих параметров можно найти в руководстве Flex.
Обычно сгенерированный сканер содержит ссылки на файл заголовка unistd.h, который является Unix специфический. Чтобы избежать генерации кода, который включает unistd.h, следует использовать% option nounistd. Другой проблемой является вызов isatty (функция библиотеки Unix), который можно найти в сгенерированном коде. Параметр% never-interactive заставляет flex генерировать код, который не использует isatty.
Flex может генерировать код только для C и C ++. Чтобы использовать код сканера, сгенерированный flex из других языков, можно использовать инструмент привязки языка, такой как SWIG.
flex ++ - это аналогичный лексический сканер для C ++, который включен как часть пакета flex. Сгенерированный код не зависит от какой-либо среды выполнения или внешней библиотеки, за исключением распределителя памяти (malloc или альтернативы, предоставленной пользователем), если только ввод также не зависит от Это. Это может быть полезно в встроенном и подобных ситуациях, когда возможности традиционной операционной системы или среды выполнения C могут быть недоступны.
Сканер C ++, созданный с помощью flex ++, включает файл заголовка FlexLexer.h
, который определяет интерфейсы двух сгенерированных классов C ++.