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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
flex
Розробник(и) Vern Paxson
Стабільний випуск 2.5.37 (3 серпня 2012; 777 днів тому)
Операційна система Unix-подібні
Тип генератор лексичних аналізаторів
Ліцензія BSD license
Сайт flex.sourceforge.net

flex (Fast LEXical analyzer generator) — вільна альтернатива до lex.[1] Часто використовується з вільним генератором синтаксичних аналізаторів Bison . На відміну від Bison, flex не є частиною GNU Project.[2] Flex був написаний на C Верном Пакссоном близько 1987. Він перекладав генератор Ratfor, який розробляв Jef Poskanzer.[3]

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

Використання[ред.ред. код]

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

[4]

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

Правила задаються в вигляді регулярних выразів ліворуч і, здебільшого, коду на мові 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 інколи має часову складність O(n) відносно розміру вхідних даних. Іншими словами, він виконує сталу кількість операцій для кожного вхідного логічного символа. Ця кількість достатньо низька: GCC генерує 12 інструкцій для циклу перевірки детермінованого автомату. Слід зазначити, що ця кількість не залежить від довжини токена, довжини регулярного виразу й розміру детермінованого автомату.

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

Повторне використання[ред.ред. код]

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

Flex++[ред.ред. код]

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

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

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

Розробники Flex[ред.ред. код]

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

Див. також[ред.ред. код]

  • 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

Посилання[ред.ред. код]

Примітки[ред.ред. код]

  1. Levine, John (August 2009). flex & bison. O'Reilly Media. с. 304. ISBN 978-0-596-15597-1. 
  2. Is flex GNU or not?, flex FAQ
  3. When was flex born?, flex FAQ
  4. IBM. Пособие.
  5. Здебільшого — yylex().
  6. http://flex.sourceforge.net/manual/Performance.html (last paragraph)