Zadanie 1

Napisać gramatykę 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, ...);

Postarać się by gramatka spełniała warunki typu LL(1) czy SLR(1). Uwaga: ręczne sprawdzanie warunków typu LR jest dość pracochłonne więc tego nie wymagam. Ale proszę zrobić trochę wysiłku w tym kierunku, tzn. wyeliminować te konflikty które Państwo zobaczą.

Zadanie 2

Dla poniższej gramatyki wyznaczyć symbole które wyprowadzają słowo niepuste. Symbolami końcowymi są znaki występujące w gramatyce.


S : T | U | V | X | Y ;

T : T X T
  | /* puste */
  ;

U : U X 'u'
  | /* puste */
  ;

V : Y 'v' Y
  | X 'v'
  ;

X : X Y X
  | /* puste */
  ;

Y : Y 'y' ;

Zadanie 3

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

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

Zadanie 4

Pokazać że gramatyka:

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

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

Zadanie 5

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 6

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 7

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 instrukcję if\n");} SYM_IF warunek instr ;

daje skutek równoważny z

intstr_if : pom_if SYM_IF warunek instr ;

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

Takie przekształcenie gramatyki może wprowadzić do niej dodatkowe konflikty. Np. poniższa gramatyka, gdzie symbolem początkowym jest S zaś symbolami końcowymi są '1', 'x', '+', '-', '*', '(' i ')' jest akceptowana bez konfliktów przez 'bison'-a

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

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) (istotna jest tu jednoznaczność wyprowadzenia symboli pustych).