Analiza składniowa powstała i rozwinęła się w ramach prac nad budową kompilatorów. Wszak kompilator musi najpierw wczytać i zanalizować składnię wczytywanego programu. Jej zastosowania są jednak dużo szersze. Praktycznie analizę składniową można zastosować w każdym programie, który wczytuje dane posiadające bardziej złożoną składnię, na przykład w: przeglądarkach internetowych, edytorach, systemach składu tekstu, programach konwertujących, czy jakichkolwiek aplikacjach posiadających pliki konfiguracyjne o określonej składni.
Konstrukcja parsera, zwłaszcza w przypadku kompilatorów lub bardziej skomplikowanych języków, to skomplikowane zadanie. Dlatego też powstały narzędzia wspomagające tworzenie parserów. Są to tzw. generatory analizatorów składniowych. Przykładem takiego generatora jest Bison, którego poznamy bliżej w tym wykładzie. Bison jest następcą generatora Yacc (ang. yet another compiler compiler -- jeszcze jeden kompilator kompilatorów). Bison jest przeznaczony do generowania parserów w C/C++. Jednak istnieje wiele generatorów parserów i w zasadzie dla każdego języka programowania można znaleźć generator przeznaczony dla danego języka.
Generator parserów na podstawie odpowiedniej specyfikacji generuje kod źródłowy analizatora składniowego. Specyfikacja taka zawiera opis składni wczytywanego języka oraz fragmenty kodu, które są wykonywane dla poszczególnych konstrukcji składniowych. Do opisu składni używa się jednoznacznych gramatyk bezkontekstowych.
Analiza składniowa stanowi kolejną fazę przetwarzania wczytywanych danych po analizie leksykalnej. Tak więc wejściem dla analizy składniowej jest strumień żetonów i atrybutów. Żetony stanowią symbole terminalne w gramatyce bezkontekstowej opisującej składnię. Efektem pracy parsera jest odtworzenie drzewa wyprowadzenia (a ściślej mówiąc jego obejścia) dla wczytywanego tekstu.
Generowane automatycznie parsery mają postać odpowiednich, deterministycznych automatów stosowych. Sposób generowania parserów wykracza poza ramy tego kursu.
Gramatyki S-atrybutywne to rozszerzenie gramatyk bezkontekstowych -- w takim sensie, że podstawowym składnikiem gramatyki S-atrybutywnej jest jednoznaczna gramatyka bezkontekstowa. (Gramatyka musi być jednoznaczna, żeby dla każdego słowa z języka istniało tylko jedno możliwe drzewo wyprowadzenia.)
Natomiast dodatkowo w gramatyce S-atrybutywnej z każdym węzłem w drzewie wyprowadzenia wiążemy pewną obliczaną wartość nazywaną atrybutem. (Jeśli potrzebujemy wielu wartości, to możemy pomyśleć o atrybucie jak o n-ce, rekordzie czy strukturze złożonej z tych wartości.) Liśćmi drzewa wyprowadzenia są symbole terminalne, czyli żetony. Żetonom mogą towarzyszyć atrybuty, jeśli zostały wyznaczone przez skaner. Natomiast atrybuty towarzyszące nieterminalom, czyli węzłom wewnętrznym, są obliczane w trakcie analizy leksykalnej.
Atrybuty nieterminali obliczamy na podstawie atrybutów ich synów w drzewie wyprowadzenia. (Atrybuty takie są nazywane syntezowanymi -- stąd ,,S'' w nazwie tego rodzaju gramatyk.) Dla każdej produkcji podajemy w specyfikacji fragment kodu, który oblicza atrybut ojca na podstawie atrybutów synów. W kontekście produkcji postaci , atrybut X-a oznaczamy przez , a atrybut Bi przez .
Parser wywołuje te fragmenty kodu obliczając atrybuty w odpowiedniej kolejności, od liści do korzenia (ang. bottom-up). Wynikiem całości obliczeń jest atrybut korzenia drzewa wyprowadzenia.
Parser wywołuje procedurę yylex żeby wczytywać kolejne leksemy. Wynikiem tej procedury powinien być żeton odpowiadający wczytanemu leksemowi. Zakłada się, że atrybut żetonu, jeśli jest obecny, to jest przypisany zmiennej yylval. Procedura yylex może również zwrócić znak ASCII -- wówczas leksemem jest pojedynczy wczytany znak.
Parser udostępnia funkcję int yyparse(). Wywołanie tej funkcji powoduje próbę wczytania słowa należącego do języka opisywanego przez gramatykę podaną w specyfikacji. Parser nie konstruuje drzewa wyprowadzenia jako struktury danych, ale wykonuje takie czynności, jakby obchodził je w porządku postfiksowym. Dla każdego odwiedzanego nieterminala w drzewie wyprowadzenia wykonywany jest fragment kodu odpowiadający zastosowanej dla niego produkcji. Jako ostatni wykonywany jest fragment kodu dla korzenia. Jeżeli w tym fragmencie kodu nie nastąpi powrót z procedury (return), to wejście ponownie jest parsowane. W przypadku wystąpienia błędu składniowego wywoływana jest procedura void yyerror (char const *s). Procedura ta musi być zdefiniowana.
Fragmenty kodu umieszczone w specyfikacji nie muszą tylko obliczać atrybuty. Mogą wykonywać dowolne czynności, np. wypisywać informacje na wyjście czy modyfikować globalne struktury danych. Trzeba jednak zdawać sobie sprawę, w jakiej kolejności różne fragmenty kodu są wykonywane.
nieterminal | : | prawa strona produkcji | {fragment kodu} |
| | prawa strona produkcji | {fragment kodu} | |
| | prawa strona produkcji | {fragment kodu} | |
; |
Skaner odróżnia słowa kluczowe SET i PRINT, liczby i identyfikatory. Wszystkie inne znaki są przekazywane dosłownie. Kod źródłowy specyfikacji skanera znajduje się w pliku calc.l.
%{ // Definicje żetonów pochodzące z Bison'a #include "skalk.tab.h" // Tablica zmiennych char *dict[1000]; int dict_size=0; // Odnajduje nazwę zmiennej w tablicy, lub ją dodaje int dict_find(const char *key) { int i; for(i=0; i<dict_size; i++) if (strcmp(key,dict[i])==0) return i; i=dict_size; dict_size++; dict[i]=(char *)malloc(strlen(key)+1); strncpy(dict[i],key,strlen(key)+1); return i; } %} INT [0-9]+ ID [A-Za-z][A-Za-z0-9]* %% PRINT { return CMD_PRINT; } SET { return CMD_SET; } {ID} { yylval=dict_find(yytext); return ID; } {INT} { yylval=atoi(yytext); return NUM; } [ t] ; [n]|. { return yytext[0]; } %%Parser pamięta w tablicy wartości zmiennych, oblicza wartości wyrażeń i przypisuje zmiennym wartości. Kod źródłowy specyfikacji parsera znajduje się w pliku calc.y.
%{ #include <stdio.h> // Tablica wartości zmiennych int d_value[1000]; // Odszukanie wartości zmiennej int dict_value(int key) { return d_value[key]; } // Przypisanie wartości zmiennej int dict_set(int key,int value) { d_value[key]=value; } %} %token NUM CMD_PRINT CMD_SET ID %% input: /* nic */ | input line ; line: 'n' | CMD_SET ID '=' exp 'n' { dict_set($2,$4); } | CMD_PRINT exp 'n' { printf("%dn",$2); } ; exp : exp '+' skl { $$ = $1 + $3 } | exp '-' skl { $$ = $1 - $3 } | skl ; skl : skl '*' czy { $$ = $1 * $3 } | skl '/' czy { $$ = $1 / $3 } | czy ; czy : NUM | ID { $$ = dict_value($1); } | '(' exp ')' { $$ = $2 } ; %% main() { // Wyzerowanie wartości zmiennych bzero(&d_value,sizeof(d_value)); yyparse(); } yyerror(s) char *s; { fprintf(stderr, "%sn", s); }
[[Opisać i dodać przykład z atrybutami różnych typów %union, %token z typem i %type.]]]
[[[JavaCup i JFlex]]]
Sposób kompilowania skanerów generowanych przez Flex'a został opisany w p. kompilacja-flex. Jest jednak jeden element, zdefiniowany w kodzie wygenerowanym przez Bison'a, z którego korzysta kod wygenerowany przez Lex'a. Są to definicje żetonów. Problem ten rozwiązuje się w ten sposób, że Bison może również wygenerować plik nagłówkowy zawierający definicje stałych reprezentujących żetony, a w kodzie skanera powinniśmy dołączyć go (dyrektywą #include). Tak więc najpierw powinniśmy wygenerować kod parsera (wraz z plikiem nagłówkowym zawierającym definicje żetonów), potem wygenerować kod skanera, a na koniec skompilować cały program.
Najprostsze wywołanie Bisona'a wygląda tak:
bison spec.yW jego wyniku Bison tworzy plik z kodem źródłowym parsera, o takiej samej nazwie jak specyfikacja, ale z rozszerzeniem .tab.c, czyli w naszym przypadku spec.tab.c. Jeśli chcemy, żeby Bison dodatkowo wygenerował plik nagłówkowy z definicjami żetonów, to musimy podać opcję -d:
bison -d spec.yPlik nagłówkowy ma taką samą nazwę jak specyfikacja, ale z rozszerzeniem .tab.h, czyli w naszym przypadku spec.tab.h.
Kompilując program powinniśmy skompilować razem wygenerowany kod skanera i parsera, wraz z ew. innymi plikami. Pamiętajmy przy tym o dołączeniu biblioteki fl wykorzystywanej przez skaner:
gcc ...spec.yy.c spec.tab.c -lfl.W przypadku programów (w C), których cały kod składa się tylko z kodu skanera i ew. parsera można skorzystać z prostego pliku Makefile. Wystarczy wówczas wydać tylko polecenie make, a ono już się samo zajmie wygenerowaniem skanera, parsera i kompilacją programu.
Napisz specyfikację (dla Lex'a i Bison'a) analizatora, który wczyta wyrażenie arytmetyczne i wypisze je w ONP.
Maszyna stosowa działa na następującej zasadzie: włóż liczbę na stos, zdejmij argumenty operacji arytmetycznej z wierzchołka stosu i włóż jej wynik na stos. Na przykład, obliczenie wyrażenia 2 + 3 * 5 wymaga stosu wielkości 3. Obliczenie to przebiega następująco: włóż 2 na stos, włóż 3 na stos, włóż 5 na stos, wykonaj mnożenie, wykonaj dodawanie. Obliczenie wyrażenia 3*5 + 2 wymaga stosu wielkości 2. Obliczenie to przebiega następująco: włóż 3 na stos, włóż 5 na stos, wykonaj mnożenie, włóż 2 na stos, wykonaj dodawanie.