Flex - generator analizatorów leksykalnych

Spis treści:

1. Wprowadzenie
   • Wyrażenia regularne
   • Schemat specyfikacji
   • Prosty przykład
   • Uruchomienie
   • Makefile
2. Rozstrzyganie niejednoznaczności
3. Rozpoznawanie kontekstu
4. Stany
5. Predefiniowane zmienne i funkcje
6. Inne materiały

Flex jest generatorem analizatorów leksykalnych (skanerów). Usiłując opisać flex-a w kilku zdaniach można powiedzieć, że:

• flex przyjmuje na wejściu opis w formie wyrażeń regularnych,
• flex konstruuje na podstawie podanych wyrażeń regularnych automat skończony,
• flex produkuje kod skanera w języku C (lub C++),
• wygenerowny przez flexa program pozwala wykrywać w strumieniu wejściowym ciągi znaków zgodne ze wzorcami określonymi przez wyrażenia regularne i wykonywać zadane akcje po rozpoznaniu wzorca.

Działanie flex-a jest schematycznie przedstawione na rysunku:

Poniżej zaprezentowany jest zbiór wyrażeń regularnych udostępniach przez flex-a.

Przykłady:

Specyfikacja (wejście) dla flex-a to najczęściej plik z rozszerzeniem .l, np. example.l. Specyfikacja ma następujący układ:

	   definicje pomocnicze
	   %%
	   reguły 
	   %%
	   podprogramy pomocnicze

Sekcja definicje pomocnicze umożliwiaja zdefinowanie pomocniczych nazw dla złożonych wyrażeń regularnych oraz podanie kodu, który będzie bezpośrdnio kopiowany na początek kodu skanera.

Sekcja reguły zawiera wyrażenia regularnym wraz z przypisanymi im akcjami w języku C (lub C++).

Sekcja podprogramy pomocnicze umożliwia podanie kodu, który ma być skopiowany bezpośrednio na koniec pliku skanera.

Poniżej przedstawiony jest specyfikacja flexa dla skanera, który wyszukuje ciąg znaków lex i zamienia go na ciąg znaków flex.

%{
/* Program wyszukuje ciag znakow "lex" i zamienia go na ciag znakow "flex" */
%}

%%

lex	printf("flex");

%%

main() {
  printf("Zamiana lex na flex:\n");
  yylex();
  return 0;
 }

Źródła:  zamien.l

Aby wygenerować kod skanera wpisujemy:

Otrzymany w ten sposób kod należy skompilować:

Skaner można uruchomić z przykladowym plikiem testowym test_zamien:

Przykładowy Makefile:

PROG = example

all : ${PROG}

lex.yy.c: ${PROG}.l
		flex ${PROG}.l
	
${PROG}: lex.yy.c
		gcc -o ${PROG} lex.yy.c -lfl

Źródła:  Makefile

Więcej informacji:
http://developers.sun.com/solaris/articles/make_utility.html
http://www.gnu.org/software/make/manual/html_chapter/make.html#SEC_Top

Gdy więcej niż jedna reguła pasuje do ciągu wejściowego flex stosuje kolejno dwie zasady:

1. Preferowany jest możliwy do uzgodnienia lexem o największej długości
2. Wśród reguł, które uzgadniają lexem o tej samej długości preferowana jest reguła, która występuje wcześniej (innymi słowy przy równej długości ciągów znaków zadziała reguła wcześniejsza w specyfikacji)

%%
begin	printf("%s slowo kluczowe\n", yytext);	// regula 1 
[a-z]+	printf("%s identyfikator\n", yytext);	// regula 2 
.|\n	/* empty */

Jeżeli na wejściu pojawi się ciąg znaków beginner, to zadziała reguła 2 i flex potraktuje ciąg znaków jako identyfikator, bo reguła begin dopasuje 5 znaków, a reguła [a-z]+ dopasuje 8 znaków.

Jeżeli na wejściu pojawi się ciąg znaków begin, to zadziała reguła 1 i flex potraktuje go jako słowo kluczowe, bo obie reguły dopasowują po 5 znaków.

Źródła:  begin.l

Zdarza się, że w różnych momentach analizy dla tego samego wzorca mają być zastosowane różne akcje. Taka sytuacja wymaga rozpoznawania kontekstu przez skaner.

Flex oferuje następujące metody rozpoznawania kontekstu:

• użycie operatorów kontekstu ^, $ i /

  	^ - początek linii,
  	$ - koniec linii,	
  	/ - prawy kontekst.
  

  %{
  /* passwd.l
     Analiza zawartosci pliku passwd */
  %}
  
  %%
  
  ^ewa		printf("uzytkownik ewa ma konto w systemie\n");
  :$		printf("uzytkownik nie ma zdefiniowanego shell-a\n");
  .|\n		;
  
  

  Źródła:  passwd.l  |  test_passwd

  %{
  /* shutdown.l
     dopasowuje ciag shut, jezeli wystapi po nim ciag down */
  %}
  
  %%
  
  shut/down	printf("%s\n", yytext);   
  .|\n		/* empty */
  
  

  Źródła:  shudown.l

Stany

Do rozpoznawania lewego kontekstu można wykorzystać również stany startowe. Zilustrowano to poniżej.

Przykład użycia stanów startowych

%{
  /* jaguar1.l
   Rozpoznawanie znaczenia slowa jaguar w zaleznosci od lewego kontekstu 
   przy uzyciu stanow */
%}

%s A B 

%%
^a		BEGIN(A);
^b 		BEGIN(B);
<A>jaguar	printf("Duzy kot\n");
<B>jaguar	printf("Sportowy samochod\n");
.|\n		;

Źródła:  jaguar1.l

Ten sam przykład z użyciem flagi

%{
/* jaguar2.l
   Rozpoznawanie znaczenia slowa jaguar w zaleznosci od kontekstu 
   z wykorzystaniem flagi */
char flag;
%}

%%
^a	flag = 'a';	
^b	flag = 'b';	

jaguar	switch(flag){
	   case 'a':  printf("Duzy kot\n");
		      break;
	   case 'b':  printf("Samochod sportowy\n");
		      break;
	}
.|\n	;

Źródła:  jaguar2.l

Flex udostępnia również stany wyłączne. W wyłącznym stanie startowym nie działają żadne reguły poza posiadającymi ten stan w prefixie.

%{
/* exclusive.l
   demonstruje dzialanie wylacznych stanow startowych */
%}

%x LITERAL
%%

raz                ECHO;
dwa                ECHO;
#                  BEGIN(LITERAL);
<LITERAL>#         BEGIN(INITIAL);
.                  /* empty */

Źródła:  exclusive.l  |  test_exclusive

Predefiniowane zmienne i funkcje

Przykłady:

%{
/* meta-dane.l
   demonstruje dzialanie funkcji yymore */
%}

%%

meta-    ECHO;  yymore();
dane     ECHO;

Źródła:  meta-dane.l

%{
/* very_easy.l 
   demonstruje wykorzystanie dyrektywy REJECT */
%}

%%

very      printf("%s ",yytext);  REJECT;
[a-z]+    ECHO;

Źródła:  very_easy.l

REJECT = yyless(0);

%{
/*  block.l 
    Zliczanie wystapien ciagow znakow block i lock  */
int block_c, lock_c;
%}

%%

block {
	 block_c++;
	 /* Po dopasowaniu ciagu block wycofaj 
            wszystkie znaki poza pierwszym do ponownej analizy */
	 yyless(1);	
      }
lock	lock_c++;
\n|.	/* empty */

%%

main(){
   
   yyout = fopen("scanner_output", "a+");
   yylex();
   fprintf(yyout, "block - %d, lock - %d.\n",  block_c, lock_c);
   fclose(yyout);
}
	   	

Źródła:  block.l  |  test_block

%{
/* pary.l
   Tworzy statystyke wystapien wszystkich par malych liter */

int digram [26][26];
int i, j;
%}

%%
[a-z][a-z]	{
		  digram[yytext[0]-97][yytext[1]-97]++;
		  REJECT;
		}
.|\n		/* empty */
%%

main(){

/* wyzeruj tablice */
  for(i=0; i<26; i++) 
    for(j=0; j<26; j++)   
       digram[i][j] = 0;   

  yylex(); 
  
/* wypisz tablice */
/* Drukowanie podsumowań często umieszcza się także w funkcji yywrap */ 	     

    for(i=0; i<26; i++) 
       for(j=0; j<26; j++)   
          if (digram[i][j] != 0)      
 	     printf("%c,%c: %d\n", i+97, j+97, digram[i][j]);
}

Źródła:  pary.l

Lex - A Lexical Analyzer Generator, M. E. Lesk,
Flex - manual po polsku,
Flex, version 2.5 - A fast scanner generator, Vern Paxson.