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 } LParser nie mógł rozpoznać (błąd składni): {\displaystyle , jeśli wszystkie słowa należące do } LParser nie mógł rozpoznać (błąd składni): {\displaystyle są wyprowadzalne z } GParser nie mógł rozpoznać (błąd składni): {\displaystyle . Rzecz jasna każda gramatyka G jest zarówno zgodna, jak i pełna względem swojego języka } L(G)Parser nie mógł rozpoznać (błąd składni): {\displaystyle . 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 } + $l u b$ -Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Dopuścimy zatem jako poprawne napisy } 123,-22,00,+013 $, a l e j a k o n i e p o p r a w n e u z n a m y n p . n a p i s y$ ++12,-+0,2+3,XVI,+,\varepsilonParser nie mógł rozpoznać (błąd składni): {\displaystyle . Oto propozycja gramatyki: <math> G=\langle \{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 | ZL, Z::=+ | -, L::= C | LC, \},S \rangle } 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 </math>L $l u b$ ZLParser nie mógł rozpoznać (błąd składni): {\displaystyle spośród dwóch wariantów, które daje nam symbol } S $. Z s y m b o l u p o m o c n i c z e g o$ LParser nie mógł rozpoznać (błąd składni): {\displaystyle możemy wygenerować dowolny niepusty ciąg cyfr, a z symbolu } ZParser nie mógł rozpoznać (błąd składni): {\displaystyle 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 } 11Parser nie mógł rozpoznać (błąd składni): {\displaystyle , 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 } 11Parser nie mógł rozpoznać (błąd składni): {\displaystyle , a liczbą } 11Parser nie mógł rozpoznać (błąd składni): {\displaystyle , tę drugą będziemy oznaczali kolorem zielonym. Zatem } 11Parser nie mógł rozpoznać (błąd składni): {\displaystyle oznacza napis złożony z dwóch znaków, a \zielone[} 11Parser nie mógł rozpoznać (błąd składni): {\displaystyle ] 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 d r z e w i e p r z e z$ I(v) $. Z a t e m$ I:V\rightarrow ZParser nie mógł rozpoznać (błąd składni): {\displaystyle 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)=\zielone[0], I(1)=\zielone[1],\ldots,I(9)=\zielone[9],I(-)=\zielone[-1],I(+)=\zielone[1] $. D a l e j * d l a p r o d u k c j i$ C::=xParser nie mógł rozpoznać (błąd składni): {\displaystyle określamy } I{C)=I(x) $g d z i e$ x\in\{0,1,\ldtots,9\} $* d l a p r o d u k c j i$ Z::=zParser nie mógł rozpoznać (błąd składni): {\displaystyle określamy } I{Z)=I(z) $g d z i e$ z\in\{+,-\} $* d l a p r o d u k c j i$ L::=CParser nie mógł rozpoznać (błąd składni): {\displaystyle określamy } I(L)=I(C)Parser nie mógł rozpoznać (błąd składni): {\displaystyle , przy czym stosujemy tu konwencję, że jeśli zastosowaliśmy produkcję } L::=C $, t o o j c i e c w t e j r e g u l e j e s t o z n a c z a n y p r z e z$ L $, a s y n p r z e z$ C $. D l a p r o d u k c j i$ L::=LCParser nie mógł rozpoznać (błąd składni): {\displaystyle musimy się umówić, jak rozróżnimy } LParser nie mógł rozpoznać (błąd składni): {\displaystyle 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)Parser nie mógł rozpoznać (błąd składni): {\displaystyle określamy } I(L)=10I(L')+I(C) $, * D l a p r o d u k c j i$ (S::=L)Parser nie mógł rozpoznać (błąd składni): {\displaystyle określamy } I(S)=I(L) $, * D l a p r o d u k c j i$ (S::=ZL)Parser nie mógł rozpoznać (błąd składni): {\displaystyle określamy } I(S)=I(Z)I(L) $O t o d r z e w o s e m a n t y c z n e d l a n a p i s u$ -124Parser nie mógł rozpoznać (nieznana funkcja „\begin{Rysunek}”): {\displaystyle . \begin{Rysunek}[semantyka-124] \end{Rysunek} Jak widać, wartość w korzeniu to } \zielone[-124]Parser nie mógł rozpoznać (błąd składni): {\displaystyle i jest to faktycznie liczba, którą chcemy oznaczać za pomocą napisu } -124Parser nie mógł rozpoznać (błąd składni): {\displaystyle . \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ź} <math> G=\langle \{S,Z,C,L\},\{-,+,0,1\},\{C::= 0 | 1, S::=L | ZL, Z::=+ | -, L::= C | LC, \},S \rangle }

Reguły semantyczne dla stałych całkowitych w systemie dwójkowym

Dla symboli końcowych określamy </math>I(0)=\zielone[0], I(1)=\zielone[1],I(-)=\zielone[-1],I(+)=\zielone[1] $* d l a p r o d u k c j i$ C::=xParser nie mógł rozpoznać (błąd składni): {\displaystyle określamy } I{C)=I(x) $g d z i e$ x\in\{0,1\} $* d l a p r o d u k c j i$ Z::=zParser nie mógł rozpoznać (błąd składni): {\displaystyle określamy } I{Z)=I(z) $g d z i e$ z\in\{+,-\} $* d l a p r o d u k c j i$ L::=CParser nie mógł rozpoznać (błąd składni): {\displaystyle określamy } I(L)=I(C) $, * D l a p r o d u k c j i$ (L::=LC)Parser nie mógł rozpoznać (błąd składni): {\displaystyle określamy } I(L)=2I(L')+I(C) $, * D l a p r o d u k c j i$ (S::=L)Parser nie mógł rozpoznać (błąd składni): {\displaystyle określamy } I(S)=I(L) $, * D l a p r o d u k c j i$ (S::=ZL)Parser nie mógł rozpoznać (błąd składni): {\displaystyle określamy } I(S)=I(Z)I(L)Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 <math> G=\langle \{Id,L,C,Ch\},\{0,1,\ldots,9,a,b,\ldots,z,\_\},\{Id::= LCh, Ch ::= \varepsilon | ChL |ChC\},Id \rangle } W gramatyce tej </math>LParser nie mógł rozpoznać (błąd składni): {\displaystyle oznacza pojedynczą literę, } CParser nie mógł rozpoznać (błąd składni): {\displaystyle oznacza pojedynczą cyfrę, } ChParser nie mógł rozpoznać (błąd składni): {\displaystyle 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 } \_Parser nie mógł rozpoznać (błąd składni): {\displaystyle . 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 } +,-,\div,\bmodParser nie mógł rozpoznać (błąd składni): {\displaystyle oraz nawiasy. Ogólnie rzecz biorąc można powiedzieć, że wyrażeniem jest stała, zmienna oraz że jeśli } U,VParser nie mógł rozpoznać (błąd składni): {\displaystyle są wyrażeniami, to wyrażeniem też jest } -U,U+V,U-V,U*V,U\div V, U \bmod V, (U)Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Daje to niezwykle prostą gramatykę: <math> 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 </math>---0 $c z y$ 0 - - 1Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 - - 3Parser nie mógł rozpoznać (nieznana funkcja „\item”): {\displaystyle \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-1Parser nie mógł rozpoznać (błąd składni): {\displaystyle powinno dać wynik } 1 $, a n i e$ 3Parser nie mógł rozpoznać (błąd składni): {\displaystyle ). \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] <math> 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 </math>PParser nie mógł rozpoznać (błąd składni): {\displaystyle jest zbiorem następujących produkcji: <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{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ź <math> G=\langle \{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| SC \},S \rangle } i reguły semantyczne:

Dla symboli końcowych określamy </math>I(0)=\zielone[0], I(1)=\zielone[1], \ldots, I(9)=\zielone[9] $* D l a p r o d u k c j i$ C::=xParser nie mógł rozpoznać (błąd składni): {\displaystyle określamy } I{C)=I(x) $g d z i e$ x=0,1,\ldots,9Parser nie mógł rozpoznać (błąd składni): {\displaystyle *Dla produkcji (S::=SC) określamy } I(S)=10I(S')+I(C)Parser nie mógł rozpoznać (błąd składni): {\displaystyle , *Dla produkcji (S::=C) określamy } I(S)=I(C)Parser nie mógł rozpoznać (błąd składni): {\displaystyle , \end{Odpowiedź} Zbadajmy teraz, jak wygląda drzewo wywodu wyrażenia } a+b*4Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Ł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*4Parser nie mógł rozpoznać (błąd składni): {\displaystyle ] \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:ID\rightarrow Z?Parser nie mógł rozpoznać (błąd składni): {\displaystyle , która zbiór wszystkich identyfikatorów } IDParser nie mógł rozpoznać (błąd składni): {\displaystyle przeprowadza w zbiór nieco rozszerzony liczb całkowitych } Z_?=Z\cup \{?\} $, g d z i e s y m b o l$ ?Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 } kParser nie mógł rozpoznać (błąd składni): {\displaystyle będzie liczbą przekątnych w wielokącie'', wówczas do końca wywodu } kParser nie mógł rozpoznać (błąd składni): {\displaystyle nie może oznaczać niczego innego. W informatyce, jeśli napiszemy niech } kParser nie mógł rozpoznać (błąd składni): {\displaystyle stanie się równe } 5Parser nie mógł rozpoznać (błąd składni): {\displaystyle , to za chwilę wartość zmiennej } kParser nie mógł rozpoznać (błąd składni): {\displaystyle może ulec zmianie, jeśli sobie tego zażyczymy. Zatem przez } V(z)Parser nie mógł rozpoznać (błąd składni): {\displaystyle będziemy rozumieli wartość zmiennej } zParser nie mógł rozpoznać (błąd składni): {\displaystyle , 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 } VParser nie mógł rozpoznać (błąd składni): {\displaystyle . Podamy teraz reguły wartościowania wyrażeń. Tym razem funkcję interpretacji oznaczymy przez } I_VParser nie mógł rozpoznać (błąd składni): {\displaystyle , ż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 } \oplusParser nie mógł rozpoznać (błąd składni): {\displaystyle *dla każdego } x\neq error: x\oplus ? = ?\oplus x = ?Parser nie mógł rozpoznać (błąd składni): {\displaystyle *dla każdego } x: x \oplus error = error \oplus x = errorParser nie mógł rozpoznać (błąd składni): {\displaystyle i analogicznie dla operacji jednoargumentowych. Reguły semantyczne *Dla symboli końcowych określamy } I_V(<stała>)=I(<stala bez znaku>) (jak w ćwiczeniu

#Stałe bez znaku)

dla produkcji $< z m i e n n a > : : = $ określamy $I_{V} (< z m i e n n a >) = V ()$
dla produkcji Parser nie mógł rozpoznać (błąd składni): {\displaystyle <czynnik>::=<stała>} określamy Parser nie mógł rozpoznać (błąd składni): {\displaystyle I_V(<czynnik>)=I_V(<stała>)}
dla produkcji $< c z y n n i k > : : = < z m i e n n a >$ określamy $I_{V} (< c z y n n i k >) = I_{V} (< z m i e n n a >)$
dla produkcji Parser nie mógł rozpoznać (błąd składni): {\displaystyle <czynnik>::=(<wyrażenie Z>)} określamy Parser nie mógł rozpoznać (błąd składni): {\displaystyle I_V(<czynnik>)=I_V(<wyrażenie Z>)}
dla produkcji Parser nie mógł rozpoznać (błąd składni): {\displaystyle <składnik>::=<czynnik>} określamy Parser nie mógł rozpoznać (błąd składni): {\displaystyle I_V(<składnik>)=I_V(<czynnik>)}
dla produkcji Parser nie mógł rozpoznać (błąd składni): {\displaystyle <składnik>::=<składnik>*<czynnik>} określamy Parser nie mógł rozpoznać (błąd składni): {\displaystyle I_V(<składnik>)=I_V(<składnik>)I_V(<czynnik>)}
dla produkcji Parser nie mógł rozpoznać (błąd składni): {\displaystyle <składnik>::=<składnik> div <czynnik>} określamy

Parser nie mógł rozpoznać (błąd składni): {\displaystyle I_V(<składnik>)=\left\{ \begin{array}{ll} I_V(<składnik'>\zielony[\div] I_V(<czynnik>)& \mbox{jeśli <math>I_V(<czynnik>\neq0} } \\ error& \mbox{jeśli $I_{V} (< c z y n n i k > = 0$ } \end{array} \right. </math>

dla produkcji Parser nie mógł rozpoznać (błąd składni): {\displaystyle <składnik>::=<składnik> mod <czynnik>} określamy

Parser nie mógł rozpoznać (błąd składni): {\displaystyle I_V(<składnik>)=\left\{ \begin{array}{ll} I_V(<składnik'>\zielony[\bmod] I_V(<czynnik>)& \mbox{jeśli <math>I_V(<czynnik>\neq0} } \\ error& \mbox{jeśli $I_{V} (< c z y n n i k > = 0$ } \end{array} \right. </math>

dla produkcji Parser nie mógł rozpoznać (błąd składni): {\displaystyle <wyrażenie Z>::=<składnik>} określamy Parser nie mógł rozpoznać (błąd składni): {\displaystyle I_V(<wyrażenie Z>)=I_V(<składnik>)}
dla produkcji Parser nie mógł rozpoznać (błąd składni): {\displaystyle <wyrażenie Z>::=-<składnik>} określamy Parser nie mógł rozpoznać (błąd składni): {\displaystyle I_V(<wyrażenie Z>)=\zielony[-]I_V(<składnik>)}
dla produkcji Parser nie mógł rozpoznać (błąd składni): {\displaystyle <wyrażenie Z>::=<wyrażenie Z>+<składnik>} określamy Parser nie mógł rozpoznać (błąd składni): {\displaystyle I_V(<wyrażenie Z>)=I_V(<wyrażenie Z>)\zielony[+] I_V(<składnik>)}
dla produkcji Parser nie mógł rozpoznać (błąd składni): {\displaystyle <wyrażenie Z>::=<wyrażenie Z>-<składnik>} określamy Parser nie mógł rozpoznać (błąd składni): {\displaystyle I_V(<wyrażenie Z>)=I_V(<wyrażenie Z>)\zielony{-}I_V(<składnik>)}

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 * b$

\Odpowiedź $6$

$c / a * b$

\Odpowiedź $0$

$c / a / b$

\Odpowiedź $e r r o r$

$(c + a) d i v (b + d)$

\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