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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle A={a_1,...,a_n\}} . {\em 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 $\epsilon$, 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$, to $A^{*}=\epsilon ,a,aa,aaa,\dots$. Jeśli $A==\{a,b\}$, to $A^{*}=\{\epsilon ,a,b,aa,ab,ba,bb,aaa,aab,\dots \}$. {\em Długość słowa}, to liczba jego liter. {\em Język} nad alfabetem $A$, to dowolny podzbiór zbioru $A^{*}$.

{\em Gramatyką} (bezkontekstową) nazwiemy uporządkowaną czwórkę $⟨N,T,P,S⟩,$gdzie $N$ oraz $T$, 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$ jest zbiorem produkcji, a $S\in N$ jest wyróżnionym symbolem pomocniczym zwanym {\em 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ę {\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] $G_1=⟨\{S\},\{a\},\{S::=\epsilon ,S::=aaS\},S⟩$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=⟨\{S\},\{a\},\{S::=\epsilon ,S::=aSa,S::=bSb\},S⟩$Gramatyka $G_2$ generuje wszystkie parzyste palindromy nad dwuelementowym alfabetem $\{a,b\}$.

\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,\dots ,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. \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_2$ wyglądają w tej notacji następująco: $\{S::=\epsilon |aSa|bSb\}$.

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 $X$, który jest węzłem w drzewie zastosowana produkcja $X::=x_1,\dots ,x_n$, to synami węzła $X$ stają się elementy $x_1,\dots ,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\to aSa\to abSba\to 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=⟨\{S\},\{a,b\},\{S::=SaS|b\},S⟩$. 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\to SaS\to SaSaS\to SaSab\to baSab\to babab$. Albo inaczej $S\to SaS\to Sab\to SaSab\to Sabab\to babab$.

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

\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 $babab$, podobnie jak i każde inne generowane przez powyższą gramatykę, miało tylko jedno drzewo wywodu. Oto ta gramatyka:

$G_3=⟨\{S\},\{a,b\},\{S::=\epsilon ,S::=baS|b\},S⟩$

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 {\em 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 {\em 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 {\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,XVI,+,\epsilon$. 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|ZL,Z::=+|-,L::=C|LC,\},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 $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}

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::=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^{\prime })+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 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|ZL,Z::=+|-,L::=C|LC,\},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::=LC)$ określamy $I(L)=2I(L^{\prime })+I(C)$,
• Dla produkcji $(S::=L)$ określamy $I(S)=I(L)$,
• Dla produkcji $(S::=ZL)$ 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=⟨\{Id,L,C,Ch\},\{0,1,\dots ,9,a,b,\dots ,z,\mathrm{\_}\},\{Id::=LCh,Ch::=\epsilon |ChL|ChC\},Id⟩$W gramatyce tej $L$ oznacza pojedynczą literę, $C$ oznacza pojedynczą cyfrę, $Ch$ 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 $\mathrm{\_}$.

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÷V,UmodV,(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:

<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ź $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|SC\},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)=10I(S^{\prime })+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:ID\to 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ść {\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\ne 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 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>)$*dlaprodukcji$<czynnik>::=<stała>Parser nie mógł rozpoznać (błąd składni): {\displaystyle określamy } I_V(<czynnik>)=I_V(<stała>)$*dlaprodukcji$<czynnik>::=<zmienna>Parser nie mógł rozpoznać (błąd składni): {\displaystyle określamy } I_V(<czynnik>)=I_V(<zmienna>)$*dlaprodukcji$<czynnik>::=(<wyrażenie Z>)Parser nie mógł rozpoznać (błąd składni): {\displaystyle określamy } I_V(<czynnik>)=I_V(<wyrażenie Z>)$*dlaprodukcji$<składnik>::=<czynnik>Parser nie mógł rozpoznać (błąd składni): {\displaystyle określamy } I_V(<składnik>)=I_V(<czynnik>)$*dlaprodukcji$<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>)$*dlaprodukcji$<składnik>::=<składnik> div <czynnik>Parser nie mógł rozpoznać (błąd składni): {\displaystyle określamy <span id=""/> <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 <span id=""/> <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>)$*dlaprodukcji$<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>)$*dlaprodukcji$<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>)$*dlaprodukcji$<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ź } ?${\displaystyle }$