W zadaniach poniżej stosujemy dla gramatyk notację używaną w programie 'bison': znaki w apostrofach (np. '+' ) oznaczają (jednoznakowe) symbole końcowe. Z lewej umieszczamy nazwę symbolu końcowego, zaś po dwukropku prawą stronę reguły. Jeśli danemu symbolowi odpowiada kilka reguł, to prawe strony oddzielamy znakiem '|'. Zestaw reguł dla danego symbolu kończymy średnikiem.

Zadanie 1

Mamy następującą gramatykę dla wyrażeń arytmetycznych (z symbolem początkowym E, symbolami końcowymi są '1', 'x', '+', -', '*', '(' i ')').

E : T | E '+' T ;
T : F | T '*' F ;
F : '-' P | P ;
P : '(' E ')' | '1' | 'x' ;

Znaleźć wyprowadzenie i narysować drzewa rozbioru dla następujących wyrażeń:

-x
x+-x
x+-(x)
x*x+-(x+1)

Zadanie 2

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 3

Wyznaczyć język generowany przez poniższą gramatykę (z symolu początkowego S, jedynym symbolem końcowym jest 'x'):

S : A T | T ;
T : B U | U ;
U : C V | V ;
V : D W | W ;
W : E X | X ;
X : /* puste */ |  'x' ;
E : 'x' 'x' ;
D : E E ;
C : D D ;
B : C C ;
A : B B ;