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.