Kontekstivabade keelte süntaksianalüüs ülalt-alla

Olgu G kontekstivaba grammatika, w - mingi selle grammatika abil genereeritud sõna. Sõna w süntaksianalüüsiks nimetatakse sõna w derivatsioonipuu leidmist grammatika G põhjal; seda puud nimetatakse sõna w derivatsioonipuuks.

Süntaksianalüüsi teostamiseks on välja mõeldud kümneid algoritme. Vastavalt sellele, kuidas derivatsioonipuud püütakse konstrueerida, võib neid (jämedalt) jagada kahte klassi: ülalt-alla ja alt-üles algoritmid.

Ülalt-alla algoritmides alatakse puu juurest (see on grammatika algussümbol) ja püütakse igal sammul jätkata (arendada) puu esimest (ülalt-alla vasakult-paremale järjestuses) "rippuvat" (s.t. veel mitte analüüsitava sõna terminalidega ühendatud) tippu. Kui see tipp on grammatika mitteterminal, kasutatakse mingit selle mitteterminali produktsiooni (s.t. produktsiooni, milles see mitteterminal on vasakul); kui see aga on terminal, peab see ühtima analüüsitava sõna esimese lugemata (analüüsimata) sümboliga (see on ka terminal); kui ta ühtib, ühendatakse need sümbolid; kui mitte, toimub tagurdus (backtracking) viimasesse tippu, kus mitteterminali jätkamiseks oli võimalik valida mitme produktsiooni vahel ja seal valitakse nüüd järgmine produktsioon.

Näide 1. Olgu grammatika G määratud järgmiste produktsioonidega:

S a S b S | aS |c

Kogu analüüs algab situatsioonis (# on analüüsitava sõna lõpumarker):

Mitteterminali S jätkamiseks on kolm võimalust, kuid analüüsitava stringi esimese sümboli "a" põhjal peab kasutama kas esimest või teist; valime esimese:

Ka nüüd on mitteterminali S arendamiseks kaks võimalust, valime taas esimese:

Järgmisel sammul tuleb mitteterminal S ilmselt arendada kolmanda produktsiooni abil:

Nüüd saame järgmiste sammudega redutseerida "rippuva" terminali b sisendstringi terminaliks b ja "rippuva" mitteterminali S sisendstringi terminaliks c:

Jätkata enam ei saa - "rippuvat" mitteterminali b pole võimalik enam arendada, sest sisend on lõppenud (järgmisena loetav sümbol on sisendi lõpusümbol #), seega peab tagurdama, s.t. proovima eespool toimunud mitteterminali S arendamiseks muid võimalusi.

Lihtne on näha, et kontekstivabade grammatikate (isegi järgmise klassi - kontekstitundlike grammatikate) jaoks on süntaksianalüüsi ülesanne - antud märgijada jaoks derivatsioonipuu genereerimine või näitamine, et derivatsioonipuud üldse ei leidu, s.t. see märgijada pole selle grammatikaga genereeritav - alati sooritatav ja võib koostada programmi, mis leiab derivatsioonipuu. Selleks teisendame algul grammatikat, nii et selles poleks enam tühja parema poolega produktsioone S λ. Tühja parema poolega produktsioonide kõrvaldamiseks tuleb iga sellise produktsiooni jaoks leida kõik produktsioonid, kus see mitteterminal esineb produktsiooni paremal pool ja lisada sellele siis produktsioon, kus seda mitteterminali enam pole, s.t. näiteks kui grammatikas on produktsioonid

A w S v
S λ

A w S v | wv

Grammatika, milles ei ole tühja parema poolega produktsioone, on nn "pikkust suurendav" - iga produktsiooni kasutamine suurendab derivatsiooniga saadava sõna pikkust. Sellepärast võib antud sõnale derivatsioonipuu otsimisel lihtsalt proovida kõikvõimalikke derivatsioone, kuni derivatsiooniga saadakse kas otsitav sõna või saame sõna, mille pikkus on suurem kui esitatud sõna pikkus. Kuna selliseid "kõikvõimalikke" derivatsioone on vaid lõplik arv, siis on lihtne teha programm, mis nad kõik süstemaatiliselt läbi proovib ja teatab, kui derivatsioonipuu leidus (või teatab, et sellist üldse pole võimalik saada).

Ülalkirjeldatud meetod on liiga aeglane, et seda translaatorites kasutada (kuigi ka seda on kasutatud). Praktilise (kiire) translaatori saamiseks tuleb teisendada grammatikat, nii et see võimaldaks (mingi meetodiga) kiiret analüüsi, s.t. derivatsioonipuu koostamist; seda vaatlemegi järgmistes peatükkides.

Ülalt-alla analüüsi jaoks ei kõlba vasakrekursiivsed grammatikad, s.t. grammatikad, milles on produktisoon kujul

A A w | v

Selline produktsioon genereerib stringid kujul v(w)+, s.t. sõna v järel võib korduda sõna w ükskõik kuimitu korda. Ülalt-alla analüsaator "näeb" algul (kui ettevaatamist ei kasutata) vaid sõna v ja peab otsutama, kas genereerida ülemises tipus olevast mitteterminalist A sõna Aw (lootes leida v järel sõna w) ja (kui see leitakse) hiljem redutseerida sõna w või genereerida kohe sõna v . Kuimitu korda mitteterminalist A peab genereerima sõna Aw - see sõltub sellest, kuimitu w-d analüüsitavas sõnas tuleb, kuid ülalt-alla analüsaator ei suuda (lõpliku, fikseeritud pikkusega ettevaatamisega) selle üle otsustada ja kas läheb tsüklisse (kasutab alati alternatiivi A A w ) või lõpetab analüüsi veaga (kasutab alternatiivi A v ), kuid analüüsitavas sõnas tuleb sõna v järel veel kord sõna w.

Vasakrekursiivsust on lihtne kõrvaldada grammatika teisendamisega, näiteks ülalesitatud produktsiooni asendamisel produktsioonidega

A vA´
A´ wA´| λ

Küsimused, probleemid: ©2004 Jaak Henno