img159

159

11.1. Analiza syntaktyczna drzew EDT

Zwróćmy jeszcze uwagę na dwa ograniczenia, które do tej pory zakładaliśmy milcząco. Pierwsze dotyczy zbioru produkcji 5P gramatyki ®edt-Otóż dla każdych dwóch produkcji Pi i p2 mających taką samą prawą stronę r : Aj —* r, A2 —► r, musi zachodzić warunek: Ai ^ Ai. W przeciwnym razie proces analizy w automacie %dfedt miałby charakter nie-deterministyczny.

Drugie ograniczenie dotyczy sposobu generowania i analizy drzewa. Zauważmy, że drzewo generowaliśmy w kolejności: korzeń, najbardziej lewe poddrzewo,... .najbardziej prawe poddrzewo (rysunek 11.3). Zasada ta została zilustrowana rysunkiem 11.4a. Najpierw generujemy terminal Ao i nieterminale Aj.A2.A3 (5 —* A(AjA2A3)). Następnie zajmujemy się generacją poddrzewa rozpoczynającego się w skrajnie lewym wierzchołku Aj i dopiero po wygenerowaniu całego poddrzewa ( w którym rekuren-cyjnie stosujemy podaną zasadę), zajmujemy się wierzchołkiem A2 (tzn. poddrzewem rozpoczynającym się w nim), itd. Natomiast analizy dokonujemy w odwrotnej kolejności, tzn. od skrajnie prawego liścia poruszamy się w drzewie z prawa - na lewo i z dołu - do góry, co zostało pokazane na rysunku 11.4b.

drzewowej

Zakończymy rozważania prezentacją algorytmu analizy sceny przedstawioną metodą. Wprowadzimy w nim następujące elementy:

zmienne:

rec, tab, list - opisano w p. 10.2, finalstates - opisano w p. 10.1,