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; } }