Generatywizm a informatyka

Generatywizm jako lingwistyczna teoria jest najbliższy teoretyczno-informatycznemu sposobowi patrzenia na język. To, co najbardziej łączy programistów i językoznawców, to postać Naoma Chomsky'ego i jego pomysł na opis gramatyk. 

UWAGA: tu zaczyna się część informatyczna; nie jest taka straszna, ale jeśli chcesz ją pominąć, przewiń post trochę niżej, do kolejnej uwagi

W informatyce, język to zbiór słów nad jakimś alfabetem. Zapisujemy to w następujący sposób: $L \subset \Sigma^*$, gdzie $L$ to język, a $\Sigma$ to alfabet - zbiór znaków. Gwiazdka na alfabecie oznacza, że wybieramy z niego słowa (ciągi znaków) o dowolnej skończonej długości. Znaczek $\subset$ oznacza podzbiór, czyli wybrane słowa ze wszystkich możliwych. 

Język możemy w zgrabny sposób opisać za pomocą gramatyki. W zależności od tego jak skomplikowany jest on do wyznaczenia, będziemy potrzebować jej innego rodzaju. Hierarchia Chomskiego, z której korzystają informatycy, wyróżnia cztery typy gramatyk:

• typ 3, reprezentujący języki regularne, które możemy opisać za pomocą gramatyk regularnych lub automatów skończonych
• typ 2, reprezentujący języki bezkontekstowe, które możemy opisać za pomocą gramatyk bezkontekstowych lub niedeterministycznych automatów ze stosem
• typ 1, reprezentujący języki kontekstowe, z którymi wiążemy gramatyki kontekstowe i automaty z ograniczoną liniowo taśmą
• typ 0, reprezentujący języki rekurencyjnie przeliczalne, z którymi wiążemy gramatyki ogólne (kombinatoryczne) i maszyny Turinga

Do opisu składni języków programowania wykorzystywana jest gramatyka bezkontekstowa (nie przejmujemy się otoczeniem przy produkowaniu wyrazów). Składa się ona z czterech elementów:

• $\Sigma$ - wspomnianego wcześniej alfabetu, który będziemy nazywać zbiorem symboli terminalnych (tworzenie wyrazów z języka będzie polegało na przepisywaniu symboli; terminalnych (czyli końcowych) już nie możemy zamienić na inne)
• $\Gamma$ - zbioru symboli nieterminalnych (te będziemy mogli, a nawet chcieli przepisywać)
• $\delta$ - reguł przepisywania, czyli tzw. produkcji
• $S$ - symbolu startowego, od którego zaczynamy przepisywanie

Przykład 1 (trochę abstrakcyjny, jeśli czujesz się przeciążony nadmiarem matematycznych znaczków, możesz go pominąć)

Załóżmy, że nasz alfabet składa się z dwóch elementów: $\Sigma = \{a,b\}$, a zbiór nieterminali z trzech: $\Gamma= \{A,B,S\}$. Jako reguły przepisywania (zamieniania nieterminali na ciągi terminali i innych nieterminali) przyjmijmy:

$S \to ASB$

$S \to \epsilon$ ($\epsilon$ oznacza słowo puste, czyli 0-literowe)

$A \to a$

$B \to b$

"A" możemy zamienić tylko na "a" - to jest taki producent literek "a". Analogicznie, nieterminal "B" to producent literek "b". "S" to nasz symbol startowy. Możemy albo zamienić go na ciąg "ASB", albo skończyć proces przepisywania i zamienić go na słowo puste.

Przykładowy ciąg zamian (wywód) może wyglądać w następujący sposób:

$S \to ASB \to AASBB \to AAASBBB \to AAABBB \to aAABBB \to ... \to aaabbb$

Jak widać na tym przykładzie, powyższa gramatyka produkuje język składający się ze słów postaci a...ab...b, gdzie ilość literek "a" musi być równa ilości literek "b".

Przykład 2 (mniej abstrakcyjny - dotyczy języków programowania)

Tworzenie ciągów aaabbb nie jest zbyt pasjonujące. Zobaczmy więc bardziej praktyczne zastosowanie - wykorzystanie gramatyk bezkontekstowych do opisu języków programowania. Jeśli nie mieliście styczności z żadnym językiem programowania wcześniej, to w dużym uproszczeniu słowa w takich językach, czyli programy komputerowe, wyglądają jak lista kolejnych rozkazów dla maszyny. 

Kilka bardzo prostych przykładowych produkcji z takich gramatyk:

$VARIABLE\_DEFINITION \to "var" NAME$

$VARIABLE\_ASSIGNMENT \to NAME "="  NUMBER$

$INSTRUCTION \to VARIABLE\_DEFINITION$

$INSTRUCTION \to VARIABLE\_ASSIGNMENT $

$BLOCK \to BLOCK$ $INSTRUCTION$

$CONDITION \to NAME "==" NUMBER$

$WHILE \to "while"$ $CONDITION$ $"do"$ $BLOCK ";"$

Powyższa gramatyka pozwala tworzyć zmienne o określonej nazwie, przypisywać im liczby i porównywać wartości zmiennych z wartościami liczb. Daje również możliwość stworzenia pętli "while", która zwykle semantycznie oznacza, że chcemy wykonywać jakiś blok poleceń dopóki jakiś warunek jest spełniony.

UWAGA: uff, tutaj kończy się część informatyczna

Okazuje się, że gramatykę języka naturalnego można (próbować) opisać w bardzo podobny sposób: za pomocą symboli nieterminalnych (tutaj nazywanych preterminalnymi) i reguł ich przepisywania. 

Najbardziej podstawowy generatywny model zawiera następujące symbole preterminalne:

$NP$ - nominal phrase, czyli fraza rzeczownikowa

$N$ - noun, czyli rzeczownik

$VP$ - verb phrase, czyli fraza czasownikowa

$V$ - verb, czyli czasownik

$AdjP$ - adjective phrase, czyli fraza przymiotnikowa

$Adj$ - adjective , czyli przymiotnik

i oczywiście symbol startowy $S$ - sentence, czyli zdanie.

Powyższe symbole możemy przepisywać za pomocą następujących reguł:

$S \to NP$ $VP$ (każde zdanie musi się składać z części związanej z podmiotem i orzeczeniem)

$NP \to AdjP$ $N$ (rzeczownik może mieć swoje określenie w postaci frazy przymiotnikowej)

$VP \to V$ $NP$ (czasownik może mieć swoje dopełnienie w postaci frazy rzeczownikowej)

oraz trywialnych:

$NP \to N$ 

$VP \to V$

$AdjP \to Adj$  

Ponieważ zapisywanie rozkładu zdania jako ciągu przepisywań jest dość nieczytelne, często do jego reprezentacji wykorzystuje się drzewka (w informatyce również, są to tzw. drzewa wywodu albo drzewa parsowania):

Na powyższym drzewku jako symbole terminalne zaznaczyłam słowa, które już mają uzgodnioną swoją ostateczną formę (np. "lubi" zamiast "LUBIĆ"). Ustalanie tej formy następuje jednak dopiero w dalszych etapach. 

W ogólności proces generowania zdania w takiej gramatyce możemy zapisać w następujący sposób:

1. Przepisywanie symboli preterminalnych

2. Ustalanie form (np. osoby, liczby, rodzaju) i sprawdzenie, czy dane słowa mogą być ze sobą zestawione
3. Transformacje (np. zmiana szyku)

Jak widzicie generatywny opis języka jest więc bardzo podobny do sposobu, w który informatycy opisują swoje języki - albo dość abstrakcyjne i czysto teoretyczne, albo np. języki programowania. Nie jest to jednak jedyne połączenie tych dwóch dziedzin nauki, mam nadzieję, że w którymś z kolejnych postów uda mi się przedstawić Wam inne ciekawe styki tyki światów.