Symbolami rachunku zdań są zmienne (wszystkie zmienne są reprezentowane przez pojadynczy symbol), negacja, iloczyn, suma, implikacja i nawiasy. Negacja ma najwyższy priorytet, następnie iloczyn, potem suma. Implikacja ma najniższy priorytet. Iloczyn i suma są łaczne. Dla uniknięcia nieporozumień przyjmiemy że implikacja jest niełączliwa (tzn. wymaga jawnych nawiasów). Napisać gramatykę akceptującą poprawne składniowo zdania rachunku zdań (nie interesuje nas w tej chwili ich wartość logiczna).
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:
}
}
Dobrać parametry automatu, tzn. zbiór stanów, tabele 'przejscie'
i 'akcja' tak by automat analizował wyrażenia odpowiadające
poniższej gramatyce:
W0 : W EOF ;
W : T | W '+' T ;
T : 'x' | '(' W ')' ;
Gdzie 'x', '+', '(', ')' i EOF są symbolami końcowymi, zaś W0, W i T są
symbolami pomocniczymi, przy czym W0 jest symbolem początkowym.
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).
Uwaga2: Wiązenie `elsei' z najdalszą instukcją 'i' spowoduje że zagnieżdżone instrukcje 'i' nie będą dopuszczały częsci `elsei'.
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ą.
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, ...);