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

From Studia Informatyczne

<<< Powrót

Spis treści

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

Język naturalny jest siłą rzeczy niejednoznaczny. Wiele pozostawia interpretacji, wyczuciu. Często słyszymy, że dwie rozmawiające osoby 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 żądania wobec komputera, 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.

Avram Noam Chomsky (1928- )
Enlarge
Avram Noam Chomsky (1928- )

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, 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. gramatyk bezkontekstowych, z których będziemy korzystali.

Alfabetem nazywamy dowolny skończony i niepusty zbiór symboli A={a_1,...,a_n}. Słowami nad alfabetem A 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 \varepsilon niezależnie od alfabetu nad którym jest utworzone. Zbiór wszystkich słów nad alfabetem A oznaczamy przez A^*. Przykładowo jeśli


A=\{a\}, \text to\ A^*={\varepsilon,a,aa,aaa,\ldots}.

Jeśli

A=\{a,b\}, \text to\ A^*=\{\varepsilon,a,b,aa,ab,ba,bb,aaa,aab,\ldots\}.

Długość słowa, to liczba jego liter. Język nad alfabetem A, to dowolny podzbiór zbioru A^*.

Gramatyką (bezkontekstową) nazwiemy uporządkowaną czwórkę

\langle N,T,P,S \rangle,

gdzie N oraz T to skończone i rozłączne zbiory, odpowiednio symboli pomocniczych (zwanych czasem nieterminalnymi lub nieterminalami) i końcowych (zwanych czasem terminalnymi lub terminalami), P jest zbiorem produkcji, a S\in N jest wyróżnionym symbolem pomocniczym zwanym aksjomatem gramatyki. Produkcje wchodzące w skład zbioru P są postaci X ::= w, gdzie X\in N, a w\in (N\cup T)^*. Pojedynczą taką produkcję interpretujemy jako możliwość zastąpienia symbolu pomocniczego X 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 S i do poszczególnych symboli pomocniczych stosujemy którąś z produkcji ze zbioru P 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ę 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

G_1=\langle \{S\},\{a\},\{S::=\varepsilon, S::=aaS\},S \rangle

Gramatyka G_1 generuje wszystkie parzyste słowa złożone z samych liter a (uwaga słowo puste jest słowem o parzystej długości!).

Przykład 2

G_2=\langle \{S\},\{a,b\},\{S::=\varepsilon, S::=aSa, S::=bSb\},S \rangle

Gramatyka G_2 generuje wszystkie parzyste palindromy nad dwuelementowym alfabetem \{a,b\}.


[Jeśli nie wiesz co to są palindromy, to kliknij poniżej]

Palindromem nazwiemy każde słowo, które czytane wprost jest identyczne, jak czytane wspak, 
czyli takie słowo a_1,\ldots,a_n, że dla każdego k\in\{1,...,n\} zachodzi 
a_k=a_{n-k+1}. 
Parzysty palindrom to palindrom o parzystej długości.

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_2 wyglądają w tej notacji następująco:

\{S::=\varepsilon | aSa | bSb\}.

Drzewa wywodu

Historię wyprowadzeń słowa w danej gramatyce możemy zapisać za pomocą drzewa wywodu. Korzeniem w tym drzewie jest aksjomat gramatyki, a jeśli została do symbolu pomocniczego X, który jest węzłem w drzewie, zastosowana produkcja X::=x_1,\ldots,x_n, to synami węzła X stają się elementy x_1,\ldots,x_n. Oto przykład wyprowadzenia słowa abba w gramatyce G_2.

\begin{Rysunek}[rys1-abba] \end{Rysunek}

Moglibyśmy to wyprowadzenie przedstawić w wersji liniowej

S \rightarrow aSa \rightarrow abSba \rightarrow abba,

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 \rangle.

Za pomocą tej gramatyki możemy wygenerować dowolną naprzemienną sekwencję liter b oraz a zaczynającą się i kończącą na literę b. Na ile sposobów można otrzymać słowo babab? W notacji liniowej tych sposobów jest sporo, przykładowo:

S \rightarrow SaS \rightarrow SaSaS \rightarrow SaSab \rightarrow baSab \rightarrow babab.

Albo inaczej

S \rightarrow SaS \rightarrow Sab \rightarrow SaSab \rightarrow Sabab \rightarrow babab.


Ćwiczenie

Na ile sposobów można liniowo zapisać wywód słowa babab?

Odpowiedź

10

Ile jest drzew wywodu tego słowa? Okazuje się, że tylko dwa. Poniżej przykład ilustrujący powstawanie wspomnianych drzew. Przykład w powiększeniu.



Można gramatykę tak skonstruować, żeby słowo babab, podobnie jak i każde inne generowane przez powyższą gramatykę, miało tylko jedno drzewo wywodu. Oto ta gramatyka:
G_3=\langle \{S\},\{a,b\},\{S::=\varepsilon, S::=baS | b\},S \rangle

Taka gramatyka ma już tylko jedno drzewo wywodu dla słowa babab. 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 G jest jednoznaczna, jeśli każde słowo wyprowadzalne z G 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 G jest zgodna z językiem L\in T^*, jeśli każde słowo wyprowadzalne z G należy do L. Powiemy, że gramatyka G jest 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).

Liczby całkowite

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,XVI,+,\varepsilon. Oto propozycja gramatyki:

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 L lub ZL 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}

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:V\rightarrow 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,\ldtots,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

Wskazówka

Odrzuć parę symboli końcowych i lekko zmodyfikuj reguły semantyczne.

Odpowiedź

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 I(0)= \textcolor{blue}{0},    I(1)= \textcolor{blue}{1},   I(-)= \textcolor{blue}{-1},   I(+)= \textcolor{blue}{1}
  • dla produkcji C::=x określamy I(C)=I(x) gdzie x\in\{0,1\}
  • dla produkcji Z::=z określamy I(Z)=I(z) gdzie z\in\{+,-\}
  • dla produkcji L::=C określamy I(L)=I(C),
  • Dla produkcji (L::=LC) określamy I(L)=2I(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)

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\divW|(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.

Wyrażenia całkowitoliczbowe


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

gdzie P 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>

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

Wskazówka

Usuń znak i związane z nim produkcje z gramatyki dla stałych całkowitoliczbowych

Odpowiedź

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 I(0)=\zielone[0], I(1)=\zielone[1], \ldots, I(9)=\zielone[9]
  • Dla produkcji C::=x określamy I(C)=I(x) gdzie x=0,1,\ldots,9
  • Dla produkcji S::=SC określamy I(S)=10I(S')+I(C),
  • Dla produkcji S::=C określamy I(S)=I(C),

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:ID\rightarrow 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=?

  • c+a*b

Odpowiedź

6

  • c/a*b

Odpowiedź

0

  • c/a/b

Odpowiedź

error

  • (c+a) div (b+d)

Odpowiedź

?