Zadanie 1

Podzbór wyrażeń języka C można zdefiniować następującą gramatyką gdzie symbolami końcowymi są znaki, i para znaków "+=" (jeśli znaki '+' i '=' występują bezpośrednio obok siebie to traktujemy je jako jeden symbol). Symbolem początkowym jest 'wyrazenie'. Spacje są pomijane, za wyjątkiem tego że używa się je do oddzielania symboli.

wyrazenie : warunkowe | zmienna "+=" warunkowe ;
warunkowe : addytywne | addytywne '?' addytywne ':' addytywne ;
addytywne : skladnik | addytywne '+' skladnik | addytywne '-' skladnik ;
skladnik : czynnik | skladnik '*' czynnik ;
czynnik : atom | '*' atom | '-' atom ;
atom : '(' wyrazenie ')' | zmienna
zmienna : 'w' | 'x' | 'y' | 'z' ;

Narysować drzewa rozbioru dla wyrażeń języka C: 'x * y - w - z', 'x * (y - w - z)', 'x * y - (w - z)', '*x * *y - w - z', 'x ? y : z + w', 'x * (y += z - w)'.

Zadanie 2

Do obliczenia wyrażenia 'x+y*(z + 2)' rekursywna metoda naszkicowana na wykładzie (najpierw obliczająca wyrażenie lewe) wymaga 4 komórek stosu. Jeśli będziemy najpierw obliczać wyrażenie prawe to wystarczą dwie komórki. Ile komórek potrzeba do obliczenia wyrażenia 'x*t+y*(z + 2)'?

Zadanie 3

W językach programowania występują struktury o stopniu rozgałęzienia większym niż dwa (w C instrukcje 'for' i 'while' czy wywołanie funkcji). Jak można reprezentować struktury o większym stopniu rozgałęzienia przy pomocy struktur o stopniu rozgałęzienia dwa (dlaczego stopień rozgałęzienia 1 to za mało). Zastanowić się jakie są wady a jakie zalety struktur o stopniu rozgałęzienia dwa w porównaniu do bezpośredniego użycia struktur o większym stopniu rozgałęzienia.