3.2. Drzewa rozbioru syntaktycznego
Drzewo rozbioru syntaktycznego według gramatyki G = <N,T,P,Z> ∈ GBK jest to drzewo zorientowane <K, D> z korzeniem k i funkcją etykietującą wierzchołki 0
f: K! M, jeśli spełnione są następujące warunki: k0
(1) M ⊆ (N ∪ T) ∪ {ε }
(2) f(k0) = Z
...
(3) niech k
będą bezpośrednimi potomkami korzenia ; k
k
k
1,...,kn
k0
1
2
n
wówczas: (Z → f(k1)f(k2)...f(kn)) ∈ P
(4) jeśli f(k
jest liściem
i) ∈ T lub jeśli n = 1 i f(ki) = ε , to ki (5) jeśli f(k
jest korzeniem drzewa (poddrzewa) rozbioru według gramatyki i) ∈ N, to ki
<N, T, P, f(ki)> Przykład:
G = < {E, T, F} , {+, *, (, ), id} , { E → E + T | T
T → T * F | F
F
→ (E) | id } ,
E >
Analizowane słowo: id + id * id korzeń=symbol
E
początkowy gramatyki
korona cięcia
E
+
T
T+T*F = forma
zdaniowa
T
T
*
F
F
F
id
korona drzewa id+id*id
id
id
= słowo języka L(G)
E
poddrzewo o korzeniu T
E
+
T
T
T
*
F
korona cięcia T*F
poddrzewa tworzy frazę związaną z korzeniem
poddrzewa T <=> T*F
F
F
id
jest frazą formy T+T*F
dla T
id
id
G = < {E, T, F} , {+, *, (, ), id} , { E→E + T | T
T→T * F | F
F→(E) | id } ,
E >
Analizowane słowo: id + id * id Wyprowadzanie
Drzewo rozbioru
Wyprowadzanie
lewostronne
syntaktycznego
prawostronne
E
E
E
E+T
E+T
T+T
E
+
T
E+T*F
F+T
E+T*id
id+T
T
T * F
E+F*id
id+T*F
E+id*id
id+F*F
F
F
id
T+id*id
id+id*F
F+id*id
id+id*id
id
id
id+id*id
Przykład:
G = < {E} , {+, *, (, ), id} , {E→E+E | E*E | (E) | id} , E > Analizowane słowo: id + id * id E
E
E
+
E
E
*
E
id
E * E
E + E
id
id
id
id
id
Dla pewnego słowa (u nas: id + id * id) udało się zbudować dwa różne drzewa rozbioru syntaktycznego. Taka gramatyka jest niejednoznaczna.
Podsumowanie:
- Dla
każdego drzewa rozbioru syntaktycznego istnieje co najmniej jedno wyprowadzenie słowa języka L(G) w gramatyce G
- Dla
każdego wyprowadzenia słowa istnieje odpowiadające mu drzewo rozbioru syntaktycznego. Kilku różnym wyprowadzeniom mogą odpowiadać identyczne drzewa rozbioru syntaktycznego.
- Dwa wyprowadzenia są równoważne, gdy odpowiadające im drzewa rozbioru syntaktycznego są identyczne.
- Słowo języka L(G) jest niejednoznaczne w gramatyce G, jeśli jego wyprowadzenia można opisać przez co najmniej dwa różne drzewa rozbioru syntaktycznego
- Gramatyka G jest niejednoznaczna, jeśli w języku L(G) istnieje co najmniej jedno niejednoznaczne słowo w tej gramatyce. W przeciwnym wypadku gramatyka jest jednoznaczna. W gramatyce jednoznacznej istnieje dokładnie jedno wyprowadzenie lewostronne i dokładnie jedno wyprowadzenie prawostronne (wśród wszystkich równoważnych wyprowadzeń tego samego słowa)