Zadanie z laboratorium programowania na Informatyce UW.
Zadanie 18 (termin wysylania rozwiazan: 23 czerwca, godz. 23:59) (Gramatyka) 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 jednoliterowe. 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->. xxx. program powinien wypisac: A->xA A->xA A->xA Wskazowka: Gramatyke o postaci opisanej w tresci zadania mozna reprezentowac przy pomocy dwuwymiarowej tablicy, 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.
A oto rozwiązanie:
#include
#include
#include
//Struktura dla produkcji
typedef struct produkcja_el{
char terminal;
char nieterminal;
struct produkcja_el * nastepny;
};
//Struktura dla nieterminali.
struct nieterminal_el {
char nieterminal;
struct produkcja_el * produkcje;
struct nieterminal_el* nastepny;
};
struct nieterminal_el* start_nieterminal;
//dodaje produkcje do struktury.
void dodaj_produkcje(char prod_in,char prod_terminal,char prod_out)
{
struct nieterminal_el* teraz_nieterminal;
struct produkcja_el* tmp_produkcja;
if(start_nieterminal==NULL)
{
//pierwszy nieterminal.
teraz_nieterminal=malloc(sizeof(struct nieterminal_el));
teraz_nieterminal->nastepny=NULL;
teraz_nieterminal->nieterminal=prod_in;
teraz_nieterminal->produkcje=NULL;
start_nieterminal=teraz_nieterminal;
}
else
{
teraz_nieterminal=start_nieterminal;
}
//szukamy odpowiedniego nieterminala.
while((teraz_nieterminal->nastepny!=NULL)&&(teraz_nieterminal->nieterminal!=prod_in))
{
teraz_nieterminal=teraz_nieterminal->nastepny;
}
if((teraz_nieterminal->nastepny==NULL)&&(teraz_nieterminal->nieterminal!=prod_in))
{
//nie znalezlismy, trzeba dodac.
teraz_nieterminal->nastepny=malloc(sizeof(struct nieterminal_el));
teraz_nieterminal=teraz_nieterminal->nastepny;
teraz_nieterminal->nastepny=NULL;
teraz_nieterminal->nieterminal=prod_in;
teraz_nieterminal->produkcje=NULL;
//dodany.
}
//Teraz jestesmy na odpowiednim nieterminalu,
//i dodajemy produkcje.
tmp_produkcja=teraz_nieterminal->produkcje;
teraz_nieterminal->produkcje=malloc(sizeof(struct produkcja_el));
teraz_nieterminal->produkcje->nastepny=tmp_produkcja;
teraz_nieterminal->produkcje->terminal=prod_terminal;
teraz_nieterminal->produkcje->nieterminal=prod_out;
//powinna byc dodana.
}
//funkcja znajdujaca produkcje i wypisujaca.
char znajdz_produkcje(char prod_in,char znak)
{
struct nieterminal_el* teraz_nieterminal;
struct produkcja_el* teraz_produkcja;
teraz_nieterminal=start_nieterminal;
//szukamy odpowiedniego nieterminala.
while((teraz_nieterminal->nastepny!=NULL)&&(teraz_nieterminal->nieterminal!=prod_in))
{
teraz_nieterminal=teraz_nieterminal->nastepny;
}
if(teraz_nieterminal->nieterminal==prod_in)
{
//jest.
teraz_produkcja=teraz_nieterminal->produkcje;
//szukamy odpowiedniej produkcji
while((teraz_produkcja->nastepny!=NULL)&&(teraz_produkcja->terminal!=znak))
{
teraz_produkcja=teraz_produkcja->nastepny;
}
if(teraz_produkcja->terminal==znak)
{
//Jest odpowiednia produkcja!!
//Wypisujemy.
//zeby przypadkiem kropki nie wypisac.
if(znak=='.')
{
printf("%c->n",prod_in);
}
else
{
printf("%c->%c%cn",prod_in,znak,teraz_produkcja->nieterminal);
}
return teraz_produkcja->nieterminal;
}
}
else
{
return '.';
}
}
int main (int argc, char *argv[])
{
//Inicjujemy
int wynik;
char znak,prod_in,prod_out,nieterminal,prod_terminal;
struct nieterminal_el* teraz_nieterminal;
struct produkcja_el* teraz_produkcja;
struct nieterminal_el* tmp_nieterminal;
struct produkcja_el* tmp_produkcja;
prod_in='.';
prod_out='.';
nieterminal='.';
prod_terminal='.';
start_nieterminal=NULL;
wynik=scanf("%c",&znak);
//Czytamy.
while((znak!='r')&&(znak!='.')&&(znak!='n')&&(wynik!=EOF))
{
if((znak>='A')&&(znak')
{
wynik=scanf("%c",&znak);
//printf("Wczytalem '%c'n",znak);
while((znak!=',')&&(znak!='.')&&(wynik!=EOF))
{
if(znak=='|')
{
//printf("Dodaje produkcje %c->%c%cn",prod_in,prod_terminal,prod_out);
dodaj_produkcje(prod_in,prod_terminal,prod_out);
prod_terminal='.'; //kropka jako oznaczenie produkcji pustej,
prod_out='.';
}
else if((znak>='a')&&(znak='A')&&(znak%c%cn",prod_in,prod_terminal,prod_out);
prod_terminal='.'; //kropka jako oznaczenie produkcji pustej,
prod_out='.';
wynik=scanf("%c",&znak);
//printf("Wczytalem '%c'n",znak);
}
else
{
//blad - brak >
return 3;
}
}
else
{
//blad brak -
return 2;
}
}
else
{
//blad zly zakres znakow duzych
return 1;
}
}
//Powinno byc wczytane.
//jesli byly jakies produkcje.
if(start_nieterminal!=NULL)
{
//przechodzimy dalej.,
while(((znak'z'))&&(wynik!=EOF))
{
wynik=scanf("%c",&znak);
}
prod_in='A';
while((((znak>='a')&&(znaknieterminal);
teraz_produkcja=teraz_nieterminal->produkcje;
while(teraz_produkcja!=NULL)
{
//printf("%c->%c%cn",teraz_nieterminal->nieterminal,teraz_produkcja->terminal,teraz_produkcja->nieterminal);
tmp_produkcja=teraz_produkcja;
teraz_produkcja=teraz_produkcja->nastepny;
free(tmp_produkcja);
}
tmp_nieterminal=teraz_nieterminal;
teraz_nieterminal=teraz_nieterminal->nastepny;
free(tmp_nieterminal);
}
return 0;
}
else
{
//nie bylo produkcji,
return 5;
}
}