Kääntäjätekniikka

Luento 7 (4.4.2017)

Inkrementit

(deadlineja päivitetty 1.6.2017)

Alustava deadline sulkeissa (klo 16 kyseisenä päivänä ellei muuta ilmoitettu)

  1. Suunnittelu ja ryhmien muodostaminen (20.3.)
  2. Jäsentäjä valmis (perjantai 7.4. klo 10)
  3. Tarkastaja valmis (perjantai 5.5. klo 10)
  4. Välikielen generointi valmis [tai muita ominaisuuksia 1 op:n arvosta lisää] (15.5.)
  5. Kohdekielen generointi (naivi rekisteriallokaatio) valmis [tai muita ominaisuuksia 1 op:n arvosta lisää] (19.6.)
  6. Fiksu rekisteriallokaatio valmis [tai muita ominaisuuksia 1 op:n arvosta lisää] (14.8. klo 12)
  7. Koko työ viimeistelty ja valmis tarkastettavaksi (28.8. klo 12)

Perustellusta syystä voit ehdottaa omaa aikataulua. Perusteluksi kelpaa ainakin se, että aiot tehdä vain osan inkrementeistä, ja se, että aloitit harjoitustyön tekemisen myöhemmin kuin muut. Ota yhteyttä Slackitse tai sähköpostilla ja muista mainita hyväksytty oma aikataulusi palautuksen yhteydessä.

Luennon aiheena tarkastaja

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

Kielioppiohjattu kääntäminen

  • engl syntax-directed translation
  • jokaiseen produktioon liitetään toiminto, joka suoritetaan kun produktion jäsennys on valmis
    • vaihtoehtoisesti: produktion koodi suoritetaan (konkreettia) jäsennyspuuta läpikäydessä aina kun produktiota vastaava sisäsolmu tulee vastaan (postorder-järjestyksessä)
  • yleistyy niin, että solmutyypillä on toiminto kullekin läpikäyntivaiheelle (preorder, inorder, postorder)

Muodollisesti attribuuttikielioppi

  • jokaiselle välike- ja päätesymbolille voidaan määritellä attribuutteja
    • jokainen jäsennyspuun solmu on jokin symboli
    • joten solmulla on ko. symbolille määritellyt attribuutit
      • kullakin solmulla omansa
  • produktioon liitetään laskentasääntöjä, jotka voivat lukea tai kirjoittaa produktiossa esiintyvien symbolien attribuutteja

Attribuuttien luokittelu

  • synteettistä attribuuttia saadaan lukea produktion oikealta puolelta ja kirjoittaa produktion vasemmalle puolelle
  • periytyvää attribuuttia saadaan lukea produktion vasemmalta puolelta ja kirjoittaa produktion oikelle puolelle
  • jokainen attribuutti on joko synteettinen tai periytyvä

Attribuuttikielioppien erityistapauksia

  • S-attributoitu kielioppi on sellainen, jossa ei lainkaan esiinny periytyviä attribuutteja.
    • LALR-jäsentimen jäsennystoiminnot noudattavat S-attributointia
  • L-attributoitu kielioppi on sellainen, jossa attribuutit voidaan laskea yhdellä puun läpikäynnillä vasemmalta oikealle.

Abstraktin jäsennyspuun käsittely

  • läpikäynti kirjoitetaan keskenään rekursiivisina aliohjelmina
    • kullekin solmutyypille oma aliohjelma
  • aliohjelma
    • lukee kohdalla olevan solmun periytyvät attribuutit
    • kirjoittaa sen lapsisolmujen periytyviin attribuutteihin
    • kutsuu lapsisolmujen käsittelyaliohjelmia yksi kerrallaan
    • lukee lapsisolmujen synteettiset attribuutit
    • kirjoittaa kohdalla olevan solmun synteettisiin attribuutteihin
  • vaihtoehtoisesti
    • periytyvät attribuutit ovat aliohjelman parametreja
    • synteettiset attribuutit ovat aliohjelman paluuarvoja

Käytännön toteutus oliokielissä

  • jokaisella AST:n solmutyypillä on oma luokkansa, esim.
    • VariableDeclaration
    • WhileStatement
    • AddExpression
  • staattisesti tyypitetyssä kielessä pitää luoda myös abstrakteja yläluokkia, esim.
    • Declaration
    • Statement
    • Expression
  • läpikäynti voidaan toteuttaa lisäämällä sitä varten metodi jokaiseen luokkaan
  • vaihtoehtoinen tapa on Visitor-suunnittelumalli

Visitor staattisessa oliokielessä

  • abstraktiin yläluokkaan (esim. Expression) abstrakti metodi T accept<T>(ExpressionVisitor<T>)
  • jokaiseen aliluokkaan toteutus:
T accept<T>(ExpressionVisitor<T> v) {
    return v.visit(this);
}
  • jokaista abstraktia yläluokkaa kohti uusi Visitor-rajapinta, johon visit-metodi jokaiselle aliluokalle, esim:
interface ExpressionVisitor<T> {
    T visit(AddExpression);
    T visit(SubExpresssion);
    T visit(MulExpression);
    ...
}
  • puunkäsittelyoperaatio kirjoitetaan Visitorin toteuttavaksi luokaksi
  • ks esim. AJK 2009

Vaihtoehtoisia ratkaisuja eri isäntäkielissä

  • Haskell (perustapaus, Villellä kehittyneempiä versioita):
    • keskenään rekursiiviset data-tyypit
      • data Expr = Add Expr Expr | Sub Expr Expr | ...
      • data Stmt = While Expr Stmt | If Expr Stmt Stmt | ...
    • keskenään rekursiiviset funktiot
  • Python (\(\geq 3.4\))
    • luokat (ei välttämättä abstrakteja yliluokkia, mutta saa olla)
    • functools.singledispatch
    • ks esim. AJK-2016
  • Common Lisp Object System
    • geneeriset funktiot

Lausekeongelma

eli Metodit vai Visitor

Philip Wadler 1998:

The Expression Problem is a new name for an old problem.  The goal is
to define a datatype by cases, where one can add new cases to the
datatype and new functions over the datatype, without recompiling
existing code, and while retaining static type safety (e.g., no
casts).  For the concrete example, we take expressions as the data
type, begin with one case (constants) and one function (evaluators),
then add one more construct (plus) and one more function (conversion
to a string).

Whether a language can solve the Expression Problem is a salient
indicator of its capacity for expression.  One can think of cases as
rows and functions as columns in a table.  In a functional language,
the rows are fixed (cases in a datatype declaration) but it is easy to
add new columns (functions).  In an object-oriented language, the
columns are fixed (methods in a class declaration) but it is easy to
add new rows (subclasses).

Staattinen semantiikka

  • semantiikka eli merkitysoppi: yleensä ohjelmointikielten tapauksessa kaikki se, mikä ei ole (kontekstittomalla) kieliopilla (helposti) kuvattavissa
  • staattinen: käännösaikana tiedossa oleva
  • staattinen semantiikka: mm. käännösaikaiset oikeellisuustarkastukset
    • joissakin kielissä puhutaan rajoitteista (constraints)

Lohkorakenne ja symbolitaulut

Mitä seuraava ohjelma tulostaa?

# scopeesim

Lohkorakenne

  • Useimmissa kielissä on lohkorakenne.
    • Ohjelmateksti jaetaan lohkoihin.
    • Kaksi lohkoa ovat kokonaan erilliset tai sitten toinen on toisen sisällä.
    • Aktiiviset lohkot muodostavat siten pinorakenteen (ehkä jopa metsän).
  • Lohkoja:
    • Koko ohjelma on lohko (ns. globaali lohko).
    • Moduli (käännösyksikkö tms.) on lohko.
    • Luokka on lohko.
    • Funktio (sisältäen myös parametrilistan) on lohko.
    • Silmukkalause on (joissakin kielissä) lohko.

Lohkorakenteisen kielen nimisäännöt

  • Nimen määritelmän lohkolla tarkoitetaan sisintä lohkoa määritelmän kohdalla.
  • Nimi saadaan määritellä useampaan kertaan vain, jos joka määritelmällä on eri sisin lohko.
  • Toisin sanoen jos saman sisimmän lohkon alueella määritellään sama nimi kahdesti, on virhe diagnosoitava.
  • Kullakin hetkellä näkyy vain sisin määritelmä; muut määritelmät ovat piilossa.

Symbolitaulu

  • Kääntäjässä nimen ja sen merkityksen yhdistää symbolitaulu.
    • merkkijonoilla indeksoitu taulu, jonka alkioita ovat määritelmät (tai niistä tehdyt muistiinpanot).
  • Symbolitaulun tulee ottaa huomioon ohjelman käsittelyn edetessä sen lohkorakenne.
  • Symbolitaulun tulee hallita nimen piilotus oikein.

Symbolitaulu, vaihtoehto I

  • Luodaan joka lohkolle oma symbolitaulunsa.
  • Symbolitaululla voi olla viite ympäröivän lohkon (engl. enclosing scope) symbolitauluun.
  • Jos symbolitaulu ei tiedä nimestä mitään, se kysyy ympäröivän lohkon symbolitaululta.
  • Tietorakennevalinta?
    • Hajautustaulu erinomainen jos nimiä on paljon (esim. globaali ja modulin symbolitaulu) mutta muuten tilasyöppö.
  • Lineaarinen haku (linkitty lista tai taulukko) kilpailukykyinen jos nimiä vähän (esim. silmukkalohko).
  • Esim. AJK-2009

Symbolitaulu, vaihtoehto II

  • Yksi iso hajautustaulu, jota päivitetään määritelmien sekä lohkojen alun ja lopun osuessa kohdalle.
  • Apuna pino, johon pistetään muistiin nimen vanha määritelmä.
  • Lohkoon tultaessa pinoon pistetään merkki.
  • Lohkosta poistuttaessa perutaan pinon avulla kaikki määritelmät lähimpään merkkiin asti.
  • Lohkot numeroitava jotta duplikaattimääritelmä voidaan diagnosoida.
  • esim. AJK-2016 ja laskin-py

Symbolitaulu, vaihtoehto III

  • Perusidea sama kuin vaihtoehdossa I: joka lohkolla oma symbolitaulunsa.
  • Tehdään Copy-On-Write (COW) -kopio ympäröivän lohkon symbolitaulusta.
  • Tietyillä tietorakenteilla (esim. binääriset hakupuut) on tämä kopiointikin mahdollista rajata koskemaan vain osaa symbolitaulusta.
  • esim. VT-2016

Symbolitaulun (osittainen) vaihtoehto

  • Tavallisesti jonkinlaista symbolitaulua tarvitaan koko käännöksen aikana.
  • Tätä voidaan rajoittaa linkittämällä rakennepuussa viittaus nimeen siihen määritelmään, johon ko. nimiviittaus viittaa.
  • Linkityksessä tarvitaan symbolitaulua, sen jälkeen ei.

Mitä seuraava ohjelma tulostaa?

# staticscope

Staattinen vs dynaaminen lohkotus

  • Vaihtoehdot:
    • staattinen lohkotus: aliohjelma näkee (vain) ne muuttujat, jotka ovat sen määrittelykohdassa näkyvissä (ohjelma tulostaa 4)
    • dynaaminen lohkotus: aliohjelma näkee kutsupaikalla näkyvissä olevat muuttujat (ohjelma tulostaaa 6)
  • Tulkkaava toteutus toteuttaa dynaamisen lohkotuksen luonnostaan, staattinen lohkotus on tulkille työläämpi.
  • Kääntäjälle staattinen lohkotus olennaisesti helpompi.
  • Useimmiten dynaaminen lohkotus on bugi.
    • ... paitsi Lispissä jossa se muuttui bugista featureksi

Tyyppitarkastus

Huomautus tyyppitarkastuksesta

  • Tällä luennolla käsitellään vain staattista tyyppitarkastusta.
  • Tarkoituksena on diagnosoida tyyppivirheet käännösaikana.
  • Jos kieli onkin dynaamisesti tyypitetty, ei tämän osan tekniikoita tarvita.

Tyyppi

  • Tyyppi on ohjelmatekstin osaa liitettävä tunnus, joka kertoo, minkälaisten arvojen tai olioiden kanssa kyseinen ohjelmatekstin osa on tekemisissä.
    • Lausekkeen tyyppi luokittelee sen laskemisen tuloksena syntyvät arvot.
    • Funktion tyyppi kertoo, minkätyyppisiä arvoja ja kuinka monta se ottaa parametriksi ja mitä se palauttaa.
    • Lauseella ei yleensä ole tyyppiä, mutta se voi sisältää diagnosoitavia tyyppivirheitä.
    • Määrittelyllä ei yleensä ole tyyppiä, mutta se määrittelee uuden nimen ja sille tyypin, ja saattaa sisältää diagnosoitavia tyyppivirheitä.

Yksinkertaiset tyypit

  • Ohjelmointikieli määrittelee joukon perustyyppejä:
    • Perustyypit edustavat yleensä matemaattisia joukkoja kuten kokonaislukuja modulo \(2^{64}\) tai totuusarvoja.
    • Perustyypillä ei ole lainkaan ohjelman manipuolitavissa olevaa sisäistä rakennetta, joten
    • perustyypin arvoja ja olioita käsitellään vain perusoperaatioiden (esimerkiksi +, ∗) ja niistä johdettujen aliohjelmien avulla.
  • Lisäksi ohjelmointikieli määrittelee joukon tyyppikonstruktoreja, mm.
    • funktiot
    • tietueet eli struktuurit
    • variantit
    • taulukot
  • Luokat eivät ole yksinkertaisia tyyppejä.

Lausekkeen tyyppitarkastus

  • Tarkastus etenee rakennepuussa alhaalta ylös, lehtisolmuista juureen.
    • läpikäynti jälkijärjestyksessä
    • kunkin solmun käsittelyssä tiedossa sen lapsisolmujen tyyppi; solmun tehtävä selvittää oma tyyppinsä
    • tyyppi on siten synteettinen attribuutti
  • Lehtisolmuja ovat vakiot ja muuttujat:
    • Vakion tyyppi on yleensä trivialiteetti.
    • Muuttujan tyyppi haetaan symbolitaulusta ko. muuttujan nimellä.
  • Sisäsolmut ovat operaatioita. Pääsääntö:
    1. Tarkastetaan ensin, onko lapsisolmuilla operaation vaatimat tyypit.
    2. Solmun oma tyyppi riippuu operaatiosta (ja joskus lapsisolmujen tyypeistä).
  • Lause tyyppitarkastetaan kuten lauseke, mutta lausesolmuilla ei ole tyyppiä.

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