Zadanie 1

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("Analizyjemy intstrukcję if\n");} SYM_IF warunek instr ;
daje skutek równoważny z 
intstr_if : pom_if SYM_IF warunek instr ;

pom_if : { printf("Analizyjemy  intstrukcję if f\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 2

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

Zadanie 3

Poniższa gramatyka opisuje strukturę instrukcji warunkowych w wielu językach programowania ('i' jest skrótem dla `if', 'e' jest skrótem dla `else', 'x' oznacza inne instrukcje, 'w' oznacza warunek (wyrażenie logiczne). 
instr : 'i' war instr elsei | 'x' ;
elsei : /* puste */ | 'e' instr ;
war : 'w' ;
`bison' dla tej gramatyki zgłasza jeden konflikt przesunięcie/redukcja. Domyślny mechanizm rozstrzygania konfliktów `bison'-a wiąże część `elsei' z najbliższą instrukcją 'i'. Dobrać deklaracje priorytetu tak by `bison' związał część `elsei' z najdalszą instukcją 'i'.

Uwaga: Polecenie `info bison' pozwala przeglądać instrukcję `bison'-a. Jeśli w części `Grammar File' punkt `Declarations' wybierzemy podpunkt `Precedence Decl' to dostaniemy podsumowanie informacji o deklaracjach priorytetu (warto też odwiedzić podpunkt `Operator Precedence' w części o algorytmie `bison'-a).

Zadanie 4

Zmodyfikować gramatykę z Zadania 3 (nie używając deklaracji priorytetu), tak była LR(1), a właściwie, żeby `bison' nie zgłaszał konfliktów (a język pozostał nie zmieniony). Zrobić dwie wersje, jedną która wiąże część `elsei' z najbliższą instrukcją 'i', drugą która wiąże z najdalszą.

Zadanie 5

Napisać gramatykę (akceptowaną przez `bison'-a) która rozpoznaje typowe nagłówki funkcji w C. Dla uproszczenia można się ograniczyć tylko do typów nazwanych przez identyfikator (wbudowane lub zadeklarowane gdzie indziej przez `typedef'). Przy takim ograniczeniu symbolami są: identyfikatory, '(', ')' , ',', ';' i '...'. Przykładowe nagłówki: 

int fun1(int, int);
typek fun2(typek x, int y);
int fun3();
int fun4(int, ...);