Gramatyka formalna: Różnice pomiędzy wersjami

Usunięte 141 bajtów ,  2 lata temu
m
m (drobne techniczne, WP:SK)
m (WP:SK+Bn)
Gramatyka formalna posiada wyróżniony symbol nieterminalny, zwany '''[[symbol startowy|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 <math>S_1 \rightarrowto S_2,</math>, gdzie <math>S_1</math> i <math>S_2</math> 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 <math>S_1,</math>, możemy zastąpić go przez <math>S_2.</math>.
 
Rozważmy przykładową gramatykę z symbolem nieterminalnym S, który jest jednocześnie symbolem startowym, oraz zbiorem symboli terminalnych <math>\{a,b\}.</math>.
Reguły tej gramatyki, która umożliwia generowanie słów postaci ba, abab, aababb, aaababbb itd. wyglądają następująco:
* <math>S \rightarrowto aSb</math>
* <math>S \rightarrowto ba</math>
 
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.
 
== Symbol startowy ==
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 <math>w_1,</math>, lub od pewnych kilku możliwych słów <math>\{w_1,\dots,w_n\},</math>, możemy dodać symbol "przedstartowy"„przedstartowy” <math>S,</math>, oraz reguły postaci <math>S\rightarrowto w_i,</math>, 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ć.
 
== 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 <math>a,</math>, a chcemy mieć tam symbol nieterminalny,
to tworzymy specjalny symbol nieterminalny <math>X_a,</math>, i regułę <math>X_a \rightarrowto a.</math>.
Wtedy wszędzie oprócz tej reguły zamiast <math>a</math> używamy <math>X_a.</math>.
 
Dla przykładu, załóżmy że mamy gramatykę:
* <math>S \rightarrowto abc</math>
* <math>a \rightarrowto bc</math>
* <math>b \rightarrowto ca</math>
* <math>c \rightarrowto ab</math>
I chcemy żeby po lewej stronie były tylko symbole nieterminalne. Dodajemy więc następujące reguły:
* <math>X_a \rightarrowto a</math>
* <math>X_b \rightarrowto b</math>
* <math>X_c \rightarrowto c</math>
A te już istniejące zamieniamy na:
* <math>S \rightarrowto X_aX_bX_c</math>
* <math>X_a \rightarrowto X_bX_c</math>
* <math>X_b \rightarrowto X_cX_a</math>
* <math>X_c \rightarrowto X_aX_b</math>
Tej techniki używa się np. w budowaniu [[postaćPostać normalna Chomsky'egoChomsky’ego|postaci normalnej Chomsky'egoChomsky’ego]] [[gramatyka bezkontekstowa|gramatyk bezkontekstowych]].
 
== Alternatywa języków ==
Załóżmy że mamy gramatykę <math>G_1</math> generującą język <math>L_1</math> i <math>G_2,</math>, generującą język <math>L_2;</math>; chcemy uzyskać język wszystkich słów które są albo w <math>L_1</math> albo w <math>L_2.</math>.
 
W tym celu tworzymy symbol startowy <math>S</math> i dodajemy reguły przepisania go na symbol startowy pierwszego bądź drugiego języka:
: <math>S\rightarrowto S_1</math>
: <math>S\rightarrowto S_2</math>
: Oraz wszystkie reguły z obu gramatyk.
 
 
== Klasy gramatyk ==
'''Ograniczając postać reguł''' wyprowadzania, otrzymujemy klasy gramatyk, takie jak (szczegółowo w artykule [[hierarchia Chomsky'egoChomsky’ego]]):
* [[gramatyka regularna|gramatyki regularne]]
* [[gramatyka bezkontekstowa|gramatyki bezkontekstowe]]
** [[postaćPostać normalna Chomsky'egoChomsky’ego|gramatyki bezkontekstowe w postaci normalnej Chomsky'egoChomsky’ego]]
** [[postać normalna Greibach|gramatyki bezkontekstowe w postaci normalnej Greibach]]
* [[gramatyka kontekstowa|gramatyki kontekstowe]]
* [[gramatykaGramatyka rekurencyjnie przeliczalnakombinatoryczna|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.
 
== Zobacz też ==
* [[Analizator składniowy|Parserparser]]
 
{{Kontrola autorytatywna}}