Kääntäjätekniikka

Luento 5 (28.3.2017)

Inkrementit

(deadlineja päivitetty 1.6.2017)

Alustava deadline sulkeissa (klo 16 kyseisenä päivänä ellei muuta ilmoitettu)

Suunnittelu ja ryhmien muodostaminen (20.3.)
Jäsentäjä valmis (perjantai 7.4. klo 10)
Tarkastaja valmis (perjantai 5.5. klo 10)
Välikielen generointi valmis [tai muita ominaisuuksia 1 op:n arvosta lisää] (15.5.)
Kohdekielen generointi (naivi rekisteriallokaatio) valmis [tai muita ominaisuuksia 1 op:n arvosta lisää] (19.6.)
Fiksu rekisteriallokaatio valmis [tai muita ominaisuuksia 1 op:n arvosta lisää] (14.8. klo 12)
Koko työ viimeistelty ja valmis tarkastettavaksi (28.8. klo 12)

Muutoksia ohjauksiin

maanantaiohjaukset jatkuvat nykymallillaan
perjantain ohjaukset peruttu tältä viikolta
7.4. ja 28.4. perjantaiohjauksissa inkrementtideadline!
- paikallaoloa ja valmiutta esittelemään harjoitustyötä läsnäolijoille suositellaan
- muutokset johtuvat osin pääsiäistauon vaikutuksista aikatauluun
yksilöohjausta (voi tulla myös 2-3 hengen ryhmässä) varattavissa minulta Korpin kalenterin kautta
- laitan aikoja yleensä viikon kerrallaan edellisen viikon lopulla
- ajan rajallisuuden vuoksi valmistaudu esittämään selkeitä ongelmia ja kysymyksiä, joihin voin ottaa kantaa

Tänään

Käsitellään kääntäjän tarvitseman kieliopin kirjoittamisessa vastaan tulevia probleemoja ja niiden tavanomaisia ratkaisuja.

Sivuhuomautus: koodigeneraattorien käytöstä

älä koskaan muokkaa generoitua koodia käsin
älä tallenna generoitua koodia versionhallintaan
- tee skripti jolla generointi on helppoa ja laita se versionhallintaan
- käytä .gitignore-tiedostoa
molempiin sääntöihin on poikkeuksia, mutta näitä on syytä noudattaa jos ei ole erinomaisia perusteita poiketa

Lausekkeiden jäsennyksestä

Lausekkeet (expression) ilmaisevat arvon tuottavaa laskentaa
Lausekkeet rakennetaan yleensä atomilausekkeita yhdistelemällä operaattoreiden avulla.
- operaattoreita voi laittaa sisäkkäin periaatteessa rajattomasti
- välituloksien käsittelystä ei tarvitse ohjelmoijan huolehtia
Atomilausekkeet eivät sisällä alilausekkeita, jotka vaikuttavat atomilausekkeen arvoon. Niitä ovat mm.
- muuttujalauseke
- kokonaislukuvakiolauseke
- merkkijonovakiot, joissa interpolaatio ei ole sallittu

Operaattorien luokittelua

Operaattori ottaa ainakin yhden operandin, joka on lauseke
- operandien lukumäärää kutsutaan yleisesti sen ariteetiiksi eli paikkaluvuksi (engl. arity)
- jos operandeja on yksi, operaattori on unaarinen
- jos operandeja on kaksi, operaattori on binäärinen
- atomilausekkeita kutsutaan joskus nullaarisiksi (nullary) operaattoreiksi
Syntaktisesti operaattorit luokitellaan neljään luokkaan:
- prefiksioperaattorilauseke päättyy operandiin (mutta ei ala operandilla)
- postfiksioperaattorilauseke alkaa operandilla (mutta ei pääty operandiin)
- infiksioperaattorilauseke alkaa ja päättyy operandiin
- suljeoperaattorilauseke ei ala eikä pääty operandiin

Tavallisia (unaarisia) prefiksioperaattoreita

Aritmeettinen negaatio -
Looginen negaatio (esim. C:ssä !)
Bittikomplementti (esim. C:ssä ~)
Tyyppimuunnosoperaattori (esim. Javassa (String))
C-sukuisten kielten pre-inkrementointioperaattori (++)
Algol-kielten valintalauseke if...then...else
lambdalausekkeet monissa kielissä (esim. Haskellin \x ->)

Tavallisia postfiksioperaatioita

unaarisia:

tietueen tai olion kentän valinta (esim. C:ssä .a)
C-sukuisten kielten post-inkrementointioperaattori (++)

ei-unaarisia:

taulukon indeksointi (esim. [5])
funktiokutsu valtakielissä (esim. ("kissa", 42))

Tavallisia infiksioperaattoreita

binäärisiä:

aritmetiikan perusoperaattorit (+, -, *, /)
tavanomaiset bittioperaattorit (C-syntaksissa &, |, ^, >>, <<)
tavanomaiset loogiset konnektiivit (C-syntaksissa &&, ||)
vertailuoperaattorit (C-syntaksissa ==, !=, <, <=, >, >=)
sijoitusoperaattorit, jos sijoitusoperaatio tuottaa arvon (esim C:n =, += jne)

ei-binäärisiä:

C-sukuisten kielten valintalauseke ? ... : (esim. x == 0 ? 1 : 2 * x)

Tavallisia suljeoperaattoreita

jäsennystä ohjaavat sulkeet (...)
- usein jätetään merkitsemättä rakennepuuhun, koska jäsennyksen jälkeen näillä ei ole vaikutusta
olionluonti Java-syntaksissa new String(...)
listaliteraalit esim. Haskellissa [...]
monikonluonti mm. Haskellissa (...,...,...)
merkkijonoliteraalit, joissa interpolaatio on sallittu (esim. Perlin "Terve, $nimi!")
quasiquote-rakenteet yleisemminkin

Välihuomautus: interpolaatio selaajassa

Jos merkkijonoliteraalissa on sallittu viitata muuttujiin tai jopa laskea lausekkeiden arvoja, jotka tulevat osaksi merkkijonoa, pitää selaajan tuottaa tällaisesta literaalista useita sanasia.
Esim: "Hei $nimi!" $\rightarrow$
- BEGIN_INTERPOLATE
- STRING_LITERAL("Hei ")
- IDENTIFIER("nimi")
- STRING_LITERAL("!")
- END_INTERPOLATE

Lausekkeet naivisti kieliopissa

Yksi välikesymboli lausekkeille. Joka atomilauseketyypille ja joka operaattorille oma produktio.

<expr> ::= <numeric constant>
         | <variable name>
         | <expr> + <expr>
         | <expr> - <expr>
         | <expr> * <expr>
         | <expr> / <expr>
         | <expr> ( <optional expr list> )
         | <expr> [ <expr list> ]
         | <expr> . <field name>
         | ( <expr> )
<optional expr list> ::= <empty>
                       | <expr list>
<expr list> ::= <expr>
              | <expr list> , <expr>

Hyvä lähtökohta, mutta tähän ei pidä jäädä. Moniselitteinen, ei ohjaa jäsennystä riittävän hyvin.

Operaattoreiden presedenssi ja assosiatiivisuus

Kerrataan Automaattien ja kielioppien luennon 29.9.2016 kalvoilta (ks myös luentovideo ja jälkipruju)

Kalvoilla kuvatun menetelmän lisäksi on mahdollista monissa työkaluissa määritellä presedenssi ja assosiatiivisuus erikseen, jolloin edellä esitetty kielioppi on riittävä.

Lauseet

Lause (engl. statement) ilmaisee toiminnan, jolla on (sivu)vaikutuksia mutta joka ei tuota arvoa.

Lause voi olla yksinkertainen lause (engl. simple statement), jota toisinaan kutsutaan myös käskyksi (engl. instruction).

Nykykielet ovat yleensä lohkorakenteisia (eng. block-structured), jolloin

lauseita voidaan laittaa peräkkäin ja näin muodostaa lohko (block)
valinta- ja toistorakenteet tulkitaan rakenteisiksi lauseiksi (engl. compound statements), jotka sisältävät yhden tai useamman lohkon

Muuttujaan sijoitus

Muuttujaan sijoitus (engl. variable assignment) on tavallisesti (yksinkertainen) lause.
Yksinkertainen sijoitus on muotoa muuttuja := lauseke
- Sijoitusoperaattori vaihtelee (esim. C:ssä =)
Jos kielessä on mahdollista sijoittaa taulukon alkioon tai tietueen kenttään, kannattaa sijoitus esittää muodossa lauseke := lauseke
- vasen lauseke ilmoittaa sijoituksen kohteen

Muita yksinkertaisia lauseita

Tyhjä lause (no-op) skip tai usein vain ;
Aliohjelman paluu return
Silmukan keskeyttäminen break tai uuden iteraation aloittaminen continue
Ehdoton hyppy goto (useista kielistä jätetty tarkoituksella pois)
Poikkeuksen heittäminen throw
Proseduuri on aliohjelma, jolla ei ole paluuarvoa. Sen kutsu on yksinkertainen lause.
- Vanhoissa kielissä alkoi avainsanalla call tms, mutta nykyään pidetään tyylikkäämpänä, että kutsu alkaa suoraan proseduurin nimellä.
Joissakin kielissä syöttö ja tulostus ovat yksinkertaisia lauseita.

Lausejonot

Vaihtoehto A: Jokainen lause päättyy johonkin avainsanaan tai välimerkkiin.

<statement> ::= <variable> := <expression> ;
              | return <expression> ;
              | ...
              
<statements> ::= <statement>
               | <statements> <statement>

Vaihtoehto B: Lauseiden väliin laitetaan välimerkki

<statement> ::= <variable> := <expression>
              | return <expression>
              | ...
              
<statements> ::= <statement>
               | <statements> ; <statement>

Vaihtoehto C: Jokainen lause alkaa avainsanalla

<statement> ::= let <variable> := <expression>
              | return <expression>
              | ...
              
<statements> ::= <statement>
               | <statements> <statement>

Yleensä vaihtoehtoa A pidetään parhaana vaihtoehtona.

Lohkot

Lohko (engl. block) on suljerakenteella rajattu jono lauseita.
- { ... } (C-sukuiset kielet)
- begin ... end (varsin moni muu kieli)
- joissakin kielissä (esim. Python ja Haskell) suljerakenne johdetaan sisennyksestä
- joissakin kielissä suljerakenteen syntaksi tulee ympäröivästä kontekstista
Moni kieli sallii lohkossa paikallisten muuttujien määrittelyjä
- helpointa tehdä niin, että muuttujan määrittely on lause
- vanhemmissa kielissä määrittely oli sallittu vain lohkon alussa
Lohko itsessään kelpaa yleensä lauseeksi.

<statement> ::= ...
              | block

<block> ::= { }
          | { <statements> }

Yleiset silmukat

Yleisin mahdollinen silmukkarakenne sisältää kolme osaa:
- Lopetusehtoa edeltävät lauseet
- Lopetusehto
- Lopetusehdon jälkeiset lauseet

<statement> ::= ...
              | loop { <statements> if ( <expression> ) break ; <statements> }

Tästä erityistapauksena ehdon tarkistus alussa:

<statement> ::= ...
              | while ( <expression> ) <block>

ja lopussa

<statement> ::= ...
              | do <statements> while <expression> ;

Rajoitetut silmukkarakenteet

säilön läpikäynti

<statement> ::= ...
              | for <variable> in <expression> <block>

klassinen for-silmukka

<statement> ::= ...
              | for <variable> = <expression> to <expression> <step_part> <block>

<step_part> ::= <empty>
              | step <expression>

Silmukoiden syntaksivariaatioita

C-tyyli

<statement> ::= while ( <expression> ) <statement>

Pascal-tyyli

<statement> ::= while <expression> <block>
<block> ::= begin <statements end

Algol 68 -tyyli

<statement> ::= while <expression> do <statements> od

Lauseet vs lausekkeet C-sukuisissa kielissä

C-sukuisissa kielissä sijoituslauseet ja proseduurikutsut ovat lausekkeita
- sijoituslauseke palauttaa sijoituksen kohteena olevan muuttujan
- proseduuri on funktio, jonka paluuarvon tyyppi on void
lauseke muuttuu lauseeksi, kun sen perään laitetaan puolipiste

<statement> ::= <expression> ;
<expression> ::= ...
               | <expression> = <expression>
               | <expression> ( <optional expression list> )
<optional expression list> ::= <empty>
                             | <expression list>
<expression list> ::= <expression>
                    | <expression list> , <expression>

Torstaille jäänee

deklaraatiot
toplevel
modulisysteemit