Bison - druga praca domowa.

Artykuł powstał z pomocą Berchalaka i Archiosa.

Druga praca domowa nie polega (wbrew doniesieniom niektórych) na zaimplementowaniu leksera i parsera dla pseudoPascala, lecz na podmienienia pliku parser.c z przykładowego kompilatora własnym, stworzonym za pomocą programu Bison.

W tym artykule przyjrzymy się następującym apektom:

  1. Skąd wziąć gramatykę do pracy domowej.
  2. Skąd wziąć akcje towarzyszące produkcjom.
  3. Co jeszcze należy zrobić, żeby całość miała szansę zadziałać.
  4. Na co uważać podczas budowania aplikacji.

UWAGA: Jak zwykle nie będzie kodu (z wyjątkiem kodu oryginalnych plików kompilatora dostępnych na stronie przedmiotu dla wszystkich), żeby nie łamać regulaminu.

UWAGA 2: Zakładam, że przeczytałeś poprzednie dwa artykuły z tej strony dotyczące Bisona. Jeśli tego nie zrobiłeś, jest ryzyko, że nic nie zrozumiesz z podanych wskazówek.

UWAGA 3: Poziom merytoryczny tego i poprzednich dwóch artykułów może być bardzo niski, więc nie należy go traktować jako materiału do nauki, ale raczej jako zbiór wskazówek do pracy domowej.

Gramatyka.

Na całe szczęście, nasze zadanie w tym spekcie jest mocno uproszczone, bo można bez problemu zaadaptować gramatykę z slajdu 27 z wykładu. Należy ją jednak trochę przerobić, żeby uwzględniała inne typy tokenów, a także fakt, że w naszym kompilatorze program kończymy średnikiem.

Generalnie rzecz biorąc mamy następujące typy (można je zauważyć przeglądając choćby plik global.h:

  1. NUM
  2. ID
  3. DONE (opcjonalnie. Jeśli już jest jako token, to musi być zdefiniowany jako zero. można to osiągnąć pisząc w definicji po prostu DONE 0. W innym przypadku należy zmienić wartość DONE w pliku global.h z 260 na 0).
  4. DIV
  5. MOD

Przy czym te dwa ostatnie są wykorzystywane jako operatory.
Zdefiniowanie DONE jako tokenu nie jest konieczne, jeśli zamieni się jego wartość w pliku global.h z 260 na 0. W każdym bądź razie DONE musi mieć wartość 0 (czy to jako token, czy jako #define), bo inaczej nie będzie rozpoznane jako poprawne zakończenie danych wejściowych.

Po przerobieniu nasza gramatyka będzie miała następującą postać:

program może mieć postać wyrażenie ; program //czyli wyrażenie zakończone średnikiem po czym znowu program
program może być produkcją pustą; //produkcja pusta to coś typu "cośtam : ;" czyli bez niczego po prawej.

wyrażenie może mieć postać wyrażenie + symbol terminalny
wyrażenie może mieć postać wyrażenie – symbol terminalny 
wyrażenie może mieć postać symbolu terminalnego

symbol terminalny może mieć postać symbol terminalny * czynnik 
symbol terminalny może mieć postać symbol terminalny / czynnik 
symbol terminalny może mieć postać symbol terminalny MOD czynnik 
symbol terminalny może mieć postać symbol terminalny DIV czynnik 
symbol terminalny może mieć postać czynnika

czynnik może mieć postać NUM
czynnik może mieć postać ID
czynnik może mieć postać ( wyrażenie )

Warto zwrócić uwagę na trzy rzeczy. Po pierwsze, podzielenie typów tokenów na symbole terminalne i na czynniki w dosyć sprytny sposób radzi sobie z problemem priorytetu operatorów, gdyż zawsze działania dla symboli terminalnych i czynników wykonają się wcześniej niż dla wyrażeń i symboli terminalnych (patrz slajd 27).

Druga sprawa, to to, że ostatnia produkcja w zasadzie załatwia cały problem nawiasów.

Trzecia sprawa, to reguła: "program może być produkcją pustą;". Jeśli jej nie będzie, to wciśnięcie ctrl+d zaraz po rozpoczęciu programu jak i po wprowadzeniu i zatwierdzeniu poprawnej linijki (np. 2+3; enter) wywoła parse error, którego w tej sytuacji nie powinno być.

Akcje towarzyszące produkcjom

Pozostaje pytanie, co zrobić z wartościami semantycznymi. Jak można zauważyć w działaniu przykładowego kompilatora, program wypisuje po prostu na wyjście dane wejściowe, ale w innej kolejności. I tu dobra wiadomość - tą kolejność jest bardzo łatwo osiągnąć w Bisonie, ponieważ korzysta on z tzw. analizy bottom-up, zatem przy odpowiednio sformułowanej gramatyce ta znaki "ustawiają się same" w pożądanej kolejności i nie trzeba wykonywać żadnych dodatkowych kombinacji.

Co pozostaje zatem do zrobienia? Po prostu musimy w odpowiednim momencie wypisać odpowiednie rzeczy.

Pewne pojęcie o tym co i kiedy wypisać, dostarczają oględziny pliku emitter.c, gdzie widać następującą instrukcję switch:

switch (t)
{
    case '+':
    case '-':
    case '*':
    case '/':
      printf ("%c\n", t);
      break;
    case DIV:
      printf ("DIV\n");
      break;
    case MOD:
      printf ("MOD\n");
      break;
    case NUM:
      printf ("%d\n", tval);
      break;
    case ID:
      printf ("%s\n", symtable[tval].lexptr);
      break;
    default:
      printf ("token %d , tokenval %d\n", t, tval);
}

Zmienna t jest tutaj typem tokenu, a tokenval jest wartością semantyczną. Jeśli czytałeś poprzednie dwa artykuły, to wiesz, jak nazywają się zamienniki tych zmiennych, które stosuje Bison. Stąd można wyczytać następujący algorytm:

Jeśli trafisz na dodawanie to wypisz znak '+'
Jeśli trafisz na odejmowanie to wypisz znak '-'
Jeśli trafisz na mnożenie to wypisz znak '*'
Jeśli trafisz na dzielenie to wypisz znak '/'
Jeśli trafisz na operację DIV to wypisz ciąg znaków "DIV"
Jeśli trafisz na operację MOD to wypisz ciąg znaków "MOD"
Jeśli trafisz na liczbę to wypisz jej wartość semantyczną
jeśli trafisz na identyfikator, to wypisz symtable[wartość semantyczna tego identyfikatora].lexptr

Oczywiście każde wypisanie kończy się znakiem nowej linii.

To w zasadzie tyle. Każdy z tych "znaków rozpoznawczych" występuje tylko raz w gramatyce, więc nie powinno być problemu z dopasowaniem odpowiednich akcji do odpowiednich produkcji (jeszcze jedne wskazówka, w miarę oczywista - wypisuj wartość semantyczną albo wartość z tablicy symboli tylko dla produkcji, gdzie po prawej stronie jest pojedynczy symbol terminalny, bo i tak wszystko jest sprowadzane do symboli terminalnych podczas parsowania, zatem dodając wypisywanie gdzieś indziej, wypiszesz wartość semantyczną więcej niż raz).

Co jeszcze należy zrobić, żeby całość miała szansę zadziałać.

Należy wrócić do leksera i przerobić go trochę. Wcześniej lekser korzystał do przekazywania typu wartości semantycznej ze zmiennej globalnej tokenval. Bison deklaruje w tym celu własną zmienną o nazwie yylval. Należy zatem podmienić wszystkie wystąpienia tokenval na yylval.

Poza tym najlepiej usunąć z global.h deklaracje stałych NUM, DIV, MOD i ID, bo inaczej kompilator będzie płakał (i słusznie) że je redefiniujemy.

Trzeba też zmienić wsystkie wywołania funkcji parse() na wywołania funkcji yyparse() i wywalić deklarację funkcji parse() z global.h. Należy także dopisać deklarację yyparse() do global.h ponieważ (o dziwo) w pliku parser.h jej nie ma…

Oczywiście pamiętaj też o zaopatrzeniu parsera w funkcję yyerror(). Funkcja ta może korzystać z zmiennej globalnej lineno, żeby wypisywać, w której linijce wystąpił błąd.

Na co uważać podczas budowania aplikacji.

Po pierwsze, deklaracja funkcji yylex() musi być widoczna dla parsera, zatem należy ją umieścić w global.h (niektórzy z tego co wiem nie usuwali deklaracji funkcji lexan(), tylko robili w pliku lexa w epilogu dodatkową funkcję lexan(), która wywoływała po prostu yylex(). Teraz takie rozwiązanie może nie okazać się wystarczające).

Po drugie, dla parsera należy generować także plik nagłówkowy, który najlepiej włączać w pliku global.h, ponieważ lekser musi skądś znać zmienną yylval oraz typy tokenów, których oczekuje parser. Plik nagłowkowy należy też uwzględnić w makefile. Jak wygenerować taki plik nagłówkowy, opisałem w poprzednim artykule.

Wygodnie jest zrobić sobie regułę o nazwie mójpliknagłówekwygenerowanyprzezBisona.h, który będzie miał na liście zależności jedynie mójparserwygenerowanyprzezBisona.c. W ten sposób mamy pewność, że plik nagłowkowy zostanie wygenerowany, jeśli będzie potrzebny (oczywiście przy okazji generacji pliku .c parsera).

astralastral

Literatura:

Regulamin laboratorium to broń obosieczna;).

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