Zadanie 1

Zakładamy że symbolami gramatyki są pojedyńcze znaki. Uzupełnić poniższą gramatykę regułami tak by rozpoznawała zwykłe liczby całkowite w notacji dziesiętnej, liczby całkowite w notacji szesnastkowej, tak jak w C: `0x1ab' i liczby zmiennopozycyjne (te muszą zawierać kropkę dziesiętną, np: `.001', `100.' `3.1415').

liczba : liczba_zmiennopozycyjna
       | liczba_dziesietna
       | liczba_szesnastkowa
       ;

Zadanie 2

Symbolami rachunku zdań są zmienne (wszystkie zmienne są reprezentowane przez pojedynczy 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).

Zadanie 3

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:

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

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: Metoda analizy syntaktycznej za pomocą automatów jest szeroko stosowana. Detale automatów mogą się różnić, różnią się też sposoby budowy tabel (zwylke tabele są generowane mechanicznie). 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 4

Dla poniższej gramatyki wyznaczyć symbole wyprowadzające słowo puste. Symbolami końcowymi są ARRAY, CONST, ID, LICZBA, OF, TYPE i znaki pojawiające się w gramatyce.

deklaracje : stale typy ;

stale : stale ';' stala
      | /* puste */
      ;

stala : CONST ID '=' LICZBA ;

typy : typy typ
     | /* puste */
     ;

typ : TYPE ID '=' typ1 ;

typ1 : ID
     | array '[' LICZBA ']' OF typ1
     ;

Zadanie 5

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

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

Zadanie 6

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 */ ;

Zadanie 7

Zapisać w postaci diagramów syntaktycznych gramatykę zadaną przy pomocy poniższch reguł (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') * ';' ;
E : 'x' ( '+' E )* ;
C : E '=' E

Zadanie 8

Wyznaczyć zbiory `FIRST' i 'FOLLOW' dla gramatyki z zadania 7. Czy jest ona LL(1)?