Zadanie 1

Wyznaczyć zbiory `FIRST' i 'FOLLOW' dla reguł poniższej gramatyki (symbolem początkowym jest `S').

S : S 'x' | /* puste */

Czy ta gramatyka jest LL(1). Dlaczego analizator rekursywny ma problem z tą gramatyką?

Zadanie 2

Wyznaczyć zbiory `FIRST' i 'FOLLOW' dla reguł poniższej gramatyki (symbolem początkowym jest `S').

S : T 'x' ;
T : A | B ;
A : 'a' | /* puste */ ;
B : 'b' | /* puste */ ;

Komentarz: Na wykładzie podalem nieco ogólniejszą niż zwykle się przyjmuje definicje gramantyki LL(1). Gramatyka powyżej spełnia warunki z wykładu, ale nie spełnia warunków tradycyjnej definicji LL(1), która wymaga by co najwyżej jedena z alternatywnych prawych stron wyprowadzała symbol pusty.

Zadanie 3

Wyznaczyć zbiory `FIRST' i 'FOLLOW' dla reguł poniższej gramatyki (symbolem początkowym jest `S').

S : I | B ;
B : 'b' I2 'e' ';' ;
I2 : /* puste */ | I2 I ';'
I : 't' X | 'v' X | 'x' '=' E ';'
  | 'i' C 'd' I2 'e'
  | 'i' C 'd' I2 'o' I2 'e'
  | 'w' C 'd' I2 'e' ;
X : 'x' ';' | 'x' ',' X ;
E : 'x' | 'x' '+' E ;
C : E '=' E

Komentarz: Dla skrócenia rachunków używam tylko jednoznakowych symboli końcowych, lecz można sobie wyobrażać że 'x' to dowolny identyfikator, 'b', 'd', 'e', 'i', 'o', 't', 'v' i 'w' to słowa kluczowe ("begin", "do", "end", "if", "otherwise", "type", "var" i "while" odpowiednio). Przerobienie tego na porządny język programowania pozostawiam Państwa wyobraźni...

Zadanie 4

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