img172

172

12. Metody grafowe

12.2. Parsing dla gramatyki grafowej klasy ETL(\)

Metodę tą zilustrujemy przykładem analizy trzech scen: dwóch (I oraz II) - rozważanych w poprzednim punkcie (rys. 12.1) oraz sceny III (rys. 12.4). Zanim zdefiniujemy reprezentacje tych scen w postaci grafów IE [36], musimy wprowadzić relację porządku w zbiorze etykiet krawędziowych T przedstawionym na rysunku 11.1. Zróbmy to, przykładowo, w następujący sposób:

P<r<s<t<u<v<x<y.

Przy tak ustalonym porządku otrzymujemy grafy IE przedstawione na rysunkach 12.5, 12.6 oraz 12.7 o następujących opisach charakterystycznych:

Rys. 12.4. Scena do analizy z wykorzystaniem gramatyki ETL(1)

I scena (rys. 12-la): 6i	a2	aa	d<	d5
2	1	2	1	0
rt	u	st	V	-
23	3	45	5	-
II scena (rys. 12.Ib): 6i	«2	63	d,
2	1	1	0
rt	U	s	-
23	3	4	-
III scena (rys. 12.4): b\	a 2	da	64	ds	ds
2	1	1	2	1	0
rt	t	r	st	V	-
23	4	4	56	6	-

Gramatyka grafowa klasy ETL( 1) generująca rozważane sceny jest postaci:

©£tl( i) = (s, A,r,ip,.z),