Rozdział 10. Flex i Bison

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

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

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

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

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

Wejściowa struktura danych

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

program hello(input,output);

(* A simple example program *)

const alength = 7;

bindex = 3;

var left, right: integer;

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

begin

if a[bindex] > 32.613 then

begin

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

left = 6 + right*21

end

end.

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

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

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

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

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

Wiersz[2] to ""

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

i tak dalej.

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

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

...

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

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

...

BLOCK(

begin

if a[bindex] > 32.613 then

BLOCK(

begin

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

left = 6.1 + right*21

end

)

end.

)

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

...

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

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

...

Skanery i analizatory składni

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

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

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

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

Jak działają generatory?

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

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

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

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

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

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

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 ź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 <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 + 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ą wskaź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 znaleźć 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.
\<char>	Znak specjalny, taki jak w języku C, który pasuje do znaków sterujących na wejściu. <char> 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<class> 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:]]

Łą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 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 ź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 wskaź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ć wskaź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 znaleźć 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 źródłem danych wejściowych mogą być nie tylko pliki. Szczegółowy opis można znaleźć 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);

<comment>[^*\n]* /* Pomijanie wszystkiego, co nie jest '*' */

<comment>"*"+[^*/\n]* /* Pomijanie '*', za którymi nie występuje '/'*/

<comment>\n line_num++;

<comment>"*"+"/" 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 <n> ("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ć:

<date> = <month-name> <day> ',' <year>

W powyższym wyrażeniu <date>, <moth-name>, <day> i <year> 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:

<month-name> = JANUARY | FEBRUARY | ... | DECEMBER

<day> = DIGIT | DIGIT DIGIT

<year> = 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. <date> 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:

<instrukcja> = <identyfikator> ":=" <wyrażenie>

| IF <wyrażenie> THEN <instrukcja>

| IF <wyrażenie> THEN <instrukcja> ELSE <instrukcja>

| BEGIN <instrukcja> END

<instrukcje> = <instrukcja>

| <instrukcja> ';' <instrukcje>

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ą <instrukcje>, 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 <instrukcje> parser najpierw próbuje dopasować strukturę <instrukcja>, a następnie, zamiast zaakceptować ją jako <instrukcje> (co jest dozwolone przez regułę), będzie dalej próbował znaleźć dopasowanie do kolejnej struktury <instrukcje>. 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ę <identyfikator> := <wyrażenie>.

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 <instrukcja>).

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 <stdio.h>

%}

%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 <stdio.h>

%}

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:

<optional_comma>: ','

| /* empty */

;

Kod dodatkowy

Część przeznaczona na kod dodatkowy zawiera deklaracje języka C i definicje funkcji, które zostaną skopiowane bez zmian do ź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 znaleźć 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óź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 ź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 wskaź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 <idval> tIDENTIFIER

%token <numval> 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 <idval> tIDENTIFIER

%token <numval> 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 <numval> 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 <stdio.h>

#include <stdlib.h>

#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óź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óźniej, a teraz zajmiemy się budową programu. Oto definicja skanera p2c.l:

/* Specyfikacja lex dla podzbioru Pascala */

%{

#include <string.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} { 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 <stdio.h>

#include "tree.h"

%}

%union {

int numval;

char *idval;

tree *tval;

}

%token tBEGIN

%token tEND

%token tIF

%token tTHEN

%token tELSE

%token tASSIGN

%token <idval> tIDENTIFIER

%token <numval> tNUMBER

%type <tval> 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 wyraź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 <sample.pas

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 --file-prefix	Określa prefiks, który będzie używany we wszystkich plikach wyjściowych. Plik wejściowy name.y wygeneruje wyjście prefix-name.c.
-d --defines	Generuje plik dołączany, zawierający makrodefinicje nazw elementów występujących w gramatyce. Jeśli wyjściem parsera jest name.c, to dołączany plik będzie się nazywał name.h.
-o --output-file	Określa nazwę pliku wyjściowego parsera.
-v --verbose	Tworzy dodatkowy plik wyjściowy (o nazwie z końcówką .output) zawierający informację o stanach generowanego parsera i konfliktach, jeśli takie występują.
-y --yacc	Tryb zgodności z programem yacc. Pliki wyjściowe będą się nazywały y.tab.c, y.tab.h oraz y.output.
-h --help	Wyświetlenie krótkiego opisu opcji.

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 odpowiedź 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ć:

<statement> = "if" <expression> "then" <statement> /* Rule 1 */

| "if" <expression> "then" <statement> "else" <statement> /* Rule 2 */

| "print" <expression> /* 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 ź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 wskaź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 ź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

;

Łą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 ź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!

36 Część I ♦ Podstawy obsługi systemu WhizBang (Nagłówek strony)

36 D:\1-dokumenty\Word\Zaawansowane programowanie w systemie Linux\R-10-05.doc

---