Analiza leksykalna cz. 1

Wprowadzenie

Plex jest generatorem analizatorów leksykalnych.

plex przyjmuje na wejściu opis w formie wyrażeń regularnych
plex produkuje program w języku Pascal, który tworzy z wyrażeń regularnych automat skończony
automat pozwala wykrywać w strumieniu wejściowym ciągi znaków zgodne ze wzorcami określonymi przez wyrażenia regularne
wygenerowny przez plexa program może wykonywać zadane akcje po rozpoznaniu określonego ciągu znaków

Działanie plex-a jest przedstawione na rysunku:

Program wygenerowany przez plex-a można włączyć do programu analizującego składnię jako moduł odpowiedzialny za wstępną analizę leksykalną.

Wyrażenia regularne

Wyrażenia regularne:

pozwalają na wyszukiwanie napisów w przetwarzanym tekście,
zawierają specjalne znaki i konteksty dopasowujące ciągi znaków.

Wyrażenie	Obejmuje	Przykład
c	dowolny znak nie będący operatorem	`a`
\c	zwykłe znaczenia znaku	`\*`
"s"	ciąg znaków	`"**"`
.	dowolny znak z wyjątkiem znaku nowej linii	`a.b`
^	początej linii	`^początek`
$	koniec linii	`koniec$`
[s]	dowolny znak ze zbioru	`[0123abc]`
[^s]	dowolny znak nie będący w zbiorze	`[^0123abc]`
[s₁-s₂]	dowolny znak ze zbioru s₁-s₂	`[0-9]`
r*	zero badź więcej wystąpień wyrażenia r	`a*`
r+	jedno badź więcej wystąpień wyrażenia r	`a+`
r?	zero bądź jedno wystąpienie wyrażenia r	`a?`
r{n,m}	od n do m wystąpień wyrażenia r	`a{1,5}`
r{m}	dokładnie m wystąpień wyrażenia r	`a{5}`
r₁r₂	wyrażenie r₁ a następnie r₂	`ab`
r₁\|r₂	wyrażenie r₁ lub r₂	`a\|b`
(r)	wyrażenie r	`(a\|b)`
r_1/r₂	wyrażenie r₁ gdy następuje po nim r₂	`a/b`
<x> r	wyrażenie r pod warunkiem przebywania w stanie x	`<x>abc`

Przykłady:

Wyrażenie regularne	Akceptowane ciągi znaków
plex	`plex`
[0-9][^0-9]	`2a, 3%, 5m`
L(R[0-9]\|L[0-9])	`LR1, LL0`
"-"?1	`-1, 1`
0x[0-9A-F]+	`0xFF`
DD" "[0-9]{7}	`DD 3452378`

Wyrażenie regularne można zamienić na odpowiadający mu automat (i odwrotnie).

Schemat specyfikacji

Specyfikacja (program wejściowy z rozszerzeniem .l) dla programu plex ma następującą postać:

	   definicje pomocnicze
	   %%
	   reguły przetwarzania
	   %%
	   podprogramy pomocnicze

Definicje pomocnicze - umożliwiają stworzenie pomocniczych nazw dla złożonych wyrażeń regularnych używanych wielokrotnie.

Reguły przetwarzania - przyporządkowują wyrażeniom regularnym akcje w języku Pascal.

Programy pomocnicze - kod funkcji pomocniczych.

Definicje pomocnicze

Definicje pomocnicze mają postać:

         nazwa           rozwinięcie

Przykłady: 	C		[0-9]
		L		[a-zA-Z]

Nazwy są stosowane później w regułach w celach skrócenia zapisu.

Dodatkowo na początku sekcji może pojawić się kod w języku Pascal ograniczony znakami %{ oraz %}. Jest on bezpośrednio wstawiany do generowanego kodu skanera.

Przykład: 
	  %{
	  (* Przykładowa specyfikacja plexa *)
  	  uses LexLib;
	  var slowa : Integer;
	  %}

Reguły przetwarzania

Reguły przetwarzania mają postać:

wyrażenie regularne    akcja

Przykłady:	[0-9]+		return(NUMBER);

		[a-z]+		begin
				   (* po wykryciu identyfikatora 
				      składającego się z małych liter 
				      zwiększamy licznik 
				      i wypisujemy jego długość *)
				   inc(slowa);
				   writeln(yyleng);
				end;

Najprostsza akcja to akcja to ";" (instrukcja pusta).

Programy pomocnicze

Sekcja zawiera kod funkcji pomocniczych:

Przykład:
	  begin
	     (* Wywołanie funkcji skanera *)
	     yylex;
	  end.

Przykład

Poniżej przedstawiony jest specyfikacja plexa dla skanera, który analizuje strumien wejsciowy, wyszukuje ciąg znaków "flex" i zamienia go na ciąg znaków "plex" w strumieniu wyjściowym.

%{
(* Program wyszukuje ciag znakow "flex" 
   i zamienia go na na ciag znakow "plex" *)

uses LexLib;
%}

%%

flex	write('plex');

%%

begin
   yylex;  
end.

Aby wygenerować kod skanera wpisujemy:

plex zamien.l

Otrzymany w ten sposób program należy skompilować (np. przy użyciu kompilatora Free Pascal):

ppc386 -Sg zamien.pas

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

./zamien <test_zamien

W rezultacie otrzymamy:

The rules section of a plex program contains the actual specification of the lexical analyzer routine.

Źródła: zamien.l

Ćwiczenia

Ćwiczenie 1

Poniżej znajdują się specyfikacje plexa dla skanerów, które w ciągu znaków pojawiających się na wejściu wyszukuje daty w formacie dd.mm.rrrr i wypisują je na standardowe wyjście.

data1.l - wersja najprostsza
data2.l - zawiera definicje pomocnicze

Proszę obejrzeć specyfikację, wygenerować skaner i sprawdzić jego działanie. Następnie proszę obejrzeć kod skanera i odnaleźć w nim fragmenty zawarte w pliku specyfikacji.

Źródła: data1.l | data2.l | test_data

Ćwiczenie 2

Poniżej znajduje się specyfikacja plexa dla skanera, który rozpoznaje identyfikatory, liczby całkowite i liczby rzeczywiste oraz wypisuje na wyjście informacje, w której linii pliku wejsciowego się znajdują.

identyfikatory.l

Proszę obejrzeć specyfikację, wygenerować skaner i sprawdzić jego działanie przy pomocy pliku testowego np. test_identyfikatory

Źródła: identyfikatory.l

Ćwiczenie 3

Proszę wygenerować skaner, który rozpoznaje poprawne identyfikatory, liczby całkowite i liczby rzeczywiste w formacie naukowym oraz wypisuje je na wyjście.

Ćwiczenie 4

Proszę wygenerować skaner, który będzie wyrywać ciągi znaków będące rzeczywistymi datami w formacie dd.mm.rrrr (tzn. eliminowane są ciągi typu 99.99.9999).