8299308025

gramatyk przypisuje się Noamowi Chomsky’emu.

Gramatyka jest skończonym zbiorem zasad rozwijania i zmieniania napisów. Występują w niej litery alfabetu oraz symbole pomocnicze. Generowanie słowa zaczyna się od początkowego symbolu pomocniczego, w jego trakcie stosuje się zasady gramatyki i otrzymuje jakieś słowo napisane samymi literami, już bez symboli pomocniczych.

Języki formalne i gramatyki zostały omówione przystępnie w już wspomnianym podręczniku Hopcroft, Motwani i Ullman [10].

O zastosowaniach gramatyk w kompilacji programów komputerowych napisano wiele; dość pełnym i niezbyt skomplikowanym wykładem jest np. Gries [9].

1.3.1 Określenie gramatyk

Definicja 1.22

Gramatyka formalna¹⁵ to czwórka G = (E, N, S,P), w której

•    E jest skończonym niepustym zbiorem liter, zwanych też symbolami terminalnymi lub krótko terminalami; sam zbiór E nazywamy alfabetem terminalnym. Słowa, które gramatyka wygeneruje, będą należeć do zbioru E* .

•    N jest skończonym niepustym zbiorem symboli pomocniczych, zwanych też nietermi-nalami; sam zbiór N nazywamy alfabetem nieterminalnym. Nieterminale używane są w trakcie generowania słowa, ale są z niego eliminowane, zanim generowanie dobiegnie końca.

•    S € N jest specjalnym nieterminalem początkowym lub aksjomatem. Od niego rozpoczyna się każde generowanie słowa.

•    P jest skończonym zbiorem produkcji gramatyki; każda produkcja jest napisem postaci W\ —* W2, gdzie W\,W2 € (EUJV)*, przy czym w słowie W\ musi występować przynajmniej jeden nieterminal. Każda produkcja zezwala na zastępowanie podsłowa w\ przez W2 w trakcie generowania słowa.

Poniżej opisane jest, w jaki sposób taka gramatyka generuje słowa.

Definicja 1.23

Niech G = (E, N, S, P) będzie gramatyką formalną. Relacja bezpośredniego wywodu w gramatyce G, =>g C (EU N)* x (EU N)*, określona jest następująco:

V\ =>G ^v2 <=> dla pewnych słów u,Wi,W2,u' € (EU N)*

V\ = UW\U' & V2 = UW2llf &

Wi —► W2 € P

Jeśli v\ =£*g V2, to mówimy, że V2 da się wywieść bezpośrednio lub wywieść w jednym kroku z tą.

Czyli ni =>c ^v2 oznacza, że V2 powstaje z v\ przez zastąpienie występującej w v\ lewej strony jakiejś produkcji z P przez prawą stronę tej samej produkcji. W sytuacjach, kiedy nie ma niejasności co do stosowanej gramatyki, indeks G się opuszcza: V\ => V2-

¹⁵Zwana też gramatyką struktur frazowych.

17