img174

174    12. Metody grafowe

Zbiór produkcji tp, którego lewe i prawe strony są przedstawione na rysunku 12.8, zdefiniowano następująco:

0M-	Ol	di	<*3	C(t,in) = {(a, 6, f,m)}
	2	1	0	C(ti, in) = {(a, 0, u, in)}
	st	V	—
	23	3	-
(2) A —►	61	di		C(t,in) = {(b,b,t,in)}
	1	0		C(u,in) = {(6,a,u,«n)}
	s	—
	2	-
(3) A —*	di	B2		C(f,in) = {(<f,6,<,m)}
	1	0		C(u, in) = {(B, a, t, in)}
	r	—
	2	-
(4) B —♦	61	di	dz	C(t,in) = {(6,a,t,in)}
	2	1	0	C(r,t'n) = {(6, d,r,in)}
	st	V	—
	23	3	-

Graf startowy Z znajdujący się na rysunku 12.8 ma opis charakterystyczny:

b i    a-i    A3

2    1    0

rt    u    —

23    3    -

Jednoprzebiegowy parser typu generacyjnego (a.ng.top-down), którego algorytm przedstawimy na końcu tego punktu, dokonuje analizy syntak-tycznej badając w każdym kroku opis charakterystyczny tylko jednego wierzchołka. Równocześnie konstruowany jest wywód, mający doprowadzić do wygenerowania analizowanego grafu (sceny). Podczas parsingu porównywane są wierzchołki analizowanego i wywodzonego grafów. Jeśli oba wierzchołki są terminalne, to badamy ich opisy charakterystyczne, a jeśli wierzchołek wywodzonego grafu jest nieterminalny, to szukamy takiej produkcji, po zastosowaniu której badane wierzchołki będą zgodne co do ich opisów. Numery produkcji użytych w trakcie parsingu są podstawą do zaklasyfikowania rozpoznawanej sceny. Rozważanym scenom odpowiadają następujące ciągi produkcji: I scena - 1, II scena - 2, III scena - 34.

Wyszukiwarka

Podobne podstrony:
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
img170 170 12. Metody grafowe i wtedy dopiero na zwolnionych wcześniejszych miejscach wektora tt zap
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)
img170 170 12. Metody grafowe i wtedy dopiero na zwolnionych wcześniejszych miejscach wektora tt zap
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
img152 152 10. Metody ciągowe produkcje tp generujące obrazy III oraz IV: (1) oraz (6) Si - 42 S5
img168 16812. Metody grafowe Rys. 12.3. Przebieg generacji sceny I z rys. 12.1 za pomocą ekspansywne
img174 174 c) Podział ciągły 0° - 260° lewy, zonitalny (ry*« 186). Oznaczenia odczytów KP 1 KL pozos

więcej podobnych podstron