Gramatyki Formalne cz II 3

Pary    S    X

(stan na wierzchołku stosu, symbol wejściowy)

są używane do indeksowania tablicy parsera dla wyznaczenia bieżącej akcji.

Akcja rnoże rnieć jedną z czterech postaci:

1.    shift s — przejście sterowane stanem s (do stanu s)

2.    reduce A □ B — redukcja przy użyciu produkcji A □ B

3.    accept — akceptacja wyrażenia wejściowego

4.    erroe — wykrycie błędu

Na podstawie każdej z tych wartości parser wykonuje pewną akcję na wejściu i na stosie, po czyrn sytuacja się powtarza. Konfiguracja parsera to para (cała zawartość stanu, niewczytane wejście)

Początkowa konfiguracja to (So, wejście! — wszystko, co na wejściu). Następna czynność to wyznaczenie konkretnej akcji będącą wartością elementu tablicy:

akcja [S_m,aj], gdzie S_m to stan na wierzchołku stosu, a aj pierwszy niewczytany symbol z wejścia.

Jeśli akcja [S_m, aj] = shift s, to następuje przejście do konfiguracji

(So Xi S-j... X_m Sm ajS, <lj+i <ln$)

So Xi S-i... X_m S_m ajS — na stosie aj+i a_n$ — na wejściu

czyli dopisanie do stosu symbolu z wejścia aj i symbolu stanu s. Jeśli akcja [S_m, aj] = reduce A =* B porser zmienia konfigurację na: {So X₁ S-j... X_m._r S_m._r As, «ij+i «i_n $1

gdzie s = go to [S_m._r, A], zaś r jest długością ES czyli prawej strony produkcji, co oznacza cofnięcie się na stosie o r i dopisaniu As na stosie: Jeśli akcja [S_m._f, A] = accept — porser kończy pracę Jeśli akcja [S_m._r, A] = error— porser zgłasza błąd i woła procedury obsługi błędu

Akcja trwa dopóki całe wejście nie zostanie zaakceptowane lub zostanie znaleziony błąd!

Po zbudowaniu parsera dla danej gramatyki, budowa kompilatora jest już łatwa. Poniższy schemat ukazuje fazy pracy współczesnego kompilatora (opcjonalne!):

program źródłowy

program wynikowy

Początkowo, problem stworzenia kompilatora uważano za zbyt trudny do realizowania. Implementacja pierwszego kompilatora Fortranu zajęła 13 lat pracy. Dziś do generowania lub pomocy w generowaniu kompilatorów służą specjalne programy, niektóre z nich potrafią wygenerować cały kompilator. Przedstawiony powyżej parser reprezentuje tzw. automat skończony. W następnym rozdziale poświęconym teorii automatów przyjrzymy się bliżej automatom skończonym. Także takie elementy komputera jak jednostka centralna czy urządzenia peryferyjne można rozpatrywać jako automaty skończone. Teorię automatów skończonych używa się do projektowania komputerów i mikroprocesorów.