img169

169

12.1. Parsing ekspansywnych języków grafowych

I₃ = [£,5,4],    h = [F,\, 5],

h = [A,X, 6].

W drugim przebiegu parsera będziemy analizować wierzchołki grafu, startując od wierzchołka o indeksie 1 i kończąc na wierzchołku o największym indeksie oraz wspomagając się wygenerowanymi trójkami. Zauważmy, że analizując np. wierzchołek o indeksie 2 zapamiętamy, że startują z niego produkcje: czwarta i szósta. Jakkolwiek w następnym kroku faktycznie będziemy sprawdzać, czy można zastosować produkcję czwartą do wierzchołka o indeksie 3, to sprawdzenie, czy możemy zastosować produkcję szóstą nastąpi dużo później - w naszym przypadku na końcu - gdyż jest ona związana z wierzchołkiem o indeksie 5. Będziemy musieli zatem zapamiętać konieczność sprawdzenia aplikacji pewnych produkcji w późniejszych krokach analizy.

Niech zatem wektor ir(i), i = l,...,m, gdzie m jest liczbą wierzchołków grafu, służy do zapamiętania numerów produkcji stosowanych w kolejnych wierzchołkach, i jest indeksem aktualnie analizowanego wierzchołka, a trójki Ii są poprzednio wprowadzonej postaci (A',, a,,/,]. Oznaczmy przez k sumę liczby produkcji, które, w momencie analizy i-tego wierzchołka, już rozważyliśmy i liczby tych produkcji, które zapamiętaliśmy do rozważenia w przyszłości.

Zauważmy, że jeśli przez d, oznaczymy długość ciągu produkcji startujących cii, to kolejne k będziemy otrzymywać zwiększając je w każdym kroku o di, tzn. k := k + d,-. Zatem, jeśli w i-tym kroku analizy okaże się, że Jfe = i, tzn. nie zapamiętaliśmy takich produkcji, które będą rozważane w przyszłości, to zapamiętujemy jedynie ciąg produkcji startujących z wierzchołka i-tego:

rr(i + 1). ,.x(i + d,) := Oj.

Natomiast jeśli k > i, tzn. w poprzednich krokach zapamiętaliśmy produkcje do rozważenia w przyszłości (jest ich k — i), to musimy je przepakować na dalsze pozycje w wektorze r, czyli

ir(i + 1 + di) := ir(i + 1),

t(* + di) := ir(k),