Bison jest generatorem parserów typu LALR. Bison generuje funkcję analizatora składniowego, która współpracuje z dostarczoną przez użytkownika funkcją analizatora leksykalnego. Skaner znajduje w strumieniu wejściowym podstawowe jednostki leksykalne zwane tokenami i na żądanie dostarcza je parserowi. Parser sprawdza, czy tokeny układają się zgodnie z regułami gramatycznymi zdefiniowanymi przez jego twórcę. Gdy uda się znaleźć skrukturę odpowiadającą jakiejś regule, wykonywany jest kod dołączony do tej reguły, zwany akcją.
Przy pomocy bison-a można tworzyć parsery w sposób pokazany na poniższym rysunku. Wygenerowany przez bison-a parser wymaga podania kodu skanera. Najczęściej kod skanera jest generowany przy pomocy flex-a.
Specyfikacja dla bison-a ma układ podobny do specykicji flex-a:
{deklaracje}
%%
{reguły}
%%
{procedury}
W sekcji deklaracje pomiędzy znakami %{ i %} umieszczany jest kod C, który ma być wstawiony bezpośrednio na początku generowanego programu. Następnie umieszczane są deklaracje tokenów. Nazwy tokenów zwyczajowo pisane sa duzymi literami.
%token NAZWA1 NAZWA2 NAZWA3
To najważniejsza sekcja. Tu umieszczamy reguły gramatyczne.
Ogólna postać reguły jest następująca:
<lewa strona> : <alternatywa 1> {akcja 1}
| <alternatywa 2> {akcja 2}
...
| <alternatywa n> {akcja n}
;
Przykładowo produkcje, które zapisywaliśmy wczesniej jako:
E --> E + T | T
T --> 0 | ... | 9
w bison-ie można zapisać jako:
wyr : wyr '+' term
| term
;
term : CYFRA
;
Symbole terminalne pojawiające się w naszej gramatyce są dwojakiego rodzaju:
%token NAZWA_TERMINALA);
Nazwa niezadeklarowana jako token traktowna jest jako nieterminal. Każdy z symboli nieterminalnych musi przynajmniej raz pojawić się po lewej stronie reguły.
Z każdą regułą skojarzona może być akcja semantyczna (kod w c zawarty w nawiasach { i }). Akcja jest wykonywana w momencie, gdy parser napotka strukturę, która została określona przez regułę. Akcje można umieszczać także wewnątrz reguł.
Akcje mogą zwracać wartości i korzystać z wartości zwróconych przez inne akcje. Do tego celu wykorzystuje się zmienne $$, $1, $2, $3... Zmienna $$ przypisuje wartość do symbolu po lewej stronie reguły, zaś zmienne $1, $2, $3... zawierają wartości odpowiadające kolejnym składnikom reguły, np.
wyr : wyr '+' term { $$ = $1 + $3; }
/*
$$ oznacza wartość zwracaną przez akcję,
$1 oznacza wartość skojarzoną z symbolem wyr (po prawej stronie produkcji),
$3 oznacza wartość skojarzoną z symbolem term,
podstawienie $$ = $1 + $3 spowoduje, że akcja zwróci wartość będącą sumą
wartości skojarzonych ze składnikami 1 i 3
*/
Jeżeli nie zdefiniowano inaczej domyślnie wartością reguły staje się wartość pierwszego składnika, tj.
A : B { $$ = $1; } ; oznacza to samo co A : B ;
Użytkownik musi dostarczyć bison-owi analizator leksykalny odpowiedzialny za bezpośrednie kontrolowanie wejścia i dostarczanie symboli terminalnych do parsera. Taką funkcję można wygenerować przy pomocy flex-a lub napisać własnoręcznie (int yylex()). Funkcja skanera zwraca na żądanie parsera numer kolejnego tokenu. Konkretna wartość danego tokenu jest dostarczana parserowi jako atrybut poprzez predefiniowaną zmienną yylval.
Wewnątrz sekcji procedury pomocnicze często umieszczane są procedury obsługi błędów.
Komantarze c (np. /* komentarz */) mogą być umieszczone w dowolnym miejscu specyfikacji.
Więcej informacji można znaleźć w dokumentacji programu bison.
Poniżej znajduje się przykład specyfikacji bardzo prostego parsera.
/* example.y - bardzo prosty parser */
/* wszystkie nazwy tokenow majace wiecej niz jeden znak musza byc zadeklarowane */
%token LETTER
%%
/* gdy na wejsciu pojawi sie symbol terminalny NUM zostanie wywolana ponizsza akcja */
input: LETTER { printf("rozpoznano -%c\n", $1); };
/* do przekazywania wartosci semantycznych pomiedzy regulami sluza tzw. pseudozmienne;
akcja moze zwrocic wartosc przez podstawienia pseudozmiennej $$;
pseudozmiennej $1 uzyto w przykladzie, aby wypisac wartosc tokenu NUM */
%%
#include "lex.yy.c"
main() {
/* aby rozpoczac parsing trzeba wywolac funkcje yyparse */
yyparse();
}
/* gdy funkcja yyparse wykryje blad wywoluje funkcje yyerror */
int yyerror(char *s) {
printf("blad: %s\n", s);
}
Źródła: example.y
/* examplelex.l - skaner wspolpracujacy z parserem example.y */
/* zmienna globalna yylval sluzy do przekazywania parserowi atrybutu tokenu
(wartosci semantycznej); zmienna yylval powinna jest typu YYSTYPE */
%%
-[abc] { yylval =yytext[1]; return LETTER; }
/* po dopasowaniu ciagu wejsciowego do yylval podstawiamy znak znajdujacy sie po -,
funkcja yylex konczy swoje dzialanie i zwraca numer dopasowanego tokenu */
.|\n ;
Źródła: examplelex.l
Przygotowany plik example.y podajemy na wejście bisona. W wyniku otrzymujemy plik example.tab.c zawierający kod parsera. Opcja -d powoduje wygenerowanie pliku nagłówkowego example.tab.h zawierającego deklaracje tokenów (dla celów komunikacji parsera ze skanerem).
bison -d example.y
Przygotowujemy plik examplelex.l i generujemy kod skanera lex.yy.c poleceniem:
flex examplelex.l
Kompilujemy wygenerowany wcześniej kod poleceniem:
gcc -o example example.tab.c -lfl
Otrzymujemy program wynikowy example. Możemy go uruchomić przykładowo podając na wejście plik_testowy:
./example <plik_testowy
Poniższy przykład przedstawia jak zmienić domyślny typ tokenu z wykorzystaniem makra YYSTYPE.
/* char.y - przyklad ilustrujacy przedefiniowanie typu tokenu z int na char */
%{
#define YYSTYPE char
%}
%token T_CHAR
%%
input :
| input '\n' { YYACCEPT; }
| input znaki '\n'
;
znaki : znaki T_CHAR { printf("Znaleziono: %c\n", $2); }
| T_CHAR { printf("Znaleziono: %c\n", $1); }
;
%%
#include "lex.yy.c"
main(){
yyparse();
}
int yyerror(char *s) {
printf("blad: %s\n", s);
}
Źródła: char.y
/* charlex.l - skaner wspolpracujacy z parserem char.y */ %% [a-zA-Z] yylval = yytext[0]; return(T_CHAR); .|\n return(yytext[0]);
Źródła: charlex.l
Poniżej umieszczonone są przykłady specyfikacji bison-a wykorzystujące fragmenty gramatyki wyrażeń arytmetycznych. Oba parsery mają w zamierzeniu działać jak kalkulator, czytać z wejścia wyrażenia arytmetyczne i wypisywać na wyjście wyniki obliczeń.
/* add.y - wygenerowany parser bedzie wykonywal dodawanie */
%token NUM
%%
input :
| input '\n'
| input expr '\n' { printf("%d\n",$2); }
;
expr : expr '+' NUM { $$ = $1 + $3;}
| NUM
;
%%
#include "lex.yy.c"
int yyerror(char *s) {
printf("blad: %s\n", s);
}
main(){
yyparse();
}
Źródła: add.y
/* addlex.l - skaner wspolpracujacy z parserem add.y */ %% [0-9] yylval = atoi(yytext); return(NUM); .|\n return(*yytext);
Źródła: addlex.l
/* exp.y - wygenerowany parser bedzie wykonywal odejmowanie */
%{
#include <stdio.h>
%}
%token NUM
%%
input: /* empty */
| input line
;
line: '\n'
| exp '\n' { printf("%d\n", $1); }
;
exp: NUM
| exp '-' exp { $$ = $1 - $3; }
| '(' exp ')' { $$ = $2; }
;
/* Jezeli na wejsciu parsera podamy ciag 4-3-1, to otrzymamy 2. Dlaczego?
Co zrobic, aby parser wypisywal poprawny wynik, tutaj 0? */
/* Nawet jesli podczas analizy gramatyki bison wykryje konflikt, to mimo to wygeneruje parser.
- konflikt shift/reduce jest rozstrzygany na korzysc shift
- konflikt reduce/reduce jest rozstrzygany na korzysc reguly wystepujacej wczesniej
w specyfikacji */
%%
#include "lex.yy.c"
int yyerror(char *s) {
fprintf(stderr, "blad: %s\n", s);
}
main() {
yyparse();
}
Źródła: exp.y
/* explex.l - skaner wspolpracujacy z parserem exp.y */ %% [ \t] ; [0-9]+ yylval = atoi(yytext); return NUM; .|\n return *yytext;
Źródła: explex.l
Proszę przeanalizować, skompilować i uruchmić przykłady przedstawione na tej stronie.
Proszę stworzyć Makefile, który ułatwia tworzenie parserów z wykorzystaniem bison-a i flex-a.
Proszę napisać parser bardzo wąskiego podzbioru Pascal-a. Parser powienien rozpoznawać: instrukcję podstawienia :=, procedurę writeln(), zmienne jednoliterowe, stałe liczbowe typu Integer. Przykładowy plik testowy: toy_pascal.
Proszę rozszerzyć parser z poprzedniego ćwiczenia o rozpoznawanie instrukcji if-then.