Flex lexical analyser

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Flex lexical analyser je v informatice nástroj, který generuje zdrojový kód pro lexikální analyzátorjazyce C. Jde o GNU variantu programu Lex. Používá se často spolu s generátorem syntaktického analyzátoru yacc nebo jeho vylepšenou alternativou GNU bison. Flex byl vytvořen Vernem Paxsonem v jazyce C v roce 1987.[1] Byl překládán pomocí Ratfor generátoru, který byl v té době veden Jefem Poskanzerem.[2]

Existuje podobný nástroj pro jazyk C++, který se jmenuje flex++, který je součástí balíčku Flex. V současné době Flex podporuje generování kódu pouze pro jazyky C a C++ (flex++). Vygenerovaný kód není závislý na žádné runtime nebo externí knihovně (s výjimkou paměťově alokované), pokud je na ní vstup také závislý. To může být užitečné v embedded systémech a podobných situacích, kde tradiční operační systém nebo C runtime zařízení nemusí být k dispozici.[1]

Příklad lexikálního analyzátoru[editovat | editovat zdroj]

Toto je příklad scanneru, který nevyužívá Flex pro naučný programovací jazyk PL/0. Uznávané symboly jsou: '+', '-', '*', '/', '=', '(', ')', ',', ';', '.', ':=', '<', '<=', '<>', '>', '>='; čísla: 0-9 {0-9}; identifikátory: a-zA-Z {a-zA-Z0-9} a klíčová slova: begin, call, const, do, end, if, odd, procedure, then, var, while.

Užití externích proměnných:

FILE *source                             /* The source file */
int cur_line, cur_col, err_line, err_col /* For error reporting */
int num                                  /* Last number read stored here, for the parser */
char id[]                                /* Last identifier read stored here, for the parser */
Hashtab *keywords

Volání externích rutin:

error(const char msg[])                              /* Report an error */
Hashtab *create_htab(int estimate)                   /* Create a lookup table */
int enter_htab(Hashtab *ht, char name[], void *data) /* Add an entry to a lookup table */
Entry *find_htab(Hashtab *ht, char *s)               /* Find an entry in a lookup table */
void *get_htab_data(Entry *entry)                    /* Returns data from a lookup table */
FILE *fopen(char fn[], char mode[])                  /* Opens a file for reading */
fgetc(FILE *stream)                                  /* Read the next character from a stream */
ungetc(int ch, FILE *stream)                         /* Put-back a character onto a stream */
isdigit(int ch), isalpha(int ch), isalnum(int ch)    /* Character classification */

Externí typy:

Symbol  /* An enumerated type of all the symbols in the PL/0 language */
Hashtab /* Represents a lookup table */
Entry   /* Represents an entry in the lookup table */

Skenování je odstartováno voláním init_scan, který pochází ze zdrojového souboru. Pokud je zdrojový soubor úspěšně otevřen, parser zavolá getsym, který opakovaně vrací po sobě jdoucí symboly ze zdrojového souboru.

Srdce scanneru – getsym – by měl být přímočarý. Zaprvé by měl přeskočit všechny mezery. Dále jsou získané znaky klasifikovány. Jestliže znak reprezentuje více symbolů, musí se provést další zpracování. Čísla jsou převedena do vnitřní formy a identifikátory jsou kontrolovány, zda nejsou klíčovým slovem.

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;
}

Nyní můžete porovnat kód, který byl vygenerovaný Flexem s ručně psaným kódem.

%{
#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;}

Přibližně 50 řádků kódu Flex versus 100 řádků ručně psaného kódu.

Flex++[editovat | editovat zdroj]

Flex++ je nástroj pro vytváření programu pro parsování jazyka. Tento program vytváří parser generátor. Toto je hlavní instance programu Flex.

Tyto programy fungují jako parséry znaků a tokenů pomocí použití deterministického konečného automatu. Tento stroj je podmnožinou Turingových strojů. Syntaxe je založená na použití regulárních výrazů.

Flex nabízí dva různé způsoby, jak generovat scannery. Primárně generuje kód jazyka C kompilovaný do C++ knihoven. Flex++, rozšíření Flexu, se používá pro generování C++ kódu a tříd. Flex++ třídy a kód vyžadují kompilátor pro vytvoření lexikálních programů a programů porovnávajících vzory. Flex, alternativní jazykový parser, zanedbává generovaní parsovacího scanneru v C kódu. C++ scanner generovaný pomocí Flex++ obsahuje hlavičkový soubor FlexLexer.h, který definuje rozhraní dvou C++ generovaných tříd.[1]

Související články[editovat | editovat zdroj]

Externí odkazy[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

  1. a b c http://en.wikipedia.org/wiki/Flex_lexical_analyser
  2. http://flex.sourceforge.net/manual/When-was-flex-born_003f.html#When-was-flex-born_003f