Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
2.2.DEFINIOWANIESKŁADNI
51
digit
list
list
digit
list
digit
2
RYSUNEK
205:Drzeworozbiorudlawyrażenia9-5+2,odpowiadające
gramatycezprzykładu2.1
gramatyki.Węzełwewnętrznyijegodzieciodpowiadająprodukcji;węzeł
wewnętrznytonagłówek,awęzłypotomnetociałotejprodukcji.
Narysunku2.5korzeńjestoznaczonyjakolist,czylisymbolemstartowym
gramatykizprzykładu2.1.Dziecikorzeniasąoznaczoneodlewejdoprawejjako
list,+orazdigit.Zauważmy,że
list
→
list+digit
jestprodukcjązgramatykizawartejwprzykładzie2.1.Lewedzieckokorzeniajest
analogicznedokorzenia,alezdzieckiemopatrzonymetykietą
-
zamiast
+
.Każdy
ztrzechwęzłówoznaczonychdigitmajednodzieckooznaczonepojedynczą
cyfrą.
Liściedrzewarozbioruodczytywaneodlewejdoprawejpozwalająuzyskaćciąg
symboliwygenerowanyczyteżwyprowadzonyznieterminalnegokorzeniadrzewa.
Narysunku2.5tymwynikiemjest
9-5+2
,dlawygodywszystkieliściezostały
umieszczonenatymsamym,najniższympoziomie.Trzebajednakzauważyć,że
niemusimykonieczniewyrównywaćliściwtensposób.Dowolnedrzewonarzuca
swoimliściomnaturalnyporządekodlewejdoprawejzgodniezzasadą,żejeśli
X
i
Y
sądziećmitegosamegorodzicai
X
jestnalewood
Y
,tokażdypotomek
XjestnalewooddowolnegopotomkaY.
Innadefinicjajęzykagenerowanegoprzezgramatykęmówi,żejesttozbiór
ciągówsymboli,zktórychkażdymożezostaćwygenerowanyprzezpewnedrzewo
rozbioru.Procesznajdowaniadrzewarozbiorudlapodanegociąguterminali
nazywanyjestparsingiemtegociągu.
2.2.4.Niejednoznaczność
Trzebazachowaćostrożność,gdymówimyostrukturzeciąguwyprowadza-
negowdanejgramatyce.Gramatykamożedopuszczaćwięcejniżjednodrzewo
rozbiorugenerującezadanyciągterminali.Takagramatykanazywanajestnie-
jednoznaczną.Abywykazać,żedanagramatykajestniejednoznaczna,wystarczy
znaleźćciągsymboliterminalnych,którydajesięutworzyćprzezwięcejniżjedno