Из Википедии, бесплатной энциклопедии
  (Перенаправлено из лексического анализатора Flex )
Перейти к навигации Перейти к поиску
сгибать
Разработчики)Верн Паксон
Первый выпускоколо 1987 г . ; 34 года назад [1] ( 1987 )
Стабильный выпуск
2.6.4 / 6 мая 2017 г . ; 3 года назад ( 2017-05-06 )
Репозиторий
Отредактируйте это в Викиданных
Операционная системаUnix-подобный
ТипГенератор лексического анализатора
ЛицензияЛицензия BSD
Веб-сайтgithub .com / westes / flex

Flex ( генератор быстрого лексического анализатора ) - это бесплатная программа с открытым исходным кодом, альтернатива lex . [2] Это компьютерная программа, которая генерирует лексические анализаторы (также известные как «сканеры» или «лексеры»). [3] [4] Он часто используется в качестве LEX реализации совместно с Беркли Yacc генератор синтаксических анализаторов на BSD -derived операционных систем (так как оба lexи yaccявляются частью POSIX ), [5] [6] [7] или совместно с ГНУ бизона (версия yacc) в портах * BSD [8] и в дистрибутивах Linux. В отличие от Bison, Flex не является частью проекта GNU и не выпускается под лицензией GNU General Public License , [9] , хотя руководство для Flex был подготовлен и опубликован Фондом свободного программного обеспечения. [10]

История [ править ]

Flex был написан на C около 1987 [1] по Верному Paxson , с помощью многих идей и много вдохновения от Van Jacobson . Оригинальная версия Джефа Посканцера . Быстрое табличное представление - это частичная реализация дизайна, разработанного Ван Якобсоном. Реализацией занимались Кевин Гонг и Верн Паксон. [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"% }цифра  [ 0-9 ] буква  [ a - zA - Z ]%% "+"  {  return  PLUS ;  } "-"  {  вернуть  МИНУС ;  } "*"  {  ВРЕМЯ возврата  ; } "/" { return SLASH ; } "(" { return LPAREN ; } ")" { return RPAREN ; } ";" { вернуть SEMICOLON ; } "," { return COMMA ; } "."{ ПЕРИОД возврата                        ;  } ": ="  {  возвращение  СТАНОВИТСЯ ;  } "="  {  return  EQL ;  } "<>"  {  return  NEQ ;  } "<"  {  return  LSS ;  } ">"  {  вернуть  ОТО ;  } "<="  {  return  LEQ ;  } "> ="  {  вернуть  GEQ ;  } "начало"  {  return  BEGINSYM ;  } "звонок" {  возврат 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. [12]

Повторный вход [ править ]

По умолчанию сканер, созданный Flex, не является реентерабельным . Это может вызвать серьезные проблемы для программ, использующих сгенерированный сканер из разных потоков. Чтобы решить эту проблему, Flex предоставляет варианты для достижения повторного входа. Подробное описание этих параметров можно найти в руководстве по Flex. [13]

Использование в средах, отличных от Unix [ править ]

Обычно сгенерированный сканер содержит ссылки на файл заголовка unistd.h, специфичный для Unix . Чтобы избежать генерации кода, включающего unistd.h , следует использовать % option nounistd . Другая проблема - это вызов isatty (функция библиотеки Unix), который можно найти в сгенерированном коде. Параметр % never-interactive заставляет flex генерировать код, не использующий isatty . [14]

Использование гибкости из других языков [ править ]

Flex может генерировать код только для C и C ++ . Чтобы использовать код сканера, созданный с помощью flex из других языков, можно использовать инструмент привязки к языку , такой как SWIG .

Flex ++ [ править ]

flex ++ - это аналогичный лексический сканер для C ++, который включен как часть пакета flex. Сгенерированный код не зависит от какой-либо среды выполнения или внешней библиотеки, за исключением распределителя памяти ( malloc или альтернативы, предоставляемой пользователем), если только ввод также не зависит от него. Это может быть полезно во встроенных и подобных ситуациях, когда традиционная операционная система или средства времени выполнения C могут быть недоступны.

Сканер C ++, созданный с помощью flex ++, включает файл заголовка FlexLexer.h, который определяет интерфейсы двух сгенерированных классов C ++.

См. Также [ править ]

  • Сравнение генераторов парсеров
  • Лекс
  • yacc
  • GNU Bison
  • Беркли Якк

Ссылки [ править ]

  1. ^ a b Левин, Джон (август 2009 г.). флекс и зубр . O'Reilly Media. п. 9. ISBN 978-0-596-15597-1. Примерно 1987, Верн Paxson из Лаборатории Беркли Лоуренса взял версию Лекса , написанный в гораздо популярнее чем Си (расширенная Fortran популярной в то время) и перевел его в C, назвав его сгибать, для ' F аст Lex ческих Analyzer генератора. '
  2. ^ Левин, Джон Р .; Мейсон, Тони; Браун, Дуг (1992). lex & yacc (2-е изд.). О'Рейли . п. 279. ISBN 1-56592-000-7. Бесплатная версия lex - это flex . CS1 maint: обескураженный параметр ( ссылка )
  3. ^ Левин, Джон Р .; Мейсон, Тони; Браун, Дуг (1992). lex & yacc (2-е изд.). О'Рейли . С. 1–2. ISBN 1-56592-000-7. CS1 maint: обескураженный параметр ( ссылка )
  4. ↑ Левин, Джон (август 2009 г.). флекс и зубр . O'Reilly Media. п. 304. ISBN 978-0-596-15597-1.
  5. ^ OpenBSD (11 декабря 2015 г.). "src / usr.bin / lex /" . Перекрестная ссылка BSD . Проверено 26 декабря 2015 . Это гибкий, быстрый генератор лексических анализаторов.
  6. ^ " " . * Справочные страницы BSD .flex(1)
  7. ^ " " . * Справочные страницы BSD .yacc(1)
  8. ^ "bison-3.0.4 - Генератор парсеров GNU" . Порты OpenBSD . 2015-11-15 . Проверено 26 декабря 2015 .
  9. ^ Это гибкий GNU или нет? Архивировано 3 марта 2016 г. на Wayback Machine , FAQ по гибкомудиску.
  10. ^ «Flex - генератор сканера - Содержание - Проект GNU - Фонд свободного программного обеспечения (FSF)» . ftp.gnu.org . Проверено 5 декабря 2019 .
  11. ^ "Flex, версия 2.5 Генератор быстрых сканеров, редакция 2.5, март 1995" . Проверено 20 апреля 2019 .
  12. ^ «Производительность - лексический анализ с помощью Flex, для Flex 2.5.37» . Flex.sourceforge.net. Архивировано из оригинала на 2014-01-27 . Проверено 25 февраля 2013 .
  13. ^ «Реентерабельность - лексический анализ с помощью Flex, для Flex 2.5.37» . Flex.sourceforge.net. Архивировано из оригинала на 2010-11-17 . Проверено 25 февраля 2013 .
  14. ^ «Параметры уровня кода и API - лексический анализ с помощью Flex, для Flex 2.5.37» . Flex.sourceforge.net. Архивировано из оригинала на 2013-03-14 . Проверено 25 февраля 2013 .

Дальнейшее чтение [ править ]

  • Левин, Джон (август 2009 г.). флекс и зубр . O'Reilly Media. ISBN 978-0-596-15597-1.
  • М. Е. Леск и Э. Шмидт, LEX - Генератор лексических анализаторов
  • Альфред Ахо, Рави Сетхи и Джеффри Уллман, Компиляторы: принципы, методы и инструменты , Эддисон-Уэсли (1986). Описывает методы сопоставления с образцом, используемые гибкими (детерминированными конечными автоматами)

Внешние ссылки [ править ]

  • Официальный веб-сайт
  • Спецификация ANSI-C Lex
  • JFlex: генератор быстрого сканирования для Java
  • Краткое описание Lex, Flex, YACC и Bison