img176

176

12. Metody grafowe

Rozważmy teraz następujący problem związany z analizą języków generowanych przez gramatyki ETL( 1). Załóżmy, że analizujemy graf g reprezentujący scenę III (rys. 12.4). Analizę rozpoczynamy od grafu startowego Z (rys. 12.9). Zauważmy, że jeśli analizujemy wierzchołki grafów g i Z indeksowane przez 2, to okaże się, że ich opisy charakterystyczne nie są zgodne. Wierzchołek grafu g indeksowany przez 2 jest opisany przez:

<>2

1

t

4

podczas gdy wierzchołek grafu Z indeksowany przez 2 jest opisany przez

02

1

u

3

Taka sytuacja wynika z faktu, że wierzchołek indeksowany przez 4 (do którego powinna wchodzić krawędź wychodząca z 02) nie istnieje w grafie Z, natomiast krawędź u wychodząca z wierzchołka 02 wchodzi do wierzchołka nieterminalnego indeksowanego przez 3. Tak więc, po zastosowaniu produkcji do wierzchołka A3 sytuacja może się zmienić wskutek działania transformacji osadzenia. Dlatego zapamiętamy następującą trójkę (4,2,<), gdzie:

4 jest indeksem wierzchołka, do którego rozważana krawędź powinna wchodzić,

2 jest indeksem wierzchołka, z którego rozważana krawędź wychodzi, t jest etykietą, którą powinna mieć rozważana krawędź (zgodnie z opisem charakterystycznym analizowanego grafu g).

Następnie analizujemy wierzchołek indeksowany przez 3. Szukamy produkcji postaci A    ponieważ wierzchołek grafu g jest etykietowany

przez d, a wierzchołek grafu Z jest etykietowany przez A. Taką produkcją jest produkcja trzecia i po jej zastosowaniu otrzymamy graf g\ przedstawiony na rysunku 12.6b. Analiza wierzchołków indeksowanych przez 3 grafów g oraz 31 wykazuje ich zgodność, w związku z czym możemy przejść