Matfyz Wiki
Ukol
Najdete spolecneho predka zinstanciovanych typu.
Zadani
Na zacatku obdrzi vas program jako argument soubor s definicemi typu. Takova definice vypada napriklad takto:
T1 x y => T0 x y y
Kde T1 a T0 jsou nazvy typu, x a y jsou formalni nazvy parametru. Predchozi zapis rika, ze definujeme typ T1 (odvozeny z T0) s parametry x a y. Parametr x se mapuje na prvni parametr typu T0. Parametr y se mapuje na druhy i treti parametr typu T0.
Zakladnim typem (nema zadny parametr) je typ S. Kazdy jiny typ je jeho vzdalenym potomkem.
Je pouze jednoducha dedicnost.
Soubor s definicemi muze vypadat napriklad takto.
T1 a => S T2 x y => T1 y T3 a b c => T1 b T4 u v w => T2 w u T5 x => T2 x x
Predchozi definice typu je korektni, nebot
Typy maji tvar [A-Z][a-zA-Z0-9_]
Parametry maj tvar [a-z][a-zA-Z0-9_]
Kazdy typ je odvozen z jiz definovaneho typu (typ S je pred definovany)
Odvozeny typ namapoval sve formalni parametry na vsechny formalni parametry predka.
Pozorovani: Neni mozne vytvorit typ, ktery nema parametry, jako potomka typu s parametry. Nemelo by se co mapovat na predkovy parametry.
Stromovy zapis predchoziho soubor definic je:
S
|
T1
/ \
T2 T3
/ \
T4 T5
Pote program bude cist standradni vstup. Na nej budou chodit dvojice typu (kazda na jednom radku) s dosazenymi parametry. Po te nasleduje prazdna radka a pak dalsi dotaz nebo EOF.
Korekti uzivatelsky vstup muze vypadat asledovne:
T1 z T5 q T5 f T4 f m f
Na to by mel program odpovedet
S T2 f f
Tedy pote co je typum predan seznam skutecnych parametru, tyto parametry probublaji jejich predky. Tak dostaneme zinstanciovany typ.
Napriklad T5 f ma svoji vyvozovaci vetev:
S -> T1 f -> T2 f f -> T5 f
Pro T4 f m f
S -> T1 f -> T2 f f -> T4 f m f
Takze jejich spolecny predchudce je T2 f m f (musi se shodovat jak nazev typu tak skutecne (dosazene) parametry).
Cas byl 3:20, protoze pak byla pisemka odpoledni skupiny.
Me se to povedlo, prede mnou jeste 2 lidem. Pak uz ale byl brzo konec, takze myslim, ze o mnoho vic nas nebylo :? .
Hodne stesti!!!