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.

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 przeczycztaniu jednego symbolu za początkiem (ekpansji) prawej strony reguły.

Zadanie 1

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. Pokazać że gramatyka ta jest LR(0). Podać przykład gramatyki tego typu która nie jest LL(1). Opisać słownie jak można przeprowadzić analizę syntaktyczną dla takiej gramatyki.

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: 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.