Sintaksa in aritmetični izrazi

Naloga: iz konkretne v abstraktno sintakso

Dane izraze, zapisane v konkretni sintaksi, predstavi z abstraktno sintakso kot drevo. Pri tem veljajo običajna pravila za prioriteto in asociativnost aritmetičnih operacij.

1. x + 7 * 8
2. 1 + 2 + 3 + 4
3. a + (b + c) + d
4. 10 - 5 - x
5. 42

Rešitev

  +              +           +           -      42
 / \            / \         / \         / \
x   *          +   4       +   d       -   x
   / \        / \         / \         / \
  7   8      +   3       a   +       10  5
            / \             / \
           1   2           b   c

Naloga: iz abstraktne v konkretno sintakso

Izraze, predstavljene z abstraktno sintakso kot drevo, pretvori v konkretno sintakso. Upoštevaj običajna pravila za prioriteto in asociativnost aritmetičnih operacij.

   +                 *           42          -
  / \               / \                     / \
 7   *             /   \                   1   2
    / \           +     *
   a   0         / \   / \
                a   b c   d

Rešitev

7 + a * 0
(a + b) * (c * d)
42
1 - 2

Naloga: kvadriranje

Dana je abstraktna sintaksa aritmetičnih izrazov:

⟨izraz⟩ ::= ⟨aditivni-izraz⟩ EOF

⟨aditivni-izraz⟩ ::= ⟨multiplikativni-izraz⟩ | ⟨aditivni-izraz⟩ + ⟨multiplikativni-izraz⟩

⟨multiplikativni-izraz⟩ ::= ⟨osnovni-izraz⟩ | ⟨multiplikativni-izraz⟩ * ⟨osnovni-izraz⟩

⟨osnovni-izraz⟩ ::= ⟨spremenljivka⟩ | ⟨številka⟩ | ( ⟨izraz⟩ )

⟨spremenljivka⟩ ::= [a-zA-z]+

⟨številka⟩ ::= -? [0-9]+

Jezik želimo razširiti s funkcijo sqr, ki sprejme argument in izračuna njegov kvadrat. Na primer, sqr(5) se izračuna v 25.

Podnaloga: Popravite abstraktno sintakso tako, da bo jezik omogočal tudi izraze oblike sqr(e), kjer je e aritmetični izraz.

Dana je semantika velikih korakov za aritmetične izraze:

—————————-
η | n ↪ n


 η(x) = n
————————––
η | x ↪ n

η | e₁ ↪ n₁  η | e₂ ↪ n₂
————————————————————–———
 η | e₁ + e₂ ↪ n₁ + n₂


η | e₁ ↪ n₁  η | e₂ ↪ n₂
————————————————————–———
 η | e₁ - e₂ ↪ n₁ - n₂


η | e₁ ↪ n₁  η | e₂ ↪ n₂
————————————————————–———
 η | e₁ * e₂ ↪ n₁ · n₂

Podnaloga: Semantiko popravite tako, da se bo vsebovala tudi ustrezno pravilo za sqr.

Rešitev

Med pravili za multiplikativni-izraz in osnovni-izraz dodamo pravilo za kvadratni-izraz. Popraviti moramo tudi pravilo za multiplikativni-izraz, tako da zamenjamo sklice na osnovni-izraz.

⟨izraz⟩ ::= ⟨aditivni-izraz⟩ EOF
⟨aditivni-izraz⟩ ::= ⟨multiplikativni-izraz⟩ | ⟨aditivni-izraz⟩ + ⟨multiplikativni-izraz⟩
⟨multiplikativni-izraz⟩ ::= ⟨kvadratni-izraz⟩ | ⟨multiplikativni-izraz⟩ * ⟨kvadratni-izraz⟩
⟨kvadratni-izraz⟩ ::= sqr ( ⟨aditivni-izraz⟩ ) | ⟨osnovni-izraz⟩
⟨osnovni-izraz⟩ ::= ⟨spremenljivka⟩ | ⟨številka⟩ | ( ⟨izraz⟩ )
⟨spremenljivka⟩ ::= [a-zA-z]+
⟨številka⟩ ::= -? [0-9]+

Semantiko dopolnimo s pravilom za kvadratni-izraz:

    η | e ↪ n
—————————————————
 η | sqr(e) ↪ n²

Naloga: bitni zamik

Obravnavamo aritmetične izraze iz naloge "Kvadriranje".

Aritmetičnim izrazom dodajte operaciji >> in <<, ki delujeta tako kot v Javi. Se pravi,

a << k

zamakne število a za k mest v levo v dvojiškem zapisu. Podobno

a >> k

zamakne število a za k mest v desno v dvojiškem zapisu.

1. Razširite abstraktno sintakso aritmetičnih izrazov, da bo vsebovala >> in <<.

2. Dopolnite semantiko velikih korakov. Premislite, kako naj se izračuna zamik, ko je k negativno število.