Ciele
- Zopakovať si definíciu a vlastnosti gramatiky a formu zápisu pomocou BNF.
- Porozumieť konštrukcii gramatiky.
- Naučiť sa definovať syntax operátorov rôznych priorít a asociatívnosti pomocou gramatiky.
- Naučiť sa zostrojiť gramatiku podľa špecifikácie.
Úvod
V tomto cvičení predstavíme základné poznatky a precvičíme praktické zručnosti, ktoré budú základom pre úspešné vypracovanie druhého zadania - kalkulačky aritmetických výrazov. Zameriame sa na konštrukciu gramatiky a na porozumenie priority a asociatívnosti operátorov.
Postup
Krok 1
V tomto kroku si zopakujte základnú definíciu gramatiky a možnosti jej vyjadrenia pomocou BNF, ktoré boli predstavené v Cvičení 3.
Úloha 1.1
Zopakujte si:
- Čo je to gramatika?
- Čo je typické pre bezkontextové gramatiky?
- Ako sa odlišujú regulárne a bezkontextové gramatiky a aké sú hlavné účely ich použitia?
Krok 2
Zopakujeme, že na vyjadrenie gramatiky jazyka sa väčšinou používa Backusova-Naurova forma (BNF) , prípadne niektoré jej rozšírenia. Na tomto predmete to bude rozšírená Backusova-Naurova forma (Extended BNF).
Úloha 2.1
Aké sú rozdiely medzi základnou BNF a rozšírenou EBNF?
Základnými prvkami gramatiky sú pravidla a symboly. Symboly môžu byť terminálne (také, ktoré môžu byť prítomné na vstupe), alebo neterminálne. Pravidlá sa zapisujú v obvyklom tvare:
neterminal → postupnosť symbolov a operátorov
Pri zápise v EBNF budeme používať tie isté operátory, aké boli použité zápise regulárnych jazykov.
| Zápis | Význam |
|---|---|
| |
alternatíva |
{} |
opakovanie 0 alebo viackrát |
[] |
voliteľnosť |
Krok 3
Ak je syntaktický analyzátor implementovaný pomocou rekurzívnych funkcií, prioritu a asociatívnosť operátorov je možné vyjadriť tvarom a poradím pravidiel gramatiky.
Pre zabezpečenie správnej priority operátorov sa pre každú prioritnú úroveň vytvorí jeden neterminál. Pravidlá sa pre jednotlivé úrovne zreťazia tak, že smerom dovnútra (vnáranie k operandom) sa zvyšuje priorita.
Asociatívnosť operátorov je zabezpečená tvarom pravidla nasledovne:
| Asociatívnosť | Pravidlo |
|---|---|
| ľavá | E → T { op T } |
| pravá | E → T [ op E ] |
| neasociatívnosť | E → T [ op T ] |
Úloha 3.1
Vytvorte gramatiku pre jazyk aritmetických výrazov, s podporou operácií pre sčítanie, odčítanie, násobenie a delenie, pri zachovaní štandardných priorít a asociatívností. Jazyk výrazov obsahuje tiež zátvorky, výrazy obsahujú celé čísla a identifikátory.
Úloha 3.2
Pridajte do uvedenej gramatiky pravidlo pre operátor unárne mínus.
Úloha 3.3
Uveďte pre každý typ asociatívnosti niektoré typické operácie. Vysvetlite vplyv tvaru gramatiky na postupnosť volaní jednotlivých funkcií.
Úloha 3.4
Pridajte do rozšírenej gramatiky z tohto kroku operáciu mocniny "^" a operáciu zvyšku po delení "%" pri dodržaní obvyklých matematických pravidiel priority a asociatívnosti.
Krok 4
Úloha 4.1
Predpokladajme jazyk aritmetických výrazov tvorený identifikátormi (tokenmi), zátvorkami a dvoma binárnymi operátormi ⊗ a ⊕. Pre uvedené operátory platia nasledujúce vlastnosti:
- operátor ⊕ má vyššiu prioritu ako operátor ⊗
- operátor ⊕ je pravo-asociatívny
- operátor ⊗ je ľavo-asociatívny.
Nakreslite strom odvodenia pre reťazec id ⊕ id ⊕ id ⊗ id ⊗ id podľa Vašej gramatiky a vysvetlite štruktúru výrazu podľa priority a asociatívnosti.
Doplňujúce úlohy
Úloha A.1
Navrhnite gramatiku pre klasickú vreckovú kalkulačku, ktorá nerozlišuje priority operátorov.
Výsledok pre 10+2*3 je 36 a pre 2*3+10 je výsledok 16.
Úloha A.2
Rozšírte gramatiku z kroku 3 rozšírte o operátor ==, ktorý je neasociatívny, má najnižšiu prioritu, a správa sa ako operátor nerovnosti.