Ciele
- Definovanie syntaxe numerálov v rôznych číselných sústavách.
- Definovanie sémantiky numerálov.
- Rozšírenie syntaxe a definície sémantiky.
Úvod
Predtým, ako postupne vybudujeme teóriu formálnej sémantiky pre imperatívne programovacie jazyky, zavedieme základné pojmy z oblasti sémantiky, ktoré predstavíme na jednoduchom jazyku číselných sústav. Najjednoduchší spôsob, ako definovať sémantiku numerických reťazcov v ľubovoľnom programovacom jazyku, je priradiť im ich denotáciu. V tomto cvičení definujeme abstraktnú syntax a sémantiku numerických reťazcov – numerálov. Zameriame sa na najbežnejšie číselné reprezentácie pre potreby informatiky, a to sústavu dvojkovú, šestnástkovú, osmičkovú a doplníme náš prístup aj o sústavu desiatkovú.
Postup
Krok 1
Pre binárne numerály zavedieme syntaktickú oblasť (kategóriu) $\mathbf{Bin}$: $$ n \in \mathbf{Bin}. $$
Pre vyjadrenie syntaxe binárnych numerálov použijeme jedno produkčné pravidlo v BNF: $$ n ::= 0 ~|~ 1 ~|~ n0 ~|~ n1. $$
Úloha 1.1
Definujte samostatne syntax desiatkových numerálov. Uvažujte len reťazce, koré reprezentujú nezáporné hodnoty.
Úloha 1.2
Definujte samostatne syntax osmičkových numerálov.
Úloha 1.3
Definujte samostatne syntax šestnástkových (hexadecimálnych) numerálov.
Krok 2
Keď sme správne definovali syntax numerálov, musíme k ním vyjadriť aj ich význam. To dosiahneme definovaním príslušnej sémantickej funkcie.
Pre binárne numerály, ktoré sme uviedli v kroku 1, definujeme nasledujúcu sémantickú funkciu
$$\mathscr{N}: \mathbf{Bin} \rightarrow \mathbf{Z}$$
nasledujúcim spôsobom:
$$ \begin{array}{l} \mathscr{N} [\![ 0 ]\!] = \mathbf{0} \\ \mathscr{N} [\![ 1 ]\!] = \mathbf{1} \\ \mathscr{N} [\![ n0 ]\!] = \mathbf{2} \otimes \mathscr{N} [\![ n ]\!] \\ \mathscr{N} [\![ n1 ]\!] = \mathbf{2} \otimes \mathscr{N} [\![ n ]\!] \oplus \mathbf{1} \\ \end{array} $$
Úloha 2.1
Nájdite význam binárneho numerálu $1011$ Použitím uvedenej sémantickej funkcie $\mathscr{N}$.
Úloha 2.2
Definujte sémantickú funkciu pre desiatkové numerály z kroku 1.
Úloha 2.3
Definujte sémantickú funkciu pre osmičkové numerály z kroku 1.
Úloha 2.4
Definujte sémantickú funkciu pre šestnástkové numerály z kroku 1.
Krok 3
Úloha 3.1
Rozšírte Vašu definíciu syntaxe desiatkových numerálov a pridajte do syntaxe spôsob, ako vyjadriť záporné numerály.
Binárne numerály môžeme vyjadriť aj iným spôsobom. Doteraz uvádzaný spôsob sa opieral o príspevok hodnoty najmenej významného bitu (angl. the least significant bit – LSB). Existuje však aj opačný prístup – výpočet hodnoty binárneho numerálu podľa hodnoty najviac významného bitu (the most significant bit – MS). Tento tvar binárnych numerálov sa tiež pojmom redukovaný tvar binárnych numerálov.
Úloha 3.2
Syntax redukovaného tvaru binárnych numerálov má nasledujúcu definíciu. Syntaktická oblasť obsahuje reťazce binárnych číslic: $$n \in \mathbf{Bin},$$ a syntax numerálov je daná nasledujúcim pravidlom: $$n ::= 0~|~1~|~0n~|~1n.$$
Definujte samostatne sémantickú funkciu pre uvedený typ binárnych numerálov.
Dokumenty
Dokumenty k cvičeniu.
Doplňujúce úlohy
Úloha A.1
Použitím Vami definovaných sémantických funkcií nájdite významy nasledujúcich numerálov:
a) $10101$, $10000101010$ použitím funkcií pre štandardné aj redukované numerály
b) $1089$, $-1066$ použitím funkcie pre desiatkové numerály
c) $777$, $605$ použitím funkcie pre osmičkové numerály
d) $A1$, $7E1$, $DED0$ použitím funkcie pre šestnástkové numerály
Záver
Podobným spôsobom, ako sme definovali syntax a sémantiku binárnych numerálov, je možné pre účely informatiky definovať aj syntax a sémantiku numerálov osmičkových, či šestnástkových. Samozrejme, uvedený postup je možné aplikovať na ľubovoľnú číselnú sústavu.