Flex

Из Википедије, слободне енциклопедије
flex
Развој Vern Paxson
Врста Генератор лексичког анализатора
Лиценца BSD license
Веб адреса flex.sf.net

Flex (брзи генератор лексичког анализатора) је слободна верзија Lex-а. Обично се користи са слободним Bison генератором. Flex настао око 1987. године и првобитно је написан у C-у, а његов аутор је Vern Paxson.

Опис flex-а дат је у упуству за његово коришћење:

"Flex је програмска алатка за генерисање скенера (читача): програма који препознају лексичке шаблоне у тексту. Flex чита дату улазну датотеку или стандардни улаз, уколико име улазне датотеке није задато, ради описа читача који ће да генерише. Описи су у облику регуларних израза и C кода, и зову се правила. Flex генерише као излаз С датотеку, 'lex.yy.c', која позива функцију 'yylex()'. Ова С датотека је компајлирана и повезана (линкована) са '-lfl' датотеком да би било могуће извршавање програма. Када се покрене програм, он анализира дати улаз тражећи онај део улаза који одговара датом регуларном изразу. Када нађе тај део улаза, онда се извршава одговарајући део C кода..."

Лексички читач који одговара C++ је flex++, и он је део flex пакета. Flex++ је доступан на јуникс системима базирани на бесплатној GNU лиценци. Он је такође доступан и нејуниксовским системима.

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 и враћа успешно прочитан симбол из улазне датотеке.

Срце читача, 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 puta;
    case '/': return podeljeno;
    case '=': return jednako;
    case '(': return ozagrada;
    case ')': return zzagrada;
    case ',': return zarez;
    case ';': return tacka_zarez;
    case '.': return tacka;
    case ':':
      ch = read_ch();
      return (ch == '=') ? becomes : nul;
    case '<':
      ch = read_ch();
      if (ch == '>') return nije_jednako;
      if (ch == '=') return manje_jednako;
      put_back(ch);
      return manje;
    case '>':
      ch = read_ch();
      if (ch == '=') return vece_jednako;
      put_back(ch);
      return vece;
    default:
      if (isdigit(ch)) {
        num = 0;
        do {  /* ne proverava se prekoracenje! */
          num = 10 * num + ch - '0';
          ch = read_ch();
        } while ( ch != EOF && isdigit(ch));
        put_back(ch);
        return broj;
      }
      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: neodgovarajuci karakter '%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"
%}
 
cifra         [0-9]
slovo        [a-zA-Z]
 
%%
"+"                  { return PLUS;       }
"-"                  { return MINUS;      }
"*"                  { return PUTA;      }
"/"                  { return PODELJENO;      }
"("                  { return OZAGRADA;     }
")"                  { return ZZAGRADA;     }
";"                  { return TACKA_ZAREZ;  }
","                  { return ZAREZ;      }
"."                  { return TACKA;     }
":="                 { return JE;    }
"="                  { return JEDNAKO;        }
"<>"                 { return NIJE_JEDNAKO;        }
"<"                  { return MANJE;        }
">"                  { return VECE;        }
"<="                 { return MANJE_JEDNAKO;        }
">="                 { return VECE_JEDNAKO;        }
"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 IDENTIFIKATOR;      }
{digit}+             { yylval.num = atoi(yytext);
                       return BROJ;     }
[ \t\n\r]            /* preskoci beline */
.                    { printf("Unknown character [%c]\n",yytext[0]);
                       return NEPOZNATO;    }
%%
 
int yywrap(void){return 1;}

50 линија кода на flex-у представља око 100 линија ручно писаног кода.


Погледајте још[уреди]