WDP Gramatyki – definiowanie składni i semantyki wyrażeń

Wykład 3. Gramatyki – definiowanie składni i semantyki wyrażeń Język naturalny jest siłą rzeczy niejednoznaczny. Wiele pozostawia interpretacji, domysłom – często słyszymy, że dwie osoby rozmawiając nie mogą się nawzajem zrozumieć. Czasem sami poniewczasie dostrzegamy, że inaczej coś zrozumieliśmy, niż miał to na myśli nasz rozmówca. Komunikacja z komputerem jest o tyle trudniejsza, że nie pozostawia miejsca na domysły, czy interpretacje. Musimy niezwykle ściśle wyartykułować nasze wobec komputera żądania, aby ten bez wahania wykonał to, o co nam rzeczywiście chodziło. Ponadto chodzi o to, żeby nasze programy były uniwersalne, przynajmniej w części dotyczącej algorytmiki, a ich wykonanie na każdym komputerze wyglądało tak samo, albo różniło się co najwyżej nieznaczącymi szczegółami, wynikającymi ze specyfiki architektury komputera, a nie z istoty zapisu algorytmu. Różnica między językiem programowania, a językiem naturalnym polega na tym, że język naturalny jest zastany, podczas gdy język programowania możemy stworzyć od zera według naszego pomysłu. Użyjemy do tego metody gramatyk formalnych, które zostały wynalezione przez znanego językoznawcę Noama Chomsky'ego. Chomsky, \Rysunek{Chomsky} jeden z największych językoznawców – postać niezwykle barwna i kontrowersyjna – przez większość swojego życia próbował usystematyzować gramatykę języka angielskiego. Mechanizm gramatyk zaproponowany przez niego co prawda nie wystarczył do tego, żeby oddać bogactwo języka naturalnego, ale okazał się niezastąpiony przy definiowaniu sztucznych języków programowania. Oto pokrótce część jego teorii dotycząca tzw. {\em gramatyk bezkontekstowych\/}, z których będziemy korzystali. {\em Alfabetem\/} nazywamy dowolny skończony i niepusty zbiór symboli $A =$ \{a_1,...,a_n\}Parser nie mógł rozpoznać (nieznana funkcja „\em”): {\displaystyle . {\em Słowami\/} nad alfabetem } AParser nie mógł rozpoznać (błąd składni): {\displaystyle nazwiemy wszystkie skończone ciągi złożone z elementów alfabetu. W szczególności dopuścimy puste słowo – słowo nie mające żadnej litery, które oznaczamy wspólnym symbolem } \varepsilonParser nie mógł rozpoznać (błąd składni): {\displaystyle , niezależnie od alfabetu nad którym jest utworzone. Zbiór wszystkich słów nad alfabetem } A $o z n a c z a m y p r z e z$ A^*Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Przykładowo jeśli } A=Parser nie mógł rozpoznać (błąd składni): {\displaystyle \{a}} , to $A^{*} = {ε, a, a a, a a a, \dots}$ . Jeśli $A = =$ \{a,b\} $, t o$ A^*=\{\varepsilon,a,b,aa,ab,ba,bb,aaa,aab,\ldots\}Parser nie mógł rozpoznać (nieznana funkcja „\em”): {\displaystyle . {\em Długość słowa}, to liczba jego liter. {\em Język\/} nad alfabetem } AParser nie mógł rozpoznać (błąd składni): {\displaystyle , to dowolny podzbiór zbioru } A^*Parser nie mógł rozpoznać (nieznana funkcja „\em”): {\displaystyle . {\em Gramatyką\/} (bezkontekstową) nazwiemy uporządkowaną czwórkę <math> \langle N,T,P,S \rangle, } gdzie </math>N $o r a z$ TParser nie mógł rozpoznać (błąd składni): {\displaystyle , to skończone i rozłączne zbiory odpowiednio symboli {\em pomocniczych\/} (zwanych czasem nieterminalnymi lub nieterminalami) i {\końcowych\/} (zwanych czasem terminalnymi lub terminalami), } P $j e s t z b i o r e m p r o d u k c j i, a$ S\in NParser nie mógł rozpoznać (błąd składni): {\displaystyle jest wyróżnionym symbolem pomocniczym zwanym {\em aksjomatem\/} gramatyki. Produkcje wchodzące w skład zbioru } PParser nie mógł rozpoznać (błąd składni): {\displaystyle są postaci } X ::= w $, g d z i e$ X\in N $, a$ w\in (N\cup T)^*Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Pojedynczą taką produkcję interpretujemy, jako możliwość zastąpienia symbolu pomocniczego } XParser nie mógł rozpoznać (błąd składni): {\displaystyle przez słowo, w skład którego mogą wchodzić zarówno symbole pomocnicze, jak i końcowe. Proces wyprowadzania słów języka zdefiniowanego przez gramatykę odbywa się w taki sposób, że zaczynamy od symbolu } SParser nie mógł rozpoznać (błąd składni): {\displaystyle i do poszczególnych symboli pomocniczych stosujemy którąś z produkcji ze zbioru } PParser nie mógł rozpoznać (błąd składni): {\displaystyle tak długo, aż wszystkie symbole pomocnicze znikną. To, co zostanie, czyli słowo złożone z samych symboli końcowych nazywamy słowem wyprowadzalnym z gramatyki. Zbiór wszystkich słów wyprowadzalnych z danej gramatyki nazywa się {\em językiem generowanym przez gramatykę}. Zwróćmy uwagę na to, że jeśli w trakcie wywodu słowa pojawia się kilka identycznych symboli pomocniczych, to każdy z nich może samodzielnie decydować o tym, co z siebie wyprodukować. \Przykład[1] <math> G_1=\langle \{S\},\{a\},\{S::=\varepsilon, S::=aaS\},S \rangle } Gramatyka </math>G_1Parser nie mógł rozpoznać (błąd składni): {\displaystyle generuje wszystkie parzyste słowa złożone z samych liter } aParser nie mógł rozpoznać (błąd składni): {\displaystyle (uwaga słowo puste jest słowem o parzystej długości!). \Przykład[2] <math> G_2=\langle \{S\},\{a\},\{S::=\varepsilon, S::=aSa, S::=bSb\},S \rangle } Gramatyka </math>G_2 $g e n e r u j e w s z y s t k i e p a r z y s t e p a l i n d r o m y n a d d w u e l e m e n t o w y m a l f a b e t e m$ \{a,b\}Parser nie mógł rozpoznać (nieznana funkcja „\begin{ukryj}”): {\displaystyle . \begin{ukryj}[Jeśli nie wiesz co to są palindromy, to kliknij tutaj] Palindromem nazwiemy każde słowo, które czytane wprost jest identyczne, jak czytane wspak, czyli takie słowo } a_1,\ldots,a_nParser nie mógł rozpoznać (błąd składni): {\displaystyle , że dla każdego } k\in\{1,...,n\} $z a c h o d z i$ a_k=a_{n-k+1}Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Parzysty palindrom, to palindrom o parzystej długości. \end{ukryj} Przyjmijmy konwencję notacyjną, która pozwoli nam uprościć wypisywanie produkcji wywodzących się z tego samego symbolu. Jeśli jest kilka wariantów produkcji z tego samego symbolu, to piszemy je w jednym ciągu oddzielając pionowymi kreskami. W szczególności produkcje gramatyki } G_2Parser nie mógł rozpoznać (błąd składni): {\displaystyle wyglądają w tej notacji następująco: } \{S::=\varepsilon | aSa | bSb\}Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Historię wyprowadzeń słowa w danej gramatyce możemy zapisać za pomocą {\em drzewa wywodu}. Korzeniem w tym drzewie jest aksjomat gramatyki, a jeśli została do symbolu pomocniczego } XParser nie mógł rozpoznać (błąd składni): {\displaystyle , który jest węzłem w drzewie zastosowana produkcja } X::=x_1,\ldots,x_nParser nie mógł rozpoznać (błąd składni): {\displaystyle , to synami węzła } XParser nie mógł rozpoznać (błąd składni): {\displaystyle stają się elementy } x_1,\ldots,x_nParser nie mógł rozpoznać (błąd składni): {\displaystyle . Oto przykład wyprowadzenia słowa abba w gramatyce } G_2Parser nie mógł rozpoznać (nieznana funkcja „\begin{Rysunek}”): {\displaystyle . \begin{Rysunek}[rys1-abba] \end{Rysunek} Moglibyśmy to wyprowadzenie przedstawić w wersji liniowej } S \rightarrow aSa \rightarrow abSba \rightarrow abbaParser nie mógł rozpoznać (błąd składni): {\displaystyle , jednak drzewo wywodu daje nam dokładnie taką informację, o jaką nam chodzi, zamazując niepotrzebne szczegóły. Przyjrzyjmy się bliżej różnicom w reprezentacji historii wywodu. Rozważmy gramatykę } G=\langle \{S\},\{a,b\},\{S::= SaS | b\},S \rangleParser nie mógł rozpoznać (błąd składni): {\displaystyle . Za pomocą tej gramatyki możemy wygenerować dowolną naprzemienną sekwencję liter } b $o r a z$ aParser nie mógł rozpoznać (błąd składni): {\displaystyle zaczynającą się i kończącą na literę } bParser nie mógł rozpoznać (błąd składni): {\displaystyle . Na ile sposobów można otrzymać słowo } bababParser nie mógł rozpoznać (błąd składni): {\displaystyle ? W notacji liniowej tych sposobów jest sporo, przykładowo } S \rightarrow SaS \rightarrow SaSaS \rightarrow SaSab \rightarrow baSab \rightarrow babab $. A l b o i n a c z e j$ S \rightarrow SaS \rightarrow Sab \rightarrow SaSab \rightarrow Sabab \rightarrow bababParser nie mógł rozpoznać (nieznana funkcja „\Pytanie”): {\displaystyle . \Pytanie Na ile sposobów można liniowo zapisać wywód słowa } bababParser nie mógł rozpoznać (nieznana funkcja „\Odpowied”): {\displaystyle ? \Odpowiedź 12 Ile jest drzew wywodu tego słowa? Okazuje się, że tylko dwa. Oto one \begin{Rysunek}[rys2-babab] \end{Rysunek} Można gramatykę tak skonstruować, żeby słowo } bababParser nie mógł rozpoznać (błąd składni): {\displaystyle , podobnie jak i każde inne generowane przez powyższą gramatykę, miało tylko jedno drzewo wywodu. Oto ta gramatyka: <math> G_3=\langle \{S\},\{a,b\},\{S::=\varepsilon, S::=baS | b\},S \rangle } Taka gramatyka ma już tylko jedno drzewo wywodu dla słowa </math>bababParser nie mógł rozpoznać (nieznana funkcja „\begin{Rysunek}”): {\displaystyle . Oto ono: \begin{Rysunek}[rys3-babab-jedno] \end{Rysunek} Podobnie, każde inne słowo wyprowadzalne z tej gramatyki ma jedno drzewo wywodu. Powiemy, że gramatyka } GParser nie mógł rozpoznać (nieznana funkcja „\em”): {\displaystyle jest {\em jednoznaczna}, jeśli każde słowo wyprowadzalne z } GParser nie mógł rozpoznać (błąd składni): {\displaystyle ma tylko jedno drzewo wywodu. Własność jednoznaczności jest niezwykle ważna – będziemy starali się tak zdefiniować język programowania, aby drzewo wywodu każdego programu było jednoznaczne. To pozwoli nam określić semantykę języka programowania jako funkcję obliczaną na podstawie drzewa wywodu. Powiemy, że gramatyka } GParser nie mógł rozpoznać (nieznana funkcja „\em”): {\displaystyle jest {\em zgodna\/} z językiem } L\in T^*Parser nie mógł rozpoznać (błąd składni): {\displaystyle , jeśli każde słowo wyprowadzalne z } GParser nie mógł rozpoznać (błąd składni): {\displaystyle należy do } LParser nie mógł rozpoznać (błąd składni): {\displaystyle . Powiemy, że gramatyka } GParser nie mógł rozpoznać (nieznana funkcja „\em”): {\displaystyle jest {\em pełna\/} względem języka $L$ , jeśli wszystkie słowa należące do $L$ są wyprowadzalne z $G$ . Rzecz jasna każda gramatyka G jest zarówno zgodna, jak i pełna względem swojego języka $L (G)$ . Zacznijmy od zdefiniowania liczb całkowitych. Po pierwsze określmy, co będziemy chcieli nazywać liczbami całkowitymi. Przyjmijmy, że poprawnymi liczbami są wszystkie skończone ciągi cyfr dziesiętnych poprzedzone pojedynczym znakiem $+$ lub $-$ . Dopuścimy zatem jako poprawne napisy $123, - 22, 00, + 013$ , ale jako niepoprawne uznamy np. napisy $+ + 12, - + 0, 2 + 3, X V I, +, ε$ . Oto propozycja gramatyki: $G = ⟨ {S, Z, C, L}, {-, +, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, {C : : = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9, S : : = L | Z L, Z : : = + | -, L : : = C | L C,}, S ⟩$ W ten sposób napisana gramatyka daje jednoznaczne wyprowadzenie każdej liczby całkowitej, zgodnej z naszymi założeniami. Zauważmy, że na samym początku wyprowadzania decydujemy, czy liczba ma być ze znakiem, czy bez – o tym decyduje wybór $L$ lub $Z L$ spośród dwóch wariantów, które daje nam symbol $S$ . Z symbolu pomocniczego $L$ możemy wygenerować dowolny niepusty ciąg cyfr, a z symbolu $Z$ znak. Przykładowe wyprowadzenie liczby -120 wygląda następująco: \begin{Rysunek}[rys3-120] \end{Rysunek} 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 zielonym. Zatem $11$ oznacza napis złożony z dwóch znaków, a \zielone[ $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 : V \to 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 Parser nie mógł rozpoznać (nieznana funkcja „\zielone”): {\displaystyle I(0)=\zielone[0], I(1)=\zielone[1],\ldots,I(9)=\zielone[9],I(-)=\zielone[-1],I(+)=\zielone[1]} . Dalej

dla produkcji $C : : = x$ określamy Parser nie mógł rozpoznać (błąd składni): {\displaystyle I{C)=I(x)} gdzie Parser nie mógł rozpoznać (nieznana funkcja „\ldtots”): {\displaystyle x\in\{0,1,\ldtots,9\}}
dla produkcji $Z : : = z$ określamy Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 : : = L C$ 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 : : = L C)$ określamy $I (L) = 10 I (L^{'}) + I (C)$ ,
Dla produkcji $(S : : = L)$ określamy $I (S) = I (L)$ ,
Dla produkcji $(S : : = Z L)$ 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 Parser nie mógł rozpoznać (nieznana funkcja „\zielone”): {\displaystyle \zielone[-124]} i jest to faktycznie liczba, którą chcemy oznaczać za pomocą napisu $- 124$ . \begin{ćwiczenie} Podaj gramatykę generującą liczby w układzie dwójkowym i określ dla niej reguły semantyczne \end{ćwiczenie}. \Podpowiedź1: odrzuć parę symboli końcowych i lekko zmodyfikuj reguły semantyczne. \begin{Odpowiedź} $G = ⟨ {S, Z, C, L}, {-, +, 0, 1}, {C : : = 0 | 1, S : : = L | Z L, Z : : = + | -, L : : = C | L C,}, S ⟩$ Reguły semantyczne dla stałych całkowitych w systemie dwójkowym

Dla symboli końcowych określamy Parser nie mógł rozpoznać (nieznana funkcja „\zielone”): {\displaystyle I(0)=\zielone[0], I(1)=\zielone[1],I(-)=\zielone[-1],I(+)=\zielone[1]}
dla produkcji $C : : = x$ określamy Parser nie mógł rozpoznać (błąd składni): {\displaystyle I{C)=I(x)} gdzie $x \in {0, 1}$
dla produkcji $Z : : = z$ określamy Parser nie mógł rozpoznać (błąd składni): {\displaystyle I{Z)=I(z)} gdzie $z \in {+, -}$
dla produkcji $L : : = C$ określamy $I (L) = I (C)$ ,
Dla produkcji $(L : : = L C)$ określamy $I (L) = 2 I (L^{'}) + I (C)$ ,
Dla produkcji $(S : : = L)$ określamy $I (S) = I (L)$ ,
Dla produkcji $(S : : = Z L)$ określamy $I (S) = I (Z) I (L)$

\end{Odpowiedź} 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 = ⟨ {I d, L, C, C h}, {0, 1, \dots, 9, a, b, \dots, z,_}, {I d : : = L C h, C h : : = ε | C h L | C h C}, I d ⟩$ W gramatyce tej $L$ oznacza pojedynczą literę, $C$ oznacza pojedynczą cyfrę, $C h$ 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. {\tt <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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle +,-,\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 mod V, (U)$ . Daje to niezwykle prostą gramatykę: Parser nie mógł rozpoznać (błąd składni): {\displaystyle G=\langle \{W,<zmienna>,<stała>\},\{\_,a,b,\ldots,z,0,1,\ldots,9,-,+,\div,\bmod,(,)\},\{<zmienna> ::= <identyfikator>, <stała> ::= <liczba całkowita>, W::= <zmienna> | <stała> | -W | W+W | W-W | W*W | W\div W | (W) \},W \rangle, } gdzie {\tt identyfikator}to Id z poprzedniej gramatyki, a {\tt 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ń. \begin{ramka} \begin{itermize} \item gramatyka wyrażeń powinna być jednoznaczna \item 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$ \item nawiasy powinny wymusić dowolną kolejność, na której nam zależy. \item 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$ ). \end{ramka} Rozwiązanie jest zaskakująco proste, jak na wyrafinowanie naszych wymagań. Oto szukana gramatyka wyrażeń całkowitoliczbowych. \begin{ramka}[Wyrażenia całkowitoliczbowe]

Parser nie mógł rozpoznać (błąd składni): {\displaystyle G_Z=\langle \{<wyrażenie Z>, <składnik>, <czynnik>, <stała>, <zmienna>\}, \{\_,a,b,\ldots,z,0,1,\ldots,9,-,+,\div,\bmod,(,) \}, \{<zmienna> ::= <identyfikator>, <stała> ::= <liczba całkowita bez znaku>,P,<wyrażenie Z> } gdzie $P$ jest zbiorem następujących produkcji: \begin{verbatim} <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> div <czynnik> | <składnik> mod <czynnik> <czynnik< ::= <stała> | <zmienna> | (<wyrażenie Z>) <stała>::= <liczba całkowita bez znaku> <zmienna> ::= <identyfikator> \end{verbatim} \end{ramka} Symbol pomocniczy <liczba całkowita bez znaku> jest prostym uproszczeniem gramatyki liczb polegającym na usunięciu znaku. \begin{Ćwiczenie}

Podaj gramatykę dla liczb całkowitych bez znaku \Podpowiedź Usuń znak i związane z nim produkcje z gramatyki dla stałych całkowitoliczbowych \Odpowiedź $G = ⟨ {S, C}, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, {C : : = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9, S : : = C | S C}, S ⟩$ i reguły semantyczne:

Dla symboli końcowych określamy Parser nie mógł rozpoznać (nieznana funkcja „\zielone”): {\displaystyle I(0)=\zielone[0], I(1)=\zielone[1], \ldots, I(9)=\zielone[9]}
Dla produkcji $C : : = x$ określamy Parser nie mógł rozpoznać (błąd składni): {\displaystyle I{C)=I(x)} gdzie $x = 0, 1, \dots, 9$
Dla produkcji (S::=SC) określamy $I (S) = 10 I (S^{'}) + I (C)$ ,
Dla produkcji (S::=C) określamy $I (S) = I (C)$ ,

\end{Odpowiedź} Zbadajmy teraz, jak wygląda drzewo wywodu wyrażenia $a + b * 4$ . Łatwo się można przekonać, że pierwszą produkcją musi być {\tt <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 {\tt <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, to 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 : I D \to Z ?$ , która zbiór wszystkich identyfikatorów $I D$ przeprowadza w zbiór nieco rozszerzony liczb całkowitych $Z_{?} = Z \cup {?}$ ,gdzie symbol $?$ oznacza wartość {\em 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 e r r o r : x \oplus ? = ? \oplus x = ?$
dla każdego $x : x \oplus e r r o r = e r r o r \oplus x = e r r o r$

i analogicznie dla operacji jednoargumentowych. Reguły semantyczne

Dla symboli końcowych określamy Parser nie mógł rozpoznać (błąd składni): {\displaystyle I_V(<stała>)=I(<stala bez znaku>) (jak w ćwiczeniu [[#Stałe bez znaku]]) *dla produkcji } <zmienna>::=<identyfikator>Parser nie mógł rozpoznać (błąd składni): {\displaystyle określamy } I_V(<zmienna>)=V(<identyfikator>) $* d l a p r o d u k c j i$ <czynnik>::=<stała>Parser nie mógł rozpoznać (błąd składni): {\displaystyle określamy } I_V(<czynnik>)=I_V(<stała>) $* d l a p r o d u k c j i$ <czynnik>::=<zmienna>Parser nie mógł rozpoznać (błąd składni): {\displaystyle określamy } I_V(<czynnik>)=I_V(<zmienna>) $* d l a p r o d u k c j i$ <czynnik>::=(<wyrażenie Z>)Parser nie mógł rozpoznać (błąd składni): {\displaystyle określamy } I_V(<czynnik>)=I_V(<wyrażenie Z>) $* d l a p r o d u k c j i$ <składnik>::=<czynnik>Parser nie mógł rozpoznać (błąd składni): {\displaystyle określamy } I_V(<składnik>)=I_V(<czynnik>) $* d l a p r o d u k c j i$ <składnik>::=<składnik>*<czynnik>Parser nie mógł rozpoznać (błąd składni): {\displaystyle określamy } I_V(<składnik>)=I_V(<składnik>)I_V(<czynnik>) $* d l a p r o d u k c j i$ <składnik>::=<składnik> div <czynnik>Parser nie mógł rozpoznać (błąd składni): {\displaystyle określamy <math> I_V(<składnik>)=\left\{ \begin{array}{ll} I_V(<składnik'>\zielony[\div] I_V(<czynnik>)& \mbox{jeśli } I_V(<czynnik>\neq0Parser nie mógł rozpoznać (błąd składni): {\displaystyle } \\ error& \mbox{jeśli } I_V(<czynnik>=0Parser nie mógł rozpoznać (błąd składni): {\displaystyle } \end{array} \right. }
dla produkcji </math><składnik>::=<składnik> mod <czynnik>Parser nie mógł rozpoznać (błąd składni): {\displaystyle określamy <math> I_V(<składnik>)=\left\{ \begin{array}{ll} I_V(<składnik'>\zielony[\bmod] I_V(<czynnik>)& \mbox{jeśli } I_V(<czynnik>\neq0Parser nie mógł rozpoznać (błąd składni): {\displaystyle } \\ error& \mbox{jeśli } I_V(<czynnik>=0Parser nie mógł rozpoznać (błąd składni): {\displaystyle } \end{array} \right. }
dla produkcji </math><wyrażenie Z>::=<składnik>Parser nie mógł rozpoznać (błąd składni): {\displaystyle określamy } I_V(<wyrażenie Z>)=I_V(<składnik>) $* d l a p r o d u k c j i$ <wyrażenie Z>::=-<składnik>Parser nie mógł rozpoznać (błąd składni): {\displaystyle określamy } I_V(<wyrażenie Z>)=\zielony[-]I_V(<składnik>) $* d l a p r o d u k c j i$ <wyrażenie Z>::=<wyrażenie Z>+<składnik>Parser nie mógł rozpoznać (błąd składni): {\displaystyle określamy } I_V(<wyrażenie Z>)=I_V(<wyrażenie Z>)\zielony[+] I_V(<składnik>) $* d l a p r o d u k c j i$ <wyrażenie Z>::=<wyrażenie Z>-<składnik>Parser nie mógł rozpoznać (błąd składni): {\displaystyle określamy } I_V(<wyrażenie Z>)=I_V(<wyrażenie Z>)\zielony{-}I_V(<składnik>)Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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=? $? *$ c+a*bParser nie mógł rozpoznać (nieznana funkcja „\Odpowied”): {\displaystyle \Odpowiedź } 6 $*$ c/a*bParser nie mógł rozpoznać (nieznana funkcja „\Odpowied”): {\displaystyle \Odpowiedź } 0 $*$ c/a/bParser nie mógł rozpoznać (nieznana funkcja „\Odpowied”): {\displaystyle \Odpowiedź } error $*$ (c+a) div (b+d)Parser nie mógł rozpoznać (nieznana funkcja „\Odpowied”): {\displaystyle \Odpowiedź } ?

WDP Gramatyki – definiowanie składni i semantyki wyrażeń

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia