3.2. Drzewa rozbioru syntaktycznego

Drzewo rozbioru syntaktycznego według gramatyki G = <N,T,P,Z>

∈

G

BK

jest to drzewo

zorientowane <K, D> z korzeniem k

0

i funkcją etykietującą wierzchołki f: K!M, jeśli

spełnione są następujące warunki:

(1) M

⊆

(N

∪

T)

∪

{

ε

}

(2) f(k

0

) = Z

(3) niech k

1

,...,k

n

będą bezpośrednimi potomkami korzenia k

0

;

wówczas: (Z

→

f(k

1

)f(k

2

)...f(k

n

))

∈

P

(4) jeśli f(k

i

)

∈

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

i

) =

ε

, to k

i

jest liściem

(5) jeśli f(k

i

)

∈

N, to k

i

jest korzeniem drzewa (poddrzewa) rozbioru według gramatyki

<N, T, P, f(k

i

)>

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

k

0

k

1

k

2

k

n

...

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

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:
G = < {E} , {+, *, (, ), id} , {E

→

E+E | E*E | (E) | id} , E >

Analizowane słowo: 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.

korona cięcia T*F

poddrzewa tworzy frazę

związaną z korzeniem

poddrzewa T <=> T*F

jest frazą formy T+T*F

dla T

E

E

T

F

id

+

T

T

*

F

F

id

id

poddrzewo o korzeniu T

E

E+T
T+T
F+T

id+T

id+T*F
id+F*F

id+id*F

id+id*id

Wyprowadzanie

lewostronne

E

E+T

E+T*F

E+T*id
E+F*id

E+id*id
T+id*id
F+id*id

id+id*id

Wyprowadzanie

prawostronne

Drzewo rozbioru

syntaktycznego

E

E

+

T

T

F

T

id

* F

F

id

id

E

E

+

E

id

E * E

id

id

E

E

*

E

+

E

E

id

id

id

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)