Drzewa rozbioru
syntaktycznego
Teoria automatów i języków
formalnych
Dr in\
. Janusz Majewski
Katedra Informatyki
Drzewo rozbioru
Drzewo rozbioru syntaktycznego według
gramatyki G = "GBK jest to
drzewo zorientowane z
korzeniem k0 i funkcją etykietującą
wierzchołki f: KaM, jeśli spełnione są
k0
następujące warunki:
" M ą" (V *" Ł) *"{�}
" f(k0) = S
...
k2 kn
k1
" niech k1,...,kn będą bezpośrednimi
potomkami korzenia k0;
wówczas: (S f(k1)f(k2)...f(kn)) " P
" jeśli f(ki) " Ł lub jeśli n = 1 i f(ki) = �,
to ki jest liściem
" jeśli f(ki) " V, to ki jest korzeniem drzewa
(poddrzewa) rozbioru według gramatyki

Przykład (1)
Przykład:
korzeń=symbol
E początkowy gramatyki
Analizujemy gramatykę G,
korona cięcia gdzie:
T+T*F = forma
E + T
V = {E, T, F} ,
zdaniowa
T = {+, *, (, ), id},
P = { E E + T | T
T T * F
T T * F | F
F (E) | id },
S = E
F F id
oraz analizujemy słowo:
korona drzewa id+id*id
id + id * id
id id
= słowo języka L(G)
Przykład (2)
Przykład (3)
G = < {E, T, F} , {+, *, (, ), id} , { EE + T | T
TT * F | F
F(E) | id } , E >
Analizowane słowo: id + id * id
Drzewo rozbioru
syntaktycznego
E
E + T
T T * F
F F id
id id
Przykład (4)
G = < {E} , {+, *, (, ), id} , {EE + E | E * E | (E) | id } , E >
Analizowane słowo: id + id * id
E
E
E * E
E + E
+
E E id
id E * E
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)
" Problem:  czy dana gramatyka bezkontekstowa jest jednoznaczna? jest
nierozstrzygalny.