Zapoctovy test, 29.1.2009 [10:00]

[zapo]

Dnes bolo nasledujuce zadanie:

Na vstupe dostane program parametre: pociatocne slovo, max pocet slov, max hlbka vypoctu, subor s gramatikou
Ulohou je nacitat subor s pravidlami (bezkontextovej) gramatiky a pre pociatocne slovo previest vypocet a vysledne terminaly (vsetky moznosti, obmadzene maximami) vypisat na standardny vystup.

Pri vypocte sa postupuje zlava a pravidla su aplikovane v takom poradi, v akom boli v subore.

Priklad vstupneho suboru:

Kód: Vybrat vše

A -> aAb
A ->

Priklad vystupu pre danu gramatiku, pociatocne slovo "A", max pocet 500 a hlbka 6:

Kód: Vybrat vše

aaaaabbbbb
aaaabbbb
aaabbb
aabb
ab

[Ota]

Přesné zadání vypadalo takle :

Kód: Vybrat vše

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 -> aAb
		A -> 
    
	vstupni slovo: A
	m = 500
	n = 6

generuje slova

aaaaabbbbb
aaaabbbb
aaabbb
aabb
ab

a testovací vstup (gramatika) :

Kód: Vybrat vše

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ů ...

[Him]

Zkoušel jsem si to napsat a těch 90 řádků je tak akorát: http://martinvseticka.eu/index.php?sekc ... e&page=188
Při testování se zdálo, že to funguje, tak snad je to dobře