Informatyka I rok
Laboratorium Metod Programowania
2000/2001

Zadanie z dnia: 26.03.01
Termin odbioru: 9.04.01

Zad. 2
=======

Należy napisać program Generuj. Jego zadaniem będzie generowanie
wszystkich słów dających się wyprowadzić z gramatyki bezkontekstowej
opisanej  we wskazanym przez użytkownika pliku (p. dalej) mających długość
wyprowadzenia nie większą niż zadana przez użytkownika. Generowane słowa 
mają być wpisywane po jednym w wierszu do pliku (o nazwie podanej przez 
użytkownika). Słowa mają być wypisywane w kolejności leksykograficznej 
(rosnącej). Każde słowo ma być wypisane tylko jeden raz (nawet jeśli jakieś
słowo ma kilka różnych wyprowadzeń o długości mieszczącej się w zadanym
limicie). Program powinien wypisać liczbę wygenerowanyc słów. Program musi 
także (jak zwykle) wypisać rozmiar zajętej pamięci na początku i końcu 
działania (oczywiście te liczby powinny być równe). Ponadto musi sygnalizować
błędy: 
 - wywołanie ze złą liczbą parametrów,
 - błędna postać pliku z danymi,
 - brak pliku z danymi bądż istnienie pliku z wynikami.
 W przypadku wykrycia błędu program powinien zakończyć swoje działanie (po 
 wypisaniu stosownego komunikatu).

Postać wywołania programu Generuj:
----------------------------------
   Generuj <plik z gramatyką> <plik z wynikami> <maksymalna długość wyprowadzenia>
        (np. Generuj  gram.txt  wyn.txt 8)

Format pliku z danymi:
----------------------
Opis gramatyki znajduje się w pliku tekstowym. Liczba wierszy tego pliku jest
równa liczbie nieterminali gramatyki. Pojedynczy wiersz zawiera wszystkie 
produkcje z jednego nieterminala i ma następującą postać:
  <wiersz> -> 
           <nieterminal> "->" <prawa strona produkcji> { "|" <prawa strona produkcji> }
  <prawa strona produkcji> -> 
           <symbol> <prawa strona produkcji> | epsilon
  <symbol> ->
           <terminal> | <nieterminal>
gdzie:
   <coś> oznacza nieterminal o nazwie coś
   "coś" oznacza terminal postaci coś
   -> i | mają standardowe znaczenie
   { coś } oznacza 0 lub  1 lub 2 lub ... wystąpień cosia
   epsilon oznacza słowo puste.
Pierwszy wiersz opisuje symbol startowy. W opisywanej gramatyce nie ma 
specjalnego symbolu dla pustego słowa (jest w gramatyce podanej powyżej),
bo nie jest potrzebny, zamiast niego używa się pustej prawej strony produkcji.


Przykładowa zawartość pliku z danymi:
-------------------------------------
  S->AB
  A->aA|
  B->|bB


Dodatkowe uwagi i założenia upraszczające:
------------------------------------------
   - terminale są pojedynczymi małymi literami, zaś nieterminale pojedynczymi 
      wielkimi literami, można wykorzystać to założenie przy projektowaniu
      struktur danych,
   - wiersze pliku z danymi nie mogą zawierać białych znaków (tzn. muszą 
      zawierać wyłącznie znaki opisujące gramatykę),
   - długość wyprowadzenia to liczba zastosowanych produkcji, 
      np. S->AB->aAB->aB->a to wyprowadzenie o długości 4,
   - ponieważ liczba generowanych słów może rosnąć wykładniczo względem
     maksymalnej długości wyprowadzeń, nie należy liczyć, że program zadziała
     dla dużych wartości trzeciego parametru (aczkolwiek program nie może 
     wprowadzać ograniczeń na wielkość tego parametru),
   - zanim zaczniesz pisać ten program zastanów się dobrze nad używanymi 
      strukturami danych (np. przy generowaniu list słów zapewne przydatne 
      będzie wyróżnianie w tych listach fragmentów zawierających słowa o tej
      samej długości wyprowadzenia).

Dodatkowe informacje o BP:
--------------------------
  - do zamiany napisu na liczbę służy procedura val.


Miejsce skąd można pobierać treści zadań zaliczeniowych:
--------------------------------------------------------
   www.mimuw.edu.pl/~janusz (i potem dość oczywiste dowiązania)