img177

177

12.2. Parsing dla gramatyki grafowej klasy ETL( 1)

do analizy wierzchołków obu grafów indeksowanych przez 4. Po zastosowaniu produkcji czwartej do wierzchołka 4 grafu <71 powinniśmy sprawdzić zgodność trójki (4,2,*) z sytuacją otrzymaną w wywodzonym grafie, który teraz jest postaci przedstawionej na rysunku 12.9. Po stwierdzeniu, że z wierzchołka indeksowanego przez 2 wychodzi krawędź etykietowana przez t wchodząca do wierzchołka o indeksie 4, możemy zapamiętaną trójkę usunąć z pamięci. Zauważmy jeszcze, że powinniśmy przeszukiwać zbiór zapamiętanych trójek przed każdym przejściem do analizy wierzchołka o indeksie k + 1 sprawdzając, czy nie została wcześniej zapamiętana trójka postaci

Wprowadźmy teraz pojęcia, które pozwolą formalnie zdefiniować algorytm analizy syntaktycznej [37],

Niech będą dane grafy IE: g oraz g'. Dwa wierzchołki n* 6 g i n'_k 6 g' mające ten sam indeks k nazywamy wierzchołkami kontekstowo identycznymi, jeśli mają takie same opisy charakterystyczne.

Dwa wierzchołki n* E g i n_k £ g' mające ten sam indeks k oraz opisane przez

n*,    n'_k (odpowiednio)

r    r'

e,...e_r    e\...e'_r

i 1 • ■ ■ »r i'l ■ ■ ■ i'_r>

nazywamy wierzchołkami potencjalnie kontekstowo identycznymi, jeśli

1)    n_k = n'_k,

2)    r = r',

3)    jeśli dla każdego j 6 {l,...,r} istnieje k 6 {l,...,r} takie, że

ij — tjfc, to €j — €jt,

4)    n iech będą dane podciągi i_x,..., ip oraz i J,..., ciągów *1,..., i_r oraz ij,... *{. (odpowiednio), które spełniają następujący warunek: dla żadnego ij_t j = 1,..., p nie istnieje i_kfk = 1,..., r takie, że ij = i_k oraz dla żadnego i'-, j = l,...,p nie istnieje i*, k = l,...,r takie, że = i*. Wtedy, dla każdego j = 1,..., p : t_;- jest etykietowany przez symbol terminalny, a i'- przez symbol nieterminalny.