img167

12.1. Parsing ekspansywnych języków grafowych

Nim przedstawimy formalny zapis algorytmu dwuprzebiegowego par-sera dla ekspansywnej gramatyki grafowej, zaprezentujemy ideę jego działania, analizując scenę 1. W pierwszym przebiegu, parser konstruuje dla każdego wierzchołka n,- analizowanego grafu g trójkę /,• = [JV<,or*, /*], gdzie: Ni jest nieterminalem lewej strony produkcji takiej, że n, jest wierzchołkiem terminalnym jej prawej strony, li numerem tej produkcji, Oj jest ciągiem produkcji startujących w generacji grafu g z tych nieterminali lewej strony /,-tej produkcji, które nie są oznaczone przez *. Konstrukcja trójek przebiega od wierzchołka o najwyższym indeksie do wierzchołka o indeksie 1. Trójka I\ powinna być postaci [5,ai,/i], tzn. ostatnim uzyskanym nieterminalem powinien być symbol startowy gramatyki, a w przeciwnym razie sygnalizowany jest błąd.

Analizując wierzchołek o indeksie 5 (grafu z rys. 12.1) zaetykietowany przez a definiujemy Is = [A, A, 6], A - symbol pusty, gdyż a o stopniu wyjściowym 0 redukuje się do A w produkcji szóstej oraz z grafu prawej strony tej produkcji nie startują żadne produkcje. Analogicznie U = [F, A, 5] (redukcja d o stopniu wyjściowym OdoFw produkcji piątej). Dla wierzchołka o indeksie 3 i etykiecie d, z którego wychodzi krawędź r - Is = [E, 5,4], ponieważ wierzchołek o etykiecie d, z którego wychodzi krawędź r redukuje się do E w produkcji czwartej, a z nieterminala prawej strony tej produkcji (F) może wystartować tylko produkcja piąta. Analiza wierzchołka drugiego - a₂ daje nam I2 = [D, 46,2] (redukcja wierzchołka o etykiecie o, z którego wychodzą krawędzie t,s,p, do D w produkcji drugiej). Zauważmy, że ciąg produkcji startujących jest dwuelementowy, a nie trójelementowy (produkcja czwarta dla E i produkcja szósta dla A), gdyż nieterminalny wierzchołek F* został wprowadzony jako element transformacji osadzenia (i w trakcie wywodu powinien połączyć się z jakimś wierzchołkiem o etykiecie F). Analizując pierwszy wierzchołek grafu g - b 1 definiujemy trójkę /1 = [5,2,1], W tym przypadku, badając produkcje startujące z nieterminala grafu prawej strony produkcji pierwszej - D (A* pomijamy, jak poprzednio) mamy do wyboru dwie produkcje: drugą i trzecią. Na podstawie opisu charakterystycznego grafu g stwierdzamy, że krawędź etykietowana przez t (wchodząca do nieterminala D w grafie prawej strony produkcji) wchodzi do wierzchołka o indeksie 2 zaetykietowanego przez a. Para D -a determinuje zatem jednoznacznie produkcję drugą (a nie trzecią, którą determinuje para D - b). Tak więc otrzymaliśmy następujące trójki:

fi =[5,2,1],    I2 = [D, 46,2],

Wyszukiwarka

Podobne podstrony:
img165 165 12.1. Parsing ekspansywnych języków grafowych II scena:
img171 171 12.1. Parsing ekspansywnych języków grafowych procedurę ExpRec (var rec); begin for i :=
img165 165 12.1. Parsing ekspansywnych języków grafowych II scena: ii
img169 169 12.1. Parsing ekspansywnych języków grafowych I3 = [£,5,4],    h = [F,, 5]
img171 171 12.1. Parsing ekspansywnych języków grafowych procedurę ExpRec (var rec); begin for i :=
img173 12.2. Parsing dla gramatyki grafowej klasy ETL( 1) 173 Rys. 12.5. Graf dla sceny z rys. 12.la
img175 12.2. Parsing dla gramatyki grafowej klasy ETL() Rys. 12.9. Analiza grafu (opis w tekście)
img177 177 12.2. Parsing dla gramatyki grafowej klasy ETL( 1) do analizy wierzchołków obu grafów ind
img179 179 12.2. Parsing dla gramatyki grafowej klasy ETL(l) conid(G, H, i) - boolowska funkcja spra
img173 12.2. Parsing dla gramatyki grafowej klasy ETL( 1) 173 Rys. 12.5. Graf dla sceny z rys. 12.la
img175 12.2. Parsing dla gramatyki grafowej klasy ETL() Rys. 12.9. Analiza grafu (opis w tekście)
img177 177 12.2. Parsing dla gramatyki grafowej klasy ETL( 1) do analizy wierzchołków obu grafów ind
img179 179 12.2. Parsing dla gramatyki grafowej klasy ETL(l) conid(G, H, i) - boolowska funkcja spra
img172 172 12. Metody grafowe12.2. Parsing dla gramatyki grafowej klasy ETL() Metodę tą zilustrujemy
img168 16812. Metody grafowe Rys. 12.3. Przebieg generacji sceny I z rys. 12.1 za pomocą ekspansywne
img172 172 12. Metody grafowe12.2. Parsing dla gramatyki grafowej klasy ETL() Metodę tą zilustrujemy

więcej podobnych podstron