Zadanie 1

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:

Innymi słowy relacja ':=:' zachodzi jeśli symbole 'A' i 'B' mogą pojawić się obok siebie (z zachowaniem kolejności) w 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 (czyli 'B' jest pierwszym symbolem podstawy reducji, lub podtawa jest pusta i 'B' jest pierwszym symbolem za podstawą). Relacja '>' zachodzi między jeśli symbole 'A' i 'B' mogą pojawić się obok siebie i 'A' jest ostatnim symbolem podstawy redukcji.

Uwaga: Powyżej słowo wyprowadza oznacza wyprowadzenie które ma co najmniej jeden nietrywialny krok, tzn. mówiąc że 'u' wyprowadza 'Bt' nie uwzględzniamy sytuacji gdy 'u' to 'Bs', lecz żądany by pierwszy symbol 'u' został wyekspadowany.

Uwaga: Symbole relacji wyglądają jak symbole relacji przechodnich, ale te relacje nie muszą być przechodnie. Relacja ':=:' zwykle nie jest symetryczna zaś '<' i '>' raczej nie będą antysymetryczne.

Wyznaczyć relacje poprzedzeniowe dla następujących gramatyk: 

S : S S | 'x'
gdzie 'S' jest symbolem początkowym zaś 'x' jedynym symbolem końcowym, oraz dla 
S : I | S I ;
I : 'x' '=' E ';'
  | 'i' C 't' S 'e'
  | 'i' C 't' S 'o' S 'e'
  | 'w' C 'd' S 'e' ;
E : 'x' | E '+' 'x' ;
C : E '=' E
gdzie 'S' jest symbolem początkowym, zaś małe litery, '+', '=', ';' i ',' są symbolami końcowymi.

Wskazówka: Przy obliczaniu relacji '<' i '>' trzeba sprawdzać czy dany symbol może pojawić się na początku jakiegoś ciągu wyprowadzanego z danej frazy. Jest to podobne do obliczania zbiorów FIRST, tyle że trzeba też uwzględniać wszystkie symbole gramatyki a nie tylko końcowe.

Zadanie 2

Gramatykę nazywmy gramatyką poprzedzeniową jeśli dla dowolnych dwu symboli zachodzi co najwyżej jedna z relacji poprzedzeniowych (zdefinowanych w zadaniu 1) i prawe strony różnych reguł są różne. Dla gramatyk poprzedzeniowych można stosować następujący algorytm analizy syntaktycznej. Symbole umieszczamy na stosie tak długo jak pomiędzy nimi zachodzą relacje '<' lub ':=:'. Jeśli pomiędzu szczytem stosu a symbolem bieżącym zachodzi relacja '>' to wykonujemy redukcję. Dokładniej, cofamy się na stosie aż zobaczymy parę symboli w relacju '<'. Wtedzy ciąg symboli w relacji ':=:' jest podstawą redukcji. Ten ciąg zastępujemy odpowiednim symbolem pomocniczym który z powrotem umieszczamy na stosie. Teraz porównujemy szczyt stosu z bieżącym symbolem i postępujemy jak poprzednio. Jeśli zobaczymy parę sąsiednich symboli dla których nie zachodzi żadna z relacji poprzedzeniowych to sygnalizujemy błąd.

Uzasadnić że w gramatyce poprzedzeniowej żadna produkcja nie może wyprowadzać ciągu pustego. Pokazać że symbol otrzymany w wyniku redukcji nie może być w relacji '>' z wcześniejszym symbolem na stosie. Uzasadnić poprawność powyższego algorytmu. Pokazać że nie trzeba uwzględniać relacji '>' gdy drugi argument jest symbolem końcowym. Dlaczego gramatyka z zadania 1 sprawia kłopot dla tej metody. Jak można poprawić gramatykę i metodę by działały.

Zadanie 3

Gramatyką operatorową nazywamy gramatykę taką że żadna produkcja nie wyprowadza ciągu pustego i w prawej stronie dowonej reguły nie magą się pojawić dwa symbole pomocnicze po kolei. Dla takich gramatyk można zdefiniować relacje poprzedzeniowe dla symboli końcowych. Jeśli te relacje są jednoznaczne to gramatykę nazywamy operatorową gramatyką poprzedzeniową i można dla niej użyć modyfikację metody z zadania 2. Zmodyfikować gramatykę z zadania 1 tak stała się operatorową gramatyką poprzedzenopwą.

Zadanie 4

Językiem generowanym przez frazę z gramtyki nazywamy zbiór wszystkich ciągów symboli końcowych które daje się wyprowadzić z tej frazy. Pokazać że gramatyka nie zawierająca zbędnych reguł jest jednoznaczna wtedy i tylko wtedy gdy spełnia następujące warunki: Komentarz: te warunki prowadzą do stosunkowo skutecznej metody sprawdzania jednoznaczności gramatyk. Oczywiście spradzanie powyższych warunków jest problemem nierozstrzygalnym, ale daje się w miarę dobrze przybliżać zagadnieniami rozstrzygalnymi.