3.2. Drzewa rozbioru syntaktycznego
Drzewo rozbioru syntaktycznego według gramatyki G = "GBK jest to drzewo
zorientowane z korzeniem k0 i funkcją etykietującą wierzchołki f: K M, jeśli
spełnione są następujące warunki:
k0
(1) M Ä…" (N *" T) *"{µ}
(2) f(k0) = Z
...
k1 k2 kn
(3) niech k1,...,kn będą bezpośrednimi potomkami korzenia k0;
wówczas: (Z f(k1)f(k2)...f(kn)) " P
(4) jeÅ›li f(ki) " T lub jeÅ›li n = 1 i f(ki) = µ, to ki jest liÅ›ciem
(5) jeśli f(ki) " N, to ki jest korzeniem drzewa (poddrzewa) rozbioru według gramatyki

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
T+T*F = forma
+ T
E
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
id
F F
jest frazÄ… formy T+T*F
dla T
id id
G = < {E, T, F} , {+, *, (, ), id} , { EE + T | T
TT * 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} , {EE+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)