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.
rycina
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\} \).
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\} \).