Vaje 1 (aritmetični izrazi)

• Kako bodo potekale vaje? Enkrat tedensko, po urniku, fizično na FRI.

• Kako bo potekal predmet? Kaj so moje obveznosti? Prisotnost na vajah je zaželena, ni pa obvezna. Ravno tako ni obveznih domačih nalog. Za uspešno opravljanje predmeta je dovolj pozitivna ocena na izpitu.

• Kje/kako si lahko presnem virtualko v kateri je že nameščena vsa programska oprema, ki jo "potrebujemo" pri tem predmetu? Prek naslednje magnetne povezave: magnet:?xt=urn:btih:4c7b48dea58ea887c6eb6248f10968241c56bfd9&dn=ppj23-ovf-1.0&tr=udp%3a%2f%2ftracker.opentrackr.org%3a1337%2fannounce

• Kje lahko dobim povezavo do Discord serverja in ostale informacije glede predmeta? Na spletni učilnici.

• Kje lahko dobim dodatne naloge: V knjigah (glej učilnico), v zapiskih predavanj, na vajah, na učilnici (pod poglavjem Naloge za utrjevanje), na Discod serverju. Trenutno je še vse prazno, tekom predmeta pa bodo na teh lokacijah objavljene naloge.

Priprava na vaje Odgovori na spodnja vprašanja (kontekst so predavanja prejšnjega tedna):

• Kaj je gramatika?
• Kaj pomeni kratica BNF?
• Kaj je parser/razčlenjevalnik?
• Kakšno vlogo igra lexer pri razčlenjevanju?
• Kaj je abstraktno sintaktično drevo (AST)?
• Kaj je operacijska semantika?
• Kaj je asociativnost operatorjev? Kaj pomeni, da je operator levo/desno asociativen? Kaj pomeni, da nima asociativnosti?
• Kaj je S-expression?

Aritmetični izrazi

Prenesi kalkulator za osnovne aritmetične izraze. Kalkulator razume jezik, opisan z naslednjo gramatiko v notaciji BNF:

⟨izraz⟩ ::= ⟨aditivni⟩ EOF
⟨aditivni⟩ ::= ⟨multiplikativni⟩ | ⟨aditivni⟩ + ⟨multiplikativni⟩
⟨multiplikativni⟩ ::= ⟨nasprotni⟩ | ⟨multiplikativni⟩ * ⟨nasprotni⟩
⟨nasprotni⟩ ::= - ⟨nasprotni⟩ | ⟨osnovni⟩
⟨osnovni⟩ ::= ( ⟨aditivni⟩ ) | ⟨spremenljivka⟩ | ⟨konstanta⟩
⟨spremenljivka⟩ ::= [a-zA-Z]+
⟨konstanta⟩ ::= ⟨float⟩

Pravilo za ⟨float⟩ je enako kot zapis nenegativnih konstant tipa float v Javi, na primer 3.14 (brez znanstvene notacije tj. 1.3E-13).

V primerih uporabljamo okolje [x ↦ 42, y ↦ 3.14, z ↦ 1].

Vprašanja:

• Ali lahko iz dane gramatike razbereš asociativnost operatorjev?
• A lahko "pokvariš" dano gramatiko tako, da bodo operatorji "brez asociativnosti"?
• A lahko iz dane gramatike razbereš prioriteto operatorjev/ločil?

Izpis drevesa abstraktne sintakse

Po vsakem interpretiranju poleg rezultata izpiši še drevo abstraktne sintakse (AST). Primer:

Izraz: 1 + 2 * 3 + -4
AST: (+ (+ 1.0 (* 2.0 3.0)) (- 4.0))
Vrednost: 3.0

Spremembe gramatike

Razširi gramatiko in popravi parser tako, da bo kalkulator podpiral naslednje operacije. Dodaj tudi ustrezne razrede, izpeljane iz razreda Izraz.

Minus

Kalkulatorju dodaj podporo za odštevanje, torej izraze oblike a - b. Primeri:

Izraz: 80 - 38
Vrednost: 42.0
Izraz: x - (12 + y)
Vrednost: 26.86
Izraz: 1 - 2 - 3
Vrednost: -4.0

Potenca

Kalkulatorju dodaj operator ^ za računanje potence, torej izraze oblike a^b. Za razliko od operatorjev +, -, * in / je potenca desno asociativna: a^b^c = a^(b^c). Primeri:

Izraz: 2^4
Vrednost: 16.0
Izraz: (x-1)^(1+3)
Vrednost: 2825761.0
Izraz: 2^3^3
Vrednost: 134217728.0

Namig: implementacija aditivnih in multiplikativnih izrazov uporablja zanko, ker sta + in * levo asociativna. Potenciranje je desno asociativno in ga lahko implementiramo neposredno, brez uporabe zanke. (Kar pomeni: ne kopiraj kode na slepo!)

Funkcije z ariteto 1

Navodila bodo podana na vajah. Primeri:

Izraz: 100 + sin x * sin x + cos x * cos x 
AST: (+ (+ 100.0 (* (sin x) (sin x))) (* (cos x) (cos x)))
Vrednost: 101.0
Izraz: sin (x + y) - (sin x * cos y + cos x * sin y) 
AST: (- (sin (+ x y)) (+ (* (sin x) (cos y)) (* (cos x) (sin y))))
Vrednost: 2.220446049250313E-16
Izraz: sin x ^ 2 + cos x ^ 2
AST: (+ (^ (sin x) 2.0) (^ (cos x) 2.0))
Vrednost: 1.0

Poenostavljanje izrazov

Razredu Izraz dodaj metodo poenostavi, ki izraz prepiše v enostavnejšo obliko. Metoda naj dani izraz poenostavi, kolikor se da. Pri tem uporabi spodnje transformacije, lahko pa se spomniš še kakšne.

Konstantni podizrazi

Izraz poenostavi tako, da izračunaš podizraze brez spremenljivk. Primeri:

Izraz: x + 2*4
Poenostavljeno: (+ x 8.0)
Izraz: 5 + 2*4
Poenostavljeno: 13.0
Izraz: 2 + (x - 1)
Poenostavljeno: (+ 2.0 (- x 1.0))
Izraz: (2 + 3) * (x + y)
Poenostavljeno: (* 5.0 (+ x y))

Množenje in prištevanje 0 in 1

Poenostavi izraze oblike 0 + e, 0 * e in 1 * e ter njihove obrnjene različice.

Dodatno lahko poenostaviš tudi izraze oblike: e ^ 0, 0 ^ e, 1 ^ e, e ^ 1, 0 - e in e - 0.

Izpis izrazov

Dana implementacija razreda Izraz izpiše izrazno drevo kot S-expression. Razredu dodaj metodo izpis, ki izraz izpiše v bolj običajnem infiksnem zapisu. Primer:

Izraz: 2 * 42 - (x + 4 + 5)
Izpis: ((2 * 42) - ((x + 4) + 5))

★ Metoda naj izpiše izraz brez odvečnih oklepajev. Primer:

Izraz: ((2 * 42) - ((x + 4) + 5))
Izpis: 2 * 42 - (x + 4 + 5)