Analiza składniowa

Wstęp

Analiza składniowa ma miejsce wówczas, gdy wczytujemy dane o pewnej określonej składni. Zadaniem analizatora składniowego (tzw. parsera) jest sprawdzenie, czy dane są poprawne składniowo i rozpoznanie struktury składniowej wczytywanych danych.

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

Zanim poznamy język specyfikacji dla Bison'a i Yacc'a, musimy zapoznać się z pojęciem gramatyk S-atrybutywnych. (Nie jest to nic skomplikowanego, a ta odstraszająca nazwa pochodzi stąd, że jest wiele różnych gramatyk atrybutywnych. My jednak nie będziemy ich tutaj omawiać.)

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 $X \to B_1B_2\dots B_k$, atrybut X-a oznaczamy przez $\$\$$, a atrybut Bi przez $\$i$.

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.

Przykład

Przypomnijmy sobie jednoznaczną gramatykę wyrażeń arytmetycznych:

\begin{eqnarray*}
E &\to& E+S \;\vert\;E-S \;\vert\;S \\
S &\to& S*F \;\vert\;S/F \;\vert\;F\\
F &\to& \emph{liczba} \;\vert\;(E)\\
\end{eqnarray*}


W tym przypadku liczba jest dla nas terminalem, gdyż jest to leksem rozpoznawany przez skaner. Oto gramatyka S-atrybutywna obliczająca wartość wyrażenia:

\begin{displaymath}
\begin{array}{rclcl}
E &\to& E+S &  & \$\$ = \$1 + \$3  ...
...& \$\$ = \$1 \\
F &\to& (E) &  & \$\$ = \$2 \\
\end{array} \end{displaymath}

A oto drzewo wyprowadzenia dla wyrażenia 42 + 5 * 2 wzbogacone o obliczone atrybuty

\begin{displaymath}
\xymatrix{
& & (E,52) \ar@{-}[dl] \ar@{-}[d] \ar@{-}[dr] \...
...czba},2) \\
& (\textsl{liczba},42) & (\textsl{liczba},5)
}
\end{displaymath}

Tak więc obliczona wartość całego wyrażenia to 52.

Sposób działania parsera

Bison został zaprojektowany tak, aby współpracował razem z Flex'em. Kod wygenerowany przez Bison'a na podstawie specyfikacji parsera może być kompilowany razem z kodem wygenerowanym przez Flex'a na podstawie specyfikacji skanera. W szczególności żetony są definiowane w specyfikacji parsera, a ich definicje w języku programowania są umieszczane w kodzie parsera. Natomiast w kodzie skanera można z nich korzystać.

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.

Specyfikacje parserów dla Bison'a

Specyfikacja dla Bison'a składa się z trzech części, oddzielonych od siebie wierszami postaci ,,%%'':

Przykład

Zbudujemy prosty kalkulator wzbogacony o zmienne. Będzie on przyjmował dwa rodzaje poleceń:
SET identyfikator = wyrażenie
PRINT wyrażenie
Polecenie SET powoduje przypisanie wartości wyrażenia na zmienną. Polecenie PRINT powoduje wypisanie wartości wyrażenia. Każde polecenie musi znajdować się w osobnym wierszu. Wyrażenia mogą zawierać nazwy zmiennych. Nazwy zmiennych mają postać [A-Za-z][A-Za-z0-9]*. Poza tym, składnia wyrażeń jest taka jak w poprzednich przykładach. Początkowo wszystkie zmienne mają wartość 0. W danych może pojawić się co najwyżej 1000 różnych nazw zmiennych.

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; 
      }
[ $\backslash$t] ;
[$\backslash$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: '$\backslash$n'
    | CMD_SET ID '=' exp '$\backslash$n' { dict_set($2,$4); }
    | CMD_PRINT exp '$\backslash$n' { printf("%d$\backslash$n",$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, "%s$\backslash$n", s);
}

Przykład

[[Przykład pokazujący przekazywanie stringów jako atrybutów]]

[[Opisać i dodać przykład z atrybutami różnych typów %union, %token z typem i %type.]]]

[[[JavaCup i JFlex]]]

Kompilacja programów generowanych przez Flex'a i Bison'a

Zodnie z przyjętą konwencją, specyfikacje dla Flex'a to pliki z rozszerzeniem .l, a specyfikacje dla Bison'a to pliki z rozszerzeniem .y. Załóżmy, że takie specyfikacje mamy w plikach spec.l i spec.y. Oba narzędzia, Flex i Bison, są tak zaprojektowane, żeby ze sobą współpracowały. Tak więc kod wygenerowany przez Bison'a oczekuje dokładnie takiej funkcjonalności, jakiej dostarcza kod wygenerowany przez Lex'a.

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.y

W 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.y

Plik 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.

Podsumowanie

W tym wykładzie poznaliśmy generator analizatorów składniowych Bison oraz związane z nim pojęcie gramatyk S-atrybutywnych. Umiejętność korzystania z Bison'a będzie jeszcze przedmiotem ćwiczeń laboratoryjnych.

Skorowidz

Praca domowa

Odwrotna notacja polska (ONP) to sposób zapisu wyrażeń, w którym najpierw podajemy argumenty, a potem operację. Jeżeli wiadomo ile argumentów mają operacje (a w przypadku operacji arytmetycznych tak jest -- mają one po dwa argumenty), to w ONP nie są potrzebne nawiasy. Na przykład, wyrażenie 2*(3+5) zapisane w ONP ma postać $2 3 5 + *$. Nota bene, wyrażenie zapisane w ONP to gotowy program dla maszyny stosowej, patrz Ćwiczenia.

Napisz specyfikację (dla Lex'a i Bison'a) analizatora, który wczyta wyrażenie arytmetyczne i wypisze je w ONP.

Ćwiczenia

  1. Napisz specyfikację (dla Lex'a i Bison'a) analizatora, który wczyta wyrażenie arytmetyczne i wyznaczy wielkość stosu potrzebnego do obliczenia wyrażenia przez maszynę stosową.

    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.

  2. Napisz specyfikację (dla Lex'a i Bison'a) analizatora, który wczyta wyrażenie arytmetyczne i wyznaczy maksymalną głębokość wyrażenia. Na przykład dla 3 + 3*(5 - 1) wynikiem powinno być 3, a dla (2 - 1) + (1 - 2) wynikiem powinno być 2.
  3. Rozszerz przykład kalkulatora z wykładu o możliwość definiowania nazwanych wyrażeń. Wartość takiego wyrażenia zależy od wartości zmiennych i jest obliczana za każdym razem, gdy takie wyrażenie jest używane.
  4. Rozważamy następujący rodzaj kompresji słów nad alfabetem {0,1}. Mając dane słowo s (o długości będącej potęgą dwójki, |s|=2i), jeśli:
    • s składa się z samych znaków 0, s = 02i, to jego kodem jest 0,
    • s składa się z samych znaków 1, s = 12i, to jego kodem jest 1,
    • w przeciwnym przypadku napis s jest dzielony na równe części s1 i s2 długości 2i-1, s=s1s2, a jego kod jest postaci: $9 \textsl{kod}(s_1) \textsl{kod}(s_2)$.
    Na przykład:
    • $\textsl{kod}(1)=1$,
    • $\textsl{kod}(0111)=99011$,
    • $\textsl{kod}(01001111)=9990101$,
    • $\textsl{kod}(00110101)=99019901901$.
    Napisz specyfikacje dla Lex'a i Bison'a dające program, który: wczyta zestaw zakodowanych słów, po jednym w wierszu i dla każdego kodu wypisze jego odkodowaną postać.