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

Napisz program, który wczyta z wejścia gramatykę oraz tekst i
spróbuje skonstruować i wypisać wyprowadzenie tego tekstu.

Będziemy się posługiwali gramatykami, w których dla każdego
symbolu pomocniczego jest co najwyżej jedna produkcja pusta, a
wszystkie produkcje niepuste mają po prawej stronie po dwa
symbole - pierwszy to symbol końcowy a drugi pomocniczy.
Ponadto, dla każdego symbolu pomocniczego prawe strony niepustych
produkcji rozpoczynają się od różnych symboli.

Wejście:

Na wejściu znajdują się dwa wiersze, każdy zakończony kropką.

W pierwszym są, rozdzielone przecinkami, grupy produkcji. Każda
grupa rozpoczyna się od symbolu pomocniczego, po nim jest strzałka
złożona ze znaków '-' i '>' a dalej, rozdzielone znakami '|', prawe
strony produkcji dla tego symbolu pomocniczego. Symbol pomocniczy
znajdujący się po lewej stronie pierwszej produkcji jest symbolem
początkowym gramatyki. Symbole pomocnicze i końcowe są jednoznakowe.

W drugim wierszu jest tekst.

Wyjście:

Program wypisuje na wyjście produkcje zastosowane do wyprowadzenia
tekstu. Kończy wraz z końcem wyprowadzenia lub wtedy, gdy kolejnej
produkcji wybrać nie można.

Np. dla danych:

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

program powinien wypisać:

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

a dla:

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

program powinien wypisać:

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

Wskazówka:

Gramatykę o postaci opisanej w treści zadania można reprezentować
przy pomocy dwuwymiarowej tablicy znaków, której wiersze odpowiadają
symbolom pomocniczym a kolumny symbolom końcowym. Produkcję A->xB
zapiszemy, umieszczając w wierszu 'A' i kolumnie 'x' znak 'B'.
Dodatkowo, dla każdego symbolu pomocniczego A, w tablicy
jednowymiarowej możemy zapisać wartość logiczną mówiącą, czy dla A
jest produkcja pusta.