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

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

Program `bison' pozwala wiązać akcje z regułami gramatyki. Normalne akcje umieszcza się na końcu reguły. Jednak `bison' pozwala umieścić akcję w dowolnym miejscu (nawet na początku reguły). Realizuje to przez wstawianie dodatkowych symboli pomocniczych które wyprowadzają tylko ciąg pusty. Np.

intstr_if : { printf("Analizujemy instrukcję if\n");} SYM_IF warunek instr ;

daje skutek równoważny z

intstr_if : pom_if SYM_IF warunek instr ;

pom_if : { printf("Analizujemy  instrukcję if\n");} ;

Takie przekształcenie gramatyki może wprowadzić do niej dodatkowe konflikty. Sprawdzić że gramatyka z zadania 1 listy 2 jest akceptowana przez `bison'-a zaś po dodaniu akcji na początku prawej strony każdej reguły (jeśli reguła ma kilka alternatyw to na początku każdej alternatywy) `bison' zgłasza informacje o konfliktach (błędach).

Uzasadnić że aby uniknąć konfliktów po dodaniu akcji na początku każdej reguły gramatyka powinna być LL(1).

Zadanie 6

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