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 znalez
ć 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.
Skanery
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 z
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.
Prosty skaner
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?
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.
Specyfikacje skanera
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:
liczby całkowite w postaci 123,
liczby dziesiętne w postaci 123.456,
liczby rzeczywiste w zapisie wykładniczym, np. 1.23e45.
Specyfikacja takiego skanera wygląda następująco:
/* Specyfikacja LEX dla liczb */
%{
#include
%}
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 + i - w pewien spójny sposób.
Wprowadziliśmy tu kilka nowości, które będziemy po kolei omawiać.
W plikach specyfikacji programu lex można używać komentarzy zgodnie z konwencją stosowaną
w języku C, tak jak to widać w naszym przykładzie:
/* Specyfikacja LEX dla liczb */
W części definicyjnej dodano kilka poleceń języka C, które zostaną dołączone na początku kodu
wygenerowanego przez skaner. Dowolny tekst, który flex wykryje między  dekoracyjnymi
nawiasami %{ i %}, jest kopiowany do skanera bez zmian. W naszym przykładzie jest to kod
dołączający standardowy plik nagłówkowy stdlib.h, który zawiera deklaracje funkcji atof i
atoi, wymaganych w dalszej części kodu.
Pozostałe definicje oznaczają nazwy pewnych wyrażeń regularnych, które będą użyte jako część
specyfikacji naszego skanera. Format wyrażeń regularnych powinien być znany w szczególności
tym osobom, które używają programów sed lub egrep. Wyrażenie EXP jest zdefiniowane tak,
aby pasowało do małej lub wielkiej litery E:
EXP "E"|"e"
Wyrażenie DIGIT pasuje do dowolnej cyfry dziesiętnej z zakresu od zera do dziewięciu:
DIGIT [0-9]
Wyrażenie DECIMAL pasuje do kropki dziesiętnej w liczbie zmiennoprzecinkowej:
DECIMAL "."
Wyrażenie SIGN pasuje do znaku plusa lub minusa:
SIGN "+"|"-"
Do zasad tworzenia wyrażeń regularnych powrócimy już niedługo.
W części zawierającej reguły zdefiniowaliśmy trzy rodzaje liczb, które mają być rozpoznawane.
Pierwszy z nich opisuje liczby zawierające kropkę dziesiętną i wykładnik, a odpowiadające mu
wyrażenie regularne ma postać:
{DIGIT}+{DECIMAL}{DIGIT}*{EXP}{SIGN}?{DIGIT}+
Należy to rozumieć następująco:
 jedna lub więcej cyfr, za którymi następuje
kropka dziesiętna, za którą następuje
zero lub więcej dalszych cyfr, za którymi następuje
oznaczenie wykładnika, za którym następuje
opcjonalny znak, za którym następuje
jedna lub więcej dalszych cyfr .
Operatory +, * oraz ? informują, że elementy liczby są opcjonalne i mogą występować
kilkakrotnie. Omówimy to ponownie za chwilę. Oczekujemy, że podane wyrażenie będzie
pasować do liczb o następującej postaci:
12.34E3
1.e-04
Zwróćmy uwagę na to, że w naszym przykładzie nie posługujemy się liczbami zawierającymi
wykładnik, lecz nie zawierającymi kropki dziesiętnej. Nie uwzględniamy także znaku plusa lub
minusa na początku liczby.
Jako druga liczba, którą chcemy rozpoznawać, występuje liczba zmiennoprzecinkowa zapisana
bez użycia wykładnika. Mamy w tym przypadku uproszczoną wersję pierwszej reguły:
{DIGIT}+{DECIMAL}{DIGIT}*
Należy to rozumieć następująco:
 jedna lub więcej cyfr, za którymi następuje
kropka dziesiętna, za którą następuje
zero lub więcej dalszych cyfr .
Oczekujemy więc, że ta reguła będzie pasować do liczb takich, jak:
0.645
768.
Trzecią postacią rozpoznawanej liczby jest liczba całkowita, czyli prosty przypadek  jedna lub
więcej cyfr . Trzecia reguła ma więc postać:
{DIGIT}+
Oczekujemy więc, że ta reguła będzie pasować do liczb takich jak:
456
1
W naszej specyfikacji użyliśmy rozszerzeń standardu POSIX wprowadzonych w programie flex,
czyli deklaracji %option. Służy ona jako pomoc dla programu przy generacji skanera. Opcje
użyte w naszym przykładzie są następujące:
%option main
Taka deklaracja powoduje, że flex generuje automatycznie funkcję main, więc można ją
pominąć w części przeznaczonej na kod własny użytkownika. Utworzona w taki sposób funkcja
main realizuje dokładnie to, co pokazaliśmy w pierwszym przykładzie, czyli wywołanie yylex i
powrót. Jeżeli jednak ważna jest przenośność kodu, to należy unikać stosowania deklaracji
%option.
W części specyfikacji skanera zawierającej reguły definiujemy oddzielnie kilka reguł. Każda z
nich ma następującą postać ogólną:
expression code-fragment
Wyrażenie expression jest po prostu wyrażeniem regularnym, które chcemy dopasowywać.
Musi się ono rozpoczynać od początku wiersza. Związany z nim fragment kodu musi być
poprawny w sensie języka C i musi się rozpoczynać w tym samym wierszu, co wyrażenie
regularne (dalej mogą występować wiersze kontynuacyjne, pod warunkiem zamknięcia ich w
nawiasy klamrowe, tak jak w naszym przykładzie).
Fragment kodu C może być pominięty i w takim przypadku dane wejściowe pasujące do
wyrażenia regularnego są po prostu usuwane. Właściwość ta jest często używana do usuwania
pustych wierszy lub spacji z ciągu danych wejściowych. Zapoznamy się z nią w dalszych
przykładach.
Fragmenty kodu C są wykonywane po dopasowaniu wyrażenia regularnego do danych
wejściowych. Posługujemy się tu jedną zmienną występującą zarówno w programie flex, jak i
lex. Ma ona nazwę yytext i jest tablicą znakową zakończoną wartością NULL. Służy ona do
przechowywania danych wejściowych, które zostały dopasowane do wyrażenia regularnego. W
naszym przypadku pobieramy z niej wartości liczb za pomocą funkcji atof lub atoi, zależnie od
dopasowanego wyrażenia regularnego.
Należy zapamiętać, że zmienna yytext nie może być trwale zapamiętana, ponieważ zmienia się
ona przy każdym wykonaniu fragmentu kodu. Zazwyczaj odnosimy się do niej za pomocą
wskaz
nika do wnętrza bufora wejściowego, który jest ciągle modyfikowany w procesie
skanowania. Jeżeli wymagane jest zapamiętanie danych wejściowych dla danego dopasowania, to
należy utworzyć kopię yytext i zachować ją w dowolnie wybranym miejscu.
Skompilujemy i uruchomimy teraz nasz skaner:
$ flex numbers.l
$ cc -o numbers lex.yy.c
$ ./numbers
12.34e3
REAL(12.34e3 -> 12340)
1.e-04
REAL(1.e-04 -> 0.0001)
0.645
DECIMAL(0.645 -> 0.645)
768.
DECIMAL(768. -> 768)
456
INTEGER(456 -> 456)
1
INTEGER(1 -> 1)
ABC123DEF
ABCINTEGER(123 -> 123)DEF
^D
$
Podobnie jak poprzednio, niedopasowane dane wejściowe są kopiowane na standardowe wyjście.
Zasada najpełniejszego dopasowania
Prawdopodobnie każdy już zauważył, że specyfikacja liczb w definicji naszego skanera może być
zupełnie dowolna. Jeżeli na wejście zostanie podany ciąg "123.34E67", to mógłby on być
interpretowany jako liczba całkowita (123) pasująca do trzeciej reguły, za którą występują jakieś
znaki. Dzięki czemu flex ma wiedzieć, że jest to liczba rzeczywista i tak ją należy traktować?
Skanery utworzone za pomocą programów lex i flex próbują dopasować możliwie najdłuższy
ciąg wejściowy. Próby dopasowania odbywają się dla wszystkich reguł aż do chwili, gdy zostanie
stwierdzony brak dopasowania. Napotkawszy więc na długi ciąg cyfr, skaner zaczyna je
gromadzić w zmiennej yytext, aż wszystkie możliwe dopasowania zakończą się niepomyślnym
wynikiem. Mając więc ciąg "123", nie otrzymujemy sekwencji trzech jednocyfrowych liczb
całkowitych, lecz jedną liczbę trzycyfrową. Podobne zasady obowiązują dla liczb
zmiennoprzecinkowych.
Skaner nie będzie się specjalnie nastawiał na proste liczby dziesiętne. Będzie on oczekiwał na
nadejście wykładnika i próbował dopasować się do liczby zmiennoprzecinkowej o takiej postaci.
Jeżeli to się nie uda, zwróci dopasowanie do prostej liczby dziesiętnej występującej przed chwilą
na wejściu. Oto przykład:
$ ./numbers
123.45E*12
DECIMAL(123.45 -> 123.45)E*INTEGER(12 -> 12)
W tym przypadku skaner próbuje znalez
ć dopasowanie do liczby zmiennoprzecinkowej w zapisie
wykładniczym, ale znaki za literą E nie pasują do definicji. Zamiast tego zostanie więc znalezione
dopasowanie do liczby dziesiętnej (123.45), za którą występują znaki E i *, a dalej nastąpi
ponowne dopasowanie do liczby całkowitej utworzonej przez pozostałe cyfry.
Trzeba zrozumieć, że flex stosuje zasadę najpełniejszego dopasowania (ang. longest possible
match principle) w celu uniknięcia dowolności w regułach podanych w specyfikacji (taka
dowolność może mieć nieprzewidywalne skutki, szczególnie w programach korzystających z
wiersza poleceń). Przykładowo: jeżeli zezwala się na podawanie na wejściu kilku wierszy i mamy
kilka opcjonalnych elementów dołączanych na końcu poleceń, to flex kontynuuje odczyt aż do
momentu stwierdzenia z całą pewnością, że nic już na wejściu się nie pojawi. Coś takiego nie
występuje, chyba że zostanie wykryty początek następnego polecenia. Aby nie dopuścić do takich
niejasnych sytuacji, należy wszystkie polecenia kończyć znakiem nowego wiersza lub kropką.
Pomimo tego, że przy pisaniu naszych reguł stosowaliśmy zasadę  najdłuższa reguła na
początku , nie musimy się zbytnio obawiać kłopotów z początkowymi fragmentami napisów
pojawiających się na wejściu i pasujących do więcej niż jednej reguły. Efektywnie utworzony
skaner dopasowuje wszystkie reguły od razu, automatycznie korzystając z zasady najpełniejszego
dopasowania przy określeniu, która reguła jest spełniona. Człowiek wymaga jednak czasem
pomocy przy czytaniu specyfikacji skanera, warto więc wyróżnić w niej pewne struktury,
ustawiając na początku najdłuższą regułę. Dzięki temu czytelnik może interpretować specyfikację
zgodnie z następującym tokiem myślenia:
Zapis liczby zawiera cyfry, kropkę dziesiętną i wykładnik.
Jeśli powyższe nie jest prawdą, to zapis liczby może składać się z cyfr i kropki
dziesiętnej.
Jeżeli powyższe nie jest prawdą, to zapis liczby składa się tylko z cyfr.
Jeżeli zdarzy się, że spełnione są dwie reguły dla ciągu wejściowego o tej samej długości, to flex
stwierdzi dopasowanie do reguły występującej jako pierwsza w specyfikacji.
Wyrażenia regularne
Każdy, kto używał programów grep, sed, awk lub perl, jest zaznajomiony z wyrażeniami
regularnymi (ang. regular expressions). Jeśli tak nie jest, wystarczy świadomość tego, że
zapewniają one sposób opisu ciągów znakowych za pomocą ich elementów składowych, czyli np.
mówimy o trzech znakach  a za którymi opcjonalnie występuje znak  b . Wyrażenia regularne
są stosowane w programie emacs przy przeszukiwaniu plików, zaś w naszym przypadku stosuje
się je do określania elementów rozpoznawanych w strumieniach wejściowych.
Wyrażenie regularne Znaczenie
a
Literalny znak a (oprócz znaków specjalnych opisanych niżej)
[abc]
Jeden ze znaków a, b lub c.
[a-z]
Jeden ze znaków od a do z.
[^x]
Dowolny znak oprócz x, które może być pojedynczym znakiem
lub grupą znaków.
"xyz"
Pasuje do dosłownie podanego ciągu znaków x, y i z.
\
Znak specjalny, taki jak w języku C, który pasuje do znaków
sterujących na wejściu. może być na przykład jednym
ze znaków a, b, f, n, r, t lub v, \n pasuje do znaku nowego
wiersza, a \t pasuje do znaku tabulacji.
\0
Znak NULL (zerowy kod ASCII) .
\123
Znak o kodzie ASCII w zapisie ósemkowym 0123.
\x12
Znak o kodzie ASCII w zapisie szesnastkowym 0x12.
.
Dowolny znak.
Pokazane tu klasy znaków mogą być ze sobą łączone. Przykładowo: [^a-z] pasuje do każdego
znaku nie zawierającego się w przedziale od a do z, zaś [i-kx-zA] pasuje do znaków i, j, k, x,
z oraz A.
Program flex udostępnia pewne skróty dla oznaczania powszechnie używanych klas znaków,
łącznie ze znakami alfanumerycznymi i spacjami rozdzielającymi (ang. whitespace). Są one
specjalnie oznaczane za pomocą [: oraz :] i muszą występować wewnątrz normalnej klasy
znaków oznaczonej nawiasami kwadratowymi. Są to klasy o oznaczeniach [:alnum:],
[:alpha:] oraz [:xdigit:]. Ogólnie rzecz biorąc, są to klasy zdefiniowane dla każdej funkcji
is w standardowym języku C w pliku ctype.h. Klasa [:alnum:] reprezentuje więc
jeden ze znaków, dla których funkcja isalnum zwraca wartość prawdziwą. Lista klas
obsługiwanych przez flex jest następująca:
alnum alpha blank cntrl digit graph
lower print punct space upper xdigit
Reguła dla wykrywania cyfr może być zatem zapisana jako:
DIGIT [[:digit:]]
A
ączenie wyrażeń regularnych
Załóżmy, że re reprezentuje jakieś wyrażenie regularne. Za pomocą dodatkowych operatorów
pokazanych w poniższej tabeli można tworzyć bardziej skomplikowane wyrażenia:
re*
Zero lub więcej wystąpień określonych przez re.
re+
Jedno lub więcej wystąpień re.
re?
Zero lub jedno wystąpienie re.
re{N}
Dokładnie N egzemplarzy re.
re{N,}
Co najmniej N egzemplarzy re.
re{N,M}
Od N do M (włącznie) egzemplarzy re.
{name}
Pasuje do wyrażenia regularnego o nazwie "name" nadanej w specyfikacji
skanera w części zawierającej definicje.
(re)
Pasuje do egzemplarza re, zaś nawiasów użyto w celu wymuszenia
pierwszeństwa, co jest ważne zwłaszcza gdy używamy wyrażeń opcjonalnych.
re1re2
Pasuje do egzemplarza re1, po którym następuje egzemplarz re2.
re1|re2
Pasuje albo do re1, albo do re2.
re1/re2
Pasuje do re1 tylko wtedy, gdy następuje po nim re2 (które samo w sobie nie
j t bj t d i )
jest objęte dopasowaniem).
^re
Pasuje do tylko egzemplarza re pojawiającego się na początku wiersza.
re$
Pasuje do egzemplarza re pojawiającego się na końcu wiersza.
Powyższe operatory stosowane w łączeniu wyrażeń regularnych podano zgodnie z ich
pierwszeństwem. W celu wymuszenia zmiany tego pierwszeństwa można zastosować nawiasy,
które zmienią porządek dopasowywania tak samo jak w wyrażeniach arytmetycznych.
Istnieje także kilka rzadko używanych metod łączenia wyrażeń regularnych, które są omówione w
podręczniku systemowym dla programu flex.
We wzorcach dopasowania dla reguł nie wolno wstawiać spacji rozdzielających poszczególne
składniki wyrażenia, ponieważ flex potraktuje to jako koniec wyrażenia i początek kodu, który
ma być uruchamiany.
Jako przykład efektywności działania klas znaków i wyrażeń regularnych podajemy dwa
przykłady wzięte z kodu z
ródłowego programu szachowego xboard. Program obsługuje dwóch
graczy i interpretuje wpisywane przez nich ruchy:
[RrBbNnQqKkPp]{/]?[a-h][1-8][xX:-]?[a-h][1-8](=?\(?RrBbNnQqKk]\)?)? {
/*
* Fully-qualified algebraic move, possibly with promotion
*/
...
}
oraz
(([Ww](hite)?)|([Bb](lack)?))" "(([Rr]esign)|([Ff]orfeit))(s|ed)? {
return (int) (ToUpper(yytext[0]) == 'W' ? BlackWins : WhiteWins);
}
Pierwsze wyrażenie pasuje do ruchów zapisanych jako np. N/g1-f3 i Ph7-h8=Q. Drugie
wyrażenie pasuje do komunikatów na zakończenie gry (np.  White Resigns lub  black
forfeit ).
Działania
Pokazaliśmy już kilka przykładów działań podejmowanych w wyniku dopasowania wyrażenia do
danych wejściowych. Aby ułatwić obsługę codziennych zadań, w programie flex zdefiniowano
kilka makropoleceń i zmiennych, które mogą być używane we fragmentach kodu związanych z
dopasowaniem danych:
yytext[]
Tablica znakowa zawierająca tekst, który pasował do wyrażenia.
yyleng
Długość ciągu przechowywanego w yytext.
YYLMAX
Makrodefinicja, która określa dopuszczalną długość yytext. Jest ona
ustawiana dość rozsądnie na dużą wartość. Ponieważ wpływa ona na
maksymalny rozmiar elementu, który może być otrzymany w naszym
skanerze, można ją zmienić za pomocą deklaracji #define w części
definicyjnej specyfikacji.
ECHO;
Kopiuje bieżącą zawartość yytext na wyjście skanera.
REJECT;
Powoduje, że skaner nie stwierdza dopasowania w danej regule i kontynuuje
przetwarzanie następnej, najlepiej pasującej innej reguły. Używanie REJECT
ma wpływ na wydajność skanera i należy tego unikać.
unput(c);
Umieszcza ponownie znak c w strumieniu wejściowym  będzie to następny
czytany znak. Takie działanie unieważni bieżący element, jeśli flex działa w
trybie domyślnym, a więc należy korzystać z tego tylko po wykonaniu
działania, które używa zawartości yytext.
yymore();
Powoduje, że skaner po stwierdzeniu dopasowania w następnej regule
dopisuje tekst do yytext, zamiast go zastępować.
yyless(n);
Umieszcza ponownie końcowy fragment bieżącego elementu w strumieniu
wejściowym, aby ponownie go odczytać  używa tylko początkowych n
znaków.
input();
Zwraca następny znak (podobnie jak int) ze strumienia wejściowego
Makropolecenie yymore może być użyte do skanowania wielokrotnie występujących prefiksów,
np. tak jak niżej:
%option main
%%
"grandfather" { printf("paternal ancestor: %s", yytext); }
"great-" {yymore();}
%%
Gdy skaner napotka tekst "great", będzie kontynuował skanowanie, pamiętając o tym prefiksie
(jako części yytext). Po dopasowaniu do słowa "grandfather" mamy więc zebrane od razu
wszystkie prefiksy.
$ ./great
grandfather
paternal ancestor grandfather
great-great-great-grandfather
paternal ancestor great-great-great-grandfather
^D
$
Przekierowanie wejścia i wyjścia skanera
Skanery utworzone za pomocą programów flex i lex będą automatycznie odczytywały dane ze
standardowego wejścia i przekazywały je do standardowego wyjścia. Takie zachowanie łatwo
zmienić, przyporządkowując strumienie wejściowe i wyjściowe do dwóch zmiennych yyin i
yyout:
FILE *yyin = stdin;
FILE *yyout = stdout;
Załóżmy, że mamy program korzystający ze skanera przy odczycie danych z pliku wskazanego w
wierszu poleceń. Mógłby on uruchamiać np. następujący kod (po dodaniu kontroli błędów!):
yyin = fopen("filename", "r");
yylex();
Podobnie można postąpić przy przekierowaniu wyjścia  wówczas zmienna yyout powinna być
przyporządkowana do odpowiedniego wskaz
nika strumienia wyjściowego.
Gdy skaner osiągnie koniec pliku wejściowego, wywołuje funkcję o nazwie yywrap. Jeżeli nie
jest ona zdefiniowana w kodzie własnym użytkownika umieszczonym w specyfikacji skanera,
wtedy będzie używana jej domyślna postać, jeśli program był konsolidowany z biblioteką flex.
Dlatego właśnie musieliśmy używać opcji -lfl w naszych poprzednich przykładach. Wartość
zwracana przez yywrap jest wykorzystywana jako informacja, czy skaner zakończył działanie.
Jeżeli jest ona różna od zera, oznacza to koniec pracy skanera.
Jeżeli chcemy kontynuować skanowanie (np. korzystając z następnego pliku wejściowego),
możemy utworzyć własną funkcję yywrap. Jednym z przykładów jej użycia może być skanowanie
wielu plików, których nazwy są przekazywane jako argumenty w wywołaniu programu głównego.
Funkcja yywrap może wówczas otwierać następny plik, przypisywać wskaz
nik strumienia do
zmiennej yyin i zwracać wartość zerową. Skaner może wtedy działać tak, jakby wejście z nowego
pliku rozciągało się na plik już odczytany.
Skaner może być użyty do zagnieżdżania wejść (ang. nest inputs, czyli np. takich, jakie mogą być
wymagane podczas przetwarzania dyrektyw #include w kompilatorze C) za pomocą stosu
strumieni wejściowych tworzących złożone wejście. Szczegółowe informacje na temat
wielostrumieniowych wejść można znalez
ć na stronach podręcznika systemowego programu
flex.
Oprócz tego, jeżeli zastąpi się niskopoziomowe funkcje obsługujące wejście używane przez
skaner, to z
ródłem danych wejściowych mogą być nie tylko pliki. Szczegółowy opis można
znalez
ć jak zwykle w podręczniku systemowym.
Zwracanie elementów
Często zdarza się, że w aplikacji nie potrzebujemy analizatora leksykalnego, który przejmowałby
od razu wszystkie dane wejściowe, lecz wymagamy tylko, aby dostarczał kolejny dostępny
element (ang. token). Aby skaner mógł tak działać, należy po prostu w kodzie wykonywanym po
dopasowaniu użyć polecenia return w tym miejscu, gdzie jest potrzebne jego zatrzymanie.
Jako przykład można podać usuwanie pustych wierszy i spacji oddzielających z danych
wejściowych oraz zwracanie do programu wywołującego pasujących słów kluczowych. Podany
niżej prosty kod działa właśnie w ten sposób, dodatkowo informując wywołujący program o
niedopasowanych danych, które wystąpiły na wejściu:
%{
#define TOKEN_GARBAGE 1
#define TOKEN_PROGRAM 2
#define TOKEN_BEGIN 3
/* i tak dalej */
%}
%%
"program" { return TOKEN_PROGRAM; }
"begin" { return TOKEN_BEGIN; }
[ \t\n]+ /* pomijanie spacji i pustych wierszy */
. { return TOKEN_GARBAGE; }
%%
int main()
{
int token;
while(token = yylex())
printf("wykryto element #%d\n", token);
}
Po wygenerowaniu skanera i uruchomieniu go możemy stwierdzić, że program działa zgodnie z
zamierzeniami:
$ flex token.l
$ cc -o token lex.yy.c -lfl
$ ./token
program
wykryto element #2
begin
wykryto element #3
1
wykryto element #1
^D
$
Funkcja yylex przy każdym wywołaniu rozpoczyna działanie od miejsca, w którym poprzednio
skończyła i próbuje ponownie dopasować dane wejściowe do wszystkich reguł. Z tego rodzaju
działaniem analizatora leksykalnego będziemy mieć często do czynienia w połączeniu z parserem
utworzonym przez programy yacc lub bison.
Skanery kontekstowe
Czasami trzeba utworzyć skaner wykorzystujący pewną informację o jakimś stanie, czyli skaner
odpowiadający na dopasowanie w różny sposób  zależnie od tego, co było dopasowane
poprzednio. Jednym z przykładów może być napis tworzący komentarz w języku C, w którym
ukośnik wewnątrz musi być traktowany inaczej niż ukośnik umieszczony poza komentarzem.
Utworzenie wyrażenia regularnego wykrywającego ukośniki w napisach jest bardzo trudne.
Możemy jednak podzielić działanie skanera na dwie lub więcej faz, z których jedna będzie
używana wewnątrz napisu, a druga na zewnątrz. W programie flex lub lex możemy rozpocząć
tworzenie takiego skanera reagującego na stan od stanu początkowego (ang. start condition).
Każda reguła w specyfikacji skanera musi być poprzedzona nazwą stanu (ang. state) podaną w
nawiasach trójkątnych, co oznacza, że jest ona używana tylko wtedy, gdy skaner znajduje się w
danym stanie. W rzeczywistości reguła musi być poprzedzona listą stanów, w których ma ona
obowiązywać. Do przełączania działań używane jest makropolecenie BEGIN(stan);.
%x comment
%%
"/*" BEGIN(comment);
[^*\n]* /* Pomijanie wszystkiego, co nie jest '*' */
"*"+[^*/\n]* /* Pomijanie '*', za którymi nie występuje '/'*/
\n line_num++;
"*"+"/" BEGIN(INITIAL);
Zwróćmy uwagę na to, że ten skaner musi sobie radzić z wielokrotnymi gwiazdkami na początku i
na końcu komentarza.
Opcje programu flex
Program flex ma niewiele opcji kontrolujących albo jego działanie, albo metody
przechowywania tabel danych używanych przy interpretacji reguł skanowania. Niektóre z częściej
używanych opcji podane są w poniższej tabeli:
-d
Tryb śledzenia błędów  wygenerowany skaner zawiera dodatkowe instrukcje
przesyłające na standardowe wyjście błędów komunikaty o dopasowaniu reguł.
-f
Tryb przyspieszony  wygenerowany skaner pracuje szybciej, lecz zużywa więcej
pamięci.
-h
Pomoc  wyświetlenie krótkich informacji o dostępnych opcjach.
-i
Pomijanie wielkości liter  wygenerowany skaner przeprowadza dopasowanie,
pomijając wielkość liter w danych wejściowych (zawartość yytext będzie miała litery
pierwotnej wielkości).
-l
Tryb zgodności z programem lex.
-t
Zapis kodu generowanego skanera na standardowe wyjście zamiast do pliku
lex.yy.c.
-I
Tryb interaktywny  generowany skaner jest odpowiedni dla aplikacji
interaktywnych. (W celu zwiększenia wydajności flex odczytuje z wejścia tylko tyle
danych, ile potrzeba do stwierdzenia dopasowania do którejś z reguł  co niekiedy
wpływa na działanie programów obsługiwanych w sposób interaktywny. Ta opcja
powoduje, że skaner zaczyna działać w sposób bardziej zachowawczy przy odczycie
danych z wyprzedzeniem, jednocześnie zachowując wymaganą zdolność
dopasowywania reguł).
-ofile
Zapis generowanego kodu skanera do pliku o podanej nazwie zamiast do lex.yy.c.
Jedną z najbardziej pożytecznych opcji, która jest stosowana wówczas, gdy nie wszystko idzie
zgodnie z planem, jest opcja wykrywania błędów -d. Instrukcje dające dodatkowe informacje
mają postać:
--accepting rule at line ("string")
Informują one o tym, która część danych wejściowych została dopasowana do reguły. Poprzedni
przykład ze słowem  grandfather dałby w takim wypadku następujące komunikaty:
$ ./great
--(end of buffer or a NUL)
great-great-grandfather
--accepting rule at line 4 ("great-")
--accepting rule at line 4 ("great-great-")
--accepting rule at line 3 ("great-great-grandfather")
paternal ancestor great-great-grandfather
--accepting default rule ("
")
--(end of buffer or a NUL)
^D
--EOF (start condition 0)
$
Analizatory składni (parsery)
Nadeszła teraz pora na zapoznanie się z parserami. Parser (analizator składni) to taki program,
który określa, czy sekwencja elementów leksykalnych spełnia albo nie spełnia daną specyfikację.
Mówiąc prościej, pobiera on słowo lub grupę słów i testuje ich zgodność z zestawem reguł
gramatycznych.
Dokładnie rzecz biorąc,  słowo może być czymkolwiek, co zostało określone jako element
leksykalny. W tym sensie parser działa podobnie do analizatora leksykalnego (skanera), który
określa, czy sekwencja znaków tworzy dany element, czy nie (i jeśli go tworzy, to jaki jest to
element). Struktury danych, którymi zajmuje się parser, są jednak zazwyczaj inne, bowiem są to
wpisy, wyrażenia i polecenia, czyli coś, co ma jakąś definiowalną składnię.
Prawdą jest więc stwierdzenie, że każdy program komputerowy wymagający danych wejściowych
(i wykonujący jakieś działania uzależnione od tych danych) określa pewien akceptowany przez
niego język wejściowy. Jak już poprzednio wspomnieliśmy, może to być bardzo skomplikowany
język programowania wysokiego poziomu (w przypadku kompilatora) lub bardzo prosta
sekwencja liter i cyfr.
Języki są definiowane przez gramatyki, czyli zestawy reguł określające, które uporządkowane
ciągi słów (nazywane zdaniami) są poprawne. W rzeczywistości języki są definiowane przez
zestaw wszystkich swoich zdań, ale reguły gramatyczne pozwalają na łatwe zestawienie
poprawnych zdań w wielu językach, szczególnie w językach sztucznych, które tutaj rozpatrujemy.
Możemy np. zastanowić się nad regułami dla specyficznego sposobu określania dat. Jedna z takich
reguł może mieć następującą postać:
= ','
W powyższym wyrażeniu , , i reprezentują w procesie
wejściowym interesujące nas struktury. Zakładamy też, że są one zdefiniowane gdzieś indziej.
Przecinek został ujęty w apostrofy, co oznacza, że musi wystąpić w oryginalnej postaci w danych
wejściowych. Przy odpowiednich definicjach ciąg danych wejściowych w postaci:
July 4, 1776
będzie pasował do wyżej zdefiniowanej reguły dla dat.
Często mamy swobodę wyboru, czy składniki strumienia wejściowego mają być rozpoznawane za
pomocą analizatora leksykalnego, czy za pomocą parsera. W omawianym przypadku można
byłoby wykorzystać analizator leksykalny zwracający elementy jednego rodzaju, reprezentujące
nazwy miesięcy oraz elementy innego rodzaju (o przyporządkowanych wartościach)
reprezentujące pojedyncze cyfry. Nasze reguły mogłyby wówczas wyglądać następująco:
= JANUARY | FEBRUARY | ... | DECEMBER
= DIGIT | DIGIT DIGIT
= DIGIT DIGIT DIGIT DIGIT
Jako alternatywne rozwiązanie można zaproponować użycie analizatora leksykalnego
zwracającego numer miesiąca na podstawie rozpoznanej nazwy oraz liczby całkowite
reprezentujące dzień miesiąca i rok.
Dokładne ustalenie równowagi miedzy analizą leksykalną i rozbiorem gramatycznym może być
kłopotliwe. Powszechnie stosuje się zasadę, że jak najwięcej operacji wykonuje analizator
leksykalny, bez wprowadzania zbyt skomplikowanych wyrażeń regularnych. Parsery powinny być
używane tylko wtedy, gdy stopień złożoności analizowanych struktur uniemożliwia ich prosty opis
za pomocą wyrażeń regularnych. Należy wówczas zwracać elementy mające jakieś znaczenie w
gramatyce, z której korzysta parser.
Tworzenie parserów
Jak już było wspomniane wcześniej, generator parserów jest programem, który tworzy parser na
podstawie zestawu reguł gramatycznych, a dobrze znanymi przykładami takich programów są
yacc i bison. Oczywiście, można także utworzyć parser ręcznie. W naszym przykładzie bardzo
łatwo można zbudować funkcję, która będzie wywoływać analizator leksykalny wybierający
elementy i sprawdzać, czy format daty jest poprawny. W przypadku bardziej skomplikowanej
gramatyki ręczne tworzenie parserów może być już bardzo pracochłonne i trudno w nich będzie
modyfikować reguły gramatyczne.
W opisie gramatyki każda reguła określa tzw. strukturę niezakończoną (ang. non-terminal),
nadając jej nazwę (np. w naszym przykładzie). Struktury niezakończone składają się z
elementów zwanych symbolami końcowymi (ang. terminal symbols) oraz z innych struktur
niezakończonych. Jest możliwe (i często się z tego korzysta) tworzenie reguł rekurencyjnych, w
których dana reguła odwołuje się do siebie samej albo bezpośrednio, albo pośrednio poprzez inne
reguły.
Oto przykład rekurencyjnego zestawu reguł wzięty ze specyfikacji gramatycznej języka
programowania Pascal:
= ":="
| IF THEN
| IF THEN ELSE
| BEGIN END
=
 | ';'
Powyższe wiersze ilustrują zasadę, że instrukcja Pascala może mieć kilka postaci, a niektóre z
nich mogą zawierać inne instrukcje. Przy odpowiednich definicjach innych struktur
niezakończonych powyższy zestaw reguł może pasować do następujących fragmentów programów
w języku Pascal:
fred := 2+bill
if fred-7 > 34
then x := x+1
else
begin
y := y-1;
bill := 2-fred
end
Zwróćmy uwagę na regułę definiującą , która będzie pasować do grupy instrukcji
oddzielonych średnikami. Podobnie jak przy programie flex, także i parsery generowane przez
bison próbują dopasować możliwie najdłuższą sekwencję danych wejściowych. Podczas próby
dopasowania struktury parser najpierw próbuje dopasować strukturę
, a następnie, zamiast zaakceptować ją jako (co jest dozwolone
przez regułę), będzie dalej próbował znalez
ć dopasowanie do kolejnej struktury .
Prowadzi to do rozpoznania grupy instrukcji. W naszych dwóch ostatnich przykładach parser
dopasuje następujące fragmenty kodu:
Drugi schemat został nieco skrócony, ponieważ każde przypisanie jest tu reprezentowane przez
strukturę := .
Parser odczytuje elementy z wejścia i zastępuje je strukturami zdefiniowanymi w regułach
gramatycznych. Ta technika nazywana jest rozbiorem redukcyjnym z przeniesieniem (ang. shift-
reduce parsing). Dopasowane elementy (symbole końcowe) i struktury niezakończone są
przenoszone z wejścia do bufora w parserze. Gdy w buforze zgromadzi się ich wystarczająco dużo
do tego, aby łącznie pasowały do jakiejś reguły, następuje ich redukcja do postaci rozpoznanej
struktury niezakończonej. Ostatecznie wszystkie dane wejściowe zostaną  zużyte i pozostanie
tylko jedna struktura  symbol początkowy (w naszym przypadku będzie to pojedyncza struktura
).
Podczas tworzenia specyfikacji parsera dla programów yacc lub bison można definiować pewne
działania, czyli fragmenty własnego kodu w języku C, podobnie jak w specyfikacji dla programów
lex i flex. Podczas redukcji reguły związany z nią kod jest uruchamiany, jeśli nastąpiło
dopasowanie.
Nadszedł już prawdopodobnie czas na przykład. Poniżej podano specyfikację gramatyczną
podzbioru języka Pascal użytego w poprzednim przykładzie analizowanego kodu. Jest to
poprawna i pełna specyfikacja dla programów yacc i bison, którą nazwiemy pascal.y
(umownie nazwy plików zawierających opis gramatyki przetwarzanych przez yacc lub bison
mają rozszerzenie .y).
%{
#include
%}
%token tBEGIN
%token tEND
%token tIF
%token tTHEN
%token tELSE
%token tASSIGN
%token tIDENTIFIER
%token tNUMBER
%start statement
%left '>'
%left '+'
%left '-'
%%
statement: tIDENTIFIER tASSIGN expression
| tIF expression tTHEN statement
| tIF expression tTHEN statement tELSE statement
| tBEGIN statements tEND
;
statements: statement
| statement ';' statements
;
expression: tNUMBER
| tIDENTIFIER
| expression '+' expression
| expression '-' expression
 | expression '>' expression
;
%%
int main()
{
yyparse();
}
int yyerror(char *s)
{
fprintf(stderr, "%s\n", s);
return 0;
}
int yylex()
{
return 0;
}
Podobnie jak w specyfikacji używanej przez lex, specyfikacja parsera składa się z trzech części:
definicji,
reguł,
kodu dodatkowego.
Części te są oddzielone od siebie za pomocą wierszy zawierających dwa znaki procenta.
Definicje
Podobnie jak w programie flex, część ta jest przeznaczona na deklaracje języka C, które mają
być dostępne w pozostałych częściach kodu:
%{
#include
%}
Podaje się tutaj także definicje dla generacji samego parsera:
%token tBEGIN
%token tEND
%token tTHEN
%token tELSE
%token tASSIGN
%token tIDENTIFIER
%token tNUMBER
%start statement
%left '>'
%left '+'
%left '-'
Te definicje są nazywane dyrektywami (ang. directives).
Głównym zadaniem programu yacc lub bison jest utworzenie funkcji parsera, która będzie
nazywana yyparse. Funkcja ta wywołuje inną funkcję o nazwie yylex, która pobiera elementy
ze strumienia wejściowego. Elementy, które mają być zwrócone przez yylex, są zadeklarowane w
części definicyjnej specyfikacji gramatycznej.
Wiersze rozpoczynające się od dyrektyw %token służą do deklaracji nazw elementów, którymi
jesteśmy zainteresowani oraz do generacji związanych z nimi stałych, które można użyć w
skanerze. Wiersz rozpoczynający się od dyrektywy %start informuje generator o tym, że ma być
utworzony parser dopasowujący strukturę zdefiniowaną w regule występującej w specyfikacji jako
pierwsza.
Przy wyborze nazw elementów należy unikać możliwych konfliktów z definicjami użytymi w innych
miejscach programu, włącznie z generowanym skanerem i parserem. Może to powodować
problemy, szczególnie przy słowach kluczowych. Nie wolno np. nazwać elementu else, który ma
być zwrócony przez skaner wykrywający słowo  else w danych wejściowych, ponieważ występuje
tu konflikt ze słowem kluczowym języka C. Prosta zmiana wielkości liter także nie wystarcza.
Należy pamiętać, że nazwy elementów mogą być już określone przez dyrektywy #define w samym
kodzie, zaś skaner i parser definiują pewne stałe na własne potrzeby, łącznie z BEGIN! Dlatego
właśnie w podanym przykładzie nazwy wszystkich elementów zostały w celu ich odróżnienia
poprzedzone prefiksem.
Do pozostałych dyrektyw (%left) powrócimy przy okazji omawiania rozbioru wyrażeń
arytmetycznych i związanych z tym zagadnień.
Reguły
Część zawierająca reguły jest bardzo podobna do tego, co pokazano przy okazji omawiania
specyfikacji struktur:
statement: tIDENTIFIER tASSIGN expression
| tIF expression tTHEN statement
| tIF expression tTHEN statement tELSE statement
 | tBEGIN statements tEND
;
statements: statement
| statement ';' statements
;
expression: tNUMBER
| tIDENTIFIER
| expression '+' expression
| expression '-' expression
| expression '>' expression
Ogólna postać reguły gramatycznej jest następująca:
coś: składniki1
| składniki2
| składniki3
...
;
Składnikiem może tu być sekwencja innych struktur niezakończonych, elementów leksykalnych
lub zwykłych znaków. Taka reguła jest rozumiana jako  struktura niezakończona o nazwie coś,
którą tworzą składniki1 lub składniki2 lub składniki3 lub... . Nie muszą tu występować
alternatywy i wówczas reguła jest po prostu skrótem zastępującym sekwencję innych pozycji.
Jedna z alternatyw może być pusta, co oznacza, że możliwe jest dopasowanie struktury
niezakończonej do pustego napisu. Zwyczajowo w takich wypadkach wyróżnia się pustą
alternatywę odpowiednim komentarzem, tak jak w poniższym przykładzie:
: ','
| /* empty */
;
Kod dodatkowy
Część przeznaczona na kod dodatkowy zawiera deklaracje języka C i definicje funkcji, które
zostaną skopiowane bez zmian do z
ródłowego pliku parsera:
int main()
{
yyparse();
}
int yyerror(char *s)
{
fprintf(stderr, "%s\n", s);
return 0;
}
int yylex()
{
return 0;
}
Zdefiniowaliśmy tu funkcję main, która wywołuje funkcję parsera yyparse, ta zaś wywołuje
funkcję analizatora leksykalnego o nazwie yylex. W tym momencie funkcja analizatora
leksykalnego jest atrapą, zwracającą tylko zerowy element oznaczający koniec pliku. Już wkrótce
zastąpimy ją jednak pełnym analizatorem leksykalnym.
Trzecią funkcją, którą musimy tu zdefiniować, jest funkcja o nazwie yyerror. Ma ona za zadanie
obsłużyć wszystkie błędy, które mogą wystąpić podczas pracy parsera. Parser wywołuje yyerror
wówczas, gdy nie jest w stanie przeprowadzić dopasowania danych wejściowych do
zdefiniowanych w specyfikacji reguł gramatycznych. Często wystarcza wtedy wyświetlenie
komunikatu ze standardowym numerem błędu  tak też postąpiliśmy w naszym przykładzie.
Funkcję yyerror można wykorzystać łącznie z innymi dodatkowymi funkcjami do inicjacji
procesu rozpoznawania błędów, podczas którego parser będzie próbował zsynchronizować się
ponownie z danymi wejściowymi. W przypadku pełnosprawnego kompilatora moglibyśmy np.
wyszukiwać wszystkie możliwe błędy. W prostszych aplikacjach wystarczy zatrzymanie parsera
po napotkaniu pierwszego błędu, tak jak to ma miejsce w naszym przykładzie. Szczegółowe
informacje o procesie rozpoznawania błędów można znalez
ć w podręcznikach systemowych
programów yacc i bison oraz na stronach informacyjnych programu bison.
Tworzenie testera składni
Użyjemy teraz przykładu pascal.y do utworzenia programu badającego składnię fragmentu
naszego kodu, czyli dokonującego rozbioru instrukcji języka Pascal zgodnie ze specyfikacją
gramatyczną.
Najpierw musimy utworzyć sam parser, czyli funkcję yyparse. To zadanie wykonuje yacc i
bison. Ich domyślne działanie jest na początek wystarczające, a więc przystępujemy do pracy:
$ yacc pascal.y
yacc: 1 shift/reduce conflict.
$
Przy korzystaniu z programu bison można użyć opcji -y powodującej jego działanie zgodne z
programem yacc:
$ bison -y pascal.y
conflicts: 1 shift/reduce
$
Obydwa programy sygnalizują liczbę potencjalnych zagrożeń występujących w specyfikacji
gramatycznej, lecz tym problemem zajmiemy się póz
niej. W naszym przypadku sygnalizowane
zagrożenia nie mają większego znaczenia.
Sama funkcja parsera będzie zachowana w pliku y.tab.c. Czyż można nie lubić takich nazw?
Jeżeli przejrzymy zawartość tego pliku, to okaże się, że zawiera on całkiem skomplikowany kod
oraz jakieś tabele z liczbami całkowitymi. Jest to właśnie parser, zaś tabele są używane do
sterowania procesem dopasowywania elementów i struktur. W danym momencie parser znajduje
się w jednym z kilku zdefiniowanych stanów. Zależnie od następnego odczytanego elementu,
może on (ale nie musi) przejść do innego stanu.
Przykładowo: zanim do parsera dotrą jakiekolwiek dane wejściowe, znajduje się on w stanie
zerowym. Następnym poprawnym elementem dla tego stanu może być tIDENTIFIER (czyli
pierwszy element w instrukcji przypisania), tBEGIN (pierwszy element w bloku) itd. Jeżeli taki
element dotrze do parsera (załóżmy, że będzie to tIF), to parser przejdzie w stan oczekiwania na
dopasowanie wyrażenia. Po dopasowaniu wyrażenia nastąpi oczekiwanie na element tTHEN, i tak
dalej. Parser gromadzi swoje stany na stosie, dzięki czemu może stwierdzić dopasowanie reguły
po dopasowaniu tworzących ją elementów.
Aby przekształcić nasz przykład pascal.y w program dający się uruchomić, musimy utworzyć
funkcję analizatora lokalnego yylex. Musi ona odczytywać dane z wejścia i wytwarzać elementy
tBEGIN, tNUMBER itp. Nazwy elementów są przekształcane w stałe języka C za pomocą dyrektyw
#define wewnątrz kodu parsera y.tab.c. Są to zwykłe liczby całkowite o wartościach od 256 w
górę. Taki zakres wartości wybrano po to, aby analizator leksykalny mógł zwracać elementy
jednoznakowe kodowane jako liczby typu small integer z zakresu od 1 do 255 i kończyć plik
znakiem o kodzie 0.
Takich wartości elementów można użyć w funkcji yylex zdefiniowanej w specyfikacji
gramatycznej, ponieważ jej dodatkowa część zawierająca kod wchodzi do y.tab.c. Aby użyć
wartości elementów w analizatorze leksykalnym, mając je zdefiniowane w oddzielnym pliku,
należy posłużyć się plikiem nagłówkowym z tymi właśnie definicjami. W naszym przypadku jest
to plik y.tab.h, ale nie jest on generowany automatycznie. Musimy go utworzyć, korzystając z
dodatkowej opcji -d (skrót od defines) w wywołaniu programu yacc lub bison:
$ yacc -d pascal.y
$ cat y.tab.h
#define tBEGIN 257
#define tEND 258
#define tIF 259
#define tTHEN 260
#define tELSE 261
#define tASSIGN 262
#define tIDENTIFIER 263
#define tNUMBER 264
$
Teraz można już zająć się tworzeniem funkcji analizatora leksykalnego. Oczywiście, dokładnie
takie zadanie realizują lex lub flex, więc można z nich skorzystać. Oto specyfikacja
odpowiedniego skanera, którą nazwiemy pascal.l:
/* Specyfikacja (f)lex dla podzbioru instrukcji Pascal */
%{
#include "y.tab.h"
%}
ID [A-Za-z][A-Za-z0-9]*
%%
"begin" { return tBEGIN; }
"end" { return tEND; }
"if" { return tIF; }
"then" { return tTHEN; }
"else" { return tELSE; }
":=" { return tASSIGN; }
{ID} { return tIDENTIFIER; }
[0-9]+ { return tNUMBER; }
[ \t\n] /* ignoruj spacje i puste wiersze */
. { return *yytext; }
%%
Zwróćmy uwagę na to, że zwracany jest każdy pojedynczy znak nie rozpoznany jako element
jednoznakowy. Zwracany jest wówczas następny znak z bufora wejściowego yytext. Nie
powoduje to konfliktu z innymi elementami, ponieważ związane z nimi wartości leżą poza
zakresem poprawnych kodów znaków.
Jeżeli uruchomimy program flex dla tak zdefiniowanej specyfikacji, wówczas w pliku lex.yy.c
zostanie utworzona funkcja yylex. Można ją skompilować oddzielnie lub dołączyć do naszej
specyfikacji gramatycznej za pomocą dyrektywy #include na miejsce pustej funkcji yylex. Oto
dodatkowy fragment kodu o nazwie pascal2.y, który wykonuje takie zadanie  pozostałe
części pliku są takie same jak dla pascal.y:
int main()
{
yyparse();
}
int yyerror(char *s)
{
fprint(stderr, "%s\n", s);
return 0;
}
#include "lex.yy.c"
Zamiast definiowania własnego kodu dołączamy tu po prostu wygenerowany kod skanera. Mamy
więc do skompilowania dwa pliki z
ródłowe: lex.yy.c zawierający skaner i y.tab.c
zawierający parser. Chcemy także dołączyć kod skanera za pomocą dyrektywy #include.
Przystąpimy teraz do kompilacji i uruchomienia pełnego parsera, korzystając z następujących
poleceń:
$ yacc -d pascal2.y
$ flex pascal.1
$ gcc -o y.tab.c -lfl
Można się dziwić, że program, w którym nie napisaliśmy własnego kodu może, być użyteczny.
Możemy się o tym przekonać, sprawdzając składnię instrukcji języka Pascal (czyli ich wcześniej
zdefiniowany podzbiór) i jeśli nie pojawią się komunikaty o błędach pochodzące z wywołań
funkcji yyerror, to parser zakończy działanie bez żadnego komunikatu!
$ ./pascal
fred := 2
^D
$
Parser działa dobrze dla prostej instrukcji podstawienia. Spróbujmy teraz sprawdzić coś, czego do
tej pory nie robiliśmy  a mianowicie liczby ujemne.
$ ./pascal
fred := -2
parse error
$
W tym przypadku program zatrzymuje się bez konieczności użycia klawiszy Ctrl-D i wypisuje
komunikat  parse error wskazujący na błąd składni. Spróbujmy teraz podać na wejście coś
trochę bardziej skomplikowanego:
$ ./pascal
if fred-7 > 34
then x := x+1
else
begin
y := y-1;
bill := 2-fred
end
^D
$
Parser bez problemów uznał, że te skomplikowane instrukcje spełniają wprowadzone przez nas
reguły gramatyczne. Moglibyśmy rozbudować te reguły jeszcze bardziej i poszerzyć analizator
leksykalny tak, aby powstał program potrafiący przeanalizować pełny program w języku Pascal.
Pozostawiamy Czytelnikowi takie ćwiczenie. W naszym przypadku trzeba teraz stwierdzić, jakie
użyteczne działania mają być wykonane w wyniku rozpoznania elementów i większych struktur.
Typy elementów
W przedstawianych do tej pory przykładach nie następowała wymiana danych między skanerem i
parserem. Niezależnie od tego, że nasz program sprawdził poprawność gramatyczną, nie można
było skompilować lub uruchomić kodu w języku Pascal. Parser nie dysponuje bowiem żadną
informacją na temat liczb i nazw zmiennych przetworzonych przez analizator leksykalny. W
przypadku programów zbliżonych bardziej do rzeczywistości chcemy wykorzystać wartości
elementów. Pierwszym takim przykładem może być wartość liczby zwracanej jako element
tNUMBER.
Parsery wygenerowane przez program bison definiują zmienną o nazwie yylval, która ze swojej
istoty jest dostępna dla analizatorów leksykalnych, przekazując wartości elementów. Jest to
zmienna typu int. Można zmienić specyfikację skanera w taki sposób, aby zwracał wartość
związaną z elementem tNUMBER:
[0-9]+ { yylval = atoi(yytext); return tNUMBER; }
Wygląda to ładnie, dopóki wszystkie wartości elementów będą mogły być przechowywane w
zmiennej całkowitoliczbowej. Cóż jednak począć z identyfikatorami elementów? Moglibyśmy
zażądać w kodzie skanera przechowywania identyfikatorów wykrytych w tabeli i zwracania
wskaz
nika na dany element tabeli. Takie działanie umożliwiałoby parserowi przetwarzanie
informacji o tym, które zmienne zostały zadeklarowane, i zachowywanie związanych z nimi
wartości.
W ogólnym przypadku występują elementy różnego typu, a więc zmienna yylval musi być na
tyle ogólna, aby umożliwiać spełnienie tego wymagania. Unia występująca w języku C może się
do tego nadawać i tak właśnie działają programy yacc i bison. Pozwalają one na tworzenie typu
yylval, który jest unią (ang. union)  co wymaga kilku zmian w naszej specyfikacji
gramatycznej. Definicje elementów mają teraz postać:
%union {
int numval;
char *idval;
}
%token tBEGIN
%token tEND
%token tIF
%token tTHEN
%token tELSE
%token tASSIGN
%token tIDENTIFIER
%token tNUMBER
Działanie skanera wymaga przyporządkowania wartości elementów do odpowiednich składników
unii yylval, jak w przykładzie poniżej:
{ID} { yyval.idval = strdup(yytext); return tIDENTIFIER; }
[0-9]+ { yylval.numval = atoi(yytext); return tNUMBER; }
Zwróćmy uwagę na to, że musimy pobrać żądaną wartość ze zmiennej yytext, ponieważ
odzwierciedla ona zmiany przetwarzanego strumienia wejściowego. Aby to wszystko uprościć,
kopiujemy nazwę identyfikatora i zwracamy go jako wartość elementu tIDENTIFIER. W pełnym
programie należałoby prawdopodobnie użyć tablicy symboli zawierającej nazwy i wartości.
Musimy także deklarować typ każdego elementu, który ma być przyporządkowany do wartości.
Dzięki temu yacc i bison mogą wygenerować poprawny kod umożliwiający odwoływanie się do
składników unii yylval. Typ jest oznaczany za pomocą podania nazwy składnika unii w
nawiasach trójkątnych w dyrektywie %token, tak jak w poniższym przykładzie:
%token tIDENTIFIER
%token tNUMBER
Następnym etapem będzie wykorzystanie wartości elementów w parserze.
Działania w regułach
Każda reguła w specyfikacji gramatycznej programu bison może zawierać fragmenty kodu,
podobne do stosowanych w specyfikacji skanera. Zazwyczaj umieszcza się je w regule na końcu
każdej alternatywy. Zmienimy teraz kilka reguł gramatycznych, dodając do nich proste działania
(tylko w celach pokazowych):
statement: tIDENTIFIER tASSIGN expression { printf("assignment seen\n"); }
| tIF expression tTHEN statement
| tIF expression tTHEN statement tELSE statement
| tBEGIN statements tEND
;
statements: statement
| statement ';' statements
;
expression: tNUMBER { printf("number seen: %d\n", $1); }
| tIDENTIFIER { printf("identifier seen: %s\n", $1); }
| expression '+' expression
| expression '-' expression
| expression '>' expression
;
Zmiany polegają na tym, że po rozpoznaniu instrukcji przypisania będzie wyświetlany komunikat.
Komunikaty będą także pojawiać się po wystąpieniu identyfikatora lub liczby w wyrażeniu.
Wartość elementu możemy uzyskać, stosując skrótowy zapis $1, który będzie rozwinięty do pełnej
postaci odnoszącej się do składnika unii yylval (w rzeczywistości jest to odniesienie do elementu
stosu wartości obsługiwanego przez parser, ale nie jest to przedmiot naszego zainteresowania). Do
pozostałych elementów w regule można odnosić się za pomocą skrótów $2, $3 itd., zgodnie z
miejscem ich występowania w regule. Np. we fragmencie reguły:
| expression '-' expression
wartość semantyczna pierwszego wyrażenia wynosi $1, a drugiego $3.
Wartości mają również niezakończone struktury i można zdefiniować ich typy podobnie, jak w
wypadku typów elementów. Do tego celu służy dyrektywa %type, która jest wstawiana w część
deklaracyjną w specyfikacji gramatycznej. Pisząc np. program obliczeniowy (kalkulator), można
żądać obliczania wartości wprowadzanych wyrażeń. Takie wymaganie mogą spełniać następujące
fragmenty reguł gramatycznych:
%type expression
statement: tIDENTIFIER tASSIGN expression
{ printf("assignment seen, value is %d\n", $3); }
| tIF expression tTHEN statement
| tIF expression tTHEN statement tELSE statement
| tBEGIN statements tEND
;
expression: tNUMBER { $$ = $1; }
| tIDENTIFIER { $$ = 0; /* would be lookup($1); see text */; }
| expression '+' expression { $$ = $1 + $3; }
| expression '-' expression { $$ = $1 - $3; }
| expression '>' expression { $$ = $1 > $3; }
Stwierdzamy tutaj, że wyrażenia mają typ numval, czyli że ich wartości mogą być
przechowywane jako liczby całkowite w składniku numval unii yylval. Można następnie użyć
tej wartości wyrażenia w wyświetlanym komunikacie sygnalizującym przypisanie, jeżeli tylko o to
zadbamy.
Aby takie zadanie wykonać, musimy być pewni, że wszystkie alternatywy w regule opisującej to
wyrażenie będą zwracały wartość liczbową. W naszym przypadku jest to spełnione. Do
oznaczenia zwracanej wartości struktury niezakończonej używamy skrótu $$ (będzie to w tym
konkretnym wypadku expression). Do wartości podwyrażeń w wyrażeniach złożonych
odnosimy się tak jak poprzednio  za pomocą skrótów $1 i $3.
W tym prostym przykładzie dla identyfikatorów zwracana jest wartość zerowa. W pełnej aplikacji
można by wyszukiwać wartość zmiennej w tablicy symboli. Można także przechować wartość
elementu e, jeśli stwierdzimy, że ma ona być użyta w instrukcji przypisania.
W niektórych przypadkach może być potrzebna wartość struktury niezakończonej, której typ nie
należy do grupy typów używanych dla elementów. Jako przykład można podać budowę struktury
danych odpowiadającej strukturze wejściowej, a następnie przetwarzanie otrzymanej struktury
jako całości (a nie stopniowe budowanie wyniku). Taka sytuacja może wystąpić przy tworzeniu
aplikacji kalkulatora.
Można tak postąpić, ale należy dodać inny typ do deklaracji %union i zadeklarować, że nasza
struktura niezakończona będzie mieć taki typ. Zakończmy nasz przykład rozbioru programu w
języku Pascal, tworząc drzewo składni (wewnętrzną strukturę danych) i wyświetlając je po
odczytaniu pełnej instrukcji.
Będzie to struktura klasycznego, abstrakcyjnego typu danych, czyli drzewo binarne. Strukturę taką
tworzą węzły. Każdy węzeł jest określonego typu i ma dwa rozgałęzienia reprezentujące
poddrzewa. Kilka pokazanych niżej przykładów wyjaśni to lepiej. Wyrażenie fred - 7 > 34
będzie więc reprezentowane jako:
Instrukcja przypisania będzie zawierać węzeł typu t_assign i dwa rozgałęzienia. Jedno z nich
jest identyfikatorem, a drugie przypisanym wyrażeniem. Instrukcja if-then-else będzie się
składać z dwóch węzłów:
Część {else} będzie równa NULL, jeżeli w instrukcji nie występuje słowo else.
A oto kod tree.h, definiujący interfejs dla naszych funkcji tworzących drzewo:
/* tree.h - definicje drzewa składni */
/* Tree types */
typedef enum {
t_block, /* Dla bloku instrukcji */
t_join, /* Dla instrukcji wewnątrz bloku */
t_if, /* Dla instrukcji if */
t_else, /* Dla instrukcji zawartych w częściach else */
t_assign,/* Dla przypisań */
t_op, /* Dla wyrażeń z operatorem */
t_num, /* Dla liczb */
t_id, /* Dla identyfikatorów */
} treetype;
typedef struct t {
treetype type;
int op;
union {
int numval;
char *idval;
} value;
struct t *left;
struct t *right;
} tree;
tree *mknum(int);
tree *mkid(char *);
tree *mknode(treetype, int, tree *, tree *);
A oto kod tree.c, zawierające funkcje służące do tworzenia węzłów z innych węzłów i symboli
końcowych (takich jak liczby i identyfikatory):
/* Definicje funkcji drzewa */
#include
#include
#include "tree.h"
tree *mkdir(char *id)
{
tree *t = mknode(t_id, 0, NULL, NULL);
t -> value.idval = id;
return t;
}
tree *mknum(int num)
{
tree *t = mknode(t_num, 0, NULL, NULL);
t -> value.numval = num;
return t;
}
tree *mknode(treetype, int op, tree *l, tree * r)
{
tree *t = malloc(sizeof(tree));
t -> type = type;
t -> op = op;
t -> left = l;
t -> right = r;
return t;
}
print_tree(tree *t)
{
/* Będzie zdefiniowane póz
niej */
}
Aby skrócić powyższy przykład, pominięto w nim sprawdzanie błędów i funkcje uwalniania
pamięci używanej przez struktury węzłów.
Funkcję służącą do przemieszczania w drzewie zdefiniujemy nieco póz
niej, a teraz zajmiemy się
budową programu. Oto definicja skanera p2c.l:
/* Specyfikacja lex dla podzbioru Pascala */
%{
#include
%}
ID [A-Za-z][A-Za-z0-9]*
%%
"begin" { return tBEGIN; }
"end" { return tEND;}
"if" { return tIF; }
"then" { return tTHEN; }
"else" { return tELSE;}
":=" { return tASSIGN; }
{ID} { yylval.idval = strdup(yytext); return tIDENTIFIER; }
[0-9]+ { yylval.numval = atoi(yytext); return tNUMBER; }
[ \t\n] /* pomijanie spacji i pustych wierszy */
. { return *yytext; }
%%
A oto specyfikacja gramatyczna p2c.y, włącznie z działaniami budującymi drzewo:
%{
#include
#include "tree.h"
%}
%union {
int numval;
char *idval;
tree *tval;
}
%token tBEGIN
%token tEND
%token tIF
%token tTHEN
%token tELSE
%token tASSIGN
%token tIDENTIFIER
%token tNUMBER
%type statement statements expression
%start pascal
%left '>'
%left '+'
%left '-'
%%
pascal: statement { print_tree($1); }
statement: tIDENTIFIER tASSIGN expression
{ $$ = mknode(t_assign, 0, mkid($1), $3); }
 | tIF expression tTHEN statement
{ $$ = mknode(t_if, 0, $2, mknode(t_else, 0, $4, NULL));
}
| tIF expression tTHEN statement tELSE statement
{ $$ = mknode(t_if, 0, $2, mknode(t_else, 0, $4, $6)); }
| tBEGIN statements tEND
{ $$ = mknode(t_block, 0, $2, NULL); }
;
statements: statement
{ $$ = mknode(t_join, 0, $1, NULL); }
| statement ';' statements
{ $$ = mknode(t_join, 0, $1, $3); }
;
expression: tNUMBER { $$ = mknum($1); }
| tIDENTIFIER { $$ = mkid($1); }
| expression '+' expression { $$ = mknode(t_op, '+'. $1, $3); }
| expression '-' expression { $$ = mknode(t_op, '+'. $1, $3); }
| expression '>' expression { $$ = mknode(t_op, '+'. $1, $3); }
;
%%
int main()
{
yyparse();
}
int yyerror(char *s)
{
fprintf(stderr, "%s\n", s);
return 0;
}
#include "lex.yy.c"
Zwróćmy uwagę na to, że występują tu odwołania do mknode i funkcji pomocniczych, tworzących
węzły drzewa z części tego drzewa wcześniej zbudowanych przez parser. Dodano także nową
strukturę niezakończoną o nazwie pascal, która działa jako symbol początkowy. Dzięki temu
mamy wyraz
nie określony punkt początkowy i nie musimy korzystać z każdej alternatywy danej
dla definicji statement.
Na zakończenie pokazujemy definicję funkcji służącej do przemieszczania się w drzewie i do jego
wyświetlenia. Kod ten powinien być umieszczony w odpowiednim miejscu w pliku tree.c:
print_tree(tree *t)
{
if(!t) return;
switch(t -> type) {
case t_block:
printf("{\n");
print_tree(t -> left);
printf("}\n");
break;
case t_join:
print_tree(t -> left);
if(t -> right)
print_tree(t -> right);
break;
case t_if:
printf("if( ");
print_tree(t -> left);
printf("\n");
t = t -> right;
print_tree(t -> left);
if(t -> right) {
printf("else\n");
print_tree(t -> right);
}
break;
case t_assign:
print_tree(t -> left);
printf(" = ");
print_tree(t -> right);
printf(";\n");
break;
 case t_op:
printf("(");
print_tree(t -> left);
printf(" %c ", t -> op);
print_tree(t -> right);
printf(")");
break;
case t_num:
printf(" %d ", t -> value.numval);
break;
case t_id:
printf(" %s ", t -> value.idval);
break;
}
}
Teraz już możemy zbudować aplikację:
$ bison -y p2c.y
$ flex -l p2c.l
$ gcc -o p2c y.tab.c tree.c -lfl
Po uruchomieniu programu i użyciu naszych fragmentów kodu Pascala jako danych wejściowych
nastąpi ich wyświetlenie w innej postaci:
$ ./p2c
fred := 2
^D
fred = 2 ;
$ cat sample.pas
if fred-7 > 34
then x := x+1
else
begin
y := y-1;
bill := 2-fred
end
$ ./p2c if( (( fred - 7 ) > 34 ))
 x = ( x + 1 );
else
{
y = (y - 1 );
bill = ( 2 - fred );
}
$
Może nie jest to jeszcze doskonałe, ale mamy tu zaczątek programu, który może odczytywać kod
języka Pascal i tworzyć jego odpowiednik w języku C. Powinno być jasne, że jest to bardzo
uproszczona postać takiego translatora i trzeba jeszcze dodać reguły gramatyczne oraz funkcje
tworzące drzewo, aby powiększyć zakres przetwarzanych instrukcji języka Pascal. Można także
skorzystać z pomocy innych aplikacji, wzbogacając program o funkcje obsługi wiersza poleceń
lub makrodefinicje.
Opcje programu bison
Istnieje wiele opcji programu bison służących do kontrolowania różnych aspektów generacji
parsera. Najczęściej używane są:
-b
Określa prefiks, który będzie używany we wszystkich plikach wyjściowych.
--file-prefix
Plik wejściowy name.y wygeneruje wyjście prefix-name.c.
-d
Generuje plik dołączany, zawierający makrodefinicje nazw elementów
występujących w gramatyce.
--defines
Jeśli wyjściem parsera jest name.c, to dołączany plik będzie się nazywał
name.h.
-o
Określa nazwę pliku wyjściowego parsera.
--output-file
-v
Tworzy dodatkowy plik wyjściowy (o nazwie z końcówką .output)
zawierający informację o stanach generowanego parsera i konfliktach, jeśli
--verbose
takie występują.
-y
Tryb zgodności z programem yacc.
--yacc
Pliki wyjściowe będą się nazywały y.tab.c, y.tab.h oraz y.output.
-h
Wyświetlenie krótkiego opisu opcji.
--help
Konflikty gramatyczne
Podczas projektowania reguł gramatycznych dla omawianego wyżej przykładu pominęliśmy
milczeniem pojawiające się błędy. Programy bison i yacc sygnalizują konflikty, ale co w istocie
oznaczają te konflikty? Pełna odpowiedz
jest dość skomplikowana, ale mówiąc ogólnie, konflikty
powstają jako skutek dowolności w jakimś języku. Dowolność może wystąpić wszędzie tam, gdzie
dozwolony jest więcej niż jeden sposób dopasowania wejścia do reguł gramatycznych.
W znanych językach programowania instrukcja warunkowa if-then-else jest typowym
przykładem archetypu. Załóżmy, że część reguły gramatycznej dla instrukcji ma postać:
= "if" "then" /* Rule 1 */
| "if" "then" "else" /* Rule 2 */
| "print" /* Rule 3 */
W takim przypadku podane niżej dane wejściowe mogą pasować do reguły w dwojaki sposób.
if a > b then if b > c then print d else print e
Na poniższym rysunku oznaczenie s[n] wskazuje, że podkreślona część danych wejściowych
została dopasowana do reguły n w zdefiniowanej wyżej gramatyce:
Mamy też alternatywne dopasowanie:
Taka sytuacja jest powszechnie znana jako tzw.  pływające else (ang. dangling else). Podczas
analizy reguły gramatycznej dla instrukcji (statement) programy bison i yacc zauważają
możliwość wyboru, napotkawszy dane wejściowe takie jak w podanym przykładzie. Problem
powstaje przy napotkaniu na else. Czy w takim wypadku parser powinien zakończyć pobieranie
na już zgromadzonym if-then i potraktować to jako pełną instrukcję (czyli zredukować ją), czy
też kontynuować działanie pobierając else (czyli przenosząc je z wejścia), aby zbudować if-
then-else? Taka możliwość wyboru dobrze ilustruje dowolność występującą w języku
zdefiniowanym przez daną gramatykę. Narzędzia sygnalizują to jako konflikt między redukcją a
przenoszeniem (ang. shift/reduce conflict).
Konflikty gramatyczne muszą być rozwiązywane, czyli musi być dokonany wybór miedzy
przeniesieniem a redukcją w wyżej opisanej sytuacji. Programy yacc i bison mają określone
zachowania domyślne w takich wypadkach i jest nim przesunięcie. Oznacza to, że parser będzie
tworzył if-then-else, czyli coś, czego się spodziewamy. Część else zostanie
przyporządkowana do najbliższej poprzedzającej części if, co odpowiada regułom języków C,
Pascal i innych powszechnie stosowanych języków, w których taka konstrukcja występuje.
Inny rodzaj konfliktu między redukcją a przesunięciem występuje wówczas, gdy dane wejściowe
pasują jednocześnie do dwóch reguł. Może to się zdarzać dosyć często przy przetwarzaniu struktur
niezakończonych, które mogą pasować do pustego napisu. Należy wówczas zmodyfikować
gramatykę w taki sposób, aby usunąć konflikt.
Prawdopodobnie największym z
ródłem konfliktów jest specyfikacja wyrażeń arytmetycznych. Jest
to na tyle istotny problem, że poświęcimy mu osobny podrozdział omawiający specyficzne
działanie naszych narzędzi.
Wyrażenia arytmetyczne
Jak już widzieliśmy poprzednio, niektóre dane wejściowe mogą spełniać proste reguły
gramatyczne w różnoraki sposób, co nieuchronnie prowadzi do konfliktów. W wypadku wyrażeń
arytmetycznych moglibyśmy zapisać reguły gramatyczne w następującej postaci:
expression: expression '+' expression
| expression '*' expression
| expression '^' expression
;
Jeżeli tak postąpimy, pojawi się cała masa konfliktów, ponieważ nie zostało tu uwzględnione
wzajemne pierwszeństwo działania operatorów. Dane wejściowe w postaci:
1 + 2 * 3
będą po rozbiorze znaczyły (1+2)*3, ponieważ parser domyślnie będzie kontynuował pobieranie
pozycji tworzących możliwie najdłuższe wyrażenie. To, co działało doskonale dla instrukcji if,
powoduje teraz poważne błędy. Należałoby zmodyfikować reguły gramatyczne, wprowadzając
nowe typy wyrażeń opisujące tylko operatory o tym samym pierwszeństwie, ale w rzeczywistości
nie musimy tego robić.
Dyrektywy %left i %right są stosowane jako wskaz
nik, czy jakiś operator (lub grupa
operatorów) działają lewostronnie, czy prawostronnie. Ta informacja jest wykorzystywana przez
generator parsera jako pomoc podczas tworzenia parsera reagującego na kolejność i łączność
operatorów. Usuwa ona również potencjalne z
ródło konfliktów. Oto fragment gramatyki, który
mógłby poprawnie sobie radzić ze zwykłymi wyrażeniami arytmetycznymi:
%token tNUMBER
%token tIDENTIFIER
%token MINUS
%left '-' '+'
%left '*' '/'
%left MINUS
%right '^'
%%
expression: tNUMBER
| tIDENTIFIER
| expression '+' expression
| expression '-' expression
| expression '*' expression
| expression '/' expression
| expression '^' expression
| '(' expression ')'
| '-' expression %prec MINUS
;
A
ączność operatorów jest zdefiniowana w kolejności rosnącego pierwszeństwa, a więc ta
gramatyka definiuje dodawanie i odejmowanie jako operacje o niższym pierwszeństwie niż
mnożenie, dzielenie itd.
Podana wyżej gramatyka obsługuje również liczby ujemne dzięki wprowadzeniu jednostronnego
operatora. Zastosowano tu specjalne słowo %prec oznaczające pierwszeństwo dla reguły nie
zawierającej operatora dwustronnego oraz element MINUS określający poprawną kolejność
operacji.
Taką regułę gramatyczną można łatwo rozszerzyć na inne operatory, dodając do niej odpowiednie
kierunki ich działania i alternatywy.
Materiały z
ródłowe
Więcej informacji na temat skanerów, parserów, budowy kompilatorów i związanych z nimi
narzędzi znajduje się w Internecie pod następującymi adresami:
Strona Yacc  http://www.combo.org/lex_yacc_page
ANTLR, inny popularny generator parserów  http:/www.antlr.org
Grupa informacyjna ANTLR  news:comp.compilers.tools.pccts
Grupa informacyjna dotycząca kompilatorów  news:comp.compilers
Katalog darmowych narzędzi  http://www.idiom.com/free-compilers
 Katalog zestawów do budowy kompilatorów 
http://www.first.gmd.de/cogent/catalog/kits.html
 Księga smoka , czyli najprawdopodobniej najbardziej znana praca na temat
kompilatorów: Principles of Compiler Design, autor: Aho and Ullman, wyd. Addison-
Wesley (ISBN 0-201000-22-9).
Understanding and Writing Compilers, autor: Bornat, wyd. Macmillan (ISBN 0-333217-
32-2).
Podsumowanie
W tym rozdziale próbowaliśmy pokazać wydajność i elastyczność niektórych narzędzi
przeznaczonych do obsługi strukturalnych danych wejściowych. Brak miejsca powoduje, że
zaledwie dotknęliśmy tych zagadnień; w szczególności dotyczy to programu bison, który ma
wiele właściwości i opcji zupełnie nie omówionych w tej książce.
Mamy nadzieję, że zachęciliśmy Czytelnika do korzystania z programów lex lub flex oraz yacc
lub bison we własnych aplikacjach. Od tego momentu Czytelnik powinien być już przekonany,
że przy tworzeniu własnego programu należy użyć tych narzędzi, a także zapoznać się z
odpowiednimi stronami podręcznika systemowego!