Gramatyka formalna

Ten artykuł od 2013-09 wymaga zweryfikowania podanych informacji.

Należy podać wiarygodne źródła w formie przypisów bibliograficznych.
Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte.
Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary)
Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu.
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

Gramatyka formalna – sposób opisu języka formalnego, czyli podzbioru zbioru wszystkich słów skończonej długości nad danym alfabetem.

Do zdefiniowania gramatyki formalnej potrzebne jest określenie zbioru symboli terminalnych, zbioru symboli nieterminalnych, symbolu startowego oraz zbioru reguł określających sposób wyprowadzania słów.

Symbol nieterminalny to symbol, który można definiować. Symbole nieterminalne zwane są również zmiennymi syntaktycznymi, ponieważ umożliwiają tworzenie ciągów zawierających kombinacje symboli terminalnych i nieterminalnych.

Symbol terminalny to symbol elementarny tworzący wyrazy języka formalnego. Symbole terminalne są znakami, które mogą pojawić się na wejściu lub wyjściu z reguł produkcji gramatyki formalnej. Symbol terminalny nie może być podzielony na „mniejsze” jednostki, lub ściślej: symbole terminalne nie mogą być zmieniane za pomocą reguł gramatyki formalnej, w odróżnieniu od symboli nieterminalnych.

Gramatyka formalna posiada wyróżniony symbol nieterminalny, zwany symbolem startowym, od którego, poprzez stosowanie reguł produkcji, zaczyna się wyprowadzanie wszystkich wyrazów języka formalnego. Tworzenie wyrazu języka formalnego kończy się wówczas gdy zawiera on już tylko symbole terminalne.

Symbole terminalne (równoważne symbolom alfabetu języka) są symbolami, które pozostaną w wyprowadzonym słowie – w przeciwieństwie do symboli nieterminalnych używanych tylko podczas wyprowadzania słowa. Reguły gramatyki postaci ${\displaystyle S_{1}\to S_{2},}$ gdzie ${\displaystyle S_{1}}$ i ${\displaystyle S_{2}}$ to ciągi symboli terminalnych i nieterminalnych, określają możliwe podstawienia symboli w wyprowadzanym słowie. Wyprowadzanie rozpoczynamy od ciągu złożonego z wyróżnionego symbolu nazywanego symbolem początkowym. Odbywa się ono przez zastępowanie podciągów tego ciągu zgodnie z regułami gramatyki. Jeśli w ciągu mamy podciąg ${\displaystyle S_{1},}$ możemy zastąpić go przez ${\displaystyle S_{2}.}$

Rozważmy przykładową gramatykę z symbolem nieterminalnym S, który jest jednocześnie symbolem startowym, oraz zbiorem symboli terminalnych ${\displaystyle \{a,b\}.}$ Reguły tej gramatyki, która umożliwia generowanie słów postaci ba, abab, aababb, aaababbb itd. wyglądają następująco:

• ${\displaystyle S\to aSb}$
• ${\displaystyle S\to ba}$

Zaczynamy od symbolu startowego S, możemy zastąpić go przez aSb zgodnie z pierwszą regułą. Możemy użyć jej jeszcze raz otrzymując aaSbb. Po użyciu drugiej reguły pozostanie nam ciąg aababb. Składa się on tylko z symboli terminalnych, więc wyprowadzenie słowa zostało zakończone.

Wymaganie, żeby symbol startowy był jeden, nie ogranicza nam szczególnie możliwości budowania gramatyk. Jeśli chcemy zacząć generację od jakiegoś innego słowa ${\displaystyle w_{1},}$ lub od pewnych kilku możliwych słów ${\displaystyle \{w_{1},\dots ,w_{n}\},}$ możemy dodać symbol „przedstartowy” ${\displaystyle S,}$ oraz reguły postaci ${\displaystyle S\to w_{i},}$ będące sumarycznie podzbiorem wszystkich dozwolonych reguł dla danej gramatyki. Wystarcza nam więc jeden symbol startowy, niezależnie od tego, od ilu możliwych słów zamierzamy zaczynać.

Nie ogranicza nas też specjalnie podział na symbole terminalne i nieterminalne. Jeśli chcemy możemy nawet wymagać, żeby po lewej stronie każdej reguły były tylko symbole nieterminalne.

Jeśli mamy w którymś miejscu symbol terminalny ${\displaystyle a,}$ a chcemy mieć tam symbol nieterminalny, to tworzymy specjalny symbol nieterminalny ${\displaystyle X_{a},}$ i regułę ${\displaystyle X_{a}\to a.}$ Wtedy wszędzie oprócz tej reguły zamiast ${\displaystyle a}$ używamy ${\displaystyle X_{a}.}$

Przykładowo, załóżmy, że mamy gramatykę:

• ${\displaystyle S\to abc}$
• ${\displaystyle a\to bc}$
• ${\displaystyle b\to ca}$
• ${\displaystyle c\to ab}$

I chcemy żeby po lewej stronie były tylko symbole nieterminalne. Dodajemy więc następujące reguły:

• ${\displaystyle X_{a}\to a}$
• ${\displaystyle X_{b}\to b}$
• ${\displaystyle X_{c}\to c}$

A te już istniejące zamieniamy na:

• ${\displaystyle S\to X_{a}X_{b}X_{c}}$
• ${\displaystyle X_{a}\to X_{b}X_{c}}$
• ${\displaystyle X_{b}\to X_{c}X_{a}}$
• ${\displaystyle X_{c}\to X_{a}X_{b}}$

Tej techniki używa się np. w budowaniu postaci normalnej Chomsky’ego gramatyk bezkontekstowych.

Załóżmy, że mamy gramatykę ${\displaystyle G_{1}}$ generującą język ${\displaystyle L_{1}}$ i ${\displaystyle G_{2},}$ generującą język ${\displaystyle L_{2};}$ chcemy uzyskać język wszystkich słów które są albo w ${\displaystyle L_{1}}$ albo w ${\displaystyle L_{2}.}$

W tym celu tworzymy symbol startowy ${\displaystyle S}$ i dodajemy reguły przepisania go na symbol startowy pierwszego bądź drugiego języka:

${\displaystyle S\to S_{1}}$

${\displaystyle S\to S_{2}}$

Oraz wszystkie reguły z obu gramatyk.

Słowo będzie więc należało do języka jeśli da się wyprowadzić w jednej z gramatyk. Musimy jednak zadbać o to, żeby nie wolno było mieszać wyprowadzeń – tak, że część słowa jest wyprowadzona pierwszą gramatyką, a część drugą. Zanim więc połączymy zbiory reguł obu gramatyk, przekształćmy je najpierw tak, żeby po lewej stronie wszystkich reguł były wyłącznie nieterminale, i zmieńmy nazwy wszystkich nieterminali, żeby żaden nieterminal nie występował jednocześnie w obu gramatykach (to jak nazwane będą nieterminale nie wpływa w żaden sposób na to, jaki język dana gramatyka generuje). Jeśli gramatyki są tej postaci, to w żaden sposób nie da się w jednym wyprowadzeniu użyć reguł obu gramatyk.

Algorytm taki nie istnieje dla dopełnienia języka (zbioru wszystkich słów które nie należą do danego języka). Jest nawet możliwe, że dany język opisuje jakaś gramatyka, ale dla zbioru słów nie należących do niego nie ma żadnej gramatyki.

Dla dwóch gramatyk potrafimy też znaleźć gramatykę przecięcia języków (zbioru słów należących do obu języków), ale jej postać może być o wiele trudniejsza od postaci gramatyk oryginalnych.

Ograniczając postać reguł wyprowadzania, otrzymujemy klasy gramatyk, takie jak (szczegółowo w artykule hierarchia Chomsky’ego):

• gramatyki regularne
• gramatyki bezkontekstowe
  • gramatyki bezkontekstowe w postaci normalnej Chomsky’ego
  • gramatyki bezkontekstowe w postaci normalnej Greibach
• gramatyki kontekstowe
• gramatyki rekurencyjnie przeliczalne (bez ograniczeń na postać reguł)

Gramatyka regularna (odpowiednio: bezkontekstowa, kontekstowa) zawsze generuje język regularny (odp.: bezkontekstowy, kontekstowy). Jednak możliwe jest też, że pewna gramatyka, która nie jest regularna (bezkontekstowa, kontekstowa), generuje język regularny (bezkontekstowy, kontekstowy). W takim przypadku zawsze istnieje też gramatyka o regułach prostszej postaci generująca ten sam język.

• parser