Bison - wprowadzenie i trywialny przykład.

Ten artykuł będzie miał na celu wyjaśnienie następujących kwestii:

  1. Co jest rolą parsera.
  2. Jak wygląda współpraca między analizatorem leksykalnym, a parserem (tzn. co jest za co odpowiedzialne).
  3. Schemat pliku Bisona.
  4. Wykonanie trywialnego parsera, który nic specjalnego nie robi, poza tym, że kompiluje się i działa.
  5. Udoskonalenie parsera, żeby dodawał dwie cyfry do siebie.
  6. Wprowadzenie prostej rekursji do przykładowego parsera.

Rola parsera.

O ile rolą leksera było tylko wyodrębnianie odpowiednich symboli i podawanie zwracanie ich po kolei gdzieś indziej (a konkretnie - do parsera, o czym potem), parser ma już troszkę poważniejszą rolę. Jego zadaniem jest implementacja gramatyki języka. Parser analizuje otrzymywane dane pod kątem zadanej gramatyki formalnej oraz przeprowadza odpowiednie akcje w zależności od tego, z jakim elementem gramatyki ma aktualnie do czynienia (nie jest to definicja parsera, lecz tylko moje intuicyjne rozumienie tego pojęcia).

Współpraca między analizatorem lekserem a parserem.

Czego może chcieć parser od leksera i na odwrót? Okazuje się, że są to bliscy krewni, którzy często się ze sobą porozumiewają. Żeby zadziałać, parser potrzebuje dwóch rodzajów informacji: typu tokenu (np. czy dana wejściowa jest liczbą, identyfikatorem, znakiem końca linii, znakiem nowej linii itd.) oraz wartości semantycznej tokenu (np. 123, "alamakota" itd.). O te dwa rodzaje informacji parser prosi leksera. Gdybyśmy podsłuchali rozmowę parsera i leksera, co jakiś czas słyszelibyśmy następującą wymianę zdań:

parser: OK, stary, dawaj następny token, co tam masz?
lekser: Mam tu token, który jest liczbą i ma wartość semantyczną 125, trzymaj…
parser: Dzięki, Zią, zaraz zgłoszę się do Ciebie po następny.

Jeśli przyglądałeś się kodowi przeklejanemu do własnego leksera robionego na pracę domową, to zauważyłeś, że są tam wykorzystywane dwa mechanizmy - zwracanie wartości takich jak NUM, NONE itp. oraz zmienna globalna tokenval. W tym przypadku zwracając wartości NUM, NONE, itd. informowaliśmy parsera, z jakim typem tokenu miał do czynienia, natomiast przypisując wartość do zmiennej tokenval "wystawialiśmy" ją parserowi na wypadek gdyby jej potrzebował. Nie zawsze wartość semantyczna jest istotna. W przytoczonym przykładzie do zaznaczenia, że wartość semantyczna tokenu nie ma znaczenia, została wykorzystana wartość NONE, ale można by jej w ogóle nie podawać w takich przypadkach. Znaki (nie wiem, czy liczby też) mogą być same w sobie typami tokenu (np. '+').

Podsumowując: lekser i parser ściśle współpracują. Parser prosi leksera o odczytanie następnego tokenu i podanie jego typu jak i wartości semantycznej. Parser potrzebuje typu tokenu po to, by dopasować go do odpowiedniej produkcji gramatyki, natomiast wartość semantyczna pozwala mu na wykonanie pewnych działań na elementach tej produkcji (jeśli teraz nie jest to jasne, to nie szkodzi, na przykładzie się wyjaśni).

Skoro już wiemy, co i po co robimy, możemy się zaznajomić z narzędziem, czyli Bisonem.

Schemat plików wejściowych Bisona.

Schemat plików Bisona do złudzenia przypomina Flexa. Wystarczy popatrzeć na zaczerpnięty z manuala bisona szkic:

%{
       Prolog
%}

     Deklaracje Bisona
%%

     Reguły gramatyczne
%%

     Epilog

Zarówno prolog jak i epilog muszą być napisane w języku C lub C++. Reszta sekcji jest specyficzna dla Bisona. Nie będę wnikać tu w szczegóły, o których można sobie poczytać w rozdziale 3.1 dokumentacji Bisona, tylko przejdę od razu do przykładu.

Wykonanie trywialnego parsera.

Zanim przejdziemy do przykładu, musisz wiedzieć, że program zrobiony w oparciu o Bisona musi zawierać, oprócz samego parsera, następujące elementy:

  1. funkcję int yylex(void), która przy okazji musi "widzieć" tokeny zadeklarowanye w pliku Bisona,
  2. funkcję int yyerror(char const* jakasNazwaArgumentu) (funkcja zwraca 0 jeśli została wywołana an skutek EOF, albo 1 jeśli błąd),
  3. funkcję int main(void), jak każdy program napisany w C lub C++.

Funkcję yylex() można wygenerować za pomocą Flexa, ale w tym trywialnym przykładzie wpiszemy ją z palca, żeby nie odwracać uwagi od istotniejszych spraw. Funkcję yyerror() (służącą do obsługi błędów parsowania) trzeba napisać samemu i może ona w najprostszym przypadku mieć następującą postać:

int yyerror(char const* s)
{
    printf("%s\n", s);
    return 1;
}

Rolą maina w najprostszym przypadku jest wywołanie funkcji yyparse(), którą wygeneruje Bison na podstawie naszego parsera.

Funkcjonalność pierwszego przykładu będzie polegać na pobieraniu od leksera cyfry z wejścia i wypisywanie jej na wyjście. Jest to oczywiście zupełnie bezsensowne zadanie dla parsera, ale pozwoli pokazać, o co chodzi z typami tokenów i wartościami semantycznymi.

W tym kodzie zdefiiniujemu sobie jeden symbol terminalny - DIGIT oraz jeden nieterminalny - expr, który będzie po prostu cyfrą (potem to rozwiniemy, ale teraz niech zostanie jak jest). Jeżeli parser napotka coś, co ma typ DIGIT, wypisze krótki komunikat i wartość semantyczną tego symbolu.

Wartości semantyczne znalezionych tokenów są zapisywane w zmiennych, które mają na początku znak $ i jakąś liczbę, np. dla produkcji "wyrażenie może mieć postać liczba '+' liczba", wartość pierwszej liczby jest zapisana w zmiennej $1, wartość semantyczna znaku '+' (która jest przypadkową liczbą, bo tylko dla cyfry wpisywaliśmy coś do yylval) jest zapisana w zmiennej $2, natomiast wartość drugiej liczby jest zapisana w $3. Tak naprawdę nie jest to gwarantowane, bo wartości semantyczne przekazuje lekser wg. własnego uznania (czyli możemy np. mu kazać dla każdej znalezionej cyfry ustawiać wartość semantyczną na 616 i takąotrzyma parser), ale nie wnikamy w to na razie.

Można (i często trzeba) odnieść się także do lewej strony produkcji, którą oznacza zmienna $$. Do lewej strony produkcji odnosimy się choćby po to, żeby obliczyć jej własną wartość semantyczną, bo symbol po lewej stronie aktualnej produkcji może się pojawić po prawej stronie innej produkcji (pamiętajmy, że gramatyka ma postać drzewiastą). Tą zmienną wykorzystamy później, kiedy będziemy troszkę rozwijać ten przykład.

Następna ważna informacja, to że lekser przekazuje parserowi wartość semantyczną przez specjalną zmienną globalną yylval, którą sobie po prostu wypełnia wedle uznania. Typ tej zmiennej to standardowo int, ale można go redefiniować.

Bez względu na to, czy powyższe tłumaczenia były zrozumiałe, czy nie, poniższy kod przykładu powinien pomóc je zrozumieć:

%{
    #include <ctype.h> //do isdigit()
    int yyerror(char const* s);
%}
 
%token DIGIT
 
%%
 
expr : DIGIT { 
                 printf("%s %d\n", "znalazlem cyfre:", $1);  //odwołujemy się do pierwszego symbolu po prawej stronie
             };
 
%%
 
int yyerror(char const* s)
{
    printf("%s\n", s);
    return 1;
}
 
int yylex() 
{
    int c;
    c = getchar();
    if (isdigit(c)) 
    {
        yylval = c - '0'; //przekaż wartość semantyczną
        return DIGIT; //przekaż typ tokenu
    }
    else if('\n' == c)
    {
        return 0;
    }
    return c;
}
 
int main(void)
{
    return yyparse();
}

Nie wgłębiając się specjalnie w funkcję yylex(), warto tylko zauważyć następujące dwie linijki:

yylval = c - '0'; //przekaż wartość semantyczną
return DIGIT; //przekaż typ tokenu

Pierwsza z nich, jak wspomniałem, służy do przekazania wartości semantycznej tokenu parserowi (parser odczytuje ją przez $1), a zwrócenie DIGIT służy dopasowaniu odpowiedniej produkcji.

Żeby wygenerować kod z pliku przykładowego Bisona (nazwijmy go sobie tutorial1.y) wystarczy wpisać:

bison tutorial1.y

powstanie plik tutorial1.tab.c który można już normalnie skompilować instrukcją:

gcc tutorial1.tab.c -o tutorial1

Teraz można już odpalić program i sprawdzić jego działanie (wpisując pojedynczą cyfrę i wciskając enter). Zauważ, że dla jakiegokolwiek innego znaku niż cyfra wyskakuje parse error. Dzieje się tak dlatego, że parser dostaje inny typ tokenu niż DIGIT i nie może go dopasować do żadnej produkcji (czyli innymi słowy - parser napotkał na błąd składniowy).

Modyfikacja parsera, tak, by dodawał dwie cyfry do siebie.

Dotychczas nasz parser nie robił absolutnie nic ciekawego. Można powiedzieć, że każdy poprawny program składał się w nim z pojedynczej cyfry. Teraz spróbujemy dodać dwie cyfry do siebie. Wykorzystamy w tym celu dalsze zmienne z dolarem: $2 i $3, a także zmienną odpowiadającą lewej stronie produkcji: $$.

Jedyne, co tak naprawdę musimy w tym miejscu zrobić, to zmodyfikować regułę gramatyczną dla symbolu expr na następującą:

expr : DIGIT '+' DIGIT { 
    $$ = $1 + $3; //działamy na wartościach semantycznych
    printf("%d + %d = %d\n", $1, $3, $$);
     };

Jak widać, wykonujemy działania na wartościach semantycznych, gdyż są to zwykłe liczby typu int. Przykładowe wykonanie zmodyfikowanego programu może wyglądać następująco:

astral@astral-laptop:~/Programming/Bison$ ./tutorial2
1+5
1 + 5 = 6
astral@astral-laptop:~/Programming/Bison$

Warto zauważyć, że znak '+' nie musi być (przynajmniej na razie) w żaden specjalny sposób obsługiwany. Tak naprawdę, moglibyśmy zmienić regułę na następującą:

expr : DIGIT '_' DIGIT { 
//...

… a program wciąż by wykonywał dodawanie dla danych wejściowych np. 1_6. Nie powinno to nikogo dziwić - produkcja służy tylko do dopasowania, natomiast działania na wartościach semantycznych definiują, co tak naprawdę się dzieje w ramach obsługi produkcji.

Wprowadzenie prostej rekursji.

Rekursja w produkcji gramatycznej polega na tym, że ten sam symbol pojawia się po lewej i po prawej stronie produkcji. W przypadku rekursji zawsze musi istnieć również taka reguła, która pozwala wyjść z rekursji. Prześledzimy to na przykładzie naszego przykładu, rozbudowując go o możliwość dodawania dowolnej liczby cyfr do siebie.

Aby osiągnąć ten cel, musimy zmodyfikować gramatykę parsera w następujący sposób:

expr : DIGIT;
 
expr : expr '+' DIGIT { 
    $$ = $1 + $3; 
    printf("%d + %d = %d\n", $1, $3, $$); 
};

W ten sposób mówimy parserowi: np. "1 to expr wg. reguły pierwszej. 1+4 to też expr wg. reguły drugiej, bo 1 to expr wg. reguły pierwszej. 1 + 4 + 5 to też expr wg. reguły drugiej, bo 1 + 4 to expr wg. reguły drugiej, bo 1 to expr. wg. reguły pierwszej. 1+4+5+6 to też expr …". Takie rozumowanie mozna by ciągnąć w nieskończoność, ale warto zauważyć, że zawsze kończy się ono na regule pierwszej. To jest właśnie ta reguła, która wyprowadza nas z rekursji.

Teraz można sobie wygenerować i skompilować ten przykład. Przykładowa sesja z programem wygląda następująco:

astral@astral-laptop:~/Programming/Bison$ ./tutorial3
1+2+4+6
1 + 2 = 3
3 + 4 = 7
7 + 6 = 13
astral@astral-laptop:~/Programming/Bison$

Na tym przykładzie widać też to sens używania zmiennej $$ - to co było najpierw $$ potem stało się $1, więc konieczne było obliczenie watrości semantycznej $$ żeby parsowanie mogło być kontynuowane.

astralastral

Literatura:

Manual do Bisona jest całkiem dobrze napisany i może nawet wyjaśnić parę rzeczy osobom, które nie do końca rozumieją wykład.

O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-Share Alike 2.5 License.