Przypominam że gramatyka G jest LR(k) (dla ustalonego k>=0) jeśli można zdecydować o (pierwszej) redukcji po przeczytaniu k symboli za prawą stroną reguły (zaczynamy czytanie od lewej od początku). Dokładniej, jeśli w i v są ciągami symboli pomocniczych i końcowych, u i s są ciągami symboli końcowych, A -> v jest jedną z reguł G, do w nie da się zastosować żadnej redukcji, z G można wyprowadzić wvu i wvs, pierwsze k symboli u i s są równe to reguła A -> v była użyta w ostatnim kroku wyprowadzenia prawostronnego wvs (innymi słowy, ciąg v w wvs pojawił się dzieki użyciu reguły A -> v).

Uwaga: dla k>0 aby uniknąć szczególnych przypadków należy na końcu słowa wyprowadzanego przez gramatykę dopisać k kopii dodatkowego symbolu (znacznika końca), różnego od symboli gramatyki.

Uwaga: defincja LR(k) powyżej jest to równoważna temu że automat LR(k) jednoznacznie wyznacza operacje (tzn. wybiera pomiędzy przesunięciem a redukcjami).

Przypominam że gramatyka G jest LL(1) jeśli analizator rekursywny może wybrać redukcję (tzn. ustalić która z prawych stron reguł była użyta) po przeczytaniu jednego symbolu za początkiem (ekpansji) prawej strony reguły.

Zadanie 1

Wyznaczyć automat LR(0) dla poniższej gramatyki:

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

Zadanie 2

Pokazać że gramatyka:

S:'x' '+' 'x' | 'x' * 'x' ;

nie jest LL(1) zaś jest LR(0).

Zadanie 3

Pokazać że gramatyka:

S: T '.' ;
T: /* puste */ | T X ',' | T Y ';';
X: 'x' | 'z' ;
Y: 'y' | 'z' ;

nie jest LR(0) zaś jest LR(1).

Zadanie 4

Pokazać że gramatyka:

S: A 'r' | B 'l' ;
A: /* puste */ | 'x' A ;
B: /* puste */ | B 'x' ;

nie jest LR(1) (ani nawet LR(k) dla żadnego k), choć jest jednoznaczna i można dla niej podać prosty algorytm analizy syntaktycznej.

Zadanie 5

Poniższa gramatyka nie jest LR(1):

S : A | B ;
A : C 'a' ;
B : D 'b' ;
C : /* puste */ | C 'x' | C 'y' ;
D : /* puste */ | D 'x' | D 'z' ;

Zmodyfikować tą gramatykę (zachowując nie zmieniony język) tak by była akceptowana przez `bison'-a. Podobnie, zrobić wersję która jest LL(1) oraz wersję LR(0). Chodzi przy tym o to żeby drzewa rozbioru były możliwie podobne (dlatego oddzielne wersje, wersja LL(1) (i LR(0)) jest akceptowana przez `bison'-a, ale wymaga wiekszych zmian).