img170

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.

Wyszukiwarka

Podobne podstrony:
img170 170 12. Metody grafowe i wtedy dopiero na zwolnionych wcześniejszych miejscach wektora tt zap
img174 174    12. Metody grafowe Zbiór produkcji tp, którego lewe i prawe strony są p
img174 174    12. Metody grafowe Zbiór produkcji tp, którego lewe i prawe strony są p
img164 12. METODY GRAFOWE Jak wspomniano w rozdziale 9, gramatyki grafowe są mocniejszym narzędziem
img172 172 12. Metody grafowe12.2. Parsing dla gramatyki grafowej klasy ETL() Metodę tą zilustrujemy
img176 176 12. Metody grafowe Rozważmy teraz następujący problem związany z analizą języków generowa
img164 12. METODY GRAFOWE Jak wspomniano w rozdziale 9, gramatyki grafowe są mocniejszym narzędziem
img166 166 12. Metody grafoweE = {a,M}, T = {r,t,p,ti,s},$}:(1) S->btDrA ,    (2)
img172 172 12. Metody grafowe12.2. Parsing dla gramatyki grafowej klasy ETL() Metodę tą zilustrujemy
img176 176 12. Metody grafowe Rozważmy teraz następujący problem związany z analizą języków generowa
img178 178 12. Metody grafowe Wierzchołki ij, j = 1,,p nazywamy wierzchołkami potencjalnie konteksto
img180 180 12. Metody grafowe rzędu 0(n2). Jakkolwiek obie metody zostały zdefiniowane dla potrzeb a
instr wyk torebki 1 Rys.1 Na prawą stronę jednego z kół, nałożyć kliny na oznaczone wcześniej miejs

więcej podobnych podstron