Zadanie 1

Mamy następującą gramatykę:

S : S S | 'x'

Jak wygląda język generowany przez tą gramatykę. Pokazać że gramatyka ta nie jest jednoznaczna zaś ilość drzew rozbioru rośnie wykładniczo z długością słowa (dokładnie jest to liczba Catalana: ((2*n-2)!)/(((n-1)!*(n-1)!)*n) ).

Zadanie 2

Wyznaczyć zbiory `FIRST' dla reguł poniższej gramatyki (symbolem początkowym jest `S').

S : I | B ;
B : 'b' I2 'e' ';' ;
I2 : /* puste */ | I2 I ';'
I : 't' X | 'v' X | 'x' '=' E ';'
  | 'i' C 'd' I2 'e'
  | 'i' C 'd' I2 'o' I2 'e'
  | 'w' C 'd' I2 'e' ;
X : 'x' ';' | 'x' ',' X ;
E : 'x' | 'x' '+' E ;
C : E '=' E

Komentarz: Dla skrócenia rachunków używam tylko jednoznakowych symboli końcowych, lecz można sobie wyobrażać że 'x' to dowolny identyfikator, 'b', 'd', 'e', 'i', 'o', 't', 'v' i 'w' to słowa kluczowe ("begin", "do", "end", "if", "otherwise", "type", "var" i "while" odpowiednio). Przerobienie tego na porządny język programowania pozostawiam Państwa wyobraźni...

Zadanie 3

Zakładamy że każda prawa strona reguły gramatyki zaczyna się od nawiasu otwierającego a kończy się nawiasem zamykającym. Nawiasy nie występują w środku reguły. Ponadto zakładamy że dla różnych symboli pomocniczych prawe strony reguł są różne. Opisać słownie jak można przeprowadzić analizę syntaktyczną dla takiej gramatyki.

Zadanie 4

W tym zadaniu gramatykę uzupełniamy trzema dodatkowymi sybolami: znacznikiem początku, znacznikiem końca tekstu i nowym sztucznym symbolem początkowym. Dodajemy też jedną sztuczną regułę. Mianowicie, nowy symbol początkowy wyprawadza ciąg: znacznik początku, stary symbol początkowy, znacznik końca.

Relacje poprzedzeniowe między symbolami gramatyki definujemy następująco:

Relacja `:=:' zachodzi między symbolami jeśli pojawiają się one obok siebie po prawej stronie jakiejś reguły.
Relacja '<' zachodzi między `A' i `B' jeśli prawa strona jakiejś reguły ma postać `wAuv' gdzie `u' jest ciągiem symboli wyprowadzającym `Bt' zaś `w', `v' i `t' są dowolnymi ciągami symboli.
Relacja '>' zachodzi między `A' i `B' jeśli prawa strona jakiejś reguły ma postać `wuBv' lub `wusv' gdzie `u' jest ciągiem symboli wyprowadzającym `rA', `s' jest ciągiem symboli wyprowadzającym `Bt' zaś `w', `v', `r' i `t' są dowolnymi ciągami symboli.

Innymi słowy relacja `:=:' zachodzi jeśli symbole `A' i `B' mogą pojawić się obok siebie tym samym kroku wyprowadzenia. Relacja '<' zachodzi jeśli symbole `A' i `B' mogą pojawić się obok siebie w wyporowadzeniu prawostronnym, i `A' pojawia się wcześniej (a więc `B' będzie pierwszym symbolem frazy'). Relacja '>' zachodzi między jeśli symbole `A' i `B' mogą pojawić się obok siebie i `A' jest ostatnim symbolem frazy.

Wyznaczyć relacje poprzedzeniowe dla gramatyki z zadania 1 i dla gramatyki z zadania 2.

Uwaga: jeśli między dwoma symbolami gramatyki zachodzi co najwyżej jedna relacja poprzedzeniowa to gramatykę nazywamy gramatyką poprzedzeniową. W takim przypadku relacje poprzedzeniowe są uogólnieniem priorytetów operatorów i mogą być użyte do sterowania analizatorem syntaktycznym podobnie jak w pierwszym przykładzie.