TIES448 Luento 1 (30.10.2018)

Opettajat

Viestintä

Lähiopetus

  • luennot 30.10.–20.12. ti ja to klo 12 (Ag Beeta)
    • itsenäisyyspäivänä 6.12. ei ole luentoa
  • ohjaukset
  • ei läsnäolopakkoa, mutta kokemuksen mukaan itseopiskelu on erittäin haastavaa

Kirjallisuutta

Kurssikirja luentojen tukena, mutta emme seuraa sitä orjallisesti. Lukeminen käytännössä pakollista.

Muita hyviä kirjoja

  • Andrew W. Appel: Modern Compiler Implementation in Java. 2nd ed. Cambridge University Press, 2002.
  • Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman: Compilers: Principles, Techniques, & Tools. 2nd ed. Pearson Addison-Wesley, 2007.

Tarvittaessa viitataan myös tutkimuskirjallisuuteen ja muuhun lisämateriaaliin.

Tentti

  • tentillä 2 op, tällöin ei tehdä harjoitustyötä
  • tentissä testataan, että opiskelija "tuntee kääntäjätekniikan perusteet lukuunottamatta varsinaisen optimoinnin tekniikoita"
    • ei algoritmien yksityiskohtia
  • joko luentotentti tai kirjallisuustentti
  • e-tentti avataan joulukuussa
    • paperitentti voidaan laatia perustellusta syystä

Harjoitustyö

  • 3-6 op, ei tehdä tenttiä
  • deadline tiistaina 12.3.2019 kello 9:00 mennessä
  • tehdään 2–3 hengen ryhmissä
    • yksin tekeminen johtaa yleensä keskeneräiseksi jäämiseen
  • tarkemmin torstain luennolla

Akateeminen rehellisyys

  • Kun käytät jonkun muun laatimaa koodia, tee tämä selväksi.
  • Tee selväksi, miten olet muiden laatimaa koodia muuttanut.
  • Puutteet estävät kurssisuorituksen hyväksymisen
    • varteenotettavat vilppiepäilyt viedään dekaanin tutkittavaksi
    • sanktio vakavimmillaan määräaikainen erottaminen yliopistosta
  • Tarkemmin ks. aiempien kurssieni ohjesivu

Luentotehtävä

Koskien lukutehtävää:

  • Mitä uutta opit?
  • Mitä jäi epäselväksi?

Miksi opiskella kääntäjätekniikkaa?

Kääntäjätekniikka on haasteellista

  • Kääntäjäprojektin tekeminen kehittää ohjelmointi- ja projektinhallintataitoja.
  • Onnistunut kääntäjäprojekti voi olla vahva näyttö osaamisesta.

Teoria ja käytäntö yhdistyvät

  • Kääntäjä on käytännönläheinen ja hyödyllinen ohjelma.
  • Kääntäjän sisällä jylläävät algoritmit ja tietorakenteeet ovat epätriviaaleja ja pitkän tutkimustyön huipentumia.
    • Kääntäjätekniikka oli tietojenkäsittelytieteen merkittävä tutkimusalue 1960- ja 1970-luvuilla.
  • Nykyisin tutkimus keskittyy aiheisiin, jotka eivät kuulu tämän kurssin ydinsisältöön.

Näkemystä kääntäjien toimintaan

  • Kääntäjätekniikan tuntemus auttaa ymmärtämään teollisten kääntäjien aivoituksia.
  • Olemassaolevia kääntäjiä ja kieliä oppii siten käyttämään paremmin.

Kääntäjätekniikan ideoilla on muitakin sovelluskohteita

  • tiedostoformaattien tulkinta
  • tiedostoformaattien muunnokset
  • rakenteisen datan käsittely
  • HTML, CSS ym
  • tietoturva (langsec)

Tietokonekielet

Määritelmä: Tietokonekieli on kieli, joka on tarkoitettu tietokoneen ymmärrettäväksi.

Esimerkkejä:

  • monet dokumenttitiedostomuodot (.docx, .xml, .html, .odt, ...)
  • useimmat sovellustason verkkoprotokollat (HTTP, ESMTP, NNTP, XMPP, ...)
  • konfiguraatiotiedostot
  • määrittelykielet (B, Z, VDM, ...)
  • ohjelmointikielet

Konekielet

Määritelmä. Konekieli on tietokonekieli, jota tietokoneen keskusyksikkö ymmärtää sellaisenaan.

Huomautus. Käytännössä konekieltä ei ymmärrä suoraan rauta, vaan keskusyksikön sisällä on ns. mikrokoodilla kirjoitettu tulkki tai JIT-kääntäjä. Tämä ei kuitenkaan näy ohjelmoijalle.

Määritelmä. Yleensä konekielestä on olemassa ainakin yksi ihmisen luettavissa oleva versio, ns. symbolinen konekieli eli assembly, joka käännetään eri ohjelmalla (ns. assembler) konekieleksi.

Instruction Set Architecture

Konekieliä on erilaisia, ja tietokoneet jaetaan eri luokkiin (instruction set architecture eli ISA, suomeksi yleensä käskykanta-arkkitehtuuri) sen mukaan, mitä konekieltä kukin hallitsee:

  • PC:issä nykyään yleensä x86-64 eli AMD64.
  • Pitkään PC-koneissa oli x86(-32) eli IA32.
  • Mobiililaitteissa yleisin on ARM.
  • Aiemmin yleisiä mm. PowerPC, Sparc, 68000, 6502, Z80
  • Teollisessa käytössä on kuitenkin useita kymmeniä erilaisia ISA:ita.

Välikielet

Määritelmä. Välikieli (engl. intermediate language) on ohjelmien kuvaamiseen tarkoitettu tietokonekieli, jota tuotetaan ohjelmallisesti ja joka suoritetaan joko tulkkaamalla tai edelleen kääntämällä.

Esimerkkejä.

  • monilla kääntäjillä oma sisäinen välikielensä
  • 1970- ja 1980-lukujen Pascalin P-code
  • Java bytecode
  • .NET:n CIL
  • LLVM

Kääntäjien peruskäsitteitä

Määritelmä. Kääntäjä (engl. compiler) on tietokoneohjelma, joka ottaa yhdellä kielellä (lähdekieli, engl. source language) kirjoitetun tietokoneohjelman syötteenään ja tuottaa ulos saman tietokoneohjelman kirjoitettuna jollakin toisella kielellä (kohdekieli, engl. target language).

Huomautus. Usein kohdekieli on jokin konekieli, mutta ei aina.

Huomautus. Tavallisesti kohdekieli on lähdekieltä yksinkertaisempi. Jos tilanne on päinvastainen ja kääntäjä pyrkii idiomaattiseen kohdekoodiin, puhutaan takaisinkääntäjästä (engl. decompiler). Jos kielet ovat suunnilleen yhtä monimutkaisia, englannin kielessä käytetään yleisemmin sanaa translator.

Isäntäkieli

Määritelmä. Kieli, jolla kääntäjä itse on kirjoitettu, on sen isäntäkieli (engl. host language).

Huomautus. Toisinaan kääntäjän isäntäkieli ja lähdekieli ovat (olennaisilta osin) sama kieli. Tällöin kääntäjän odotetaan kykenevän kääntämään itsensä; tällainen kääntäjä on itsensä isännöivä (engl. self-hosting)

Isäntäarkkitehtuuri

Määritelmä. ISA, jossa kääntäjä on suoritettavissa, on sen isäntäarkkitehtuuri (engl. host architecture).

Huomautus. Tavallisimmin isäntäarkkitehtuuri on sama kuin kohdekieli. Jos näin ei ole, kääntäjä on ristiinkääntäjä (engl. cross-compiler).

Bootstrapping

Määritelmä. Prosessi, jolla itsensä isännöivä kääntäjä saadaan käännetyksi suoritettavaan muotoon, on nimeltään bootstrapping.

Luentotehtävä. Olet suunnitellut uuden ohjelmointikielen, ja haluat kirjoittaa sille itsensä isännöivän kääntäjän. Kuinka bootstrapping voisi onnistua?

Tulkki

Määritelmä. Tulkki (engl. interpreter) on tietokoneohjelma, joka ottaa syötteenään lähdekielisen tietokoneohjelman ja käyttäytyy sen jälkeen kuten kyseinen tietokoneohjelma. Tulkkia kutsutaan joskus myös virtuaalikoneeksi (virtual machine) tai simulaattoriksi.

Tulkkeja on kolmea päälajia:

  • Klassinen tulkki suorittaa ohjelmaa sitä mukaa kuin lukee sitä.
  • Moderni tulkki kääntää ohjelman ensin välikielelle ja luovuttaa tuloksen edelleen välikielen tulkille.
  • JIT-kääntäjä (engl. just-in-time compiler) kääntää ohjelman tai sen osan konekielelle juuri, kun se tulee suorittaa, ja luovuttaa suorituksen välittömästi tämän jälkeen käännöksen tulokselle.

Kääntäjän rakenne

# compilerstructure
test src Lähdeohjelma toks Sanasjono src->toks selaaja ast Rakennepuu toks->ast jäsentäjä ast->ast kontekstianalysoija il Välikoodi ast->il välikoodin generoija il->il optimoija asm Kohdekoodi il->asm kohdekoodin generoija asm->asm optimoija

Selaaja

  • ..., lekseri, selain, palastelija, tokenisoija, sanastin ...
  • syötteenä lähdeohjelmaa esittävä merkkijono
  • tulosteena jono sanasia (engl. token), pienimpiä merkityksellisiä osia, vrt. sanat suomen kielessä; tyypillisesti:
    • kokonaislukuvakio 521
    • merkkijonovakio "kissa"
    • välimerkki ;
    • luokan nimi Window
    • muuttujan nimi it
    • avainsana while
    • Välilyönnit ym. eivät yleensä ole sanasia.
  • tuottaa virheilmoituksia ja varoituksia
  • voi hylätä ohjelman virheellisenä.

Jäsentäjä

  • ..., parseri, parsija, syntaktinen analysaattori, ...
  • syötteenä selaajan tuottama sanasjono
  • tulosteena rakennepuu eli abstrakti jäsennyspuu
    • engl. abstract syntax tree (AST)
    • tietorakenne, joka kuvaa ohjelman (staattisen) loogisen rakenteen
    • kukin sisäsolmu edustaa operaatiota ja sen lapsisolmut sen operandeja
  • tuottaa virheilmoituksia ja varoituksia
  • voi hylätä ohjelman virheellisenä.

Kontekstianalysoija

  • ..., semanttinen analysoija, staattinen tarkastaja, tarkastin ...
  • syötteenä jäsentäjän tai sokerinpilkkojan tuottama rakennepuu
  • tulosteena (ehkä muokattu) rakennepuu
  • yhdistää nimien määritelmät ja käyttöpaikat
  • tarkastaa, että ohjelmassa ei ole mitään sellaisia virheitä, joiden takia kääntäminen tulisi keskeyttää, esimerkiksi:
    • muuttujaa käytetään ennen määrittelyä
    • funktiolle annetaan väärä määrä parametreja
    • tyyppimäärittelyt ovat keskenään ristiriitaisia
    • myös usein lisää rakennepuuhun muistiinpanoja, esimerkiksi tyyppi-informaatiota
  • Tarkastaja on viimeinen osa, joka voi hylätä ohjelman virheellisenä. Myöhemmät osat olettavat koodin olevan virheetöntä

Sokerinpilkkoja

  • engl. desugarer
  • ei ole kaikissa kääntäjissä
  • syötteenä jäsentäjän tai tarkastajan tuottama rakennepuu
    • Valinta riippuu kääntäjästä.
    • Sokerinpilkkojan sijoittaminen tarkastajan jälkeen on käyttäjäystävällistä mutta monimutkaistaa tarkastajaa.
  • tulosteena rakennepuu
  • Pilkkoo käyttömukavuutta lisääviä rakenteita (eli syntaktista sokeria) yksinkertaisempiin osiin; esimerkiksi:
for (int i = 0; i < n; i++) { s(i); }
⇓
{ int i = 0; while (i < n) { s(i); i++; } }

Välikoodin generoija

  • engl. intermediate code generator
  • syötteenä tarkastajan ja sokerinpilkkojan läpikäymä rakennepuu
  • tulosteena ohjelma välikielellä esitettynä
  • Jotkut kääntäjät lopettavat kääntämisen tähän ja luovuttavat välikoodin tulkattavaksi virtuaalikoneelle.
    • mahdollista myös antaa toisen kääntäjän edelleen käännettäväksi

Optimoija

  • syö ja tulostaa välikoodia tai
  • syö ja tulostaa kohdekoodia
  • koostuu tavallisesti monesta erillisestä osasta
  • Analyysiosat tutkivat koodia ja tekevät siitä päätelmiä, joista sitten tehdään muistiinpanoja koodiin jatkokäyttöä varten.
  • Muokkausosat muuttavat koodia analyysiosien tekemien havaintojen perusteella.
  • monesti iteroidaan useita kertoja
  • sivuutetaan tällä kurssilla

Kohdekoodin generoija

  • engl. (target) code generator
  • syö välikoodia
  • tulostaa kohdekoodia
  • jos kovin naiivi, tarvitsee usein kohdekoodin optimoijan (tyypillisesti ovisilmäoptimoija, engl. peephole optimizer) kaverikseen

Kääntäjän päät

Etupää, engl. front end. Kääntäjän etupää on se osa kääntäjästä, joka on tekemisissä lähdekielen erityispiirteiden kanssa – selaaja, jäsentäjä, tarkastaja, sokerinpilkkoja sekä välikoodin generoija.

Välipää, engl. middle end. Kääntäjän välipää on se osa kääntäjästä, joka ei ole sen paremmin lähdekielen kuin kohdekielenkään kanssa tekemisissä – suuri osa välikoodin optimoijasta.

Takapää, engl. back end. Kääntäjän takapää on se osa kääntäjästä, joka on tekemisissä kohdekielen erityispiirteiden kassa – kohdekoodin generoija, kohdekoodin optimoja sekä mahdollisesti osa välikoodin optimoijasta.

Kääntäjäkokoelmat

Taitavasti laadittu välipää mahdollistaa etupäiden ja takapäiden vaihtamisen tarvittaessa. Tyypillinen esimerkki on GNU Compiler Collection (GCC).

Kääntäjä, jonka takapää on vaihdettavissa, on tähdättävä kääntäjä, engl. retargetable compiler.

Moniosaiset kääntäjät

  • Muinoin (ennen 1990-lukua) tietokoneiden työmuistit olivat niin pieniä, etteivät kääntäjä ja koko käännettävä ohjelma mahtuneet yhtä aikaa muistiin.
  • Yksiosainen kääntäjä (one-pass compiler) käänsi ohjelmaa rivi tai aliohjelma kerrallaan sitä mukaa kuin sitä luki.
  • Moniosainen kääntäjä (multi-pass compiler) koostui monesta eri ohjelmasta, jotka kommunikoivat aputiedostojen avulla.
    • esim. jäsentäjä oma ohjelmansa
  • Nykyään aika lailla kuollut ongelma. Ohjelma ja kääntäjä mahtuvat muistiin ongelmitta, eikä tarvetta kikkailuun ole enää.
    • sana pass esiintyy edelleen, mutta saisi kuolla tarpeettomana
  • vrt kirjan narrow/broad compiler

Kääntäjä osana käännöstyökalustoa

Nykyaikana kääntäjät tuottavat harvoin suoraan ajettavaa ohjelmaa. Tulos on yleensä joko symbolista konekieltä tai linkittämätön konekielinen ohjelmayksikkö.

# linking
test src lähdekielinen ohjelma comp kääntäjä src->comp ass assembleri comp->ass link linkkeri ass->link exe suoritettava ohjelma link->exe lib ohjelmakirjasto lib->link

Kääntäjän ajuri

  • lyhyt ohjelma, joka yhdistää kääntäjän eri osat sekä kääntäjän ulkopuoliset välineet (assembleri, linkkeri)
  • helpottaa kääntäjän käyttämistä
  • esim. komento gcc ei ole kääntäjä, vaan ajuri

These are the current permissions for this document; please modify if needed. You can always modify these permissions from the manage page.