System update on April 6th from 00.00 to 02.00 UTC+3. Expect possible downtime during the maintenance.

Kääntäjätekniikka

Luento 4 (23.3.2017)

Kääntäjän rakenne

# 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

Luennon aiheet

  • selaaja
  • sanaset
  • jäsentäjä
  • rakennepuut

Teoria tuttua (toivottavasti)

Kertaa tarvittaessa Automaattien ja kielioppien materiaalista:

  • regexpit
  • kontekstittomat kieliopit
  • kontekstittoman kieliopin jäsentäminen
  • jäsennyspuut

Tänään tarkastellaan lähinnä käytännön toteutuksen ongelmia ja ratkaisuja.

Asiaa käsitelty laajemmin mm. vuoden 2009 materiaaleissa, ks vaihe B, mutta erityisesti ennustavan jäsennyksen kuvauksessa on siellä virheitä.

Selaajan tehtävät

  • lähdeohjelman lukeminen tietovarastosta
    • joskus tosin esikäsittelyvaiheita (esim. C-esikääntäjä)
  • mahdollisten merkistömuunnosten tekeminen
    • joskus erillinen esikäsittelyvaihe tähän
  • kommenttien ja tyhjän tilan eliminointi merkitys säilyttäen
  • ohjelman alustava (”leksikaalinen”) analyysi
  • rivinumerotiedon ylläpitäminen

Lekseemi

  • minimaalinen ohjelmatekstin osamerkkijono, jolla on itsenäistä semanttista sisältöä
  • tyypillisesti:
    • välimerkit
    • erilaiset luku-, merkkijono- ym. vakiot
    • erilaiset muuttujien, tyyppien ym. nimet

Sananen

  • engl. token (kirjaimellisesti ’poletti’, ’rahake’, ’kuponki’)
  • analysoitu lekseemi
  • sananen koostuu yleensä
    • itse lekseemistä
    • sen luokittelusta (sanasluokka, engl. token class, token type)
    • mahdollisesti sen semanttisesta sisällöstä
    • sen paikkatiedosta (lähdetiedosto, rivinumero ym.)

Lekseemien luokittelu

  • tarkka luokittelu riippuu lähdekielestä
  • on tavallisesti jopa määritelty kielen määrittelydokumentissa (standardi tms.)
  • idea: jäsentäjä pystyy päättelemään pelkästään lekseemin luokituksesta (tutkimatta lekseemiä tarkemmin), mitä lekseemille pitäisi tehdä

Konfliktien ratkaiseminen

  • eiffel – nimi (eiffel) vaiko jono [nimi e, avainsana if, nimi fel]?
  • >> – välimerkki >> vaiko jono [välimerkki >, välimerkki >]?
  • Yleensä konfliktit ratkaistaan seuraavien sääntöjen nojalla:
    • Lähdekoodi käydään läpi lineaarisesti lekseemi kerrallaan.
    • Kun lekseemi on päätetty julistaa, tätä päätöstä ei peruta.
    • Jos samasta kohdasta alkaen voidaan rakentaa useita vaihtoehtoisia lekseemejä, niistä valitaan pisin. (ns. maximal munch rule)

Selaajan rajapinta

  • yleensä yksi aliohjelma Token next() tms
    • palauttaa syötteessä seuraavan sanasen
  • jokin selaaja saattaa myös tuottaa kokonaisen listan kaikista sanasista
    • yleensä laiska lista (Haskell tms)
  • joskus tarvitaan myös seuraavat (tms):
    • void declare_typename(String) - määrittelee, että jokin nimi on tyypinnimi
    • void enter_scope()
    • void leave_scope() - peruu viimeisimmän enter_scopen jälkeen tehdyt deklaraatiot
    • lähinnä jos kielessä tyypinnimet ja muuttujan nimet ovat leksikaalisesti samanlaiset, erona edeltävä tyypinmäärittely, ja tyyppi ja muuttujannimi voivat esiintyä samassa paikassa

Selaajan toteutus

Paitsiosääntö

  • Useimmissa kielissä tyhjä tila on (lähes) merkityksetöntä, jolloin sisennystavat ym. ovat vain ”hyviä tapoja”.
  • Joissakin kielissä rivitys ja sisennys ovat osa syntaksia.
    • tunnetuimmat modernit esimerkit ovat Python ja Haskell
    • ideana että lohkorakenne esitetään sisennyksellä, ei muuten
  • Sisennyksestä lohkorakenteen päättelmisestä käytetään joskus Peter Landinin keksimää termiä paitsiosääntö (engl. off-side rule).

Paitsiosäännön toteutuksen idea

  • ks esim AJK-2016
  • tee filtteri selaajan ja jäsentäjän väliin
    • filtteri generoi sanasia BEGIN, END ja SEP (tms)
  • jotkin sanaset aloittavat lohkon (Pythonissa :, Haskellissa mm. do)
    • generoi lohkon aloittavan sanasen jälkeen BEGIN
    • seuraavan oikean sanasen sisennys laitetaan sisennyspinoon
  • kun jokin sananen on ensimmäinen uudella rivillä:
    • laske sen sisennys
    • poista sisennyspinosta sisennykset, jotka ovat tätä isompia
      • generoi sanasen eteen kullekin END
    • jos sisennys on nyt sama kuin pinon päällimmäinen, generoi sanasen eteen ENDien perään SEP
  • syötteen loppuun generoi sisennyspinon koon verran ENDejä

Jäsentäjän tehtävät

  • selaajan tuottaman sanasjonon muuttaminen ohjelman loogista rakennetta kuvaavaksi tietorakenteeksi
  • ohjelmassa olevien kielioppivirheiden tunnistaminen ja diagnosointi

Jäsentäjän laatiminen

  • nykyaikana pitää AINA perustua kontekstittomaan kielioppiin!
    • kannattaa etsiä harjoitustyön lähdekielen pohjana olevan kielen valmis kielioppi, josta voi sitten lähteä liikkeelle
  • voi tehdä käsin rekursiivisesti etenevän (ennustavan) jäsentimen (ks. AuKi)
  • yleensä kannattaa käyttää jäsentäjägeneraattoreita
    • parserikombinaattorikirjasto on hyvä vaihtoehto Haskellissa

Jäsentäjägeneraattoreita

Kielioppimalleja

Valinnaisuus

<optional-semicolon> ::= <empty> | ;
<empty> ::=

Toisto (tyhjä sallittu)

<stmts> ::= <empty> | <stmts> <stmt>
<empty> ::=

Epätyhjä lista (pilkulla erotettu)

<list> ::= <item> | <list> , <item>

Rakennepuut

  • Tietorakenne-esityksessä ei yleensä tarvita kaikkea tekstiesityksen yksiselitteistämiseen käytettyä tauhkaa.
  • Esimerkkinä lausekkeiden sulkeet: niillä ei ole (yleensä) mitään semanttista sisältöä sen jälkeen, kun lausekkeen rakenne on jäsennetty.
  • Siksi kääntäjän sisäinen esitysmuoto ei ole yleensä ohjelman (konkreetti) jäsennyspuu vaan ns. abstrakti jäsennyspuu (engl. abstract syntax tree eli AST) eli rakennepuu.

Rakennepuu vs (konkreetti) jäsennyspuu

# parsetree
test l1 lauseke l11 lauseke l1->l11 plus + l1->plus l12 lauseke l1->l12 one 1 l11->one l121 lauseke l12->l121 times * l12->times l122 lauseke l12->l122 two 2 l121->two three 3 l122->three
# ast
test l1 + one 1 l1->one l12 * l1->l12 two 2 l12->two three 3 l12->three

Rakennepuu

Lausekkeen rakennepuu on puu, jonka

  • lehtisolmut ovat vakioita, muuttujia tms
  • sisäsolmut ovat operaattoreita
  • operaattorin lapsisolmut ovat sen operandilausekkeiden rakennepuiden juuret

Yleistyy totta kai myös lauseisiin, määrittelyihin ym.

Composite-suunnittelumalli

  • Javan kaltaisessa staattisesti tyypitetyssä oliokielessä hyvä tapa toteuttaa rakennepuu on Composite-suunnittelumalli.
  • Ideana on abstrakti yläluokka, jonka aliluokkia ovat niin puun lehti- kuin sisäsolmutkin.
  • Hyvä luoda abstrakti yläluokka lausekkeille, lauseille, deklaraatioille tms
  • Yläluokkaan voi lisätä abstraktin metodin kullekin rakennepuuta syötteenään käyttävälle kääntäjän osalle (esim. tarkastaja, välikoodin generoija).
    • hyvä ratkaisu, jos kieli muuttuu useammin kuin sitä käsittelevät algoritmit

Visitor-suunnittelumalli

  • Rakennepuuhun kohdistuvien operaatioiden erottaminen ohjelmatekstissä rakennepuun määrittelystä on usein hyödyllistä.
  • Tämän toteuttaa Visitor: rajapinta, jossa on visit-metodi jokaiselle rakennepuu-Compositen lehtisolmuluokalle.
    • ei tarvita kaikissa kielissä
  • Lisäksi Compositen yläluokassa on abstrakti metodi accept, joka toteutetaan jokaisessa lehtisolmuluokassa täsmälleen samalla koodilla.
  • Tässä hyödynnetään metodin ylikuormitusta, joten saman koodin siirtäminen yläluokkaan rikkoo Visitorin.
  • Jokainen rakennepuusta erilleen koodattava operaatio on yksi Visitor-rajapinnan toteuttava luokka.

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

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
    • ks esim AJK-2017
  • 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

Etenemisjärjestys

Suosittelen:

  • tee ensin jäsentäjä
  • lisää sitten selaaja
  • lisää sitten rakennepuun määrittely ja rakentaminen

Voit myös aloittaa rakennepuun määrittelystä, jos se tuntuu helpommalta. Tee selaaja kuitenkin vasta jäsentäjän jälkeen.

Muista testaus!

  • Kääntäjän tulee toimia (lähes) kaikissa tilanteissa oikein.
  • Kääntäjä on monimutkainen ja siksi virheherkkä.
  • Automaattinen testaus on siksi erittäin suositeltavaa.
    • perustestit ennen koodia tai pian koodin kirjoittamisen jälkeen
    • joka bugista testi ennen korjausta, jotta bugin uusiutuminen huomattaisiin
    • kaikki testit hyvä ajaa aina käännöksen jälkeen
    • feilaavaan testiin puututtava välittömästi (ei saa jättää myöhemmäksi)

Perustestit

  • Pyri tekemään ainakin yksi testi jokaisesta toiminnosta.
    • Älä kuitenkaan tuhlaa aikaasi sellaisen asian testaamiseen, joka ei voi hajota (ellei osoittaudu, että olet väärässä)
  • Jos et ole varma, osaatko koodata jonkin asian oikein, tee siitä testi.
  • Priorisoi virheherkkiä tilanteita.
    • Rajankäynnit ovat usein virheherkkiä – niihin kannattaa kiinnittää huomiota.
  • tarkemmin testauskursseilla (TIES546, TJTS50)

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