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 = <V,Σ,P,S>

∈G

BK

jest to

drzewo zorientowane <K, D> z
korzeniem k

0

i funkcją etykietującą

wierzchołki f: K

a

M, jeśli spełnione są

następujące warunki:

•

M

⊆

(V

∪

Σ)

∪

{

ε

}

•

f(k

0

) = S

•

niech k

1

,...,k

n

będą bezpośrednimi

potomkami korzenia k

0

;

wówczas: (S

→

f(k

1

)f(k

2

)...f(k

n

))

∈

P

•

jeśli f(k

i

)

∈

Σ lub jeśli n = 1 i f(k

i

) =

ε

,

to k

i

jest liściem

•

jeśli f(k

i

)

∈

V, to k

i

jest korzeniem drzewa

(poddrzewa) rozbioru według gramatyki
<V, Σ, P, f(k

i

)>

k

0

k

1

k

2

k

n

...

Przykład (1)

Przykład:

Analizujemy gramatykę G,

gdzie:

V = {E, T, F} ,

T = {+, *, (, ), id},
P = { E → E + T | T

T → T * F | F
F → (E) | id

},

S = E

oraz analizujemy słowo:

id + id * id

E

E

T

T

F

id

T

F

id

*

F

id

+

korona cięcia

T+T*F = forma

zdaniowa

korona drzewa id+id*id

= słowo języka L(G)

korzeń=symbol

początkowy gramatyki

Przykład (2)

Przykład (3)

Drzewo rozbioru

syntaktycznego

E

E

+

T

T

F

T

id

* F

F

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

Przykład (4)

G = < {E} , {+, *, (, ), id} , { E→E + E | E * E | (E) | id

} , E >

Analizowane słowo: id + id * id

E

E

+

E

id

E * E

id

id

E

E

*

E

+

E

E

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.