Kod parsera prostego kalkulatora wygląda następująco %{ #include #include int yylex(void); void yyerror(char* ); %}
%token INTEGER
%%
program : program line | line ;
line : expr '\n' { printf("%d\n",$1); } | '\n' ;
expr : expr '+' mulex { $$ = $1 + $3; } | expr '-' mulex { $$ = $1 - $3; } | mulex { $$ = $1; } ;
mulex : mulex '*' term { $$ = $1 * $3; } | mulex '/' term { $$ = $1 / $3; } | term { $$ = $1; } ;
term : '(' expr ')' { $$ = $2; } | INTEGER { $$ = $1; } ;
%%
void yyerror(char *s) { fprintf(stderr, "%s\n", s); }
int main(void) { /* yydebug = 1; */ yyparse(); return 0; } Straszne, prawda? A wiec po kolei. Plik dzieli się na trzy części rozdzielone podwójnym znakiem procent. Są to: definicje, reguły przetwarzania i podprogramy.
Definicje %{ #include /* (1) */ #include int yylex(void); /* (2) */ void yyerror(char* ); %} %token INTEGER W definicjach najpierw dołączamy potrzebne pliki Następnie definiujemy nagłówki standardowych funkcji dostępnych w Bisonie by mogły być później dołączone do leksera Na końcu definiujemy listę tokenów. Są one zamieniane na tym enum o wartościach od 256 do maksimum jakie przyjmuje int. w przypadku przekazywania do parsera przez lekser pojedynczych znaków, jak na przykład '+' w naszym wypadku, nie musimy tworzyć dla niego tokena ponieważ dostanie automatycznie wartość równą kodowi ASCII.
Reguły przetwarzania Reguła przetwarzania składa się z wyniku i składników i jest zapisywana jako > wynik : skladnik_1 skladnik_2 skladnik_n ; jeżeli jest można otrzymać wynik na wiele sposobów poszczególne kombinacje składników są rozdzielane znakiem '|' > wynik : skladnik_1 |skladnik_1 skladnik_2 | skladnik_nie_1 a_moze_jednak_1 ; Głowa Pierwszą regułą przetwarzania jest głowa. w naszym przypadku jest to : program : program line | line ; Od niej parser zaczyna dopasowywanie. W przypadku braku dopasowania reguły od razu jest ona odkładana na stos i następuje próba dopasowania jej elementów. Zapis 'program : program line' gwarantuje że reguła będzie wywoływana rekurencyjnie aż zostaną przetworzone wszystkie znaki.
Linia line : expr '\n' { printf("%d\n",$1); } /* (2) */ | '\n' /* (1) */ ; 1. Linia może być pusta, 2. lub zawierać wyrażenie arytmetyczne
Wyrażenie arytmetyczne Wyrażenia arytmetyczne mają różny priorytet dlatego gramatyka musi być jednoznaczna
expr : expr '+' mulex { $$ = $1 + $3; } /* (1) */ | expr '-' mulex { $$ = $1 - $3; } /* (2) */ | mulex { $$ = $1; } /* (3) */ ; Wyrażenie może być sumą wyrażenia i 'iloczynu' może być różnicą wyrażenia i iloczynu lub w szczególnym wypadku może być 'iloczynem' Jak już pisałem niedopasowane reguły są odkładane na stos. Tak więc w momencie dopasowania reguły dla przypadku (1) na stosie będzie się znajdować wynik wyrażenia, znak + oraz wynik iloczynu. Jak łatwo zauważyć $1, $2 i $3 są adresami elementów względem szczytu stosu. W przypadku dopasowania reguły przeważania wszystkie jej elementy są ściągane ze stosu a następnie jest na nowym szczycie stosu zapisywany jej wynik.
mulex : mulex '*' term { $$ = $1 * $3; } | mulex '/' term { $$ = $1 / $3; } | term { $$ = $1; } ; Tutaj mamy sytuację analogiczną jak dla dodawania i odejmowania. Jeśli byśmy chcieli dodać potęgowanie i pierwiastkowanie należało by wprowadzić kolejny poziom.
term : '(' expr ')' { $$ = $2; } /* (1) */ | INTEGER { $$ = $1; } ; To jest już na szczęście ostatnia reguła przetwarzania. Terminal może być wyrażeniem w nawiasach. Wtedy cała zabawa zaczyna się od początku. Lub może być liczbą której wartość znajduje się na stosie i została przekazana z leksera
Podprogramy void yyerror(char *s) /* (1) */ { fprintf(stderr, "%s\n", s); }
int main(void) { /* yydebug = 1; */ yyparse(); return 0; } W podprogramach możemy umieścić dowolny kod w języku C. W tym przypadku znajduje się tu definicja Definicja funkcji wbudowanej yyerror która jest wywoływana w przypadku wystąpienia błędu składni Oraz definicja funkcji main