Analiza leksykalna i generatory analizatorów leksykalnych

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: Tym ostatnim zastosowaniem zajmiemy się bliżej. Najpierw jednak musimy przybliżyć pojęcie analizy leksykalnej.

Analiza leksykalna

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:

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.

Leksemy, żetony i atrybuty

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: Najlepiej powyższe pojęcia zilustrować na przykładach.

Przykład

Rozważmy instrukcję (z kompilowanego programu) postaci:

\begin{displaymath}
\mathtt{E := m * c {}^{\wedge} 2;}
\end{displaymath}

Możemy ją rozbić na następujący ciąg leksemów:

\begin{displaymath}
\mathtt{E}, \mathtt{:=}, \mathtt{m},\
\mathtt{*}, \mathtt{c}, {}^{\wedge},\
\mathtt{2}, \mathtt{;}
\end{displaymath}

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''
${}^{\wedge}$ 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

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:

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:

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.

Definicje nazwanych wzorcó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.

Specyfikacje skanerów dla Lex'a

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:

Części te są oddzielone od siebie wierszami postaci: ,,%%''.

Deklaracje programistyczne

Dowolne globalne deklaracje programistyczne można umieścić ujmując je w nawiasy %{ ...%}. Dotyczy to również dyrektyw #include.

Definicje nazwanych wzorców

Zapisane zgodnie z opisaną powyżej składnią.

Reguły rozpoznawania leksemów

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.

Dodatkowe procedury

W trzeciej części można umieścić deklaracje własnych procedur. W szczególności można tam zdefiniować procedurę main.

Rozpoznawanie leksemów

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; }
 
.|$\backslash$n      { /* Nic */ }
 
%%
 
int main() {
    int sum=0;
    
    while (yylex() == LICZBA) sum += attr; 
    printf("suma = %d$\backslash$n", 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; 
}
  
.|$\backslash$n      { return ZNAK; }
  
%%
  
int main() {
  int token;
  
  while ((token=yylex()) > 0) {
    if (token == IDENTYFIKATOR) printf("`%s'$\backslash$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.
%%
  
"/*"([${}^{\wedge}$*]|("*"+[${}^{\wedge}$*/]))*"*"*"*/"  { /* Nic */ }

   "/*"                             { printf("Nieprawidłowy komentarz."); }    %% int main() {     yylex();     return 0; }

Przykład ten znajduje się w pliku uncomment.l.

Tryby

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>(.|$\backslash$ 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.

Podsumowanie

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.

Skorowidz

Praca domowa

  1. (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.
  2. (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... 
    
    

Ćwiczenia

  1. Podaj leksemy pojawiające się w poniższych programach.
    • function abs (i : integer): integer;
      { Oblicza wartość bezwzględną i }
      begin
        if i > 0 then abs := i else abs := -i
      end;
      
      
    • int abs (i)
      int i;
      /* Oblicza wartość bezwzględną i */
      {
         return i>0?i:-i;
      }
      
      
  2. 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).
  3. Napisz specyfikację skanera, który:
    1. Usuwa białe znaki z początku/końca każdej linii. (Przeczytaj w dokumentacji Lex'a o znaczeniu ${}^{\wedge}$ i $ we wzorcach.)

      Rozwiązanie

      Przykładowe rozwiązanie znajduje się w pliku unindent.l.
      zamknij

    2. Zamienia ciąg białych znaków na jeden odstęp.

      Rozwiązanie

      Przykładowe rozwiązanie znajduje się w pliku compress-whitespace.l.
      zamknij

    3. 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
      Przykładowe rozwiązanie znajduje się w pliku capitalize.l.
      zamknij

    4. 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

      Przykładowe rozwiązanie znajduje się w pliku interpunkcja.l.
      zamknij

    5. 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

      Przykładowe rozwiązanie znajduje się w pliku uncomment2.l.
      zamknij

    6. 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