Přesné zadání vypadalo takle :
Generovani mnoziny slov zadanych gramatikou
Spusteni:
generuj "pocatecni slovo" m n jmeno_souboru
m - maximalni pocet generovanych slov
n - maximalni pocet odvozeni
soubor - obsahuje bezkontextovou gramatiku
soubor vypada nasledovne:
Kazdy radek je prazdny a nebo obsahuje prepisovaci pravidlo ve tvaru "N -> text"
N je libovolne velke pismeno ( neterminal ) , retezec za sipkou se sklada z tisknutelnych znaku a mezery.
Terminalem je kazdy znak krome velkych pismen.
Gramatika generuje slovo S ze slova T, pokud slovo S vznikne ze slova T konecnym poctem aplikaci nejakeho pravidla.
Pravidlo P -> Q muzeme na slovo T pouzit pokud T obsahuje neterminal P. Slovo po aplikaci pravidla je steje, az na to, ze tam kde bylo P je Q
Pocatecni slovo na vstupu je tvoreno terminaly i neterminaly a slova na vystupu maji byt tvorena samymi terminaly.
Program ma generovat vsechna slova, nicmene jejich poradi je jednoznacne dano nasledujicimi pravidly.
- Jako prvni se vzdy prepisuje prvni neterminal ve slove ( vyrabime tzv. levou derivaci )
- Pokud ma neterminal vice pravidel, pouziva se nejdrive to, ktere bylo ve vstupnim souboru prvni.
Priklad:
gramatika:
A -> aAbA ->
vstupni slovo: Am = 500n = 6
generuje slova
aaaaabbbbb
aaaabbbb
aaabbb
aabb
ab
a testovací vstup (gramatika) :
V -> R P S T.
V -> V a V.
P -> pes
P -> kocka
P -> sud
P -> test
R -> cerveny
R -> tichy
R -> maly
R ->
S -> leta
S -> skace
S -> M I
S -> generuje
S -> pada
M -> muze
M -> umi
M -> smi
I -> letat
I -> skakat
I -> generovat
T -> test
T ->
A -> aAb
A -> X
X -> A
A -> stred
G -> D ; G
G ->
D -> Z -> Y
Z -> a
Z -> b
Z -> c
Z -> d
Z -> e
Z -> f
Z -> g
Z -> h
Y ->
Y -> YZ
Šlo o to, rekurzivně nahrazovat výskyty neterminálů (velkých písmen) jiným řetězcem podle gramatických pravidel.
Zadání bylo docela v pohodě, navíc jsme mohli předpokládat, že vstupní soubor i vstupy od uživatele budou napsané korektně. Takže stačilo načíst vstup a pak jedna rekurzivní funkce. Mel sem to na 90 řádků ...:-)
Matfyz Wiki