Kääntäjätekniikka

Luento 4 (6.4.2016)

Luennolla koodattu laskin Yousourcessa

Kääntäjän rakenne

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

• voi tehdä käsin
  • olennaisesti koodataan laaja mutta rakenteeltaan yksinkertainen DFA
  • ks. esim. AJK-2009:n varhainen versio
• kannattaa yleensä tehdä työkalulla, esim.
  • Flex
  • JFlex (ks. AJK-2009)
  • Alex
  • PLY Lex (ks. AJK-2016)
• jäsentäjän laatimistekniikasta riippuen voi tehdä myös jäsentimen osana

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

• ANTLR - LL(*)
• JavaCC - LL(1), osittain LL(k)
• SableCC - LALR
• CUP - LALR, ks. AJK-2009
• Yacc - LALR
• Bison - LALR / GLR
• Happy - LALR / GLR
• Frown - LALR
• PLY Yacc - LALR, ks. AJK-2016

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

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

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)

Ville jatkaa tästä

materiaali