img166

166

12. Metody grafowe

E = {a,M},

T = {r,t,p,ti,s},

$}:(1) S->btDrA',    (2) D -* a łE $F"pA,

(3) D - 6 sF p>4,    (4)E-+d rF,

(5) F —> d,    (6)A-*a.

Zbiór produkcji został zilustrowany na rysunku 12.2 (cyfry w nawiasach kwadratowych oznaczają numery porządkowe przypisane nieter-minalom prawych stron produkcji), natomiast generacja sceny I (według reguł opisanych w Dodatku 4), znajduje się na rysunku 12.3. Cyfry pod strzałkami oznaczają numery stosowanych produkcji, a napis ET oznacza zastosowanie transformacji osadzenia. Zauważmy, że „odziedziczenie” przez wierzchołek A krawędzi o etykiecie r po wierzchołku o etykiecie A* jest możliwe, ponieważ numer porządkowy wierzchołka A (tzn. 2) jest wielokrotnością numeru porządkowego wierzchołka A" (tzn. 1). Scenę II generujemy poprzez zastosowanie produkcji o numerach: 1, 3, 5, 6. Zatem wypisanie na wyjściu sekwencji produkcji 124546 po analizie przez parser jakiejś sceny oznacza, że jest to scena I, a 1356 - scena II.

Rys. 12.2. Zbiór produkcji ekspansywnej gramatyki grafowej