Süntaksianalüüs = programmi teisendamine puuks

Süntaksianalüüsi peamine ülesanne on transleeritava programmi teisendamine puuks. See puu on transleeritava programmi derivatsioonipuu programmeerimiskeele süntaksi kirjeldamiseks kasutatud grammatika  põhjal.

Kui programmeerimiskeeles aritmeetiline avaldis on kirjeldatud produktsioonidega

avaldis  yksl | yksl + avald | yksl - avald
yksl  tegur | tegur * yksl | tegur / yksl
tegur  CONST | IDENT

siis avaldis 2*3+4*5 teiseneb kõrvalolevaks puuks. Avaldise väärtuste arvutamiseks tuleb selle puu tipud läbida lõppjärjestuses (endorder - alampuud vasakult paremale ja siis puu tipp): 2 3 * 4 5 * + . See arvude ja operatsioonimärkide jada on magasini abil jooksvalt (puu läbimise ajal) arvutatav: - kui tipus on number, surutakse see magasini; kui tipus on operatsioonimärk, on selle operatsiooni argumendid magasini tipu elemendid; need asendatakse operatsiooni tulemusega.

Sama skeem töötab ka kogu omistuslause korral:

omist  IDENT = avaldis

Omistamise X= 2*3 + 4*5 puu läbimisel lõppjärjestuses pannakse algul magasini muutuja X; kui jõutakse kõige ülemise tipu '=', on magasini tipus omistatav väärtus ja kohe selle all - (viit) muutuja X ja jällegi on omistamise sooritatav "käigu peal".

Vaatame veidi suuremat näidet. Olgu programmeerimiskeele süntaks kirjeldatud grammatikaga

programm käsk | käsk  programm
käsk  omistamine | tingimuskäsk | tsükkel 
omistamine  IDENT = avaldis
avaldis  prim | prim operand avaldis 
prim  IDENT | CONST | (avaldis)
operand  + | - | * | /
tingimuskäsk  IF tingimus THEN programm ENDIF
tingimus  avaldis tingimusop avaldis
tsükkel  WHILE tingimus DO programm ENDLOOP
tingimusop  = | > | < 

Sellise grammatikaga võib saada näiteks programmilõigu:

X = 2
I = 1
WHILE I < 4 DO 
X = X * 2
I = I + 1
ENDLOOP

Süntaksianalüüsi tulemusena (ja puust ebaoluliste vahetippude eemaldamisega) saadakse ka sellest programmist puu, kuid siin ainult lõppjärjestuses puu läbimine pole magasini abil arvutamiseks (interpreteerimiseks) ega koodi genereerimiseks veel piisav: tingimuse kontrolli järel on tarvis teada, kus kogu WHILE-lause (s.t. selle programm-osa) poolt genereeritud kood lõpeb (kui tingimus on väär, tuleb minna sinna), kuid see lõpp võib olla kuitahes kaugel. Kuid veidi nipitades saab ka siin arvutamise korraldada magasini abil, sellepärast on magasinmasin klassikaline transleerimisel kasutatav infostruktuur/vahekeel - sellest on lihtne genereerida translaator ükskõik millise sihtkeele jaoks.

Küsimused, probleemid: ©2004-2013 Jaak Henno