Zadanie 4 (termin oddania: 8 grudnia 2005, godz. 23:59)

Napisz program, ktory wczyta z wejscia gramatyke oraz tekst i
sprobuje skonstruowac i wypisac wyprowadzenie tego tekstu.

Bedziemy sie poslugiwali gramatykami, w ktorych dla kazdego
symbolu pomocniczego jest co najwyzej jedna produkcja pusta, a
wszystkie produkcje niepuste maja po prawej stronie po dwa
symbole - pierwszy to symbol koncowy a drugi pomocniczy.
Ponadto, dla kazdego symbolu pomocniczego prawe strony niepustych
produkcji rozpoczynaja sie od roznych symboli.

Wejscie:

Na wejsciu znajduja sie dwa wiersze, kazdy zakonczony kropka.

W pierwszym sa, rozdzielone przecinkami, grupy produkcji. Kazda
grupa rozpoczyna sie od symbolu pomocniczego, po nim jest strzalka
zlozona ze znakow '-' i '>' a dalej, rozdzielone znakami '|', prawe
strony produkcji dla tego symbolu pomocniczego. Symbol pomocniczy
znajdujacy sie po lewej stronie pierwszej produkcji jest symbolem
poczatkowym gramatyki. Symbole pomocnicze i koncowe sa jednoznakowe.

W drugim wierszu jest tekst.

Wyjscie:

Program wypisuje na wyjscie produkcje zastosowane do wyprowadzenia
tekstu. Konczy wraz z koncem wyprowadzenia lub wtedy, gdy kolejnej
produkcji wybrac nie mozna.

Np. dla danych:

A->|xB,B->yA.
xyxy.

program powinien wypisac:

A->xB
B->yA
A->xB
B->yA
A->

a dla:

A->xA|yB,B->.
xxxzz.

program powinien wypisac:

A->xA
A->xA
A->xA

Wskazowka:

Gramatyke o postaci opisanej w tresci zadania mozna reprezentowac
przy pomocy dwuwymiarowej tablicy znakow, ktorej wiersze odpowiadaja
symbolom pomocniczym a kolumny symbolom koncowym. Produkcje A->xB
zapiszemy, umieszczajac w wierszu 'A' i kolumnie 'x' znak 'B'.
Dodatkowo, dla kazdego symbolu pomocniczego A, w tablicy
jednowymiarowej mozemy zapisac wartosc logiczna mowiaca, czy dla A
jest produkcja pusta.