Vaje 1 (aritmetični izrazi)
Ponovimo
Odgovori na spodnja vprašanja, pomagaj si s predavanji:
- Kaj je slovnica ali gramatika?
- Kaj pomeni kratica BNF?
- Kaj je razčlenjevalnik (angl. parser)?
- Kakšno vlogo igra lexer pri razčlenjevanju?
- Kaj je abstraktno sintaktično drevo (angl. abstract syntax tree (AST))?
- Kaj je asociativnost operatorjev? Kaj pomeni, da je operator levo ali desno asociativen? Kaj pomeni, da nima asociativnosti?
- Kaj je operacijska semantika?
Razčlenjevanje nizov
Dana je slovnica Boolovih izrazov:
⟨izraz⟩ ::= ⟨disjunktivni⟩ EOF
⟨disjunktivni⟩ ::= ⟨konjuktivni⟩ | ⟨konjuktivni⟩ ∨ ⟨disjunktivni⟩
⟨konjuktivni⟩ ::= ⟨negirani⟩ | ⟨konjuktivni⟩ ∧ ⟨konjuktivni⟩
⟨negirani⟩ ::= ¬ ⟨negirani⟩ | ⟨osnovni⟩
⟨osnovni⟩ ::= ( ⟨disjunktivni⟩ ) | ⊥ | ⊤ | ⟨spremenljivka⟩
⟨spremenljivka⟩ ::= [a-zA-Z]+
Da asistentu ne odpade roka (pri pisanju na tablo) bo uporabil naslednje okrajšave:
⟨i⟩ ::= ⟨d⟩ EOF
⟨d⟩ ::= ⟨k⟩ | ⟨k⟩ ∨ ⟨d⟩
⟨k⟩ ::= ⟨n⟩ | ⟨k⟩ ∧ ⟨k⟩
⟨n⟩ ::= ¬ ⟨n⟩ | ⟨o⟩
⟨o⟩ ::= ( ⟨i⟩ ) | ⊥ | ⊤ | ⟨s⟩
⟨s⟩ ::= [a-zA-Z]+
Za vsakega od naslednji izrazov ugotovi, ali ga lahko z zgornjimi pravili razčlenimo in ali lahko to naredimo enolično:
0 ∧ 1 ∨ 0(¬a ∧ b) ∨ (c ∧ (¬d ∨ e)) ∧ f¬a ∧ (b ∨) c ∧ (¬d ∨ e) ∧ f¬a ∧ (b ∨ ⊥) ∧ (¬d ∨ e) ∧ ⊤¬a ∧ b ∧ ⊥ ∧ (¬d ∨ e) ∧ ⊤(¬a ∧ b ∨ c ∧ d) ∧ ¬e ∨ f ∧ g ∨ h ∨ (⊤ ∧ (¬(i ∨ j) ∧ k))(¬(a ∧ b) ∨ (c ∧ d)) ∧ (¬e ∨ (f ∧ (g ∨ h))) ∨ (⊤ ∧ (¬(i ∨ j) ∧ k))
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 s členostjo 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)