Rozdział 10. Flex i Bison



Pobieranie 297.01 Kb.
Strona1/3
Data02.05.2016
Rozmiar297.01 Kb.
  1   2   3

Rozdział 10. Flex i Bison


Typowy program komputerowy wykonuje trzy podstawowe czynności: odczyt danych wejściowych, wykonanie jakichś działań i zapis danych wyjściowych. Aplikacje napisane w języku C wywołują wiele funkcji bibliotecznych pomocnych w realizacji tych zadań. Standardowa biblioteka funkcji wejściowo-wyjściowych (stdio) zawiera wiele funkcji znanych każdemu programiście, który posługuje się tym językiem. Są tu zawarte zarówno podstawowe funkcje obsługi wejścia i wyjścia, takie jak fread i fwrite, jak i bardziej rozbudowane procedury zapisu i odczytu liczb i napisów, takie jak printf i scanf.

Bardzo często aplikacje muszą odczytywać dane mające postać pewnych struktur, takie jak nazwiska i adresy, pliki konfiguracyjne, formuły matematyczne czy instrukcje języków programowania. Pomimo że takie dane wejściowe składają się ze znaków, liczb lub napisów, które mogą być odczytane za pomocą funkcji z biblioteki stdio, to w rzeczywistości nie ma prawdziwego wspomagania ułatwiającego odczyt złożonych struktur danych.

W tym rozdziale omówimy wejściowe struktury danych i wskażemy dwa narzędzia przydatne dla programistów używających takich złożonych danych. Pierwsze z nich powstały w latach siedemdziesiątych i były przeznaczone do budowania kompilatorów. Były to programy lex i yacc, które zyskały popularność wśród programistów piszących wszelkiego rodzaju aplikacje w języku C. Należą one obecnie do standardu POSIX dla programów pomocniczych systemu UNIX.

Różne wersje tych narzędzi (lub ich niekomercyjne odpowiedniki flex i bison) są dostępne dla systemu UNIX, a więc i dla systemu Linux. Programy te można stosować do aplikacji pisanych w innych językach, a na podkreślenie zasługuje wersja programu yacc przystosowana specjalnie do języka Perl. Prawie wszystkie dystrybucje Linuksa zawierają te narzędzia, ale często są one pomijane jako trudne do zrozumienia i wykorzystania. Rzut oka na podręcznik systemowy programu yacc nie daje ogólnego wrażenia, że jest to narzędzie łatwe do opanowania, ale jak to wkrótce zobaczymy, wrażenie może być mylące.

W pojedynczym rozdziale nie ma miejsca na omówienie wszystkich aspektów użycia tych dwóch programów. Naszym celem jest pokazanie istoty tych narzędzi i sposobu ich użycia. Jak zwykle, pełną informację można znaleźć w wielu innych miejscach, a szczególnie w zasobach Internetu (wymienionych na końcu tego rozdziału) i w dokumentacji dostarczanej razem z dystrybucją Linuksa.

Wejściowa struktura danych


Zanim przejdziemy do szczegółowych zastosowań omawianych programów, zastanówmy się najpierw, co program musi robić ze swoimi danymi wejściowymi. Skoncentrujmy się na wejściu następującego programu:

program hello(input,output);

(* A simple example program *)

const alength = 7;

bindex = 3;

var left, right: integer;

a : array[1..alength] of real'

begin

if a[bindex] > 32.613 then

begin

writeln(left:5, a[bindex]:0:2);

left = 6 + right*21

end

end.

Jako doświadczeni programiści możemy łatwo rozpoznać, że jest to program napisany w języku Pascal. Możemy nawet stwierdzić, że jest on napisany zgodnie z wszelkimi regułami tego języka (po jego uruchomieniu można się przekonać, że nie wykonuje on jednak niczego użytecznego).

Aplikacja, która musi odczytać takie wejście, będzie jednak „widzieć” je zupełnie inaczej. Na niskim poziomie program widzi tylko strumień znaków, np.:

'p' 'r' 'o' 'g' 'r' 'a' 'm' ' ' 'h' ... 'e' 'n' 'd' '.'

Ta wewnętrzna reprezentacja programu odczytywanego z wejścia nie ma żadnego odniesienia do programu w języku Pascal widzialnego oczyma programisty. Nie różni się ona niczym od innego dowolnego strumienia przypadkowych znaków. Najczęściej może to zupełnie wystarczyć. W rzeczywistości programy takie jak edytory tekstu mogą całkiem celowo traktować dane wejściowe jako strumień znaków, zakładając, że nie ma on żadnej struktury. Procesory tekstu mogą zaś te same dane traktować jako wiesze tekstu i widzieć strumień wejściowy jako sekwencję napisów, z których każdy kończy się znakiem nowego wiersza:

Wiersz[1] to "program hello(input,output);"

Wiersz[2] to ""

Wiersz[3] to "(* A simple example program *)"

i tak dalej.

Niektóre edytory używają wyróżniania składni, nadając specjalnym elementom tekstu różne atrybuty wyświetlania (np. kolorując słowa kluczowe na czerwono). Takie programy traktują dane wejściowe jako sekwencję słów kluczowych, pomiędzy którymi znajduje się inny tekst, np.:



KEY(program) "hello(input,output);"

...


KEY(if) "a[bindex] > 32.613" KEY(then)

Edytor stosujący wcięcia tekstu rozwija tę ideę jeszcze bardziej, ponieważ może przetwarzać oddzielne fragmenty danych wejściowych, pozwalając na podawanie całych bloków kodu jako jednej porcji. W takim przypadku dane wejściowe mogą być widziane jako:

...

BLOCK(

begin


if a[bindex] > 32.613 then

BLOCK(

begin


writeln(left:5, a [bindex]{10:2);

left = 6.1 + right*21

end

)

end.



)

Wreszcie kompilator języka Pascal wymaga danych prawie w takiej postaci, jak postrzega je ludzkie oko, czyli jako deklaracji i instrukcji korzystających ze stałych i zmiennych do opisu wymaganych działań:

...

ASSIGNMENT(VARIABLE("left"), EXPRESSION(ADD(NUMBER(6.1),



EXPRESSION(TIMES(VARIABLE("right"0, INTEGER(21))))))

...

Skanery i analizatory składni


Narzędzia, z którymi zapoznamy się w tym rozdziale, pozwalają programiście pisać program, który przetwarza dane wejściowe o umiarkowanie złożonej strukturze. Nawet gdy planujemy napisać własny kompilator, to istnieje wiele przykładów, w których strukturalne przetwarzanie danych wejściowych może być wielce pomocne. Przykłady te obejmują rozpoznawanie poleceń w programie, który musi współdziałać z użytkownikiem (np. jak w wierszu poleceń programu do przenoszenia plików), rozpoznawanie wyrażeń arytmetycznych w debuggerze, zapis specyfikacji układu danych na ekranie oraz sprawdzanie formatu danych (np. przy odczycie HTML).

Zadanie rozpoznawania różnych rodzajów elementów w strumieniu wejściowym nazywane jest analizą leksykalną (ang. lexical analysis). Program, który odczytuje dane wejściowe i zapewnia rozróżnianie, który składnik (zwany elementem, ang. token) został napotkany, nazywany jest analizatorem leksykalnym lub skanerem (ang. scanner). Programy takie jak lex i jego niekomercyjny odpowiednik flex są aplikacjami służącymi do tworzenia skanerów. Podaje się im opis elementów (np. słów kluczowych, liczb i znaczników), które mają być rozpoznawane, oraz trochę kodu, który ma być uruchomiony po napotkaniu takiego elementu. Następnie programy te tworzą kod służący do rozpoznawania elementów i wywołują kod, który ma być analizowany.

Drugim zadaniem jest rozpoznawanie struktury wyższego poziomu w sekwencji elementów, czyli rozpoznawanie bloków, instrukcji przypisania, wyrażeń arytmetycznych lub całej struktury HTML. Czynność ta jest nazywana rozbiorem (ang. parsing), a program, który ją realizuje — analizatorem składni (parserem). Nazwa pochodzi od rozbioru gramatycznego zdania na czasowniki, rzeczowniki, przymiotniki itd. Programy takie jak yacc i jego niekomercyjny odpowiednik bison służą właśnie do tworzenia analizatorów składni. Są one nazywane generatorami analizatorów składni (ang. parser generators)lub kompilatorami kompilatorów.

Nazwa yacc stanowi skrót od słów „Yet Another Compiler Compiler” (odzwierciedla to popularność parserów w owych czasach), zaś nazwa bison wzięła się od skojarzenia nazw dwóch zwierząt: bizona i jaka.

Jak działają generatory?


Do generatora parserów wprowadza się opis struktury, która ma być rozpoznawana (z wykorzystaniem specyficznej gramatyki) oraz kod, który ma być uruchomiony po rozpoznaniu tej struktury (zazwyczaj służący do tworzenia pewnej wewnętrznej reprezentacji danych wejściowych, np. w postaci struktury drzewa, reprezentującej całą stronę HTML lub złożone obliczenia). Generator parserów buduje następnie funkcję, która tworzy wymagane struktury z dostarczonych danych wejściowych.

Pomimo tego, że parser wymaga użycia analizatora leksykalnego na wejściu, do utworzenia takiego analizatora nie trzeba stosować programu lex lub flex. Często przy prostszych zadaniach wystarczy analizator leksykalny napisany od ręki. Trzeba jednak pamiętać, że nie jest łatwo utworzyć taki analizator, który będzie obsługiwał wszystkie kombinacje danych wejściowych. W takich przypadkach łatwiejsze będzie użycie programu flex. Dodatkowo tworzenie kodu przez flex zostało już sprawdzone przez bardzo wielu użytkowników.

Proces odczytu strukturalnych danych wejściowych można przedstawić schematycznie tak, jak na poniższych rysunkach. W przypadku odczytu zwykłego tekstu możemy mieć (dla języka polskiego):



Dla wejścia programu komputerowego możemy mieć:



Czytając dane od lewej do prawej widzimy, że surowe dane wejściowe (ang. raw input) są przekształcane na reprezentującą je strukturę. Analizator leksykalny jest odpowiedzialny za odczyt danych wejściowych najniższego poziomu, rozpoznawanie słów i ich typów. Parser rozpoznaje bardziej złożone struktury danych, takie jak zdania i instrukcje.

Teraz zajmiemy się zastosowaniem skanerów i parserów.


  1   2   3


©absta.pl 2016
wyślij wiadomość

    Strona główna