E : T | E '+' T ;
T : F | T '*' F ;
F : '-' P | P ;
P : '(' E ')' | '1' | 'x' ;
Napisać program który wygeneruje losowe wyrażenie wyprowadzane
przez tą gramatykę.
Wskazówka: Dla każdego symbolu pomocniczego gramatyki definujemy
funkcję która wyprodukje odpowiedni losowy ciąg znaków. Ta
funkcja najpierw losuje produkcję, a następnie produkuje ciąg
dla danej produjkcji, posuwając się od lewej do prawej.
Dla symboli końcowych wystarczy wypisać odpowiedni znak.
Dla symbolli pomocniczych rekursywnie wywołujemy odpowiednią
funkcję. Program główny wywołuje funkcję odpowiadającą
symbolowi początkowemu.
Proszę napisać funkcję w C która odczyta ze standartowego wejscia ciąg znaków tworzący wyrażenie arytmetyczne lub instrukcję podstawienia i zbuduje odpowiadające mu drzewo rozbioru. Zakładamy że wyrażenie arytmetyczne używa tylko '+', '-' i '*' jako operatory i że każde podwyrażenie (w tym całe wyrażenie) zawierające operator jest ujęte w nawiasy. Ponadto '-' można tylko używać jako operator jednoargumentowy. Dopuszczamy tylko jednoliterowe nazwy zmiennych i jednocyfrowe stałe. Instrukcje podstawienia mają postać nazwy zmiennej po której występuje znak '=' po którym występuje wyrażenie arytmetyczne, np:
x=(y+4)lub
x=(y+(2*(y+(1))))Dla uproszczenia nie pozwalamy na spacje na wejściu, Wyrażenie lub instrukcja kończy się znakiem nowej linii. Jako węzly drzewa prosze używać następującą strukturę w C:
struct drzewo {
char nazwa;
struct drzewo * lewe;
struct drzewo * prawe;
};
Funkcja ma zaalokować węzły drzewa przy pomocy 'malloc'.