Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
50
ROZDZIAŁ2.PROSTYTRANSLATORSTEROWANYSKŁADNIĄ
Terminologiadrzew
Strukturydanychtypudrzewoliczniepojawiająsięwzagadnieniachdoty-
czącychkompilatorów,zatemwartouściślićterminologię.
•
Drzewoskładasięzjednegolubwięcejwęzłów.Węzłymogąmieć
etykiety,którymiwtejksiążcetypowobędąsymbolegramatyki.
Przyrysowaniudrzewaczęstoprzedstawiamywęzłyjedynieprzez
teetykiety.
•
Dokładniejedenwęzełjestkorzeniem(root).Wszystkiewęzłypoza
korzeniemmająunikatowegorodzica;korzeńniemarodzica.Przy
rysowaniudrzewaumieszczamyrodzicawęzłaponadtymwęzłem
irysujemykrawędźmiędzynimi.Tymsamymkorzeńjestnajwyższym
(szczytowym)węzłem.
•
Jeśliwęzeł
N
jestrodzicemwęzła
M
,wówczas
M
jestdzieckiemN.
Potomkówjednegowęzłanazywamyrodzeństwem.Maonoporządek,
odlewejdoprawej,igdyrysujemydrzewa,rysujemydzieciustalonego
węzławtakiwłaśniesposób.
•
Węzełpozbawionydziecinazywamyliściem.Innewęzły–te,które
mająjednolubwięcejdzieci–towęzływewnętrzne.
•
Potomkiemwęzła
N
jestalbosamwęzeł
N
,albodzieckowęzła
N
,
lubteżdzieckodzieckawęzła
N
itakdalej,przezdowolnąliczbę
poziomów.Powiemy,żewęzeł
N
jestprzodkiemwęzła
M
,jeśli
M
jestpotomkiemwęzłaN.
Mówiącformalnie,dladanejgramatykibezkontekstowejdrzewoanalizy
odpowiadającetejgramatycejestdrzewemonastępującychwłaściwościach:
1.Korzeńoznaczonyjestsymbolemstartowym.
2.Każdyliśćjestoznaczonysymbolemterminalnymlubć.
3.Każdywęzełwewnętrznyjestoznaczonysymbolemnieterminalnym.
4.
Jeślinieterminalne
A
jestoznaczeniemjakiegośwewnętrznegowęzła,a
X1
,
X2
,
...
,
Xn
sąetykietamipotomkówtegowęzłaodlewejdoprawej,
wówczaswgramatycemusiistniećprodukcjaA
→X1X2lllXn
.Wtym
przypadkukażdyzzapisów
X1
,
X2
,
...
,
Xn
oznaczasymbol,któryjest
alboterminalny,albonieterminalny.Wszczególnymprzypadku,gdymamy
produkcję
A→ć
,wówczaswęzełzetykietą
A
możemiećpojedynczego
potomkaoznaczonegoć.
Przykład2.4:
Wyprowadzeniezapisu
9-5+2
zprzykładu2.2ilustrujedrzewo
pokazanenarysunku2.5.Każdywęzełwtymdrzewiejestoznaczonysymbolem