Wyrażenia całkowitoliczbowe
<tt> \( G_Z \)=\( \langle \{ \)<wyrażenie Z>,<składnik>,<czynnik>,<stała>,<zmienna>\( \} \) \( \{\ \)_,a,b,...,z,0,1,...,9,-,+,\( \div\ \),\( \bmod\ \),(,)\( \} \), P,<wyrażenie Z>\( \rangle \)</tt>
gdzie \( P \) jest zbiorem następujących produkcji:
<tt><wyrażenie Z> ::= <składnik> | -<składnik> | <wyrażenie Z> + <składnik> | <wyrażenie Z> -<składnik> <składnik> ::= <czynnik> | <składnik> * <czynnik> | <składnik><b>div</b><czynnik> | <składnik><b>mod</b><czynnik> <czynnik> ::= <stała> | <zmienna> | (<wyrażenie Z>) <stała>::= <liczba całkowita bez znaku> <zmienna> ::= <identyfikator></tt>
Symbol pomocniczy (liczba całkowita bez znaku) jest uproszczeniem gramatyki liczb polegającym na usunięciu znaku.
Ćwiczenie
Podaj gramatykę dla liczb całkowitych bez znaku
Zbadajmy teraz, jak wygląda drzewo wywodu wyrażenia \( a+b*4 \). Łatwo się można przekonać, że pierwszą produkcją musi być <wyrażenie Z> ::= <wyrażenie Z> + <składnik>. Żadna inna produkcja nie wchodzi w grę: dwie z nich wprowadzają znak minus, którego byśmy się już nie pozbyli, a trzecia <wyrażenie Z> ::= <składnik> przenosi nas do składnika, z którego nie daje się już uzyskać plusa bez wprowadzenia nawiasów.
Skoro tak, dalej dostajemy już w jednoznaczny sposób następujące drzewo wywodu.
\begin{rysunek}[Drzewo wywodu dla wyrażenia \( a+b*4 \)] \end{rysunek}
Jakie reguły semantyczne należy dobrać do naszych produkcji? Dość naturalne. Dla stałych nie ma problemu: już je mamy. Ze zmiennymi jest jednak mały kłopot: jaką wartość powinny mieć zmienne? Musimy tu zrobić dygresję na temat implementacji. Wszystkie zmienne w programie w momencie, w którym się z nich korzysta, mają swoje miejsce w pamięci. W czasie kompilacji i konsolidacji programu ustala się adres, pod którym można je znaleźć i kiedy odwołujemy się do nich, ich wartość uzyskujemy zaglądając do tego miejsca w pamięci. Przyjmijmy, że pamięć w naszym ujęciu modeluje funkcja \( V:IDarrow Z_? \), która zbiór wszystkich identyfikatorów \( ID \) przeprowadza w zbiór nieco rozszerzony liczb całkowitych \( Z_?=Z\cup \{?\} \), gdzie symbol \( ? \) oznacza wartość nieokreśloną. Ta wartość jest nam potrzebna, gdyż wszystkie zmienne w chwili, gdy zaczynamy wykonywać program, mają wartości nieokreślone i dopiero w efekcie wykonywania instrukcji konkretne wartości będą im sukcesywnie nadawane (i zmieniane). Przy okazji mała dygresja. W odróżnieniu od całej matematyki, zmienne naprawdę zmieniają swoje wartości. Gdy w matematyce zaczynamy wywód mówiąc np. „Niech \( k \) będzie liczbą przekątnych w wielokącie”, wówczas do końca wywodu \( k \) nie może oznaczać niczego innego. W informatyce, jeśli napiszemy „niech \( k \) stanie się równe \( 5 \)”, to za chwilę wartość zmiennej \( k \) może ulec zmianie, jeśli sobie tego zażyczymy.
Zatem przez \( V(z) \) będziemy rozumieli wartość zmiennej \( z \), a wartość wyrażenia, w którym zmienne występują, będzie zależała od tego wartościowania. Interpretację wyrażenia musimy zatem uzależnić od wartościowania \( V \). Podamy teraz reguły wartościowania wyrażeń. Tym razem funkcję interpretacji oznaczymy przez \( I_V \), żeby podkreślić zależność interpretacji wyrażenia od wartościowania zmiennych. Musimy jeszcze zauważyć, że jeśli w wyrażeniu występuje dzielenie (niezależnie od tego czy div czy mod), to wynik dzielenia będzie błędny, jeśli dzielnik będzie zerem. Komputer, zmuszony do wykonania takiego dzielenia, odmawia współpracy i generuje błąd. Wygodnie jest, określając semantykę, tę sytuację uwzględnić w dziedzinie semantycznej, dodając wartość error do zestawu wartości całkowitych. Zatem ostatecznie nasza dziedzina liczb całkowitych rozrasta się nam o dwie wartości: \( error \) i \( ? \). Rozszerzmy jeszcze działania na te wartości. Przyjmujemy więc, że dla każdej operacji dwuargumentowej \( \oplus \)
- dla każdego \( x\neq error: x\oplus ? = ?\oplus x = ? \)
- dla każdego \( x: x \oplus error = error \oplus x = error \)
i analogicznie dla operacji jednoargumentowych.
Reguły semantyczne
- dla symboli końcowych określamy \( I_V( < stala>)=I_V( < stala bez znaku>) \) (jak w ćwiczeniu stałe bez znaku)
- dla produkcji \( < zmienna>::= < identyfikator> \) określamy \( I_V( < zmienna>)=I_V( < identyfikator>) \)
- dla produkcji \( < czynnik>::= < stala> \) określamy \( I_V( < czynnik>)=I_V( < stala>) \)
- dla produkcji \( < czynnik>::= < zmienna> \) określamy \( I_V( < czynnik>)=I_V( < zmienna>) \)
- dla produkcji \( < czynnik>::=( < wyrazenie Z>) \) określamy \( I_V( < czynnik>)=I_V( < wyrazenie Z>) \)
- dla produkcji \( < skladnik>::= < czynnik> \) określamy \( I_V( < skladnik>)=I_V( < czynnik>) \)
- dla produkcji \( < skladnik>::= < skladnik'>* < czynnik> \) określamy \( I_V( < skladnik>)=I_V( < skladnik>)I_V( < czynnik>) \)
- dla produkcji \( < skladnik>::= < skladnik> div < czynnik> \) określamy
\( I_V( < skladnik>) = \begin{cases} I_V( < skladnik'>\textcolor{blue}{\div} I_V( < czynnik>) & \mbox{jeśli }I_V( < czynnik>)\neq0 \\ error & \mbox{jeśli }I_V( < czynnik>)=0 \end{cases} \)
- dla produkcji \( < skladnik>::= < skladnik> mod < czynnik> \) określamy
\( I_V( < skladnik>) = \begin{cases} I_V( < skladnik'> \textcolor{blue}{\bmod} I_V( < czynnik>) & \mbox{jeśli }I_V( < czynnik>)\neq0 \\ error & \mbox{jeśli }I_V( < czynnik>)=0 \end{cases} \)
- dla produkcji \( < wyrazenie Z>::= < skladnik> \) określamy \( I_V( < wyrazenie Z>)=I_V( < skladnik>) \)
- dla produkcji \( < wyrazenie Z>::=- < skladnik> \) określamy \( I_V( < wyrazenie Z>)=\textcolor{blue}{-}I_V( < skladnik>) \)
- dla produkcji \( < wyrazenie Z>::= < wyrazenie Z>+ < skladnik> \) określamy \( I_V( < wyrazenie Z>)=I_V( < wyrazenie Z'>)\textcolor{blue}{+} I_V( < skladnik>) \)
- dla produkcji \( < wyrazenie Z>::= < wyrazenie Z>- < skladnik> \) określamy \( I_V( < wyrazenie Z>)=I_V( < wyrazenie Z'>)\textcolor{blue}{-} I_V( < skladnik>) \)
Ćwiczenie
Uff! Wiemy już więc, jak interpretować wyrażenia arytmetyczne. A teraz parę pytań sprawdzających.
Ćwiczenie
Ile to jest dla \( a=2, b=0, c=6, d=? \)