Mis on translaatoris erilist?

Translaatorite tegemise ("Compiler Construction" ) kursus kuulub (vist) kõigi infotöötlemise ja tarkvarategemist õpetavate ülikoolide kursuste loetellu, ja sageli see on kohustuslik baaskursus, ilma milleta ei saada diplomeeritud tarkvarategijaks ja infotöötlejaks.

Translaator on programm. Kuigi erinevate, peamiselt eriotstarbeliste translaatorite (näiteks pihuarvutite ja mobiiltelefonide tarkvara tegemise) translaatori koosseisu võib kuuluda mitmeid mooduleid (mälukasutuse optimiseerimiseks, linkurid jne), on tähsaim osa translaatorist tavaliselt realiseeritud ühe programmina, mis isegi koos kõigi lisamoodulitega ei ole eriti suur.

Ühegi teise programmi jaoks ei ole oma kursust. Ülikoolides õpetatakse programmeerimist, andmebaasi- ja infosüsteeme jne edasi, s.t. märksa üldisemaid asju kui seda on mingi konkreetse programmi tegemine - kes on õppinud programmeerimist, peab oskama teha mistahes programmi. Erandiks on vaid translaatorid - nende tegemist õpetatakse omaette kursusel. Mis on translaatoris nii erilist, et nende tegemist õpetatakse eraldi kursusel? Ja tavaliselt ühesemestrilise baaskursuse lõppedes isegi veel ei eeldata, et osavõtjad oskaks ise valmis teha töötava, kasutuskõlbliku translaatori. Kursuse jooksul tutvutakse peamiselt translaatorite teoreetiliste alustega ja nn translaatori esiosaga (first end); paljud praktikas olulised probleemid (koodigenereerimise peensused, mälukasutuse ja koodi optimiseerimine jne) jäävad erikursustes ja seminarides käsitlemiseks. Miks ei ole võimalik ühe programmi tegemist selgeks saada ühesemestrilise kursusega, mis on translaatoris nii erilist?

Translaatorite "erilisus" tuleb translaatori ülesandest: mingis ühes programmeerimiskeeles kirjutatud programmi tõlkimine mingis teises programmeerimiskeeles kirja pandud programmiks (ja kui see teine keel on mingi protsessori masinkood, siis sageli ka loodud koodi täitmine). "Tavalised" programmid töötlevad sisendideid, mille kohta enamasti täpselt teada, mis liiki suurused (täisarvud, reaalarvud, tekstistringid jne) need on ja programm sooritab nendega rea programmi koodiga määratud teisendusi: liidab-lahutab arve, teisendab stringe. Translaatori sisend (transleeritav programm) on kõige üldisemat liiki: märgijada. Mida sellega tuleb teha, on määratud selle märgijada struktuuris (transleeritava programmi süntaksiga) ja translaatori esiosa ülesandeks ongi sisestatud märgijada struktuuri (süntaksi) leidmine. Alles siis saab hakata seda jada (transleeritavat programmi) teisendama. Mida jada erinevate osadega tuleb teha, on samuti määratud jada (programmi) struktuuriga, kuid see on juba "kõrgem" struktuur ja selle käsitlemiseks on otstarbekas esialgne sisend teisendada nn vahekujule. Need etapid on transaatoris tavaliselt üsna selgelt eraldatud: sisendi analüüs, sisendi teisendamine vahekujule ja seejärel väljundprogrammi genereerimine hilisemaks täitmiseks (kompilaator) või töödeldava programmi otsene täitmine (interpretaator). Ülesande (transleerimise) jagamine lihtsamateks alamülesanneteks on programmeerise üks tähtsamaid tehnoloogiad, translaator on selle tehnoloogia kasutamise hea näide.

Transleeritava programmi struktuuri (milline on aritmeetiliste avaldiste struktuur, kus on muutujate deklaratsioonid, kus täidetavad käsud, kust peab programmi täitmine jätkuma näiteks if...then... lausetes jne) leidmine on üsna keeruline ülesanne. Translaator oli (ajalooliselt) esimene programm, mille loomisel saadi aru, et seda ei ole võimalik teha "hakkame aga nurgast kirjutama"-meetodil - enne on tarvis kogu ülesanne teoreetiliselt "lahti harutada". Esimeste translaatorite tegemise ajal loodigi selliste teooriate alused - Bacus-Nauri valemid (kontekstivabad grammatikad), regulaarsed avaldised, lõplike ja magasinmäluga automaatide teooria jne. Need teooriad on tänaseni kogu arvutiteaduse (computer science) nurgakivid ja translaatorite tegemine põhineb nende kasutamisel. Translaatorite tegemise kursuses ei uurita mitte ühe programmi loomise tehnoloogiat, kuivõrd selle programmi loomiseks vajalikke teooriaid ja nende kasutamist; nende abil on ka võimalik suur osa translaatori tegemisest automatiseerida nn "translaatorite translaatori" süsteemide (compiler compiler system) abil. Suur osa translaatori koodist ei ole käsitsi kirjutatud, vaid genereeritud selliste "metaprogrammeerimise" süsteemidega. Genereerimisel on "otse", käsitsi programmi kirjutamisega võrreldes palju eelisid - programmerija kirjeldab nii sisendi kui ka väljundi palju kõrgemal abstarktsioonitasandil ja sellepärast tekib palju vähem vigu, mis on tavaliselt seotud mingite madala taseme detailidega. Sellist "kõrgtasemel" probleemidest aru saamist, nende kirjeldamist ja selleks kasutatavaid formalisme saab ja peabki kasutama ka paljude teiste andmetöötlusprobleemide lahendamisel.

Kuid pärast transleeritava programmi struktuuri leidmist peab translaator lahendama veel rea Ülesandeid: leitud (hierahilist, s.t. puu-)struktuuri on tavaliselt otstarbekas (selle kiiremaks käsitlemiseks koodi genereerimisel) teisendada, koodi genereerimisel peab tegelema mälujaotuse ja selle optimiseerimise probleemidega jne. Ka need probleemid esinevad paljude teistegi programmide (programmisüsteemide) loomisel ja nende lahendamiseks kasutatavad algoritmid kuuluvad samuti programeerimistehnoloogia alase hariduse alustesse.

Translaator on tegelikult faili formaadi teisendaja - ta teisendab lähtekeele formaadis kirjutatud faili (transleeritava programmi) väljundkeele formaadis kirjutatud failiks (transleeritud programmiks). Selline failiformaadi teisendamise ülesanne esineb andmetöötluses väga sageli: trükkimiseks tuleb dokumendid teisendada Postscript-formaati (postscript printeri kasutamisel), WWW-saidil esitamiseks tuleb nad teisendada HTML-i, TeX- tekst konverteeritakse dvi-formaati jne. Kõigi selliseid teisendusi tegevate programmide kirjutamisel kasutatakse translaatorite tegemise tehnoloogiaid.

Alati on tarvis ka uusi translaatoreid. Uusi programmeerimiskeeli tuleb kogu aeg juurde: Boo, Cesil, Comega, Curry, Groovy, Lua, Squeak, Sather... . Mitmed suhteliselt traditsioonilised keeled on muutunud väga kiiresti populaarseteks, nagu näiteks Python ja Ruby. Kõikvõimalikke XML-formaadil põhinevaid keeli ilmub praegu "nagu Vändrast saelaudu" (neid käsitletakse raamatu teises osas). Suuremate mängude tegijad loovad tavaliselt oma mängu juhtimiseks ka uue (interpreteeritava) keele; (praegu) on mängukeelte tegemisel väga populaarne Lua. Ka uusi operatsioonisüsteeme ja -keskkondi ilmub kogu aeg: Linux, Lindows, pihuarvutid, mobiilid.

Translaatorite tegemisel kasutatavaid tehnoloogiaid, formalisme ja teooriaid kasutatakse ka paljude teiste info- ja programmeerimistehnoloogia probleemide lahendamisel. Sellepärast, ongi translaatorite tegemise kursus info- ja programmeerimistehnoloogia-alaste õppeprogrammide "raudvara".

1. Ülesandeks on koostada programm, mis leiab kõigi sisestatud tekstis esinevate sõnade esinemissageduse; lihtsustamiseks loeme kõik morfoloogilisid vormid erinevateks sõnadeks, s.t. "laud" ja "lauad" on erinevad sõnad. Millisteks alamülesanneteks võiks probleemi jagada ja milliseid andmestruktuure oleks programmis otstarbekas kasutada?

2. Ülesandeks on koostada programm, mis oskab arvutada ühendsüsteemis (arv 3 esitatakse kujul | | |). Ühendsüsteemis esitatud avaldise (kasutatakse üht aritmeetilist tehet +, -, x, : ) järel oleva võrdusmärgi = leidmisel peab programm kirjutama selle järele vastuse (samuti ühendsüsteemis), näit. rea

|| + ||| =

lõppu peab programm väljastama ||||| . Millised siin võiks olla alamülesanded ja kasutatavad andmestruktuurid?

3. Kuidas tuleb täiendada eelneva ülesande lahenduse struktuuri, kui
- sisestatud avaldises võib olla ükskõik kui mitu aritmeetikatehet, kuid need sooritatakse järjest, vasakult paremale (operatsioonide prioriteeti ei arvestata), s.t. | + | x || = sisestamisel väljastab programm |||| (mitte ||| )?
- arvestatakse ka operatsioonide prioriteete, s.t. | + | x || = sisestamisel peab vastus olema ||| ?

4. Mida tuleb eelmise ülesande lahenduses muuta, kui programm peaks avaldise arvutamisel arvestama ka tehete prioriteeti , s.t. x, : tuleb sooritada enne kui +, -, seega | + | x || = ||| ?