Flex i Bison/Prosty kalkulator - parser
Kod parsera prostego kalkulatora wygląda następująco
%{
#include <stdlib.h>
#include <stdio.h>
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
[edytuj]%{
#include <stdlib.h> /* (1) */
#include <stdio.h>
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
[edytuj]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
[edytuj]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
[edytuj]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
[edytuj]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
[edytuj]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