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.
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
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(
writeln(left:5, a [bindex]{10:2);
left = 6.1 + right*21
)
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))))))
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.
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.
Nie będziemy tu traktować odmiennie programów lex i flex, ponieważ flex jest bardziej ogólny niż lex i może być stosowany w systemach, w których lex nie jest zainstalowany. Oczywiście, ponieważ flex jest rozpowszechniany zgodnie z zasadami licencji BSD, dostępny jest jego kod źródłowy, można go kompilować i instalować prawie we wszystkich odmianach systemu UNIX, łącznie z Linuksem. Wchodzi on zazwyczaj do zestawu pakietów dla programistów, a więc domyślnie może nie być zainstalowany.
Warto także zapamiętać, że flex spełnia wymagania standardu POSIX znacznie lepiej niż lex.
Jeżeli trzeba utworzyć specyfikację skanerów, które będą generowane przez lex, to korzystając z programu flex można w nim ustawić tryb zgodności z programem lex, podając opcję -l przy uruchamianiu go z wiersza poleceń.
Dzięki temu mamy gwarancję, że skanery generowane za pomocą obydwóch programów są do siebie bardzo podobne. Niestety, zgodność ta jest okupiona koniecznością wyłączenia wszystkich udogodnień specyficznych dla programu flex.
W systemach Linux lex bywa czasem dołączany jako niewielki skrypt powłoki, który wywołuje flex ze wspomnianą opcją zgodności.
Skanery utworzone za pomocą programu domyślnie korzystają ze standardowego wejścia, uruchamiając każdy fragment kodu związany z elementami, których rozpoznawanie zostało zaprogramowane. Każdy znak, który nie jest częścią składową elementu, jest kopiowany na standardowe wyjście.
Oto przykład kompletnego, prostego skanera, który dokonuje korekty jednego z najczęściej spotykanych błędów pisowni, czyli błędu w nazwisku autora tej książki.
%%
Mathews printf("Matthew");
int main()
{
yylex();
return(0);
}
Zachowajmy ten plik pod nazwą matthew.l i utwórzmy skaner za pomocą podanych niżej magicznych poleceń. Wkrótce zobaczymy dokładniej, co się stanie.
$ flex matthew.l
$ gcc -o matthew lex.yy.c -lfl
Mamy więc program o nazwie matthew, który koryguje błąd pisowni. Wypróbujmy teraz jego działanie.
$ ./matthew
Dear Mr Mathews,
Dear Mr Matthew,
How is Mrs Matthew today?
^D
$
Jak widać, rozpoznany napis "Mathews" jest zamieniany na wyjściu na napis "Matthew". Dopasowanie uwzględnia wielkość liter, dlatego napisy muszą dokładnie do siebie pasować. Każdy znak, który nie pasuje do wzorca, jest bez zmian kopiowany na standardowe wyjście, więc dotyczy to także poprawnie napisanego nazwiska (jak w drugim wprowadzonym wierszu).
Skaner działa po prostu tak, że szuka na wejściu wyrażenia regularnego (podobnie jak sed lub grep). W przypadku, gdy dane wejściowe pasują do tego wyrażenia, wykonywany jest fragment kodu. Dowolne dane wejściowe nie pasujące do wyrażenia są domyślnie przekazywane na wyjście bez zmian. Dla danych wejściowych i wyjściowych używane są domyślnie strumienie stdin i stdout.
Ogólna postać specyfikacji skanera składa się z trzech części oddzielonych wierszami, które zawierają dwa znaki procentu.
Pierwsza część, pominięta w naszym przykładowym programie, zawiera definicje. Są to albo makrodefinicje programu flex, albo kod w języku C, który ma być włączony do skanera, najczęściej za pomocą dyrektywy #include; oraz deklaracje zmiennych i funkcji statycznych lub globalnych, które będą wykorzystywane w kodzie umieszczonym w części przeznaczonej na reguły.
Druga część zawiera reguły skanera i kod, który ma być wykonywany po dopasowaniu wyrażenia regularnego podanego w regule. W naszym programie następuje próba dopasowania do błędnie wpisanego nazwiska i jeśli takie dopasowanie wystąpi, wykonany będzie określony kod.
Trzecia część zawiera własny kod użytkownika, który będzie włączony bez zmian do utworzonego skanera. Ogólnie rzecz biorąc, w tej części mieści się większość naszego własnego kodu, zaś część pierwsza jest umownie zarezerwowana dla plików dołączanych i deklaracji. W naszym przykładzie zadeklarowaliśmy prostą funkcję main. Nie wykonuje ona niczego więcej oprócz wywołania utworzonej funkcji skanera, która domyślnie jest nazywana yylex.
Wygenerowany plik skanera lex.yy.c automatycznie dołącza stdio.h. W naszym przykładzie nie musimy więc tworzyć części przeznaczonej na definicje, zawierającej dyrektywę #include. Normalnie moglibyśmy to zrobić, ponieważ fragment kodu naszego skanera wywołuje printf.
Zajmijmy się teraz dokładniej tym, co się dzieje podczas generacji naszego skanera.
Najpierw uruchomiony został program flex z plikiem specyfikacji matthew.l. Program flex odczytuje reguły i generuje kod skanera, który będzie działał zgodnie z naszymi wymaganiami. Kod ten jest zapisywany do pliku nazwanego domyślnie lex.yy.c. Następnie kompilujemy ten kod i konsolidujemy go z biblioteką programu flex (opcja -lfl), zawierającą liczne funkcje wymagane przez skaner do normalnego działania.
Przy korzystaniu z programu lex zamiast z flex trzeba pamiętać, że odpowiednia biblioteka ma inną nazwę (zazwyczaj program jest konsolidowany z opcją -ll).
W kodzie C z pliku lex.yy.c jest zdefiniowana funkcja skanera. Funkcja ta (yylex) odczytuje wszystkie dane z wejścia, dopasowując je na bieżąco do wyrażenia regularnego. Nasz właściwy program (main) przejmuje kontrolę nad yylex i będzie wywoływał ten kod na żądanie. Działa to podobnie jak odwołania do funkcji wywołań zwrotnych w aplikacjach z interfejsem graficznym. Ponieważ yylex w rzeczywistości przegląda w pętli całe wejście, toteż główny program musi go wywołać tylko raz i następnie zakończyć działanie. Cały kod, który ma być uruchomiony (przy rozpoznawaniu elementów) musi być wywołany z fragmentów kodu zawartych w części z regułami.
Zajmijmy się teraz nieco bardziej skomplikowanym przykładem. Poniżej podano specyfikacje skanera rozpoznającego liczby. Obsługuje on trzy rodzaje liczb:
q liczby całkowite w postaci 123,
q liczby dziesiętne w postaci 123.456,
q liczby rzeczywiste w zapisie wykładniczym, np. 1.23e45.
Specyfikacja takiego skanera wygląda następująco:
/* Specyfikacja LEX dla liczb */
%{
#include <stdlib.h>
%}
EXP "E"|"e"
DIGIT [0-9]
DECIMAL "."
SIGN "+"|"-"
%option main
{DIGIT}+{DECIMAL}{DIGIT}*{EXP}{SIGN}?{DIGIT}+ {
printf("REAL(%s -> %g)", yytext, atof(yytext));
{DIGIT}+{DECIMAL}{DIGIT}* {
printf("DECIMAL(%s -> %g)", yytext, atof(yytext));
{DIGIT}+ {
printf("INTEGER(%s -> %d)", yytext, atoi(yytext));
Plik ten nazwiemy numbers.l. Tworzy on skaner rozpoznający liczby w żądanej postaci (całkowite, dziesiętne i w zapisie wykładniczym).
Zwróćmy uwagę na to, że w specyfikacji nie uwzględniono liczb poprzedzonych znakiem plusa lub minusa. Postąpiliśmy tak dlatego, że w pełnej aplikacji obsługującej wyrażenia arytmetyczne musimy zajmować się prostymi operatorami ...
Wolf-1