img178

178

12. Metody grafowe

Wierzchołki ij, j = 1,,p nazywamy wierzchołkami potencjalnie kontekstowymi dla wierzchołka n*, natomiast krawędzie wchodzące do wierzchołków ij nazywamy krawędziami potencjalnie kontekstowymi dla wierzchołka n*. Wierzchołki i'-, j = 1    nazywamy wierzchołkami quasi-

-kontekstowymi dla wierzchołka n*.

Zauważmy, że wierzchołki indeksowane przez 2 grafów g oraz Z, w rozważanym przykładzie, są potencjalnie kontekstowo identyczne. Natomiast elementy zapamiętanej trójki postaci (q,k,e) mają następujące znaczenie:

q jest indeksem wierzchołka potencjalnie kontekstowego dla wierzchołka indeksowanego przez k - ny,

e jest etykietą krawędzi potencjalnie kontekstowej dla wierzchołka n*.

Trójkę o postaci (ę, 1, e) nazywamy opisem potencjalnie kontekstowej identyczności.

Przed prezentacją algorytmu parsera wprowadźmy następujące oznaczenia:

G - analizowany graf,

H - graf wywodzony (generowany) w trakcie parsingu,

Z - graf startowy gramatyki,

D - zbiór opisów potencjalnie kontekstowej identyczności, n(i) - etykieta wierzchołka grafu G indeksowanego przez i, n'(ł) - etykieta wierzchołka grafu H indeksowanego przez t, m - liczba wierzchołków analizowanego grafu.

Zdefiniujmy procedury i funkcje parsera:

choose(/l, a, fc) - jeśli istnieje produkcja, dla której A jest etykietą lewej strony oraz a jest etykietą wierzchołka pierwszego poziomu grafu prawej strony produkcji, to:

k := numer takiej produkcji; w przeciwnym przypadku k := 0;

production(//, i,k) - zastosowanie i-tej produkcji dla i-tego wierzchołka grafu H ;