Reguły semantyczne
Podamy teraz reguły semantyczne związane z produkcjami, które pozwolą na określenie wartości liczby na podstawie jej drzewa wywodu. Reguły te będą związane z produkcjami gramatyki. Musimy dokonać tu pewnego rozróżnienia, często niezauważonego. Gdy piszemy na przykład \( 11 \), to myślimy o tym napisie, jako o liczbie "jedenaście". Jednak na dobrą sprawę są to po prostu dwie jedynki napisane na klawiaturze, które można zinterpretować też na przykład jako trójkę w systemie dwójkowym. Gramatyka służy do tego, aby produkować napisy. Zbiór napisów wyprowadzalnych z gramatyki jest językiem. Nas jednak przede wszystkim będzie interesowało znaczenie tych napisów w pewnej dziedzinie. Umówmy się więc, że aby zrobić rozróżnienie między napisem \( 11 \), a liczbą \( 11 \), tę drugą będziemy oznaczali kolorem niebieskim. Zatem \( 11 \) oznacza napis złożony z dwóch znaków, a \( \textcolor{blue}{11} \) będzie oznaczało liczbę jedenaście.
Teraz możemy już ustalić znaczenie poszczególnych produkcji gramatyki. Będziemy wiązali z każdą produkcją regułę semantyczną. Węzły drzewa będą interpretowane w wybranej przez nas dziedzinie. Określenie wartości węzła będzie zależało od wartości podwieszonych pod nim węzłów, czyli jego synów. Reguła semantyczna będzie określała jak wartość węzła zależy od wartości synów. Oznaczmy wartość węzła \( v \) w drzewie przez \( I(v) \). Zatem \( I:Varrow Z \) jest funkcją, która każdemu węzłowi przypisze liczbę całkowitą.
Zacznijmy od tego, że określimy znaczenie węzłów końcowych – liści drzewa. Są one cyframi - symbolami końcowymi. Ustalamy zatem, że:
\( I(0) = \) \( \textcolor{blue}{0}, \) \( I(1)= \) \( \textcolor{blue}{1}, \) \( \ldots, \) \( I(9)= \) \( \textcolor{blue}{9}, \) \( I(-)= \) \( \textcolor{blue}{-1}, \) \( I(+)= \) \( \textcolor{blue}{1}. \)
Dalej
- dla produkcji \( C::=x \) określamy \( I(C)=I(x) \) gdzie \( x\in\{0,1, ,9\} \)
- dla produkcji \( Z::=z \) określamy \( I(Z)=I(z) \) gdzie \( z\in\{+,-\} \)
- dla produkcji \( L::=C \) określamy \( I(L)=I(C) \),
przy czym stosujemy tu konwencję, że jeśli zastosowaliśmy produkcję \( L::=C \), to ojciec w tej regule jest oznaczany przez \( L \), a syn przez \( C \). Dla produkcji \( L::=LC \) musimy się umówić, jak rozróżnimy \( L \) z lewej i z prawej strony produkcji. Zatem umawiamy się, że jeśli symbol powtarza się z lewej strony i prawej, to ten z prawej wystąpi we wzorze z primem. Kolejne reguły zatem, to
- Dla produkcji \( (L::=LC) \) określamy \( I(L)=10I(L')+I(C) \),
- Dla produkcji \( (S::=L) \) określamy \( I(S)=I(L) \),
- Dla produkcji \( (S::=ZL) \) określamy \( I(S)=I(Z)I(L) \)
Oto drzewo semantyczne dla napisu \( -124 \).
\begin{Rysunek}[semantyka-124] \end{Rysunek}
Jak widać, wartość w korzeniu to \( \textcolor{blue}{-124} \) i jest to faktycznie liczba, którą chcemy oznaczać za pomocą napisu \( -124 \).
Ćwiczenie
Podaj gramatykę generującą liczby w układzie dwójkowym i określ dla niej reguły semantyczne
Zmienne, których będziemy używali w wyrażeniach, będą oznaczane za pomocą identyfikatorów. Identyfikatory będą ciągami liter lub cyfr zaczynającymi się od litery. Zatem gramatyka dla identyfikatora to
\( G=\langle \{Id,L,C,Z\},\{0,1,\ldots,9,a,b,\ldots,z,\_\},\{Id::= LZ, Z ::= \varepsilon | ZL |ZC\},Id \rangle \)
W gramatyce tej \( L \) oznacza pojedynczą literę, \( C \) oznacza pojedynczą cyfrę, \( Z \) oznacza ciąg złożony z liter lub cyfr. Zgodnie z tradycją programistyczną, poza literami alfebetu łacińskiego dopuszczamy jeszcze jako literę symbol podkreślenia.
Zbliżyliśmy się do momentu, kiedy może nam braknąć oznaczeń na symbole pomocnicze. W rzeczywistości w językach programowania gramatyki mają sto kilkadziesiąt symboli pomocniczych. Żeby się nam to wszystko nie pomyliło, przyjmijmy konwencję, w myśl której symbole pomocnicze piszemy w nawiasach rombowych, a oznaczamy je znaczącym tekstem, np. <cyfra>, <litera>, <ciąg liter lub cyfr> itp.
Jak teraz w analogiczny sposób określić gramatykę wyrażeń całkowitoliczbowych? Zauważmy, że w wyrażeniach są zmienne, stałe, operatory \( +,-,*,\div,\bmod \) oraz nawiasy. Ogólnie rzecz biorąc można powiedzieć, że wyrażeniem jest stała, zmienna, oraz że jeśli \( U,V \) są wyrażeniami, to wyrażeniem też jest \( -U,U+V,U-V,U*V,U\div V, U \bmod V, (U) \). Daje to niezwykle prostą gramatykę:
G=\( \langle \{ \)W,<zmienna>,<stała>\( \} \),\( \{\ \)_,a,b,...,z,0,1,...,9,-,+,*,\( \div\ \),\( \bmod\ \),(,)\( \} \),\( \{ \)<zmienna>::=
<identyfikator>,<stała>::=<liczbacałkowita>,W::=<zmienna>|<stała>|-W|W+W|W-W|W*W|W\( \div \)W|(W)\( \} \),W\( \rangle \),
gdzie identyfikator to Id z poprzedniej gramatyki, a liczba całkowita, to S z naszej gramatyki definiującej liczby całkowite.
Niestety ta gramatyka ma kilka wad. Po pierwsze, nie jest jednoznaczna. Po drugie, nie można określić dla niej semantyki – ta wada jest konsekwencją niejednoznaczności. Po trzecie, dopuszcza wytworzenie dziwolągów typu \( ---0 \) czy \( 0 - - 1 \) i w żaden sposób nie oddaje właściwego związku z tradycją matematyczną.
O co nam zatem chodzi? Oto lista naszych wymagań:
1. Gramatyka wyrażeń powinna być jednoznaczna.
2. Wartości wyrażeń powinny być zgodne z tradycją matematyczną, w szczególności należy zachować priorytety operatorów oraz wykluczyć napisy typu \( 2 - - 3 \).
3. Nawiasy powinny wymusić dowolną kolejność, na której nam zależy.
4. Operacje niełączne, takie jak odejmowanie i dzielenie powinny być lewostronnie łączne, czyli ich wykonywanie musi być od lewej do prawej (w szczególności np. \( 5-3-1 \) powinno dać wynik \( 1 \), a nie \( 3 \)).
Rozwiązanie jest zaskakująco proste jak na wyrafinowanie naszych wymagań. Oto szukana gramatyka wyrażeń całkowitoliczbowych.