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

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

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

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

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

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

%%

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

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

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

%%
if		printf ("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) для імперативної мови програмування PL/0.

Розпізнаються наступні логічні символи: '+', '-', '*', '/', '=', '(', ')', ',', ';', '.', ':=', '<', '<=', '<>', '>', '>='; числа: 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++ — інструмент для створення лексичних аналізаторів. Генератор синтаксичних аналізаторів створює програму синтаксичного аналізу мови. Це ж стосувалось програми flex.

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

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

• 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 (детерміновані скінченні автомати)

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

• Flex Homepage
• Flex Manual
• ANSI-C Lex Specification
• JFlex: Fast Scanner Generator for Java
• Brief description of Lex, Flex, YACC, and Bison
• Compiler Construction using Flex and Bison - course by Anthony Aaby 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++