Magasinmäluga automaat ülalt-alla süntaksianalüüsiks

LL(k) grammatikate ülalt-alla süntaksianalüüsi on lihtne kirjeldada magasinmäluga automaatide abil.

Sellise magasinmäluga automaadi seisund on määratud:
- sisendlindilt veel lugemata osa esimese k sümboliga u;
- magasinlindi ülemise (nähtava) sümboliga X ; tööd alustades on magasinlindil S$, kus S on grammatika algussümbol ja $ on magasini "põhja" sümbol;
- juba toodetud väljundiga ; väljundiks võib olla näiteks puu konstrueerimise (algussümboli arendamise) käigus tekkinud produktsioonide numbrid - need määravad üheselt derivatsioonipuu (vt allpool).


Automaadi tööd juhib tabel (kahe argumendi funktsioon), mis magasini tipus oleva sümboli ja sisendi k-tähelise lõigu põhjal sooritab ühe järgnevatest teisendustest:
- kui magasini tipus on mitteterminal X ja sisendlindilt loetav k-täheline string u kuulub hulka FIRSTk(X w) (mingi produktsiooni X w jaoks), asendab automaat magasini tipus oleva mitteterminali X selle produktsiooni parema poolega w ja lisab väljundile selle produktsiooni numbri;
- kui magasini tipus ja sisendlindil loetav sümbol sama terminal, eemaldab magasini tipust terminali, mis oli ka sisendi lugemispea all ja liigutab sisendlindi lugemispead ühe koha võrra paremale (nn operatsioon POP, sisendi ja magasini vastastikune redutseerimine);
- kui sisendi lugemispea näeb sisendlindi lõpusümbolit # ja magasini lugemispea - magasini lõpusümbolit $, teatab sisendi tunnistamisest (nn operatsioon OK);
- kõigil muudel juhtudel teatab veast (nn operatsioon ERROR).

Näide. Grammatika

S aAS | b
A a | bSA

on lihtne LL(1) grammatika ja selle ülalt-alla tunnistamise sooritab järgmise tabeliga juhitav automaat (veerud vastavad sisendlindilt loetavatele sümbolitele, read - magasini tipusümbolilile; tabelis on iga produktsiooni parema poole järel ka selle järjekorranumber, produktsioonid on numereeritud loomulikus järjekorras 1 .. 4):

a

b

#

S

aAS, 1

b, 2

E

A

a, 3

bSA, 4

E

a

POP

E

E

b

E

POP

E

$

E

E

OK

Sisendi abbab tunnistamisel muutub kolmik (sisendi lugemata osa, magasinlint, genereeritud väljund) järgmiselt:

(abbab#, S$, - ) (abbab#, aAS$, 1) (bbab#, AS$, 1) (bbab#, bSAS$, 14) (bab#, SAS$, 14) (bab#, bAS$, 142) (ab#, AS$, 142) (ab#, aS$, 1423) (b#, S$, 1423) (b#, b$, 14232) (#, $, 14232) OK

Genereeritud produktsiooninumbrite jada põhjal on lihtne rekonstrueerida derivatsioonipuu: alates ühetipulisest puust mille tipu tähis on algussümbol tuleb igal sammul asendada puu esimene (lõppjärjestuses) mitteterminal väljundi (produktsiooninumbrite jada) järgmisele produktsiooninumbrile vastava produktsiooni parema poolega.

Ülesandeid:
1. Kontrollida, et allpool esitatud lihtsaid aritmeetilisi avaldisi kirjeldav grammatika on LL(1)ja koostada selle tunnistamiseks magasinmäluga automaadi juhtimistabel:

E TE'
E' +TE' |
T FT'
T' *FT' |
F (E) | a

2. Kontrollida, et allpool esitatud grammatika on LL(2) ja koostada selle tunnistamiseks magasinmäluga automaadi juhtimistabel:

S aAaa | bAba
A b |

3. Kontrollida, et allpool esitatud grammatika on LL(2) ja koostada selle tunnistamiseks magasinmäluga automaadi juhtimistabel:

S abA |
A b | Saa

4. Kontrollida, et allpool esitatud grammatika on LL(1) ja koostada selle tunnistamiseks magasinmäluga automaadi juhtimistabel:

S AS |
A aA | b

5. Kontrollida, et allpool esitatud grammatika on LL(3) ja koostada selle tunnistamiseks magasinmäluga automaadi juhtimistabel:

S aAaB | bAbB
A a | ab
B aB | a

Küsimused, probleemid: ©2004 Jaak Henno