img170

170

12. Metody grafowe

i wtedy dopiero na zwolnionych wcześniejszych miejscach wektora tt zapamiętujemy ciąg produkcji startujących z i-tego wierzchołka:

ir(i + 1) • ■ • )r(i + d.) := a, .

Przed formalną prezentacją algorytmu, prześledźmy jeszcze trzy pierwsze kroki drugiego przebiegu parsera dla naszego przykładu.

Inicjałizacja: i := 1; k := 1.

1.    Stwierdzenie, że I\ jest postaci [S, cri, /i], S - symbol startowy, umożliwia prawidłowe rozpoczęcie analizy;

*0) :=!(/>);

*(2) :=2(/₂);

i := 1 + 1 (k + di) = 2;

i .= i+l=2.

2.    Stwierdzenie, że li = w (i) (/₂ = t(2), tzn. 2 = 2) oznacza zgodność numeru produkcji jaką zastosowaliśmy do wygenerowania grafu w i-tym kroku (podczas pierwszego przebiegu) - li z numerem produkcji jaka powinna być zastosowana w i-tym kroku - w(i); stwierdzamy, że k = i, więc

t(3):= 4;

*(4) := 6;

*:=2 + 2 (k + d₂) = 4;

i := 3.

3.    Stwierdzamy, że li = ir(i) (tzn. 4 = 4, k > i (4 > 3), więc:

a)    łr(5) := ir(4) (tzn. jt(5) := 6),

b)    ir(4) := 5 ;

k := 4 + 1 (k + d₃) = 5 ;

i := 4.

Po przeanalizowaniu wszystkich wierzchołków otrzymujemy ciąg tt(1) n(2) ... Jr(5) = 12456, co oznacza rozpoznanie sceny I.

Algorytm parsera przedstawimy przyjmując wprowadzone oznaczenia oraz oznaczając przez maketrip!e(i, Ii) wywołanie procedury tworzącej trójkę Ii dla wierzchołka o indeksie i. Zmienne: rec, list, tab, oraz funkcja decide zostały zdefiniowane w rozdziale 10.