img167

167

12.1. Parsing ekspansywnych języków grafowych

Nim przedstawimy formalny zapis algorytmu dwuprzebiegowego par-sera dla ekspansywnej gramatyki grafowej, zaprezentujemy ideę jego działania, analizując scenę 1. W pierwszym przebiegu, parser konstruuje dla każdego wierzchołka n,- analizowanego grafu g trójkę /,• = [JV<,or*, /*], gdzie: Ni jest nieterminalem lewej strony produkcji takiej, że n, jest wierzchołkiem terminalnym jej prawej strony, li numerem tej produkcji, Oj jest ciągiem produkcji startujących w generacji grafu g z tych nieterminali lewej strony /,-tej produkcji, które nie są oznaczone przez *. Konstrukcja trójek przebiega od wierzchołka o najwyższym indeksie do wierzchołka o indeksie 1. Trójka I\ powinna być postaci [5,ai,/i], tzn. ostatnim uzyskanym nieterminalem powinien być symbol startowy gramatyki, a w przeciwnym razie sygnalizowany jest błąd.

Analizując wierzchołek o indeksie 5 (grafu z rys. 12.1) zaetykietowany przez a definiujemy Is = [A, A, 6], A - symbol pusty, gdyż a o stopniu wyjściowym 0 redukuje się do A w produkcji szóstej oraz z grafu prawej strony tej produkcji nie startują żadne produkcje. Analogicznie U = [F, A, 5] (redukcja d o stopniu wyjściowym OdoFw produkcji piątej). Dla wierzchołka o indeksie 3 i etykiecie d, z którego wychodzi krawędź r - Is = [E, 5,4], ponieważ wierzchołek o etykiecie d, z którego wychodzi krawędź r redukuje się do E w produkcji czwartej, a z nieterminala prawej strony tej produkcji (F) może wystartować tylko produkcja piąta. Analiza wierzchołka drugiego - a₂ daje nam I2 = [D, 46,2] (redukcja wierzchołka o etykiecie o, z którego wychodzą krawędzie t,s,p, do D w produkcji drugiej). Zauważmy, że ciąg produkcji startujących jest dwuelementowy, a nie trójelementowy (produkcja czwarta dla E i produkcja szósta dla A), gdyż nieterminalny wierzchołek F* został wprowadzony jako element transformacji osadzenia (i w trakcie wywodu powinien połączyć się z jakimś wierzchołkiem o etykiecie F). Analizując pierwszy wierzchołek grafu g - b 1 definiujemy trójkę /1 = [5,2,1], W tym przypadku, badając produkcje startujące z nieterminala grafu prawej strony produkcji pierwszej - D (A* pomijamy, jak poprzednio) mamy do wyboru dwie produkcje: drugą i trzecią. Na podstawie opisu charakterystycznego grafu g stwierdzamy, że krawędź etykietowana przez t (wchodząca do nieterminala D w grafie prawej strony produkcji) wchodzi do wierzchołka o indeksie 2 zaetykietowanego przez a. Para D -a determinuje zatem jednoznacznie produkcję drugą (a nie trzecią, którą determinuje para D - b). Tak więc otrzymaliśmy następujące trójki:

fi =[5,2,1],    I2 = [D, 46,2],