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

%{
    #include <stdlib.h> /* (1) */
    #include <stdio.h>
    int yylex(void);  /* (2) */
    void yyerror(char* );
%}
%token INTEGER

1. W definicjach najpierw dołączamy potrzebne pliki
2. Następnie definiujemy nagłówki standardowych funkcji dostępnych w Bisonie by mogły być później dołączone do leksera
3. 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) */
;

1. Wyrażenie może być sumą wyrażenia i 'iloczynu'
2. może być różnicą wyrażenia i iloczynu
3. 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.

1. Terminal może być wyrażeniem w nawiasach. Wtedy cała zabawa zaczyna się od początku.
2. 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

1. Definicja funkcji wbudowanej yyerror która jest wywoływana w przypadku wystąpienia błędu składni
2. Oraz definicja funkcji main