Zadanie 1

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

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

Zadanie 2

Automat z stosem ma taśmę wejściową na której w danym momencie widzi jeden znak i po której przesuwa się tylko do przodu. Ma też stos na którym zapamiętuje stany i symbole. W danym momencie automat może wykonać jedną z trzech rodzajów operacji, mianowicie przesuniecie, redukcję lub stop. Przesunięcie zapamiętuje bieżący stan i bieżący symbol na stosie i przesuwa się do przodu po taśmie wejsciowej. Redukcje są związane z regułami gramatyki: logicznie redukcja zastępuje prawą stronę reguły przez lewą, tzn. jesli prawa stron redukcji ma długość k to odczytuje się ze stosu k par symboli i stanów. Ostatni odczytany stan staje się bieżącym stanem. Następnie automat przechodzi do nowego stanu na zależnie od bieżącego stanu (przed chwilą odczytanego ze stosu) i symbolu z lewej strony produkcji. Jeśli operacją jest stop to automat zatrzymuje się albo akceptując albo zgłaszając błąd. Poniższy pseudo kod ilustruje dzialanie automatu:

stan = poczatkowy;
while (1) {
   znak = daj_znak();
   switch(akcja(stan, znak)) {
       case przesuniecie:
            push(stan, znak);
            stan = przejscie(stan, znak);
            znak = daj_znak();
            break;
       redukcja_1:
            for(i=0; i < dlugosc1; i++) {
                (stan, _) = pop();
            }
            push(stan, nonterminal1);
            stan = przejscie(stan, nonterminal1);
            break;
        redukcja_2:
            ...
        stop_błąd:
            ...
        stop_akceptuj:
            goto koniec;
    }
}
koniec:

Dla wyrażeń arytmetycznych tabelę przejść można zbudować w następujący sposób. Ciąg znaków (symboli) tworzących wyrażenie uzupełniamy dodatkowym symbolam znacznika końca. Stany kodują informację o tym czy ostatnio widziane podwyrażenie jest kompletne i o operatorze. Jeśli na wejściu jest zmienna a stan odpowiada niekompletnemu podwyrażeniu to w tabeli 'akcja' mamy przesunięcie, zaś stan zmienia się na kompletne podwyrażenie (z tym samym operatorem). Jeśli na wejściu jest operator zaś stan odpowiada kompletnemu podwyrażeniu to porównujemy priorytety operatorów, tego ze stanu i tego widzianego na wejściu. Jeśli operator ze stanu ma wyższy lub równy priorytet to wykonujemy redukcję (pobieramy trzy pozycje ze stosu), jeśli niższy to przesunięcie i przechodzimy do stanu odpowiadającego przesuniętemu operatorowi i niekompletnemu wyrażeniu. Jeśli na wejściu jest nawias otwierający, zaś stan odpowiada niekompletnemu podwyrażeniu to przesuwamy, a odpowiadający mu stan traktujemy jako niekompletny i mający niższy priorytet od prawdziwych operatorów. Jeśli na wejściu mamy nawias zamykający zaś stan odpowiada kompletnemu prawdziwemu operatorowi to wykonujemy redukcję (pobieramy trzy pozycje ze stosu). Jeśli zaś stan odpowada "kompletnemu" nawiasowi to wykonujemy przesunięcie i przechodzimy do specjalnego stanu w którym niezależnie od wejścia wykonujemy redukcję. Jeśli na wejściu jest znacznik końca zaś stan to "kompletny" stan początkowy to akceptujemy, jeśli inny "kompletny" stan to wykonujemy redukcję. Redukcje zwykle zachowują stan podniesiony ze stosu, ale jeśli podniesiony stan to stan początkowy (traktujemy go jako niekompletny) to zmieniamy go na kompletny. Podobnie redukcja w stanie po nawiasie zamykającym zmienia niekompletny stan podniesiony ze stosu na kompletny. Nieopisane pozycje tabel albo są niemożliwe albo oznaczają błąd składni w wejściowym wyrażeniu. Zgodnie z powyższym opisem jawnie wypisać tabele 'akcja' i 'przejscie' tak by analizować wyrażenia arytmetyczne z operatorami '+', '*' i nawiasami. Odpowiada to zmodyfikowanej gramatyce z zadania 1:

W0 : W EOF ;
W : T | W '+' T ;
T : P | T '*' P ;
P : 'x' | '(' W ')' ;

Gdzie 'x', '+', '*', '(', ')' i EOF są symbolami końcowymi, zaś W0, W, T i P są symbolami pomocniczymi, przy czym W0 jest symbolem początkowym.

Komentarz1: W powyższym automacie zapisywanie na stosie symboli może się wydawać zupełnie niepotrzebne. Ale łatwo zmodyfikować automant tak by produkował (być może spłaszczone) drzewo rozbioru i do tego symbole na stosie są niezbędne.

Komentarz2: Powyższy szkielet można stosować z tablami przejść otrzymanymi metodą LR.

Komatarz3: Dla wyrażeń metodę można trochę uprościć, bo nietrywialne zmiany stanu zależą tylko od operatorów i nawiasów a nie zależą od zmiennych.

Zadanie 3

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

Komentarz: W zadaniu 7 z listy 3 pokazaliśmy że ta gramatyka 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).