TIES448 Luento 2 (1.11.2018)

Palataas vielä tiistain luennon asiaan

Haskell-versio esimerkistä

Harjoitustyöstä

Lähdekieli

  • suositeltavaa ottaa olemassaoleva ohjelmointikieli pohjaksi
  • suunnitelmassa hahmoteltava poikkeamat pohjaksi otetusta kielestä
  • Kurssin aikana keretään todennäköisesti toteuttaa vain osa kielestä, joten halutut ominaisuudet on hyvä priorisoida.

Hyviä kohdekieliä

  • Voitte valita, että teette tulkin (joko suoraan taikka oman välikielen kautta).
  • Standardoitu välikieli (LLVM, Java bytecode, .NET CIL, webassembly)
  • Oikea konekieli (lähinnä AMD64 ja ARM)
    • sallittua on tuottaa symbolista konekieltä,
    • suositeltavaa, että tällöin kääntäjä kutsuu assembleria automaattisesti
    • kiinnitä myös käyttöjärjestelmä (esim. Linux tai Windows)

Isäntäkielen valinnasta

  • mikä tahansa ohjelmointikieli, jonka tulkkaaminen tai kääntäminen onnistuu luentosalissa (viimeistään omalla läppärillä)
  • kiinnitä huomiota:
    • Kuinka hyvin kieli tukee laajojen ohjelmien tekemistä?
    • Kuinka helppoa sillä on käsitellä puu- ja graafitietorakenteita?
    • Onko sille olemassa kielioppityökaluja (vrt. yacc, CUP)?
    • Kuinka hyvin osaat kieltä jo valmiiksi?
  • Suosittelen Haskellia ja muita ML-suvun kieliä (SML, OCaml),
    • vain jos osaat niitä jo valmiiksi.

Vastuun jako

Ryhmässä on hyvä jakaa seuraavat vastuut:

  • ryhmänjohtaja, joka huolehtii siitä, että tekeminen etenee ja ratkaisee kiistat siitä, kuka tekee mitäkin
  • (lähde)kielitsaari, joka ratkaisee kiistat lähdekielen ominaisuuksista
  • testi-inkvisiittori, joka vastaa testauksen kattavuudesta
  • kohdekieliguru, joka tutustuu kohdekielen saloihin ja selvittää tarvittaessa vastaukset kohdekieltä koskeviin kysymyksiin
  • työkaluguru, joka tutustuu valittuihin työkaluihin ja selvittää tarvittaesa vastaukset työkaluja koskeviin kysymyksiin

Luonnollisesti samalla henkilöllä voi olla useita rooleja. Jokainen tietenkin osallistuu itse tekemiseen!

Harjoitustyöstä selviälminen

  • aloita heti
  • älä pysähdy
  • ajattele mitä teet
  • älä pelästy epämukavuuden tunnetta
  • pyydä apua ajoissa
  • pidä tuntikirjanpitoa
    • jos op-määrät ylittyvät perustellusti, voidaan harkita ylimääräisten opintopisteiden antamista toisella koodilla (esim. ohjelmointityö tai erikoistyö)

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)

Luentotehtävä

Koskien lukutehtävää:

  • Mitä uutta opit?
  • Mitä jäi epäselväksi?

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

Sanasten määrittely säännöllisillä lausekkeilla

  • Kustakin sanasluokasta annetaan säännöllinen lauseke, joka kuvaa tämän sanasluokan lekseemit
  • Yleensä maximum munch rule: jos voidaan muodostaa useampi lekseemi, valitaan niistä pisin.
  • Lausekkeet laitetaan järjestykseen niin, että ylin täsmäävä valitaan.

Regular descriptions

  • (kirjan termi, en ole nähnyt muualla)
  • Annetaan säännöllisille lausekkeille nimiä, joita voi käyttää toisissa säännöllisissä lausekkeissa.
  • Rekursiiviset määritelmät kielletään.

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ä

Välimerkit

  • jokainen oma lekseemiluokkansa, koska jokaisella eri syntaktinen tehtävä
  • myös operaattorit välimerkkejä
    • poikkeus: kielet joissa omien operaattoreiden määrittely mahdollista (esim. Haskell)
  • tavallisesti yhden merkin pituisia, mutta ei suinkaan aina
  • semanttinen merkitys identtinen lekseemiluokan kanssa
  • Javassa:
   (  )  {  }  [  ]  ;  ,  .  =  >  <  !  ~  ?  :  ==  <=  >=  !=  &&
   ||  ++  --  +  -  *  /  &  |  ^  %  <<  >>  >>>  +=  -=  *=  /=  &=  |=
   ^=  %=  <<=  >>=  >>>=

Vakiot

  • kokonaisluvut, desimaaliluvut, e-notaatio, merkkivakiot, merkkijonovakiot
  • rakenne usein monimutkainen – selaajan kannalta hankalaa
    • lukujen eri esitysmuodot
    • merkki(jono)vakioiden escape-merkinnät (\n)
  • lekseemiluokkia yleensä yksi per semanttinen tyyppi
  • semanttinen arvo: lukuvakion lukuarvo, merkkijonovakion tarkoittama merkkijono ym.

Kokonaislukuvakiot

  • perusrakenne selkeä:
    • aluksi yksi tai useampia numeromerkkejä
    • vakio päättyy viimeiseen numeromerkkiin
  • komplikaatioita:
    • numerojärjestelmän kantaluvun esittäminen (10H, 010, 0x10)
    • mahdolliset suffiksit (esim. C:n tyyppisuffiksit: 10ul)
    • lukutyyppiin nähden liian isot tai liian pienet luvut

Liukulukuvakiot

  • perusrakenne:
    • aluksi nolla tai useampia numeromerkkejä (kokonaisosa)
    • sitten mahdollisesti desimaalierotin (yleensä .)
    • sitten nolla tai useampia numeromerkkejä (desimaaliosa)
    • sitten mahdollisesti kirjain e tai E
    • sitten (mahdollisesti etumerkillinen) kokonaisluku (eksponentti)
  • desimaalierotin on pakollinen jos desimaaliosa löytyy
  • e-kirjain on pakollinen, jos eksponentti löytyy
  • joko kokonaisosa tai desimaaliosa tulee löytyä
  • joko desimaaliosa tai eksponentti tulee löytyä
  • hankalaksi selaamisen tekee monien osien vapaaehtoisuus
  • semanttinen tulkinta myös hankalaa

Merkki(jono)vakiot

  • tyypillinen rakenne:
    • alkaa ja päättyy lainausmerkillä (yleensä ' tai ")
    • koostuu merkeistä sellaisinaan sekä komentomerkkisarjoista
  • lainausmerkki ei voi sellaisenaan olla osa merkki(jono)vakiota
  • paljon vaihtelua eri kielissä
    • komentomerkkisarjat hyvin erilaisia
    • Voiko merkkijonovakio koostua useasta rivistä?
      • Jos voi, kuuluvatko merkkijonon sisällä olevan rivinvaihdon jälkeiset välilyönnit ja tabulaattorit merkkijonon semanttiseen sisältöön?
    • Voiko ohjelman muuttujiin viitata merkkijonon sisällä (interpolaatio)?

Merkki(jono)vakioiden komentomerkkisarjoja

  • C-sukuisten kielten komentomerkkisarjoja
    • \l, missä l on kirjain, edustaa erityismerkkiä, esim. \t
    • \m, missä m on välimerkki, edustaa ko. välimerkkiä sellaisenaan, esim. \\, \"
    • \xhh, missä h on heksadesimaalinumero, edustaa heksadesimaaliluku hh:n tarkoittamaa merkkiä (esim. \x20 on ASCII-koodauksen vallitessa välilyönti)
    • \0ooo, missä o on oktaalinumero, edustaa oktaaliluku ooo:n tarkoittamaa merkkiä (esim. \044 on ASCII-koodauksen vallitessa dollarinmerkki)
    • \uhhhh, missä h on heksadesimaalinumero, edustaa heksadesimaaliluku hhhh:n tarkoittamaa Unicode-merkkiä (esim. \u203D on ns. interrobang ‽)
  • joissakin kielissä "" edustaa lainausmerkkiä sellaisenaan eikä päätä merkki(jono)vakiota

Nimet

  • perusrakenne:
    • alkaa merkillä, joka luokitellaan nimenaloittajaksi
    • jatkuu niin kauan kuin löytyy merkkejä, jotka luokitellaan nimenjatkajiksi
  • nimenaloittajia ovat yleensä kirjaimet ja jokunen erikoismerkki (esim. alaviiva ja dollari)
  • nimenjatkajia ovat yleensä kaikki nimenaloittajat sekä lisäksi kymmenjärjestelmän numeromerkit
  • Kielissä, jotka sallivat omien operaattoreiden määrittelyn, esimerkiksi Haskell, samaa periaatetta käytetään usein myös operaattorin määrittelyssä.
  • lekseemiluokkia
    • avainsanat (engl. keyword), kukin erikseen
    • tyyppinimi (engl. type name)
    • tunnus (engl. identifier)

Avainsanat

  • esimerkkejä: if, while, class
  • nimiä, joilla on syntaktinen erityistehtävä
  • tavallisesti varattuja sanoja (engl. reserved words)
    • Jos avaisana löytyy lähdekoodista, se käsitellään avainsanana.
  • Joissakin (vanhemmissa) kielissä avainsanat eivät ole varattuja, vaan avainsanan tunnistaminen tapahtuu vasta jäsennysvaiheessa.
    • sivuutetaan tämä sotku tällä kurssilla kokonaan
    • klassinen varoittava esimerkki (PL/I):
      IF IF = THEN THEN THEN = ELSE; ELSE ELSE = IF;

Tyyppinimet

  • tyyppinimet usein erillinen lekseemiluokka jäsennyksen helpottamiseksi
  • Osa tyypeistä nimetään yleensä avainsanoilla (esim. Javan int); nyt kyse ohjelmoijan nimeämistä tyypeistä.
  • Joissakin kielissä tyyppinimet alkavat isolla kirjaimella.
  • Toisissa kielissä tyyppinimet määritellään ohjelmatekstissä.
    • Selaajalla tulee tällöin olla luettelo kullakin hetkellä määritellyistä tyyppinimistä.
    • Jäsentäjä päivittää listaa tarpeen mukaan.
    • Tässä systeemissä selaaja ja jäsentäjä eivät voi olla erillisiä.

Entäpä kommentit ja välilyönnit?

  • tavallisesti eivät lekseemejä
  • selaaja lopettaa lekseemin kommentin tai välilyönnin vastaan tullessa
  • seuraavaa lekseemiä etsitään kommentin loputtua tai välilyönnin jälkeen
  • välilyönnin veroisia myös rivinvaihdot ja tabulaattorit

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ä

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