Harjoitukset 5

Näistä harjoituksista voi saada 0-6 pistettä.

HUOM: Voit käyttää vastaavia osia omasta harjoitustyöstäsi esimerkkikielen sijaan.

Oppimistavoitteet

• Opit manipuloimaan AST:tä
• Opit toteuttamaan sokerinpilkkojan

Tehtävä 1

Tarkastellaan jälleen tuttua kieltä:

	Abstrakti muoto	Syntaksi	Selite
Typ τ ::=	\(\text{num}\)	Number	Numerotyyppi
	\(\text{str}\)	String	Merkkijonotyyppi
	\(\text{bool}\)	Bool	Merkkijonotyyppi
Exp e ::=	\(x\)	alphanum	Muuttuja
	\(\text{num}[n]\)	n	Numero
	\(\text{str}[s]\)	"s"	Merkkijono
	\(\text{bool}[b]\)	b	Totuusarvo
	\(\text{plus}(e_1;e_2)\)	\(e_1\) + \(e_2\)	Yhteenlasku
	\(\text{mul}(e_1;e_2)\)	\(e_1\) * \(e_2\)	Kertolasku
	\(\text{cat}(e_1;e_2)\)	\(e_1\) ++ \(e_2\)	Yhteenlasku
	\(\text{len}(e)\)	\(e\).length()	Merkkijonon mitta
	\(\text{null}(e)\)	null \(e\)	Onko tyhjä?
	\(\text{let}(e_1;x.e_2)\)	let \(x\) be \(e_1\) in \(e_2\)	Lokaali sidonta
	\(\text{if}(e_1;e_2;e_3)\)	if \(e_1\) then \(e_2\) else \(e_3\)	Ehtolause

Laajennetaan kieltä vielä seuraavalla taulukolla:

	Abstrakti muoto	Syntaksi	Selite
Typ τ ::=	\(\text{cmd}(\tau)\)	cmd \(\tau\)	Komento
Cmd m ::=	\(\text{pure}(e)\)	pure(\(e\))	Komento joka laskee lausekkeen
	\(\text{bnd}(e;x.m)\)	\(x\) <- \(e\) ; \(m\)	Ketjutus
	\(\text{dcl}(e;a.m)\)	new \(a\) = \(e\) ; \(m\)	Muuttuvaisen luominen
	\(\text{get}[a]\)	\(@a\)	Muuttuvaisen lukeminen
	\(\text{set}[a](e)\)	a := e	Muuttuvaiseen kirjoittaminen
	\(\text{read}\)	read	Käyttäjän syötteen lukeminen
	\(\text{print}(e)\)	print \(e\)	Tulostaminen konsoliin
Exp e ::=	\(\text{cmd}(m)\)	do \(m\)	Komento Expiksi
Top T ::=	\(\text{toplevel}[x](m)\)	program \(x\) is \(m\)	Toplevel tjsp. "pääohjelma"

Kuten aiemmin huomattiin, tämä kieli on jo melko ilmaisuvoimainen, mutta melko kömpelö käyttää. Esimerkiksi ainoa tapa suorittaa komentoja on \(\text{bnd}[e;x.m]\), joka sitoo aina uuden muuttujan, eli pelkkä hello-world ohjelmakin näyttää kankealle:

() <- print "Hello";
() <- print "World";
pure(0);

Ongelma voitaisiin ratkaista luomalla uusi "\(\text{nonbnd}[e;m]\)" komento, joka automaattisesti jättäisi muuttujan sitomatta. Tämä kuitenkin lisää tyypintarkastukseen ja koodingenerointiin yhden ylimääräisen tilanteen kuhunkin.

Tässä on mahdollista käyttää sokerinpilkontaa. Tee AST:hesi ylimääräinen muoto \(\text{nonbnd}[e;m]\) (tai tee kokonaan eri versio AST:stäsi jossa tälläinen on). Tee seuraavaksi konversio, joka etsii AST:stäsi kaikki nonbnd:t ja korvaa ne vastaavalla tavallisella bnd-muodolla.

Huomaa, että tyypintarkastuksen voit olettaa jo tehdyksi ja näin ollen annetun AST:n "virheettömäksi".

2pt

Tehtävä 2

Seuraava ohjelmakin näyttää kömpelölle:

program Testi is

new laskuri = 0; 

i <- read;
s <- @laskuri;
laskuri := s+i;

i2 <- read;
s2 <- @laskuri;
laskuri := s2+i2;

i3 <- read;
s3 <- @laskuri;
laskuri := s2+i3;

tulos <- @laskuri;

print tulos;

pure 0;

.. Käyttäjä syöttää "42" "41" "1"
.. Ohjelma tulostaa "84"
.. Ohjelma päättyy paluuarvolla 0

Olisi paljon kätevämpää, jos kielessä olisi Javan ja C:n kaltainen += operaattori. Lisää kieleen tälläiset operaattorit yhteen- ja kertolaskulle sekä merkkijonojen yhdistämiselle. Luo sitten sokerinpilkkoja, joka korvaa nämä rakenteet vastaavilla olemassa olevilla rakenteilla.

2pt

Tehtävä 3

Laajenna edellisen tehtävän välikieltä käsittelemään myös seuraava laajennos

	Abstrakti muoto	Syntaksi	Selite
Exp e ::=	\(\text{while}[x;m]\)	while x in m	Rekursio

Toteuta tälle tyypitys.

1pt

Tehtävä 4

Lisää pythonmaiset for-silmukat ASThesi. Tee tehtävän 3 pohjalta sokerinpilkkoja, joka muuttaa ne while silmukoiksi.

2pt

Tehtävä 6 -- Vaihe 3 harjoitustyöpalautus

Palauta harjoitustyösi vaihe 3 siinä kunnossa, että se täyttää harjoitustyöltä vaaditut minimivaatimukset.

Harjoitustyön 3. inkrementissä tavoitteena on lisätä harjoitustyöhön staattiset tarkistukset (mm. tyyppitarkastukset) ja tarvittaessa myös sokerinpilkkoja. Näiden kuuluu toimia ja olla testattuja vähintään harjoitustyön minimivaatimustason täyttävältä osalta.

Staattiset tarkistukset ovat toimivia, jos ne päästävät läpi vain sellaisia ohjelmia, jotka kääntäjä tulee valmistuttuaan kykenemään kääntämään loppuun asti virheettä.

6pt