W kolejnych wpisach pokażę jak zbudować własny, prosty interpreter. Na początek zacznę od budowy interpretera, który będzie interpretował wyrażenia:
<liczba> + <liczba> <liczba> - <liczba>
Jako <liczba> będzie można wprowadzić liczbę naturalną. Ilość działań na razie ograniczyłem do dwóch (dodawanie i odejmowanie).
Aby zbudować interpreter będę potrzebował parser oraz lekser. Do budowy parsera wykorzystam narzędzie yacc, a do budowy leksera narzędzie flex.
Yacc
Do działania parsera potrzebny będzie mi opis gramatyki.
expression:
NUM
| expression '+' expression
| expression '-' expression
;
Na podstawie powyższego opisu gramatyki przygotuję plik dla programu yacc. Plik ten składa się z trzech sekcji rozdzielonych znacznikiem %%. Pierwsza sekcja służy do umieszczenia deklaracji i definicji potrzebnych do skonfigurowania parsera. Druga sekcja służy do opisania gramatyki. Trzecia sekcja służy do wprowadzenia dodatkowego kodu w języku C.
%start expression
%token NUM
%left '-' '+'
%%
expression:
NUM
| expression '+' expression
| expression '-' expression
;
%%
int main (int argc, char **argv) {
return yyparse();
}
W pierwszej sekcji pliku (część pliku przed pierwszym znacznikiem %%) wskazałem, że parser ma rozpoczynać analizę składniową od symbolu expression (polecenie %start). Wskazany został również wykorzystywany token, który zostanie przekazany przez wygenerowany w późniejszym czasie lekser (patrz niżej). Wyrażenie %left określa sposób wiązania do lewej – innymi słowy w jaki sposób parser ma zinterpretować wyrażenie 1-2-3, czy jako (1-2)-3 czy jako 1-(2-3).
W drugiej sekcji pliku (część pliku po pierwszym znaczniku %%) zawiera definicję naszej gramatyki.
W części trzeciej znajduje się definicja funkcji main, której jedynym zadaniem jest wywołanie naszego parsera.
Powyższy plik zapisałem jako parser.y. Aby wygenerować kod dla parsera należy podać komendę:
yacc -d parser.y
W wyniku działania programu yacc powstały pliki y.tab.c oraz y.tab.h. Spróbujmy skompilować wygenerowany plik i … pojawiły się niestety błędy. Musimy dodać do pliku parser.y jeszcze kilka definicji potrzebnych dla działania parsera tj. dodać dwie funkcje: yyerror oraz yylex. Uzupełniony plik zaprezentowany jest poniżej.
%{ #include <stdio.h> int yylex(void); void yyerror(char *s ); %} %start expression %token NUM %left '-' '+' %% expression: NUM | expression '+' expression | expression '-' expression ; %% void yyerror(char *s ) { fprintf (stderr, "%s\n", s); } int main (int argc, char **argv) { return yyparse(); }
Flex
W celu przygotowania leksera muszę zdefiniować listę tokenów, które będą wykrywane. Na potrzeby opisywanego przykładu potrzebuję token NUM oraz operatory + i -. Plik leksera składa się, podobnie jak plik parsera, z trzech części rozdzielonych znacznikiem %%. Pierwsza część to część deklaracyjna. Druga część pliku to definicja tokenów. W trzeciej części można umieścić dodatkowy kod w języku C, który ma zostać przepisany do generowanego leksera.
%% [0-9]+ return NUM; [-+] return *yytext; %%
Tak zdefiniowany lekser w zasadzie mógłby wystarczyć ale dodamy jeszcze reguły ignorujące białe znaki oraz generujące błąd w przypadku napotkania innych znaków niż opisane wcześniejszymi regułami.
%{ #include <stdio.h> #include "y.tab.h" void yyerror(char *s ); %} %% [0-9]+ return NUM; [-+] return *yytext; [ \t] ; . yyerror("Niepoprawny znak"); %%
Powyższy plik zapisałem jako scanner.l. Aby wygenerować kod leksera należy wykonać komendę:
flex scanner.l
W wyniku działania programu yacc oraz flex zostały wygenerowane pliki y.tab.c, y.tab.h oraz lex.yy.c. Aby skompilować nasz interpreter musimy wykonać następujące polecenie:
gcc y.tab.c lex.yy.c -o interpreter -ll
Jeżeli kompilacja przebiegła bez problemu to możemy uruchomić już nasz interpreter poleceniem:
./interpreter
Wpiszmy wyrażenie 1+1 i naciśnijmy klawisz enter – wyświetlił się komunikat syntax error. Oznacza to, że gramatyka nie działa poprawnie. Wprowadziłem kilka zmian – m.in. aby lekser oraz parser wykrywały naciśnięcie klawisza enter.
Plik parser.y
%{
#include <stdio.h>
int yylex(void);
void yyerror(char *s );
%}
%start expression_list
%token NUM
%left '-' '+'
%%
expression_list:
expression_list expression '\n'
| expression_list '\n'
|
;
expression:
NUM
| expression '+' expression
| expression '-' expression
;
%%
void yyerror(char *s )
{
fprintf (stderr, "%s\n", s);
}
int main (int argc, char **argv) {
return yyparse();
}
Plik scanner.l
%{
#include <stdio.h>
#include "y.tab.h"
void yyerror(char *s );
%}
%%
[0-9]+ return NUM;
[-+\n] return *yytext;
[ \t] ;
. yyerror("Niepoprawny znak");
%%
Po kolejnej kompilacji oraz uruchomieniu, interpreter poprawnie obsługuje wprowadzane wyrażenia – niestety nasz interpreter nie wykonuje obliczeń 🙁
Dlatego dodam opis zadań, które interpreter ma wykonywać po znalezieniu danego symbolu w naszej gramatyce.
%{
#include <stdio.h>
int yylex(void);
void yyerror(char *s );
%}
%start expression_list
%token NUM
%left '-' '+'
%%
expression_list:
expression_list expression '\n'{ printf(" = %d\n",$2); }
| expression_list '\n'
|
;
expression:
NUM
| expression '+' expression { $$ = $1 + $3; }
| expression '-' expression { $$ = $1 - $3; }
;
%%
void yyerror(char *s )
{
fprintf (stderr, "%s\n", s);
}
int main (int argc, char **argv) {
return yyparse();
}
Ponownie trzeba wygenerować parser i lekser
yacc -d parser.y flex scanner.l
oraz skompilować
gcc y.tab.c lex.yy.c -o interpreter -ll
i uruchomić komendą
./interpreter
W ramach praktyki proponuję spróbować dodać dodatkowe dwa działania czyli mnożenie i dzielenie. Pamiętajcie proszę, że trzeba zmodyfikować zarówno plik leksera (dodać rozpoznawanie znaków * i / – najlepiej dodając te dwa znaki w linijce [-+\n]) oraz parsera ( dodając w definicji gramatyki odpowiednie wpisy).
Makfile
W celu ułatwienia kompilacji i generowania leksera i prasera, przygotowałem Makefile.
LEX = flex
LFLAGS =
YACC = yacc
YFLAGS = -d
LDFLAGS = -ll
OBJ = scan.o parse.o
SRC = scan.l parse.y
all: interpreter
interpreter: $(OBJ)
$(CC) $(LDFLAGS) $(CPPFLAGS) $(CFLAGS) $(OBJ) -o $@
scan.o: parse.c
scan.c: scan.l
$(LEX) $(LFLAGS) -o $@ $^
parse.c: parse.y
$(YACC) $(YFLAGS) -o $@ $^
clean:
$(RM) *.o scan.c parse.c parse.h interpreter
Aby skorzystać z Makefile trzeba jeszcze zmienić nazwy stworzonych wcześniej plików parser.y i scanner.l:
mv parser.y parse.y mv scanner.l scan.l
Pliki y.tab.c, y.tab.h, yy.lex.c można już usunąć.
W pliku scan.l trzeba zmienić linię
#include "y.tab.h"
na
#include "parse.h"
Automatyczne generowanie plików leksera i parsera oraz ich kompilacja będzie następowała po wydaniu komendy:
make
Wydanie komendy
make clean
będzie powodowało usunięcie wygenerowanych plików leksera i prasera ora skompilowanego programu. Pliki źródłowe nie są usuwane.