interpreter, Linux, Mac, Raspberry Pi

Zbudujmy Interpreter (1) – yacc i flex w akcji

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.

Standard

Dodaj komentarz