Wzorce możemy spotkać w wielu narzędziach --
wszędzie tam, gdzie chcemy wyszukiwać pewne fragmenty tekstu,
wyszukiwany fragment możemy opisać właśnie za pomocą wzorca:
- w edytorach tekstów często możemy podać nie tylko wyszukiwany
tekst, ale właśnie wzorzec,
- programy systemowe służące do wyszukiwania informacji,
np. grep, sed, czy awk,
- biblioteki programistyczne zawierające procedury rozpoznające
wystąpienia wzorców w tekście,
- generatory analizatorów leksykalnych (skanerów).
Tym ostatnim zastosowaniem zajmiemy się bliżej.
Najpierw jednak musimy przybliżyć pojęcie analizy leksykalnej.
Miejsce na analizę leksykalną jest wszędzie tam, gdzie
wczytujemy dane o określonej składni.
Wczytując takie dane, zanim będziemy mogli je przetwarzać,
musimy rozpoznać ich składnię.
Pomysł polega na tym, aby najpierw wczytywany ciąg znaków
podzielić na elementarne cegiełki składniowe --
nazywane leksemami -- a dopiero dalej analizować
ciąg leksemów.
Analizator leksykalny (nazywany też skanerem)
to wyodrębniony moduł zajmujący się tym
zadaniem.
Analiza leksykalna powstała i rozwinęła się w ramach
prac nad budową kompilatorów.
Wszak kompilator musi najpierw wczytać i zanalizować składnię
wczytywanego programu.
Jej zastosowania są jednak dużo szersze.
Praktycznie analizę leksykalną można zastosować w każdym
programie, który wczytuje dane posiadające jakąś składnię,
na przykład w:
przeglądarkach internetowych, edytorach,
systemach składu tekstu, programach konwertujących,
czy jakichkolwiek aplikacjach posiadających pliki konfiguracyjne
o określonej składni.
Czemu wyodrębniać analizę leksykalną jako osobny moduł?
Jest kilka powodów:
- uproszczenie konstrukcji programu --
łatwiej opracować osobno analizę leksykalną i resztę analizy
składniowej,
- zwiększenie przenośności --
w module analizie leksykalnej można ukryć wszystkie
szczegóły związane ze sposobem wczytywania plików,
reprezentacją znaków, itp.,
- zwiększenie efektywności --
analiza leksykalna, choć koncepcyjnie prosta,
może zajmować dużą część czasu pracy programu;
właściwe jej zaimplementowanie może poprawić efektywność
programów,
Napisanie efektywnego skanera nie jest proste.
Nie musimy jednak tego robić ręcznie.
Praktycznie dla każdego języka programowania istnieją narzędzia,
tzw. generatory analizatorów leksykalnych, które zrobią to za
nas.
Musimy im jedynie dostarczyć specyfikacji opisującej jak
wyglądają leksemy, owe elementarne cegiełki, na które chcemy
podzielić wczytywany ciąg znaków i jakie jest ich znaczenie.
W trakcie analizy leksykalnej wczytywany ciąg znaków jest
dzielony na leksemy.
Jednak to co jest przekazywane dalej, to nie są dokładnie
leksemy.
Formalnie, leksem to ciąg znaków.
To co jest przekazywane, to informacja reprezentująca
znaczenie leksemu.
Informacja ta jest reprezentowana za pomocą
tzw. żetonu i opcjonalnego atrybutu.
Żeton niesie informację o rodzaju leksemu.
Jeżeli leksemy danego rodzaju niosą ze sobą pewną ,,wartość'',
to żetonowi towarzyszy atrybut i jest on równy tej wartości.
Podsumujmy więc znaczenie tych trzech terminów:
- leksem
- to ciąg kolejnych znaków stanowiących semantycznie niepodzielną
całość,
- żeton
- (ang. token)
to stała (całkowita) reprezentująca rodzaj wczytanego leksemu,
- atrybut
- to opcjonalna wartość reprezentująca znaczenie leksemu.
Typowe leksemy, to:
- identyfikatory,
- słowa kluczowe,
- napisy,
- liczby całkowite i rzeczywiste,
- operacje arytmetyczne i relacje,
- nawiasy i innego rodzaju znaki ,,interpunkcyjne''.
Najlepiej powyższe pojęcia zilustrować na przykładach.
Przykład
Rozważmy instrukcję (z kompilowanego programu) postaci:
Możemy ją rozbić na następujący ciąg leksemów:
Natomiast ich reprezentacja za pomocą żetonów i atrybutów
będzie następująca:
Leksem |
Żeton |
Atrybut |
E |
identyfikator |
,,E'' |
:= |
przypisanie |
|
m |
identyfikator |
,,m'' |
* |
mnożenie |
|
c |
identyfikator |
,,c'' |
|
potęgowanie |
|
2 |
liczba całkowita |
2 |
; |
średnik |
|
Przykład
Rozważmy fragment źródeł HTML:
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-2">
<title>PJWSTK - JFA</title>
Jak ten fragment należy podzielić na leksemy?
Pamiętajmy, że leksemy muszą być niepodzielne semantycznie.
Oto jeden z możliwych podziałów:
|
Leksem |
Żeton |
Atrybut |
|
|
<head |
open-start-tag |
,,head'' |
|
|
> |
close-tag |
|
|
|
<meta |
open-start-tag |
,,meta'' |
|
|
http-equiv |
identyfikator |
,,http-equiv'' |
|
|
= |
równość |
|
|
|
"Content-Type" |
napis |
,,Content-Type |
|
|
content |
identyfikator |
,,content'' |
|
|
= |
równość |
|
|
|
"text/html; charset=iso-8859-2" |
napis |
,,text/html; charset=iso-8859-2'' |
|
|
> |
close-tag |
|
|
|
<title |
open-start-tag |
,,title'' |
|
|
> |
close-tag |
|
|
|
PJWSTK - JFA |
text |
,,PJWSTK - JFA'' |
|
|
</title |
open-end-tag |
,,title'' |
|
|
> |
close-tag |
|
|
Jak widać z powyższych przykładów, typowe atrybuty leksemów to
- identyfikator -- nazwa identyfikatora
(jeśli nie odróżnia się małych i wielkich liter, to
w znormalizowanej postaci, np. pisana samymi wielkimi literami),
- napis -- treść napisu,
- liczba -- jej wartość,
Pisząc specyfikację dla Lex'a musimy dla każdego żetonu
opisać jaką postać mogą mieć leksemy odpowiadające temu
żetonowi.
Robimy to podając dla każdego żetonu wzorzec.
Następnie dla każdego żetonu podajemy fragment kodu, który na
podstawie leksemu oblicza wartość atrybutu.
Przykład
Oto kilka przykładów żetonów i wzorców opisujących
odpowiadające im leksemy:
Żeton |
Przykład leksemu |
Wzorzec |
sł_klucz_if |
if |
if |
identyfikator (złożony tylko z liter) |
Pom |
[a-zA-Z]+ |
liczba_całkowita |
-42 |
-?[0-9]+ |
Projektując podział wejścia na leksemy i dobierając żetony
powinniśmy kierować się następującymi zasadami:
- Leksemy powinny być niepodzielne semantycznie.
- Leksemom, które mają tego samego rodzaju semantykę powinien
odpowiadać ten sam żeton.
- Leksemy odpowiadające jednemu żetonowi powinno się dać
opisać wzorcem.
Skaner jest zwykle zrealizowany w postaci modułu,
który udostępnia procedurę ,,daj kolejny leksem''.
Procedura ta rozpoznaje jeden leksem i zwraca odpowiadający mu
żeton i atrybut.
Można więc powiedzieć, że skaner przetwarza strumień znaków w
strumień par: żeton, atrybut.
Proste atrybuty, takie jak liczby, są przekazywane wprost.
Bardziej złożone atrybuty, takie jak nazwy
identyfikatorów, mogą być przez skaner umieszczane w specjalnym
słowniku, nazywanym tablicą symboli.
Wówczas jako atrybut przekazywany jest wskaźnik lub pozycja w
tablicy symboli.
Z jednej strony, dzięki temu oszczędzamy na pamięci.
Z drugiej strony, sama pozycja w tablicy symboli jest
wystarczająca, gdyż zwykle nie jest istotne, jak się dany
identyfikator nazywa, tylko który z identyfikatorów to jest.
Generator analizatorów leksykalnych Lex
Generator analizatorów leksykalnych na podstawie specyfikacji skanera sam generuje jego kod.
Jest wiele różnych generatorów analizatorów leksykalnych, różnego pochodzenia i przeznaczonych dla różnych języków programowania.
Na wykładzie skupimy się na generatorze Flex/Lex przeznaczonym dla C/C++.
Nazwa [F]lex to skrót od [Fast] LEXical analyzer generator.
Specyfikacja taka zawiera z jednej strony opis składni
leksemów różnych rodzajów, a z drugiej zawiera fragmenty
kodu, które mają być wykonane w przypadku napotkania
leksemu określonego rodzaju.
Dla każdego rodzaju leksemów (tj. dla każdego żetonu)
specyfikacja skanera zawiera:
- wzorzec opisujący postać leksemów (danego rodzaju),
- fragment kodu wykonywany w momencie napotkania leksemu
danego rodzaju.
Fragmenty kodu wykonywane w momencie rozpoznania leksemu
mają oczywiście dostęp do słowa (napisu) stanowiącego
rozpoznany leksem.
Ich głównym zadaniem jest przekazanie żetonu i obliczenie ew.
atrybutu.
Jednak z punktu widzenia Lex'a mogą one robić cokolwiek.
Jeżeli np. naszym zadaniem jest przetłumaczenie jednej postaci
danych na inną, takie fragmenty mogą wypisywać przetłumaczone
odpowiedniki wczytanych leksemów.
W specyfikacji dla Lex'a zwykle pewne wzorce pojawiają się
wielokrotnie.
Żeby nie powtarzać ich, wprowadzono możliwość definiowania
pomocniczych nazwanych wzorców.
Definicje takie mają postać:
nazwa wzorzec
Od momentu zdefiniowania nazwanego wzorca, można się do
niego odwoływać w innych wzorcach poprzez:
{nazwa}.
W definicjach nazwanych wzorców można się odwoływać do
nazwanych wzorców zdefiniowanych wcześniej, ale tylko
wcześniej -- tym samym definicje wzorców nie mogą być
rekurencyjne.
Przykład
cyfra [0-9]
cyfry {cyfra}+
cz_ułamkowa "."{cyfry}
znak_opc ("+"|"-")?
wykładnik_opc (E{znak_opc}{cyfry})?
liczba {znak_opc}({cyfry}{cz_ułamkowa}|{cyfry}|{cz_ułamkowa}){wykładnik_opc}
Definicje nazwanych wzorców pozwalają w zwięzły sposób
powiązać nazwy z określonymi wzorcami.
Nie wnoszą one jednak nic do siły wyrazu wzorców.
Definicji nazwanych wzorców można się zawsze pozbyć rozwijając
wszystkie definicje.
Język specyfikacji dla Lex'a zawiera mnóstwo
szczegółów, których nie będziemy tutaj omawiać.
W tej chwili naszym zadaniem jest wprowadzenie
Czytelnika w typowy sposób wykorzystania Lex'a.
Gdy zawarte tu informacje okażą się niewystarczające,
odsyłamy Czytelnika do dokumentacji generatora skanerów
(man lex).
Specyfikacja dla Lex'a składa się z trzech części:
- deklaracji programistycznych (stałych i zmiennych), oraz
definicji regularnych,
- reguł rozpoznawania leksemów,
- dodatkowych procedur zdefiniowanych przez użytkownika.
Części te są oddzielone od siebie wierszami postaci: ,,%%''.
Dowolne globalne deklaracje programistyczne można umieścić
ujmując je w nawiasy %{ ...%}.
Dotyczy to również dyrektyw #include.
Zapisane zgodnie z opisaną powyżej składnią.
Reguły rozpoznawania leksemów mają postać:
wzorzec fragment kodu
Jeżeli fragment kodu jest dłuższy niż jedna instrukcja, to
musi być ujęty w nawiasy { ...}).
Wzorzec musi zaczynać się na początku wiersza i nie może
zawierać żadnych (nie ujętych w cudzysłowy) odstępów.
W trzeciej części można umieścić deklaracje własnych procedur.
W szczególności można tam zdefiniować procedurę
main.
Zanim zobaczymy przykłady specyfikacji, musimy zrozumieć,
jak działają wygenerowane przez Lex'a skanery.
Skaner udostępnia funkcję (int yylex()) służącą do wczytania
jednego leksemu.
Jeżeli plik został wczytany, to yylex zwraca 0.
Wpp. stara się dopasować pewien fragment początkowy wejścia
do jednego z podanych wzorców, wg. następujących zasad:
Przykład
Oto specyfikacja skanera, który każdy napis ,,
FOO''
zamienia na ,,
Foo'', ,,
BAR'' na
,,
Bar'' i ,,
FOOBAR'' na
,,
Foobar''.
Wszystko inne jest przepisywane z wejścia na wyjście bez
zmian.
%{
#include <stdio.h>
%}
%%
FOO printf("Foo");
BAR printf("Bar");
FOOBAR printf("Foobar");
%%
int main() {
yylex();
return 0;
}
Przykład ten znajduje się w pliku
foobar.l.
Przykład
Oto specyfikacja skanera, który wyszukuje w wejściu liczby
zmiennopozycyjne i wypisuje je.
Wszystko inne jest ignorowane.
%{
#include <stdio.h>
%}
cyfra [0-9]
cyfry {cyfra}+
cz_ułamkowa "."{cyfry}
znak_opc ("+"|"-")?
wykładnik_opc ((e|E){znak_opc}{cyfry})?
liczba {znak_opc}({cyfry}{cz_ułamkowa}|{cyfry}"."?|{cz_ułamkowa}){wykładnik_opc}
%%
{liczba} { printf(" %g ", atof(yytext)); }
. { /* nic */ }
%%
int main() {
yylex();
return 0;
}
Przykład ten znajduje się w pliku
liczby.l.
W powyższych przykładach nie używaliśmy żetonów ani atrybutów.
Jedno wywołanie funkcji yylex przetwarzało całe
wejście.
Poniższy przykład ilustruje wykorzystanie żetonów i
atrybutów.
Przykład
Oto specyfikacja prostego skanera, który sumuje wszystkie liczby
całkowite znajdujące się na wejściu, pomijając wszystko
inne.
%{
#include <stdio.h>
#define LICZBA 1
int attr;
%}
INTEGER -?[0-9]+
%%
{INTEGER} { attr = atoi(yytext);
return LICZBA; }
.|n { /* Nic */ }
%%
int main() {
int sum=0;
while (yylex() == LICZBA) sum += attr;
printf("suma = %dn", sum);
return 0;
}
Przykład ten znajduje się w pliku
sum.l.
Przykład
Kolejny przykład pokazuje jak przekazywać inne atrybuty niż liczby całkowite.
Poniższy skaner wychwytuje wszystkie identyfikatory i przekazuje ich nazwy jako atrybuty.
%{
#include <stdio.h>
#include <string.h>
#define IDENTYFIKATOR 6942
#define ZNAK 1234
char* attr;
%}
IDENT [a-zA-Z][a-zA-Z0-9_]*
%%
{IDENT} {
attr = malloc (yyleng+1);
strcpy(attr, yytext);
return IDENTYFIKATOR;
}
.|n { return ZNAK; }
%%
int main() {
int token;
while ((token=yylex()) > 0) {
if (token == IDENTYFIKATOR) printf("`%s'n", attr);
};
return 0;
}
Przykład ten znajduje się w pliku identyfikatory.l.
Przykład
Następująca specyfikacja opisuje skaner, który usuwa
komentarze postaci
/* ...*/.
Uwaga: nie uwzględnia ona innych rodzajów komentarzy, ani
napisów.
%%
"/*"([*]|("*"+[*/]))*"*"*"*/" { /* Nic */ }
"/*" { printf("Nieprawidłowy komentarz."); }
%%
int main() {
yylex();
return 0;
}
Przykład ten znajduje się w pliku
uncomment.l.
Domyślnie, analizator leksykalny dopasowuje standardowe wejście do wszystkich wzorców reguł podanych w specyfikacji.
Można jednak określić kilka trybów działania skanera i w określonym trybie dopasowywać wzorce
tylko określonych reguł.
Tryby deklarujemy w pierwszej części specyfikacji, zaczynając wiersz od %s lub %x
i wymieniając dalej nazwy trybów.
Jeżeli tryb został zadeklarowany za pomocą %s to obejmuje dodatkowo reguły bez określonego trybu,
a jeśli został zadeklarowany za pomocą %x to ich nie obejmuje.
Jeżeli chcemy, żeby dany wzorzec był dopasowywany tylko w określonym trybie, to
dodajemy przed nim nazwy tych trybów ujęte w trójkątne nawiasy <...> i pooddzielane przecinkami.
Tryb możemy zmieniać za pomocą polecenia BEGIN(tryb).
Tryb, w którym skaner pracuje w momencie uruchomienia i który obejmuje wszystkie reguły bez podanego trybu,
nazywa się INITIAL.
Możliwe jest też sprawdzenie w jakim trybie jesteśmy.
Aktualny tryb jest pamiętany na zmiennej YY_START.
Przykład
Używając trybów możemy napisać dużo prościej skaner usuwający komentarze postaci
/* ...*/.
Wystarczy, że wprowadzimy dodatkowy tryb
KOMENTARZ, w którym będziemy analizować treść komentarzy.
%x KOMENTARZ
%%
"/*" { BEGIN(KOMENTARZ); }
<KOMENTARZ>"*/" { BEGIN(INITIAL); }
<KOMENTARZ>(.| n) { /* Nic */ }
%%
int main() {
yylex();
if (YY_START == KOMENTARZ) printf("Nieprawidłowy komentarz.");
return 0;
}
Przykład ten znajduje się w pliku
uncomment-start.l.
Kompilacja programów generowanych przez Flex'a
Zodnie z przyjętą konwencją, specyfikacje dla Flex'a to pliki z rozszerzeniem .l.
Załóżmy, że w pliku spec.l znajduje się taka specyfikacja.
Najprostsze wywołanie Flex'a wygląda tak:
flex spec.l
W jego wyniku Flex tworzy plik lex.yy.c z kodem źródłowym skanera.
Możemy oczywiście określić (za pomocą opcji -o) inną nazwę pliku z kodem źródłowym,
na przykład polecenie:
flex -ospec.yy.c spec.l
spowoduje umieszczenie kodu źródłowego skanera w pliku spec.yy.c.
Tak wygenerowany kod korzysta ze standardowej biblioteki o nazwie fl.
Można go skompilować za pomocą polecenia postaci: gcc ...spec.yy.c -lfl.
Wykład ten wyjaśnia czym jest analiza leksykalna i
generatory analizatorów leksykalnych, takie jak Lex.
Pokazuje też jak pisać specyfikacje analizatorów leksykalnych
dla Lex'a.
Umiejętność korzystania z Lex'a będzie jeszcze przedmiotem
ćwiczeń laboratoryjnych.
- (3p.)
Dla następującego fragmentu pliku ini:
[main]
version=3.0.0.9
LinuxDesktop=0
OpenFileCMD=kfmclient exec
IndiPanelCmd=cd /usr/local/dcd ; python ./dcd.py
[catalog]
starcatpath=/usr/share/apps/skychart/cat/bsc5
StarmagMax=10
NebmagMax=14
podaj:
- jak byś go podzielił na leksemy,
- jakie żetony byś wyodrębnił
- jakie atrybuty będą towarzyszyć leksemom.
- (7p.)
Znaki interpunkcyjne, to: kropka, przecinek, znak zapytania, wykrzyknik i średnik.
Napisz specyfikację skanera, który usuwa wszelkie białe znaki poprzedzające znaki interpunkcyjne.
Inne znaki powinny być wypisywane bez zmian.
Na przykład, tekst:
Ala ma kota ,psa i kanarka
, chyba . . .
powinien zostać zamieniony na:
Ala ma kota,psa i kanarka, chyba...
- Podaj leksemy pojawiające się w poniższych programach.
- Podaj wyrażenia wzorce opisujące następujące leksemy:
- numery rejestracyjne samochodów (takie rodzaje, jakie znasz),
- identyfikatory (w Twoim ulubionym języku programowania),
- napisy (w Twoim ulubionym języku programowania)
wraz z możliwością umieszczania
ogranicznika napisu w napisie,
- komentarze (w Twoim ulubionym języku programowania).
- Napisz specyfikację skanera, który:
- Usuwa białe znaki z początku/końca każdej linii.
(Przeczytaj w dokumentacji Lex'a o znaczeniu
i $ we wzorcach.)
Rozwiązanie
- Zamienia ciąg białych znaków na jeden odstęp.
Rozwiązanie
- Zamienia wszystkie słowa tak, że są pisane z wielkiej litery, ale pozostałe litery są małe.
Wszystkie inne znaki, powinny być wypisywane bez zmian.
Rozwiązanie
- Wstawia odstęp po każdej kropce i przecinku, chyba
że taki odstęp już tam jest.
(Przeczytaj w dokumentacji Lex'a o znaczeniu wzorców postaci r/s.)
Rozwiązanie
- Usuwa komentarze typu // z programu w C/C++.
(Ignorujemy problemy z komentarzami postaci
/*...//...*/):
- nie uwzględniając stałych napisowych,
- uwzględniając je.
Rozwiązanie
- Zamienia pierwszą literę w każdym zdaniu na wielką, a pozostałe na małe.
(Zdanie, to dowolny ciąg znaków zakończony kropką.
Inne znaki niż litery powinny być wypisywane bez zmian.)
Rozwiązanie
Przykładowe rozwiązanie znajduje się w pliku
capitalize-sentence.l.
Wstawka w kodzie zamieniająca litery odpowiednio na wielkie i małe może wyglądać rozmaicie.
zamknij