TIES448 Luento 6

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.

Abstrakti jäsennyspuu 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)
  • kirja puhuu kontekstinhallinnasta, pitkälti sama asia

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.

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ä.

Tulkki

  • Suora tulkki on olennaisesti samantyylinen kuin tyyppitarkastin, mutta tyyppien asemesta käsitellään arvoja.
  • Moni tyyppitarkastin onkin erikoistapaus symbolisesta suorittamisesta.

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