Kääntäjätekniikka

Luento 5 (12.4.2016)

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

AJK:n C++-esimerkki

Yousourcessa

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