Test A, priorita a asociatívnosť operátorov

Ciele
  1. Test A: Odvodenie DKA z regulárneho výrazu a význam inštrukcií Computron.
  2. Zopakovať si implementáciu syntaxou riadeného interpretátora na základe gramatiky jazyka.
  3. Naučiť sa definovať syntax operátorov rôznych priorít a asociatívnosti pomocou gramatiky.
  4. Zvládnuť zmeniť asociatívnosť výrazov v gramatike aj v kóde a experimentálne zistiť rozdiel medzi jednotlivými typmi asociatívnosti.
Úvod
    Test bude pozostávať z dvoch úloh:
    • 1. úloha (3b)
      • jedna inštrukcia Computron VM,
      • úlohou je napísať operačnú sémantiku inštrukcie slovne aj formálne.
    • 2. úloha (7b) - Prevod RV na KSA
      • nakresliť prechodový diagram RV,
      • odvodiť prechodový graf,
      • nakresliť KSA.
Postup
  1. Úloha: Pripravte si pero a papier rozmeru min. A5.

  2. Ak je syntaktický analyzátor implementovaný pomocou rekurzívnych funkcií, prioritu a asociatívnosť operátorov je možné vyjadriť tvarom pravidiel gramatiky.

    Pre zabezpečenie správnej priority operátorov sa pre každú prioritnú úroveň vytvorí jeden neterminál. Právidla sa pre jednotlivé úrovne sa zreťazia tak, že smerom dovnútra (vnáranie k operandom) sa zvyšuje priorita. Napríklad: 

    
E ->  T  { ( + | - ) T }
T ->  F  { ( * | / ) F }
F ->  [-] G
G ->  cislo | ( E )

    Vplyv tvaru gramatiky na postupnosť volaní jednotlivých funkcií je znázornený na obrázku:

    Obr.: : Stromy odvodenia pri rôznej priorite operátorov

    Asociatívnosť operátorov je zabezpečená tvarom pravidla nasledovne:

    Asociatívnosť Pravidlo
    ľavá V → P { op P }
    pravá V → P [ op V ]
    neasociatívnosť V → P [ op P ]
    Obr.: : Stromy odvodenia pri rôznej asociatívnosti operátora

    Upravte lexikálny analyzátor a interpretátor tak, aby akceptoval aj operátor násobenia "*", delenia "/" a mocniny "^", pričom:

    • operátory násobenia a delenia budú mať vyššiu prioritu ako operátory "+" a "-",
    • operátor mocniny bude mať najvyššiu prioritu,
    • operátor mocniny bude mať pravú asociatívnosť.
    Úloha: Rozšírte gramatiku o pravidla pre operátory násobenia, delenia a mocniny. 
    
Expr → Mul {("+" | "-") Mul}
Mul → ....
Power → ....
Term → value | "(" Expr ")"
    Úloha: Pridajte do implementácie syntaxou riadeného interpretátora funkcie pre nové neterminály na základe vytvorených pravidiel gramatiky s pomocou existujúcich funkcií interpretátora ( term(), expr()).
    Poznámka: Pre implementáciu mocniny môžete použiť funkciu pow() definovanú v math.h
  3. Odskúšajte príklad s viacnásobným použitím operátora mocniny bez použitia zátvoriek, napr.: 2^2^3
    Úloha: Aký ste dostali výsledok? Prečo?
  4. Zmeňte gramatiku aj kód interpretátora tak, aby operátor mocniny bol neasociatívny.
  5. Odskúšajte rovnaký príklad ako v bode 5.
    Úloha: Aký ste dostali výsledok? Prečo?
  6. Úloha: Opätovne zmeňte operátor mocniny na pravo asociatívny a príklad si odložte pre ďalšie použitie.
comments powered by Disqus