Gramatyki Formalne cz II 2

Rozważmy zatem gramatykę liniową w postaci:

G = {{S, T}, {a}, P, S}, gdzie P = {S aT, T aS, T a}

Wygenerujmy nią poprzednio generowane gramatyką bezkontekstową słowo aaaaaa S □ aT □ aaS □ aaaT □ aaaaS □ aaaaaT □ aaaaaa

Użyliśmy 3 razy pierwszą produkcję, 2 razy drugą i 1 raz trzecią. Udało się narn znaleźć prostszą gramatykę generującą ten sarn język.

Język nazywamy określeniem najprostszej gramatyki, która go generuje.

Zatem język słów o parzystej ilości liter a (postaci a2n) jest liniowy. Dla języka postaci anbn nie da się zbudować gramatyki liniowej, jest on więc bezkontekstowy (bo taka była nasza gramatyka).

Istnieją języki np. typu aⁿbⁿcⁿ1 dla których nie da się znaleźć gramatyki bezkontekstowej. Musimy zatem rozważyć możliwości zbioru produkcji. Niech będzie to nadal skończony zbiór reguł postaci w-* t, gdzie w jest dowolnym słowem zawierającym choć jeden symbol nieterminalny fotoczenie tego symbolu nazywamy kontekstoyyym). zaś t dowolnym słowem zawierającym symbole terminalne i nieterminalne. Podczas generowania możemy zastępować zamiast pojedynczych symboli nieterminalnych całe lewe strony produkcji.

Niech G = {N. T, P, S}. gdzie

N = {S. B. 0}

T = {a.b,c}

P = {S -» aSBC, S -» abc, cB -> Bc, bB —» bb, cC -> cc}

Spróbujmy wygenerować słowo aaa bbb ccc

S aSBC => aaSBCBC =$■ aaabcBCBC =» aaabBcCBC =*• aaabbcCBC =*• aaabbccBC =$■ aaabbcBcC =* aaabbBccC => aaabbbccC => aaabbbccc Zatem istotnie była tu potrzebna gramatyka kontekstowa. Spośród używanych języków takiej gramatyki kontekstowej wymagał język ALGOL 68 (bardzo elastyczny, ale skomplikowany). Komplikacja tej gramatyki przeszkodziła wjego rozpowszechnieniu (trudności w zbudowaniu powszechnie dostępnego translatora, którego nigdy nie uzyskano, gdyż był zbyt skomlikowany dla większości komputerów). Dlatego został on wyparty przez PASCALA (czy PASCAL jest bezkontekstowy?!).

Gramatyki formalne wykorzystywane są głównie do budowy kompilatorów. Zasadniczym elementem kompilatora jest paisei. Jest to algorytm dokonujący sprawdzenia czy dany napis należy x należy do alfabetu terminalnego T jest zdaniem generowanym przez gramatykę G. Jeśli tak, to odnajduje wywód S=?X,jeśli nie, zgłasza błąd. Czy robi, to co my przed chwilą?! Pars er składa się z wejścia, wyjścia, stosu, programu sterującego dwuczęściowej tablicy: akcji i przejścia.

WEJŚCIE

Program sterujący jest identyczny dla wszystkich parserów, ale tablice zależą od gramatyk.

Parser czyta po jednym znaku z wejścia i zapamiętuje na stosie ciągi postaci:

So Xi Si X2 S2.... X_m S_m, gdzie Xj — symbole języka (symbol na wejściu) Sj (symbol wejściowy) symbolizuje stan, a S_m jest na szczycie stosu.