Do realizacji zadań na pracownię z przedmiotu Metody Translacji dla IV roku Inżynierii Oprogramowania pomocne mogą być narzędzia wspomagające pracę twórcy kolejnego języka programowania. Takie narzędzia nazywa się często kompilatorami kompilatorów, gdyż praca z takimi programami przypomina pracę ze zwykłymi kompilatorami, tzn. na początku deklaruje się język (składnię i semantykę) w pewnym ustalonym formacie w pliku, a następnie plik ten jest przetwarzany ('kompilowany') za pomocą owych narzędzi. Narzędzia te wspomagają przede wszystkim konstrukcję analizatora składniowego (parsera) i analizatora leksykalnego, co w znacznym stopniu przyspiesza tworzenie kompilatora i pozwala na łatwe później jego modyfikacje. W znanych mi narzędziach danymi wejściowymi są produkcje bezkontekstowe definujące składnię języka wraz z akcjami semantycznymi, zaś wynikiem przetworzenia takiego pliku jest tekst program w znanym już języku (C, Java, Pascal). Aby otrzymać wykonywalną wersję programu, trzeba go jeszcze oczywiście skompilować. Otrzymany program jest już prawdziwym kompilatorem.
Pierwszym etapem konstrukcji kompilatora jest konstrukcja analizatora składniowego, sprawdzającego, czy podany tekst programu jest napisem zgodnym z podaną definicją. W dokumencie tym skupię się przede wszystkim na analizatorach składniowych opartych na idei automatów stosowych. W translatorach używa się szczególnej klasy automatów stosowych budowanych na podstawie gramatyki bezkontekstowej. Automaty te sprawdzają przynalezność słowa wejściowego do języka odtwarzając jego wyprowadzenie. Są znane dwie podstawowe strategie konstruowania takich analizatorów: zstępująca i wstępująca.
Analiza zstępująca (znana też jako analiza LL) polega na próbie wyprowadzenia z symbolu początkowego napisu będącego na wejściu. Jedną z możliwych realizacji takiego parsera jest program, w którym każdemu symbolowi nieterminalnemu odpowiada odrębna procedura, a każda taka procedura ma strukturę odpowiadającą odpowiedniej produkcji. W szczególności w procedurze tej wywoływane są odpowiednie procedury odpowiadające symbolom nieterminalnym z prawej strony produkcji. Przykładowo fragmentowi gramatyki
S -> A B A -> @ B -> b C
gdzie @ oznacza symbol pusty, może odpowiadać następujący szkielet programu w Pascalu:
procedure S;
begin
A();
B()
end;
procedure A()
begin
end;
procedure B()
begin
if input_char = 'b' then
C()
else
Parse_Error()
end;
Znane mi narzędzie do automatycznego generowania analizatorów typu LL nazywa się ANTLR (ANother Tool for Language Recognition). Jego realizacją jest projekt PCCTS (The Purdue Compiler Construction Tool Set). Więcej na ten temat można znaleźć na odpowiedniej liście dyskusyjnej.
Wadą takich kompilatorów jest ich stosunkowo mała stosowalność: gramatyki, dla których można konstruować kompilatory LL, muszą spełniać wiele istotnych ograniczeń, dlatego nie będziemy się nimi dalej zajmować.
Inną strategią jest analiza wstępująca. Polega ona na odtworzeniu ze słowa wejściowego wyprowadzenia tego słowa (stąd inna nazwa: bottom up analysis), aż do otrzymania symbolu początkowego danej gramatyki. Ta klasa gramatyk (zwana klasą LR) jest obszerna i wystarcza do wielu zastosowań, choć i ona, niestety, nie obejmuje wszystkich języków bezkontekstowych. Ceną, jaką trzeba zapłacić za lepszy analizator, jest algorytm konstrukcji parsera, który nie jest trudny, lecz wymaga pacochłonnych obliczeń. Nie będę go tu przytaczał. Na szczęście powstało wiele programów wspomagających pisanie parserów typu LR. Powszechnie nazywa się je YACC (Yet Another Compiler's Compiler) i pod taką nazwą występuje np. w UNIX'ie. Wszyscy następcy YACC'a używają podobnego formatu pliku wejściowego, który będzie omówiony w dalszej części tego dokumentu. YACC generuje jako plik wynikowy progam w C, akceptowany przez standardowy kompilator UNIX'owy cc. Razem z YACC'em stowarzyszony jest program lex, wspomagający konstuowanie analizatora leksykalnego. Obydwa narzędzia zwane są czasem odpowiednio bison i flex, ale o tym później.
Zazwyczaj parser nie odwołuje się bezpośrednio do wejścia; robi to poprzez analizator leksykalny, który nie tylko buforuje dane z wejścia, ale także dokonuje wstępnej analizy tekstu wejściowego. Doświadczenia pokazują, że wygodnie jest posługiwać się w analizatorze składniowym symbolami leksykalnymi (tokens) zamiast takich napisów jak liczby czy identyfikatory. Jest to bardzo wygodne, gdyż oddziela się fizycznie samą definicję struktury języka od pewnych szczegółów, takich jak postać liczby zmiennoprzecinkowej czy dopuszczania podkreślenia w nazwach zmiennych. Każdy symbol leksykalny zwykle jest zdefiniowany za pomocą pewnego wyrażenia regularnego. I tak na przykład symbolowi NUMBER może odpowiadać wyrażenie ([1-9][0-9]*)|0, a symbolowi IDENTIFIER wyrażenie [a-zA-Z][a-zA-Z0-9_]+. W ten sposób łatwo jest modyfikować różne detale bez zmiany samego parsera. Znaki, które nie zostaną "zrozumiane" przez analizator leksykalny, przesyłane sę w nie zmienionej postaci do parsera. Oczywiście, każdy symbol leksykalny przechowuje ciąg znaków, którym odpowiada. Można to narysować tak:
| WEJŚCIE | -> | analizator leksykalny | -> | analizator składniowy | -> | WYNIK |
Przykładowo, jeśli na wejściu pojawi się ciąg znaków "94873", to analizator leksykalny wysyła parserowi jedynie symbol "NUMBER".
Również programy yacc/lex opierają się na podobnej strukturze. Program wynikowy utworzony za pomocę yacc'a odwołuje się do wejścia poprzez funkcję yylex(), której rolą jest dostarczać znaków lub symboli leksykalnych, kiedy tylko parser sobie tego zażyczy. Funkcja ta nie jest generowana przez yacc'a, a jej definicja jest zupełnie dla niego nieistotna. Zazwyczaj odwołuje się ona do pliku, lecz oczywiście może też pobierać znaki z pamięci czy też nawet samodzielnie generować losowe znaki. Żąda się tylko, aby ta funkcja zwracała wartość typu int. Zwykle "małe" wartości (0-255) tej funkcji oznaczają, że wartością funkcji jest przeczytany znak. Większe zarezerwowane są dla symboli leksykalnych. Można sobie np. wyobrazić, że gdzieś w programie znajduje się deklaracja
#define NUMBER 566
a fragment funkcji yylex() wyględa następująco:
if (...) return NUMBER; ...
Oczywiście, definiując gramatykę można pisać tak:
... exp: exp '+' exp; exp: NUMBER ...
Niestety, napisanie złożonego analizatora składniowego nie jest zadaniem prostym, więc w pracy nad analizatorem leksyklanym można się wspomóc programem lex, którego rolą jest na podstawie podanych wyrażeń regularnych wygenerować ową funkcję yylex() spełniającą podane wyżej warunki. Używając powyższych programów można więc szybko i sprawnie napisać działający kompilator.
Przypuśćmy, że interesuje nas napisanie kalkulatora obliczającego wyrażenia podane w postaci ONP opisane gramatyką:
Exp -> Exp Exp '+' Exp -> Exp Exp '-' Exp -> Exp Exp '*' Exp -> Exp Exp '/' Exp -> NUMBER
Plik parser1.y definiujący gramatykę wraz z odpowiednimi akcjami semantycznymi wygląda następująco:
%{
#define YYSTYPE double
#include <math.h>
%}
%token NUM
%%
input:
| input line ;
line: exp '\n' { printf("%.10g\n",$1); } ;
exp: NUM { $$ = $1; }
| exp exp '+' { $$ = $1 + $2; }
| exp exp '-' { $$ = $1 - $2; }
| exp exp '*' { $$ = $1 * $2; }
| exp exp '/' { $$ = $1 / $2; }
;
%%
#include <ctype.h>
#include "lexer1.c"
int main()
{
printf("zaczynamy ... \n\n");
yyparse();
return 0;
}
#include <stdio.h>
yyerror(s)
char *s;
{
printf("%s\n",s);
}
Struktura pliku: plik podzielony jest na trzy części oddzielone znakami %%. W pierwszej części znajduję się deklaracje, m.in. deklaracja
%token NUMBER
deklarująca symbol leksykalny NUMBER. W nawiasach %{ i %} znajdują się niezbędne deklaracje, które stanowić będą później nagłówek programu w C. Wszystko to, co jest między tymi nawiasami jest dosłownie przepisywane na początek pliku wynikowego bez żadnej interpretacji. Każdy symbol nieterminalny można traktować jak zmienną, której można nadawać wartość. Zgodnie z konwencją przyjętą w C; jeśli nie zadeklarowano inaczej, to wszystkie symbole nieterminalne traktowane są jak zmienne typu int. W tym przykładzie za pomocą dyrektywy
#define YYSTYPE double
zadeklarowano, że wszystkie symbole nieterminalne są typu double.
W drugiej części pliku umieszczana jest deklaracja gramatyki wraz z akcjami semantycznymi umieszczonymi w nawiasach {}. Akcjami są fragmenty programu w C. Do wartości nieterminali odwołujemy się za pomocę znaku $: $$ oznacza symbol z lewej strony produkcji, symbol $1 oznacza pierwszy symbol po prawej stronie produkcji, $2 drugi itp., przy czym do numeracji wliczane są kolejno wszystkie symbole: terminalne, nieterminalne, leksykalne i akcje semantyczne. Na podstawie tej części konstruowana jest funkcja yyparse() definiująca analizator składniowy.
Trzecia część zawiera definicje odpowiednich funkcji (m.in. main()), w tym w pewnym miejscu może zawierać wywołanie funkcji yyparse().
Ten program nie jest jeszcze kompletny, brakuje jeszcze definicji funkcji yylex(), o której założyłem, że jej definicja jest w pliku lexer1.y. Można samodzielnie napisać tę funkcję, np. w taki sposób:
yylex()
{
int c;
while ((c = getchar()) == ' ' || c == '\t')
if ( c == '.' || isdigit(c))
{
ungetc(c, stdin);
scanf("%lf", &yylval);
return NUMBER;
}
if (c == EOF)
return 0;
return c;
}
Wtedy wystarczy wydać polecenie
yacc parser1.y
oraz skompilować otrzymany program w C
cc y.tab.c
co wyprodukuje pożądany program.
Jednak zamiast pracowicie konstruować analiazator leksykalny, wystarczy
skorzystać z programu lex generującego automatycznie taki analizator.
Odpowiedni plik lexer1.y dla lex'a może wyglądać
następująco:
%option noyywrap
%%
[ \t] ;
[0-9]+"."[0-9]+ { yylval = atof(yytext); return NUM; } ;
\n { return yytext[0]; }
. { return yytext[0]; }
%%
Po wydaniu polecenia
lex -t lexer1.y > lexer1.c
powstanie plik wynikowy, który wystarczy dołączyć do powyższego za pomocą dyrekrywy
#include
Znaczenie poszczególnych wierszy:
| [ \t]; | jeżeli napotkano znak spacji lub tabulacji to żadna akcja nie jest wykonywana, w praktyce oznacza to pominięcie znaków; |
| [0-9]+; { yylval = atof(yytext); return NUMBER; } ; | jeżeli zostało rozpoznane wyrażenie regularne będące dowolnym niepustym ciągiem cyfr, to za zmienną yylval zostanie podstawiona wartość tej liczby, zaś analizator leksykalny zakończy chwilowo pracę zwracając jako wartość wartość symbolu NUMBER, jest to ten sam symbol jaki został zadeklarowany w definicji parsera i nie trzeba go deklarować oddzielnie; |
| \n { return yytext[0]; } | jeżeli napotkano znak końca wiersza, to analizator leksykalny kończy chwilowo pracę i przekazuje ten znak parserowi. |
| [^ ] { return yytext[0]; } | jeżeli napotkano znak nie będący spacją, to należy go zwrócić parserowi, znak karetki ^ oznacza każde wyrażenie oprócz, np ^a to każdy znak prócz znaku a; zamiast tego można użyć . (kropki), oznacza ona każdy znak prócz znaku końca wiersza. |
Jak widać, nigdzie nie jest nic wspomniane o znaku końca pliku. Jeżeli jest deklaracja . (kropka) lub [^ ], to napotkany znak końca jest dopasowywany do takiego wyrażenia regularnego i zwracany parserowi, który sam już reaguje na niego. Pełny ciąg poleceń, które tworzą cały program to
lex leks.y yacc test.y cc y.tab.c
Jak już wcześniej napisałem, standardowo każdej produkcji jest przypisana wartość typu 'int'. Można w ten sposób 'zwracać' wartości wyżej. Można to zmienić deklaracją
#define YYSTYPE double
tak jak to podano w poprzednim przykładzie. W ten sposób nasz kalkulator może prowadzić obliczenia na liczbach zmiennoprzecinkowych. Jednak w przypadku tworzenia bardziej zaawansowanych kompilatorów konieczne może być posługiwanie się symbolami nieterminalnymi róznych typów. Aby to uzyskać w pierwszej sekcji definicji kompilatora trzeba zadeklarować unię, np. taką:
%union{
int it;
float fl;
char *name;
}
Jak widać, na końcu nie dajemy średnika. Każdemu symbolowi leksykalnemu i nieterminalnemu przypisujemy typ za pomocą dyrektywy:
%token <it> NUM %token <name> VAR %type <fl> exp
Do tych symboli odwołujemy się w akcjach semantycznych tak samo jak poprzednio, jednak interpretacja tych symboli jest nieco inna:
exp: VAR; {printf("%s ", $1); $$ = 0;}
| NUM; {$$ = (float)$1;}
; ...
Modyfikacji musi ulec analizator leksykalny. Zmienna yylval jest unią taką, jaka została wcześniej zadeklarowana. Odpowiedni plik dla lex'a może wyglądać np. tak:
char *i;
%option noyywrap
%%
[ \t] ;
[0-9]+ { yylval.it = atof(yytext); return NUM; }
[a-z]+ { i = malloc(yyleng); yylval.name = i; strcpy(i, yytext); return VAR;}
\n { return yytext[0]; }
[^ ] { return yytext[0]; }
%%
Pełny plik dla lex'a wygląda następująco:
%option noyywrap
%%
[ \t] ;
[0-9]+ { yylval.liczba = atoi(yytext); return NUM; } ;
true { return TRUE; }
false { return FALSE;} ;
or { return OR; } ;
[a-zA-Z]+ { yylval.zmienna = malloc(yyleng);
strcpy(yylval.zmienna, yytext);
return VAR; };
. { return yytext[0];};
\n { return yytext[0]; }
%%
a dla yacc'a
%{
#include <math.h>
%}
%union{
char bool;
int liczba;
char *zmienna;
}
%token <liczba> NUM
%token <zmienna> VAR
%token <bool> TRUE FALSE
%token OR
%type <liczba> exp
%type <bool> bexp
%left OR
%%
line: bexp '\n' { printf("%s \n", ($1 > 0 ? "prawdziwe" : "falszywe")); } ;
bexp: VAR { $$ = wartosc($<zmienna>1); }
| TRUE { $$ = 1; }
| FALSE { $$ = 0; }
| bexp OR bexp { $$ = $1 || $3; }
| exp '>' exp { $$ = $<liczba>1 > $<liczba>3; }
;
exp: NUM { $$ = $1; }
| exp exp '+' { $$ = $1 + $2; }
| exp exp '-' { $$ = $1 - $2; }
;
%%
#include <ctype.h>
#include "lexyy.c"
main()
{
printf("zaczynamy ... \n\n");
yyparse();
}
#include <stdio.h>
yyerror(s)
char *s;
{
printf("%s\n",s);
}
int wartosc(s)
char *s;
{
return 1;
}
W większości systemów UNIX'owych programy yacc i lex są dostępne w standardowym zestawie narzędzi dostarczanych wraz z systemem. W ramach pakietu GNU dostępnego zarówno na platfomy UNIX'owe jak i system DOS, dostępne są programy flex i bison odpowiadające funkcjonalnie lex'owi i yacc'owi. Dostępne są one na lokalnej sieci NOVELL.
Aby używać narzędzi GNU pod Novell'em konieczne jest ustawienie środowiska poleceniem
gnuc
ale przy WYŁĄCZONYCH nakładkach typu XTree czy Norton Commander. W przypadku braku koprocesora może być konieczne wydanie następującego polecenia:
set go32=emu h:\jezyki\gnuc\bin\emu487 gnuc
Razem z DOS-owskim GNU jest dostępny interaktywny help uruchamiany poleceniem 'info', chodzi się za pomocę klawisza <TAB> i <ENTER>. Wraca się wyżej klawiszami 'u' lub 'p'.
Między wersjami GNU i UNIX'owymi występują drobne różnice, które czasem mogą spowodować kłopoty przy 'przesiadaniu' się z yacca na bisona i odwrotnie. Z moich doświadczeń wynika, że wersje GNU są poprawne pod DOS'em jak i pod UNIX'em. Wszystkie podane programy są przetestowane pod GNU.
Jedną z istotnych różnic pomiędzy wszystkimi wersjami jest sposób nadawania domyślnych nazw wygenerowanym plikom C-owym. Panuje tu pewien nieporządek, lex i flex (odpowiednio yacc i bison) nadają pod UNIX'em nadają domyślnie różne nazwy, również flex i bison w zależności od uzywanego systemu operacyjnego (DOS a UNIX) nadają rózne nazwy. Nieporządek powiększa fakt, że informacje na ten temat podawane w dokumentacjach czasem są niezgodne ze stanem faktycznym, nie wiem, czy różnice mogą też wystąpić na różnych komputerach. Chcąc uzyskać przenośność odpowiednich zleceń generujących aplikację w środowisku GNU można używać parametru -y plik.c wymuszającego odpowiednią nazwę pliku wynikowego. Najprościej wszystkie polecenia wykonywać za pomocę własnego makrozlecenia bądź używajęc skryptów dla programów 'make' ('gmake' dla GNU pod UNIX'em). Poniżej zamieszczony jest przykładowy skrypt makefile:
Papierowa kopia tych dokumentów została przekazana do naszej biblioteki.
Podobne narzędzia do wyżej opisanych powstały także dla innych języków.
Miłosnicy Standard ML'a mogą używać ml-lex'a i ml-yacc'a. Dla języka JAVA opracowano JavaCC. Są też opracowane podobne programy dla innych języków, np. pascala.
A. Appel napisał 3 książki poświęcone projektowaniu kompilatorów i ich automatycznemu generowaniu w różnych językach programowania i środowiskach: C + Flex + Bison, Standard ML i JAVA. Na jego stronach można znaleźć definicje kompilatora TIGER w poszczególnych językach. Same książki są również znakomite.
Stronę opracował Marcin Młotkowski