img205

205

D4. Wybrane pojęcia teorii języków drzewowych i grafowych

3) Zbiór krawędzi E jest przetransformowany tak, że wszystkie krawędzie są skierowane od wierzchołka o niższym indeksie do wierzchołka

0    wyższym indeksie (gdy zachodzi potrzeba, to „odwracamy” krawędź, tzn. zastępujemy ją przez odwrotną - semantycznie równoważną).

Zdefiniujemy teraz gramatykę grafową edNLC [33], dla podklasy której - ETL(l) - został zdefiniowany analizator syntaktyczny [37].

Krawędziowo-etykietowaną, skierowaną, sterowaną etykietą wierzchołka gramatyką grafową (gramatyką ®_eiNLC ~ ang. edge-labelłed directed Node-Label Controlled graph grammar) nazywamy piątkę

®edNLC = (S, A, T, P, Z),

gdzie £ - skończony, niepusty zbiór etykiet wierzchołkowych, A (podzbiór £) - zbiór terminalnych etykiet wierzchołkowych, T - skończony, niepusty zbiór etykiet krawędziowych, P - skończony zbiór produkcji o postaci (/, D, C), gdzie / € £, D jest grafem EDG, C : T x [in.out] —> Exrx{m,c/ut} j_est transformacją osadzenia, Z - startowy graf EDG.

Wywód w gramatyce grafowej ®_t<iNLC = (£, A, T,P,Z) jest rekurencyj-nie zdefiniowany według następujących reguł:

1.    Startujemy z grafu g = Z.

2.    Jeśli w g istnieje wierzchołek nieterminalny n etykietowany przez

1    € E oraz (/, D,C) 6 P, to zastępujemy wierzchołek n przez graf D.

3.    Stosujemy transformację osadzenia C w następujący sposób. Jeśli (a,c,y,out) € C(x, in), to krawędź etykietowaną przez x (C(x,...)), która wchodziła (C(..., in)) do wierzchołka n zastępujemy przez krawędź:

a)    łączącą wierzchołek grafu D etykietowany przez a ((a, z wierzchołkiem rest-grafu(³) etykietowanym przez c((..., c,

b)    etykietowaną przez y ((.............)),

c)    i wychodzącą z wierzchołka a grafu D    , out))(⁴).

Pojęcia te zostały zdefiniowane w [36].

(³) Rest-grafem nazywamy wywodzony graf bez wierzchołka n.

(^ł) Reguła transformacji osadzenia została podana w intuicyjny sposób. Formalną definicje można znaleźć w [33].