Laboratorium programowania zad 18

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

Leave a Reply