Zadanie 1

Wyznaczyć zbiory `FIRST' 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 2

Obowiązuje gramatyka z zadania 1. Przeanalizować metodą CYK poniższe zdania (tzn. zbudować tabelkę opisującą dla wszystkich odcinków zdania jakie symbole gramatyki mogą wyprowadzać dany odcinek):

zdanie1: 'i' 'x' '=' 'x' 'd' 'x' '=' 'x' ';' ';' 'e' ';'
zdanie2: 't' 'x' ';' 'x' '=' 'x' ';'

Zadanie 3

Obowiązuje gramatyka z zadania 1. Rekursywnie wypełniamy tabelkę metody CYK dla zdań z zadania 2. Zaczynamy od lewej i od symbolu startowego. Daną pozycję wypełniamy tylko wtedy gdy jest potrzebna. Dokładniej, na starcie chcemy sprawdzić czy (i jak!) symbol początkowy wyprowadza nasze zdanie. Aby sprawdzić czy jakiś symbol pomocniczy wyprowadza jakiś podciąg zaczynający się na bieżącej pozycji musimy sprawdzić prawe strony produkcji odpowiadjących temu symbolowi, przy tym pierwszy symbol produkcji sprawdzamy na bieżącej pozycji, zaś następny za nim. Porównać to z naiwnym algorytmem rekursywnym (sprawdzić że naiwna rekursja by się zapętliła, zaś my sprawdzamy daną pozycję co najwyżej raz). Porównać z tabelką z zadania 2 (które pozycje okazują się niepotrzebne)

Zadanie 4

W tym zadaniu gramatykę uzupełniamy trzema dodatkowymi sybolami: znacznikiem początku, znacznikiem końca tekstu i nowym sztucznym symbolem początkowym. Dodajemy też jedną sztuczną regułę. Mianowicie, nowy symbol początkowy wyprawadza ciąg: znacznik początku, stary symbol początkowy, znacznik końca.

Relacje poprzedzeniowe między symbolami gramatyki definujemy następująco:

Relacja `:=:' zachodzi między symbolami jeśli pojawiają się one obok siebie po prawej stronie jakiejś reguły.
Relacja '<' zachodzi między `A' i `B' jeśli prawa strona jakiejś reguły ma postać `wAuv' gdzie `u' jest ciągiem symboli wyprowadzającym `Bt' zaś `w', `v' i `t' są dowolnymi ciągami symboli.
Relacja '>' zachodzi między `A' i `B' jeśli prawa strona jakiejś reguły ma postać `wuBv' lub `wusv' gdzie `u' jest ciągiem symboli wyprowadzającym `rA', `s' jest ciągiem symboli wyprowadzającym `Bt' zaś `w', `v', `r' i `t' są dowolnymi ciągami symboli.

Innymi słowy relacja `:=:' zachodzi jeśli symbole `A' i `B' mogą pojawić się obok siebie tym samym kroku wyprowadzenia. Relacja '<' zachodzi jeśli symbole `A' i `B' mogą pojawić się obok siebie w wyporowadzeniu prawostronnym, i `A' pojawia się wcześniej (a więc `B' będzie pierwszym symbolem frazy'). Relacja '>' zachodzi między jeśli symbole `A' i `B' mogą pojawić się obok siebie i `A' jest ostatnim symbolem frazy.

Wyznaczyć relacje poprzedzeniowe dla gramatyki z zadania 1, dla gramatyki z zadania 1 z listy 2 i dla gramatyki z zadania 4 z listy 3.

Uwaga: jeśli między dwoma symbolami gramatyki zachodzi co najwyżej jedna relacja poprzedzeniowa to gramatykę nazywamy gramatyką poprzedzeniową. W takim przypadku relacje poprzedzeniowe są uogólnieniem priorytetów operatorów i mogą być użyte do sterowania analizatorem syntaktycznym podobnie jak w pierwszym przykładzie.