Gramatyka formalna: Różnice pomiędzy wersjami

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>.

* <math>S \rightarrowto aSb</math>

* <math>S \rightarrowto ba</math>

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ć.

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>.

* <math>S \rightarrowto abc</math>

* <math>a \rightarrowto bc</math>

* <math>b \rightarrowto ca</math>

* <math>c \rightarrowto ab</math>

* <math>X_a \rightarrowto a</math>

* <math>X_b \rightarrowto b</math>

* <math>X_c \rightarrowto c</math>

* <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]].

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>.

: <math>S\rightarrowto S_1</math>

: <math>S\rightarrowto S_2</math>

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

** [[postaćPostać normalna Chomsky'egoChomsky’ego|gramatyki bezkontekstowe w postaci normalnej Chomsky'egoChomsky’ego]]

* [[gramatykaGramatyka rekurencyjnie przeliczalnakombinatoryczna|gramatyki rekurencyjnie przeliczalne]] (bez ograniczeń na postać reguł)

* [[Analizator składniowy|Parserparser]]