Flex (лексичний аналізатор)

flex (Fast LEXical analyzer generator) — вільна альтернатива до . Часто використовується з вільним генератором синтаксичних аналізаторів Bison . На відміну від Bison, flex не є частиною GNU. Flex був написаний на C близько 1987.

flex

Тип	генератор лексичних аналізаторів
Автор	^d^[1]^[2]
Розробник
Стабільний випуск	2.5.37 (3 серпня 2012; 11 років тому (2012-08-03))
Операційна система	UNIX-подібна
Мова програмування	C^[3]
Ліцензія	BSD license
Репозиторій	github.com/westes/flex.git
Вебсайт	flex.sourceforge.net

Подібний лексичний сканер для  — flex++, включений до пакету flex.

Використання

Lex (чи Flex) — інструмент для лексичного аналізу, що може використовуватись для виділення з сирцевого тексту певних рядків наперед заданим способом. Yacc (чи Bison) — інструмент для ; він читає текст і може використовуватись для конвертування послідовності слів у структурований формат для подальшої обробки.

На вході отримує текст у вільному форматі й правила виділення лексем. На виході дає код аналізатора, в вигляді функції на мові C.

Правила задаються в вигляді регулярних виразів ліворуч і, здебільшого, коду на мові C праворуч. Правила містять три секції, відокремлені рядком «%%»:
визначення
%%
правила
%%
код користувача

Визначення містять стартові значення й визначення, правила, безпосередньо самі вирази й дії, що відповідають їм, користувацький код просто включається в вивід flex. Деякі секції можуть бути відсутніми.

Функція аналізатора отримує текст на вході й виконує заданий код для кожної знайденої лексеми. Наприклад, даний код, для кожного входження username в тексті, виконає код («%s», getlogin()):

%% username  printf( "%s", getlogin() ); 

Дана функція виведе в потік рядок, що повертається функцією getlogin(). Тобто, кожне входження username у вхідному потоці буде замінено значенням, поверненим getlogin(). Наприклад, іменем поточного користувача.

Правила, відповідно до яких підсумкова функція має друкувати на виході тип лексеми (if, змінна, число, унарна чи бінарна операція) та значення для деяких лексем:

%% ifprintf ("IF statement\n"); [a-z]+printf ("tag, value %s\n", yytext); {D}+printf ("decimal number %s\n", yytext); "++"printf ("unary op\n"); "+"printf ("binary op\n"); 

Приклад підрахунку кількості рядків і символів у тексті:

%{  int num_lines = 0, num_chars = 0; %} %% \n  ++num_lines; ++num_chars;  .  ++num_chars; %% main() {  yylex();  printf( "# of lines = %d, # of chars = %d\n", num_lines, num_chars ); } 

Далі, функцію, створену генератором можливо використовувати з генераторами синтаксичних аналізаторів — зазвичай flex використовується разом з yacc чи bison. Синтаксичний аналізатор викликає функцію yylex(), створену генератором flex для пошуку наступної лексеми.

Приклад лексичного аналізатора

Одним із базових понять лексичного аналізу є логічний символ (токен). Логічний символ може складатися з одного чи кількох звичайних символів. Прикладом логічних символів, складених з кількох простих символів, можуть бути знаки операцій >=, <=, <>, ++ тощо. Ключові слова комп'ютерної мови також можуть розглядатись як різновид логічних символів. Тут і далі символами будуть називатись лише прості символи, щоб відрізнити їх від логічних символів.

Приклад сканера (написаного на C) для імперативної мови програмування .

Розпізнаються наступні логічні символи: '+', '-', '*', '/', '=', '(', ')', ',', ';', '.', ':=', '<', '<=', '<>', '>', '>='; числа: 0-9 {0-9}; ідентифікатори: a-zA-Z {a-zA-Z0-9} та ключові слова: begin, call, const, do, end, if, odd, procedure, then, var, while.

Використовуються зовнішні змінні:

FILE *source /* Початковий файл */ int cur_line, cur_col, err_line, err_col /* Дані для інформації про помилку */ int num /* Останнє прочитане число, для синтаксичного аналізу */ char id[] /* Останній прочитаний ідентифікатор, для синтаксичного аналізу */ Hashtab *keywords /* Перелік ключових слів */ 

Зовнішні процедури:

error(const char msg[]) /* Повідомити про помилку */ Hashtab *create_htab(int estimate) /* Створити пошукову таблицю */ int enter_htab(Hashtab *ht, char name[], void *data) /* Додати елемент до пошукової таблиці */ Entry *find_htab(Hashtab *ht, char *s) /* Знайти елемент пошукової таблиці */ void *get_htab_data(Entry *entry) /* Повернути дані з пошукової таблиці */ FILE *fopen(char fn[], char mode[]) /* Відкрити файл для читання */ fgetc(FILE *stream) /* Прочитати наступний символ з потоку */ ungetc(int ch, FILE *stream) /* Повернути символ у потік */ isdigit(int ch), isalpha(int ch), isalnum(int ch) /* Класифікація символів */ 

Зовнішні типи:

Symbol /* Перелічуваний тип усіх логічних символів мови PL/0 */ Hashtab /* Пошукова таблиця */ Entry /* Елемент пошукової таблиці */ 

Сканування запускається викликом init_scan, з передачею імені початкового файла. Якщо початковий файл успішно відкрито, синтаксичний аналізатор циклічно викликає getsym, щоб повернути successive символи з вхідного файлу.

Основа сканера, getsym, має бути зрозумілою. По-перше, пропускаються пробіли. Далі завантажений логічний символ класифікується. Якщо поточний простий символ входить до логічного символу з кількох простих символів, слід виконати додаткові дії. Числа перетворюються до внутрішнього формату, ідентифікатори перевіряються на наявність збігів з ключовими словами.

int read_ch(void) {  int ch = fgetc(source);  cur_col++;  if (ch == '\n') {  cur_line++;  cur_col = 0;  }  return ch; } void put_back(int ch) {  ungetc(ch, source);  cur_col--;  if (ch == '\n') cur_line--; } Symbol getsym(void) {  int ch;  while ((ch = read_ch()) != EOF && ch <= ' ')  ;  err_line = cur_line;  err_col = cur_col;  switch (ch) {  case EOF: return eof;  case '+': return plus;  case '-': return minus;  case '*': return times;  case '/': return slash;  case '=': return eql;  case '(': return lparen;  case ')': return rparen;  case ',': return comma;  case ';': return semicolon;  case '.': return period;  case ':':  ch = read_ch();  return (ch == '=') ? becomes : nul;  case '<':  ch = read_ch();  if (ch == '>') return neq;  if (ch == '=') return leq;  put_back(ch);  return lss;  case '>':  ch = read_ch();  if (ch == '=') return geq;  put_back(ch);  return gtr;  default:  if (isdigit(ch)) {  num = 0;  do { /* no checking for overflow! */  num = 10 * num + ch - '0';  ch = read_ch();  } while ( ch != EOF && isdigit(ch));  put_back(ch);  return number;  }  if (isalpha(ch)) {  Entry *entry;  id_len = 0;  do {  if (id_len < MAX_ID) {  id[id_len] = (char)ch;  id_len++;  }  ch = read_ch();  } while ( ch != EOF && isalnum(ch));  id[id_len] = '\0';  put_back(ch);  entry = find_htab(keywords, id);  return entry ? (Symbol)get_htab_data(entry) : ident;  }  error("getsym: invalid character '%c'", ch);  return nul;  } } int init_scan(const char fn[]) {  if ((source = fopen(fn, "r")) == NULL) return 0;  cur_line = 1;  cur_col = 0;  keywords = create_htab(11);  enter_htab(keywords, "begin", beginsym);  enter_htab(keywords, "call", callsym);  enter_htab(keywords, "const", constsym);  enter_htab(keywords, "do", dosym);  enter_htab(keywords, "end", endsym);  enter_htab(keywords, "if", ifsym);  enter_htab(keywords, "odd", oddsym);  enter_htab(keywords, "procedure", procsym);  enter_htab(keywords, "then", thensym);  enter_htab(keywords, "var", varsym);  enter_htab(keywords, "while", whilesym);  return 1; } 

Тепер порівняйте наведений вище код з кодом, щоб згенерувати сканер для тієї ж мови за допомогою flex:

%{ #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 = (char *)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;} 

Близько 50 рядків коду для flex проти близько 100 рядків отриманого коду.

Недоліки

Часова складність

Лексичний аналізатор Flex інколи має часову складність ${\displaystyle O(n)}$ відносно розміру вхідних даних. Іншими словами, він виконує сталу кількість операцій для кожного вхідного логічного символу. Ця кількість достатньо низька: GCC генерує 12 інструкцій для циклу перевірки детермінованого автомату. Слід зазначити, що ця кількість не залежить від довжини токена, довжини регулярного виразу й розміру детермінованого автомату.

Однак, одна необов'язкова можливість Flex може змусити Flex генерувати сканер з нелінійною продуктивністю: використання макроса REJECT в сканері з можливістю позначати вкрай довгі токени. В цьому випадку, програміст безпосередньо вказав flex повернутись і спробувати ще раз після того, як він уже підібрав вхідні дані. В результаті, детермінований автомат буде змушений повернутись до пошуку інших прийнятних станів. Теоретично, часова складність становить ${\displaystyle O(n+m^{2})\geq O(m^{2})}$, де ${\displaystyle m}$ — довжина найдовшого токена (це повертає до ${\displaystyle O(n)}$, якщо токени малі в порівнянні з розміром вхідних даних). Можливість REJECT за замовчуванням не дозволена, і вплив її на продуктивність детально задокументовано в інструкції користувача Flex.

Повторне використання

За замовчуванням синтаксичний аналізатор, згенерований за допомогою Flex, не розрахований на повторне використання. Це може викликати серйозні проблеми з програмами, що викликають згенерований сканер з різних тредів. Для обходу цієї проблеми існує додаткова опція, з якою Flex забезпечує можливість паралельного використання. Детальний опис цих опцій можна знайти в інструкції користувача Flex .

Flex++

Flex++ — інструмент для створення лексичних аналізаторів. Генератор синтаксичних аналізаторів створює програму синтаксичного аналізу мови. Це ж стосувалось програми flex.

Ці програми здійснюють синтаксичний аналіз і токенізацію шляхом використання машини визначеного кінцевого стану. Детермінований (чи недетермінований) автомат — теоретичний автомат, що приймає регулярні мови. Ці машини — підмножина колекції машин Тюрінга. Детерміновані автомати еквівалентні до (машин Тюрінга, де зі стрічки, що рухається вправо, можливе лише читання) чи недетермінованих автоматів. Синтаксис базується на використанні регулярних виразів.

Flex надає два способи генерування сканерів. Він початково генерує код мовою C код для компіляції на противагу бібліотекам і коду. Flex++, розширення flex, використовується для генерування C++ коду і класів. Класи й код Flex++ потребують компілятора C++ для створення програм лексичної перевірки та звіряння з шаблонами. Flex, альтернативний мовний синтаксичний аналізатор, за замовчуванням генерує a parsing scanner на мові C. Сканери на , згенеровані у Flex++, включають файл заголовку FlexLexer.h, який визначає інтерфейси двох згенерованих класів .

Розробники Flex

, з використанням багатьох ідей .

Див. також

• John Levine, Tony Mason, and Doug Brown, Lex & Yacc, O'Reilly and Associates (2nd edition).
• M. E. Lesk and E. Schmidt, LEX - Lexical Analyzer Generator
• Alfred Aho, Ravi Sethi and Jeffrey Ullman, Compilers: Principles, Techniques and Tools, Addison-Wesley (1986). Описує технології що використовуються в flex (детерміновані скінченні автомати)

• Генератор синтаксичних аналізаторів Bison

Посилання

• Flex Homepage
• ANSI-C Lex Specification [ 12 грудня 2010 у Wayback Machine.]
• JFlex: Fast Scanner Generator for Java [ 6 жовтня 2011 у Wayback Machine.]
• Brief description of Lex, Flex, YACC, and Bison [ 7 травня 2005 у Wayback Machine.]
• A Romanian rebuild version of this book in pdf format "fb2-press.pdf" or "fb2-printing.pdf" may be downloaded from or directly from or .
• Download Win32 binaries of Flex++ and Bison++ [ 14 квітня 2005 у Wayback Machine.]

Примітки

1. Здебільшого — yylex().

Джерела

1. https://cvsweb.openbsd.org/src/usr.bin/lex/README
2. https://cvsweb.openbsd.org/src/usr.bin/lex/parse.y
3. http://openbsd.su/src/usr.bin/lex/Makefile
4. (August 2009). . O'Reilly Media. с. 304. ISBN . Архів оригіналу за 16 серпня 2011. Процитовано 15 листопада 2010.
5. Is flex GNU or not? [ 3 березня 2016 у Wayback Machine.], flex FAQ
6. Brown, Martin (31 травня 2006). (англ.). IBM. Архів оригіналу за 24 червня 2021. Процитовано 17 червня 2021.
7. http://flex.sourceforge.net/manual/Performance.html [ 27 січня 2014 у Wayback Machine.] (last paragraph)