Gramatyki Formalne cz I 3

Wreszcie wprowadza się "["i"]" dla oznaczania elementów opcjonalnych.

Przykładem może tu być definicja liczby całkowitej (zbudowanej z cyfr i ewentualnie znaku):

liczba = [-] cyfra {cyfra)

Formalna definicja gramatyki generacyjnej G:

czwórka elementów (N, T, P, S) gdzie:

N — zbiór elementów pomocniczych zwanych nieterminalnymi T — zbiór symboli terminalnych — alfabet języka, który budujemy P — zbiór produkcji — formalny opis składni języka, który chcemy zbudować S — symbol startu, od którego zaczyna się generacja wcześniej nazywaliśmy go aksjomatem

Zestaw (zbiór) produkcji składa się z par (A, w), gdzie A jest symbolem pomocniczym, zaś w słowem zbudowanym z symboli terminalnych i nieterminalnych. Często produkcie oznaczamy A-*w.

Dla naszej gramatyki wyrażeń arytmetycznych (z poprzedniego przykładu) można podać następującą definicję (kładąc o^-jako "wyrażenie" a o jako "składnik", p jako "czynnik"):

N = {o-, a.

T = {x. y. z, +,*,(,)} p = { o- -> o^- + a a -> ? a -> a * p a->0 P—>(a)

P->x

P y P * z }

Zauważmy, że do opisu produkcji użyliśmy pojedynczej strzałki Wprowadzając słowa przy użyciu gramatyk użyjemy strzałek podwójnych =*•. Wiąże się to z tym, że w gramatyce w zbiorze produkcji, wyznaczamy możliwe zamiany symboli lub ich zestawów. Przy opisie generacji zastępujemy całe słowa. Mówimy, że słowo w generuje słowo J (co zapisujemy w^t), jeśli w słowie w potrafimy wskazać symbol nieterminalny A. zaś w słowie t podsłowo p takie że A -»p należy do zbioru produkcji P.