Prˇ´ıloha 1. Uzˇivatelska´ prˇ´ırucˇka k programu Simula´tor programovane´ gramatiky Program slouzˇ´ı k simulaci derivace podle programovane´ gramatiky s bezkontextovy´mi pravidly. Umozˇnˇuje automaticky´ pru˚beˇh derivace, pokud je pokracˇovanı´ jednoznacˇne´. Prˇi nedeterministicke´m pokracˇova´nı´ mu˚zˇe pravidlo vybrat uzˇivatel nebo na´hodneˇ simula´tor. Pravidla aplikovatelna´ v kazˇde´m kroku mohou by´t volena na za´kladeˇ leftmost omezenı´. Da´le je mozˇne´ urcˇit, ktery´ vy´skyt leve´ strany v aktua´lnı´ veˇtne´ formeˇ ma´ by´t prˇepsa´n.
1.1
Instalace a spusˇteˇnı´
Program je psa´n v programovacı´m jazyce JAVA. Pro spusˇteˇnı´ proto potrˇebuje interpret nazvany´ JVM (Java Virtual Machine). JVM je mozˇne´ sta´hnout na internetove´ adrese www.sun.com jako soucˇa´st distribucı´ JRE (Java Runtime Environment) nebo JDK (Java Development Kit). JRE slouzˇ´ı pouze ke spousˇteˇnı´ aplikacı´, JDK poskytuje navı´c tvu˚rcu˚m prostrˇedky pro vy´voj. Pro spusˇteˇnı´ Simula´toru programovane´ gramatiky je potrˇeba JRE ve verzi 1.2 nebo vysˇsˇ´ı. Operacˇnı´ syste´m mu˚zˇe by´t libovolny´, pro ktery´ existuje JRE. Program vyzˇaduje existenci graficke´ho prostrˇedı´ (naprˇ. v linuxovy´ch syste´mech je nutne´ spustit XWindow, v operacˇnı´ch syste´mech firmy Microsoft Windows od verze 95 je graficke´ prostrˇedı´ automaticky). Aplikaci Simula´tor programovane´ gramatiky tvorˇ´ı adresa´rˇ simulator. Pro beˇh aplikace stacˇ´ı jeden soubor GrammarSimulator.jar. Spusˇteˇnı´ programu se prova´dı´ v adresa´rˇi simulator prˇ´ıkazem java -classpath GrammarSimulator.jar gui.GrammarSimulator Pro zjednodusˇenı´ jsou ve stejne´m adresa´rˇi prˇilozˇeny jesˇteˇ soubory run.bat a run, ve ktery´ch je tento prˇ´ıkaz vypsa´n. Spusˇteˇnı´ jednoho z nich prˇ´ıkaz vykona´ a tı´m spustı´ i simula´tor. Soubory se lisˇ´ı znakem pouzˇity´m pro konec rˇa´dku. run je urcˇen pro unixove´ syste´my a run.bat pro syste´my Windows firmy Microsoft. Dalsˇ´ı mozˇnostı´ je otevrˇenı´ HTML stra´nky GrammarSimulator.htm v prohlı´zˇecˇi podporujı´cı´m applety jazyka JAVA. Program se automaticky spustı´ jako applet, ale z bezpecˇnostnı´ch du˚vodu˚ kladeny´ch na applety nebude podporovat pra´ci se soubory.
1.2
Omezenı´ kladena´ na prvky gramatiky
Gramatika mu˚zˇe obsahovat libovolny´ pocˇet pravidel. Omezena´ nenı´ ani de´lka prave´ strany pravidla, pocˇet prvku˚ v poli u´speˇchu i neu´speˇchu. Kazˇde´ pravidlo musı´ mı´t prˇirˇazeno jednoznacˇne´ oznacˇenı´, ktere´ jej zastupuje v polı´ch u´speˇchu a neu´speˇchu. Protozˇe je simula´tor omezen na 1
bezkontextova´ pravidla, tvorˇ´ı leve´ strany vsˇech pravidel pra´veˇ jeden netermina´l. U pravidel se nekontroluje, jestli je neˇjaky´ prvek v poli u´speˇchu nebo neu´speˇchu. Pokud se aplikuje pravidlo, ktere´ ma´ prˇ´ıslusˇne´ pole pra´zdne´, derivace se zablokuje. Mu˚zˇe jı´t ale i o u´speˇsˇny´ konec derivace, kdy je vygenerova´no termina´lnı´ slovo. Take´ se nekontroluje, jestli existuje pravidlo s pocˇa´tecˇnı´m netermina´lem na leve´ straneˇ. Bez takove´ho pravidla ale derivace ani nezacˇne. V prvnı´m kroku derivace jsou jako pouzˇitelna´ uzna´na i vsˇechna pravidla aplikovatelna´ v mo´du testova´nı´ vy´skytu. Definici programovane´ gramatiky jejich uzˇitı´ totizˇ neodporuje. Oddeˇlovacˇe – Znaky, ktere´ oddeˇlujı´ symboly na prave´ straneˇ pravidla a jednotliva´ oznacˇenı´ v polı´ch u´speˇchu a neu´speˇchu. Jedna´ se o mezeru, tabela´tor, konec rˇa´dku, cˇa´rku, strˇednı´k, dvojtecˇku, pomlcˇku, vsˇechny druhy za´vorek, znak veˇtsˇ´ı a mensˇ´ı. Oznacˇenı´ pravidla – Libovolny´ rˇeteˇzec znaku˚ bez oddeˇlovacˇu˚. Termina´l – Rˇeteˇzec znaku˚ zacˇ´ınajı´cı´ maly´m pı´smenem. Nesmı´ obsahovat oddeˇlovacˇe. Netermina´l – Rˇeteˇzec znaku˚ zacˇ´ınajı´cı´ velky´m pı´smenem. Nesmı´ obsahovat oddeˇlovacˇe. Pra´zdne´ slovo – Symbol λ, ktery´ se pro oznacˇenı´ pra´zdne´ho slova pouzˇ´ıva´, nenı´ mozˇne´ z kla´vesnice zadat. V programu ma´ stejny´ vy´znam termina´l la.
1.3
Ovla´da´nı´ programu
1.3.1 Okno derivace Po spusˇteˇnı´ programu se otevrˇe okno derivace, ktere´ je na obra´zku 1.1. Aby mohla derivace zacˇ´ıt, je nutne´ nejprve zadat gramatiku. Provede se to po stisku tlacˇ´ıtka Nova gramatika nebo volbou Nova v menu Gramatika. V noveˇ otevrˇene´m okneˇ se mohou zada´vat jednotliva´ pravidla. Konkre´tnı´ popis ovla´da´nı´ prˇi editaci gramatiky bude popsa´n v cˇa´sti 1.3.2 te´to prˇ´ırucˇky. Gramatiku mu˚zˇeme nacˇ´ıst ze souboru. Po zvolenı´ polozˇky Nacist v menu Gramatika se otevrˇe standardnı´ okno pro vy´beˇr souboru. Po oznacˇenı´ souboru a stisku tlacˇ´ıtka Open se gramatika ze souboru nacˇte a zobrazı´ v editacˇnı´m okneˇ gramatiky. Pokud je vy´beˇr souboru prˇerusˇen stiskem Cancel, je v editacˇnı´m okneˇ mozˇne´ zada´vat novou gramatiku z kla´vesnice. Po nacˇtenı´ gramatiky mu˚zˇe zacˇ´ıt derivace. V rˇa´dku nadepsane´m Vetna forma je vzˇdy zobrazena´ aktua´lnı´ veˇtna´ forma. V seznamu oznacˇene´m Pouzit pravidlo jsou aplikovatelna´ pravidla. Kazˇde´ pravidlo v seznamu je popsa´no oznacˇenı´m, samotny´m bezkontextovy´m pravidlem, polem u´speˇchu (oznacˇenı´ pravidel patrˇ´ıcı´ch do neˇj) a polem neu´speˇchu (opeˇt oznacˇenı´ pravidel). Pokud by sˇlo o aplikaci v mo´du testova´nı´ vy´skytu, je prˇed oznacˇenı´m pravidla jesˇteˇ rˇeteˇzec ac:. Po vy´beˇru pravidla se stiskem Aplikuj nebo volbou Aplikuj pravidlo v menu Derivace provede prˇepis jednoho vy´skytu leve´ strany ve veˇtne´ formeˇ. Vy´beˇr vy´skytu je da´n hodnotou v textove´m poli oznacˇene´m Vyskyt. Je-li v tomto poli 1, jde o nejleveˇjsˇ´ı vy´skyt leve´ strany a kazˇde´ veˇtsˇ´ı cˇ´ıslo znamena´ vy´skyt vı´ce vpravo. Pokud je pozˇadova´n vy´skyt, ktery´ neexistuje, zobrazı´ se okno s chybovou hla´sˇkou. Krok derivace potom nenı´ proveden. Kdyzˇ je vygenerova´no termina´lnı´
2
Obra´zek 1.1: Okno derivace
slovo nebo nenı´ pouzˇitelne´ zˇa´dne´ pravidlo, derivace koncˇ´ı. Tlacˇ´ıtko Aplikuj je v takove´m prˇ´ıpadeˇ neaktivnı´. Pokud je zatrzˇena´ mozˇnost automaticke´ derivace v zasˇkrta´vacı´m tlacˇ´ıtku oznacˇene´m Automaticky, probı´ha´ derivace bez za´sahu uzˇivatele, dokud je jednoznacˇne´ pokracˇova´nı´. Mezi kroky se cˇeka´ tolik milisekund, kolik je urcˇeno v textove´m poli oznacˇene´m Zpozdeni. Automaticky´ pru˚beˇh je mozˇne´ prˇerusˇit tlacˇ´ıtkem Stop. K prˇerusˇenı´ take´ dojde, pokud je vygenerova´no termina´lnı´ slovo, je vı´ce aplikovatelny´ch pravidel nebo nenı´ zˇa´dne´ aplikovatelne´ pravidlo. Je-li aplikovatelny´ch pravidel vı´ce, vybere uzˇivatel jedno z nich a po stisku Aplikuj bude automaticka´ derivace pokracˇovat. Prˇi automaticke´m pru˚beˇhu je vzˇdy pravidlo uzˇito na nejleveˇjsˇ´ı vy´skyt leve´ strany (prˇi zasˇkrtnutı´ Automaticky se v poli Vyskyt nastavı´ 1 a nepu˚jde zmeˇnit). Prˇi zvolene´ automaticke´ derivaci je mozˇne´ zasˇkrtnout volbu Nahodne. Pokud je potom vı´ce pouzˇitelny´ch pravidel, vybere se jedno z nich na´hodneˇ a automaticky´ pru˚beˇh se neprˇerusˇ´ı. Volba Leftmost ma´ vliv na urcˇova´nı´ aplikovatelny´ch pravidel. Jako pouzˇitelne´ je urcˇeno to pravidlo, jehozˇ leva´ strana se vyskytuje ve veˇtne´ formeˇ nejvı´ce vlevo. Jen pokud ma´ vı´ce pravidel stejnou levou stranu, je jich aplikovatelny´ch vı´ce. Samozrˇejmeˇ musı´ vsˇechna aplikovatelna´ pravidla patrˇit do pole u´speˇchu nebo neu´speˇchu pravidla pouzˇite´ho v minule´m kroku derivace, 3
jak je to u programovany´ch gramatik definova´no. Kazˇdy´ krok derivace je zobrazen jako jeden rˇa´dek v seznamu v leve´m dolnı´m rohu okna. Vzˇdy je zobrazena aktua´lnı´ veˇtna´ forma a na ni pouzˇite´ pravidlo. Libovolny´ rˇa´dek je mozˇno vybrat. Po stisku Zpet nebo volbeˇ Zpet v menu Derivace se nastavı´ za aktua´lnı´ veˇtna´ forma z vybrane´ho rˇa´dku a vsˇechny pozdeˇjsˇ´ı kroky jsou zapomenuty. Pokud nenı´ vybra´n zˇa´dny´ rˇa´dek, zpu˚sobı´ stejne´ tlacˇ´ıtko i polozˇka menu na´vrat o jeden krok zpeˇt. Stisk tlacˇ´ıtka Nova derivace nebo stejneˇ pojmenovana´ volba v menu Derivace vra´tı´ derivaci na u´plny´ zacˇa´tek. Veˇtnou formu bude tvorˇit pocˇa´tecˇnı´ netermina´l. Gramatiku je mozˇne´ kdykoliv zmeˇnit. Po stisku Upravit gramatiku nebo volbeˇ Upravit v menu Gramatika se otevrˇe okno editace gramatiky. Slouzˇ´ı k prˇida´nı´, maza´nı´ a zmeˇneˇ pravidel a take´ k urcˇenı´ pocˇa´tecˇnı´ho symbolu. Nova gramatika otevrˇe stejne´ okno, ale pro zada´va´nı´ nove´ gramatiky. Nejsou v neˇm tedy zˇa´dna´ pravidla. Polozˇky menu Derivace Nova derivace – Vra´tı´ derivaci na zacˇa´tek. Veˇtnou formu tvorˇ´ı pocˇa´tecˇnı´ netermina´l a vsˇechny provedene´ kroky jsou zapomenuty. Aplikuj pravidlo – Aplikuje na veˇtnou formu pravidlo vybrane´ v rozbalovacı´m seznamu Pouzit pravidlo. V prˇ´ıpadeˇ zvolene´ automaticke´ derivace zacˇne automaticke´ prova´deˇnı´. Stop – Nacha´zı´ se v menu jen prˇi probı´hajı´cı´ automaticke´ derivaci. Zpu˚sobı´ prˇerusˇenı´ automaticke´ho pru˚beˇhu. Vsˇechny automaticky provedene´ kroky zu˚stanou platne´. Zpet – Vra´tı´ derivaci prˇed krok vybrany´ v seznamu (na vybranou veˇtnou formu). Pokud nenı´ v seznamu zˇa´dny´ rˇa´dek oznacˇen, vra´tı´ se derivace o jeden krok. Konec – Ukoncˇ´ı simula´tor. Polozˇky menu Gramatika Nova – Otevrˇe okno editace gramatiky bez existujı´cı´ch pravidel. Nacist – Umozˇnı´ vy´beˇr souboru a nacˇtenı´ gramatiky z neˇj. Nacˇtena´ gramatika je opeˇt zobrazena v okneˇ editace gramatiky. Upravit – Otevrˇe okno editace gramatiky. Jsou v neˇm zobrazena existujı´cı´ pravidla a mohou by´t zmeˇneˇna, smaza´na nebo prˇida´na nova´. Ulozit – Gramatika, podle ktere´ probı´ha´ derivace, bude ulozˇena do souboru. Konkre´tnı´ soubor vybere v okneˇ uzˇivatel. Prˇi vy´beˇru je stiskem Cancel ukla´da´nı´ zrusˇeno a program se vra´tı´ do situace prˇed volbou ulozˇenı´. Po stisku Save prˇi vy´beˇru souboru je gramatika ulozˇena a program se take´ vra´tı´ do situace prˇed ukla´da´nı´m.
4
Polozˇky menu Napoveda Derivace – Zobrazı´ okno se strucˇny´m popisem ovla´da´nı´ pru˚beˇhu derivace. Tlacˇ´ıtko v tomto okneˇ umozˇnı´ prˇepnutı´ na informaci o programu. O programu – Zobrazı´ okno se strucˇnou informacı´ o programu. Tlacˇ´ıtko v tomto okneˇ umozˇnı´ prˇepnutı´ na na´poveˇdu k ovla´da´nı´ pru˚beˇhu derivace. Prvky uzˇivatelske´ho rozhranı´ v okneˇ Aplikuj pravidlo – Aplikuje na veˇtnou formu pravidlo vybrane´ v rozbalovacı´m seznamu Pouzit pravidlo. V prˇ´ıpadeˇ zvolene´ automaticke´ derivace zacˇne automaticke´ prova´deˇnı´. Zpet – Vra´tı´ derivaci prˇed krok vybrany´ v seznamu (na vybranou veˇtnou formu). Pokud nenı´ v seznamu zˇa´dny´ rˇa´dek oznacˇen, vra´tı´ se derivace o jeden krok. Nova derivace – Vra´tı´ derivaci na zacˇa´tek. Veˇtnou formu tvorˇ´ı pocˇa´tecˇnı´ netermina´l a vsˇechny provedene´ kroky jsou zapomenuty. Nova gramatika – Otevrˇe okno editace gramatiky bez existujı´cı´ch pravidel. Upravit gramatiku – Otevrˇe okno editace gramatiky. Jsou v neˇm zobrazena existujı´cı´ pravidla a mohou by´t zmeˇneˇna, smaza´na nebo prˇida´na nova´. Automaticky – Po zasˇkrtnutı´ bude derivace spusˇteˇna´ tlacˇ´ıtkem Aplikuj probı´hat bez nutnosti za´sahu uzˇivatele, dokud bude jednoznacˇne´ pokracˇova´nı´. Leftmost – Aplikovatelne´ bude jen pravidlo, jehozˇ leva´ strana se ze vsˇech z pole u´speˇchu nebo neu´speˇchu pravidla pouzˇite´ho v minule´m kroku vyskytuje nejvı´ce vlevo ve veˇtne´ formeˇ. Pravidlo ve smyslu testova´nı´ vy´skytu je aplikovatelne´ pouze tehdy, nenı´-li zˇa´dne´ jine´ pouzˇitelne´ klasicky´m zpu˚sobem. Nahodne – Pokud je prˇi automaticke´ derivaci aplikovatelny´ch vı´ce pravidel, vybere program jedno na´hodneˇ a pokracˇuje bez prˇerusˇenı´. Vyskyt – Porˇadı´ vy´skytu leve´ strany pravidla ve veˇtne´ formeˇ. Na tento vy´skyt bude pravidlo aplikova´no. Pocˇ´ıta´ se zleva od 1. Zpozdeni – Cˇas v milisekunda´ch, ktery´ uplyne mezi jednotlivy´mi kroky automaticke´ derivace. Pouzit pravidlo – Rozbalovacı´ seznam pouzˇitelny´ch pravidel. Vybrane´ bude aplikova´no po stisku Aplikuj Vetna forma – Aktua´lnı´ veˇtna´ forma.
5
Obra´zek 1.2: Okno editace gramatiky
1.3.2
Okno editace gramatiky
Prˇi pozˇadavku na editaci gramatiky se otevrˇe okno, ktere´ je na obra´zku 1.2. V neˇm je mozˇno editovat pravidla (prˇida´vat, mazat a meˇnit) a zmeˇnit pocˇa´tecˇnı´ netermina´l. Kdykoliv je mozˇne´ okno uzavrˇ´ıt bez toho, aby se provedene´ zmeˇny projevily v gramatice, podle ktere´ probı´ha´ derivace. V hornı´ cˇa´sti okna je peˇt textovy´ch polı´. Slouzˇ´ı k zada´nı´ jednotlivy´ch cˇa´stı´ pravidla. Mezi nimi se prˇepı´na´ kla´vesou tabela´tor nebo kliknutı´m mysˇ´ı na pozˇadovane´ pole. Do pole s nadpisem Ozn. se vypisuje oznacˇenı´ pravidla. Musı´ splnˇovat pozˇadavky, ktere´ jsou popsane´ v cˇa´sti 1.2. Dalsˇ´ı dveˇ textova´ pole jsou oddeˇlena „− >“. Tı´m je naznacˇeno, zˇe jedno bude tvorˇit levou a druhe´ pravou stranu pravidla. Tvar termina´lu˚ a netermina´lu˚ byl popsa´n drˇ´ıve. Pokud nebude vyplneˇna prava´ strana, bude do nı´ automaticky dosazen termina´l la. Pod nadpisy Uspech a Neuspech se vypisujı´ pole u´speˇchu a neu´speˇchu. Jedna´ se o oznacˇenı´ pravidel, ktera´ si prˇejeme aplikovat v kroku na´sledujı´cı´m po pra´veˇ vyplnˇovane´m pravidle. Oznacˇenı´ mohou by´t oddeˇlena libovolny´m oddeˇlovacˇem. Prˇida´nı´ vyplneˇne´ho pravidla se provede stiskem kla´vesy Enter, pokud se kurzor nacha´zı´ 6
v jednom z textovy´ch polı´ pravidla, tlacˇ´ıtkem Pridat nebo stejnou volbou v menu Pravidlo. Pravidlo se nejprve prˇekontroluje, jestli splnˇuje vsˇechny pozˇadavky. Potom je prˇida´no do gramatiky a objevı´ se v seznamu v leve´m dolnı´m rohu okna. Pokud je v pravidle neˇjaka´ chyba, zobrazı´ se okno s chybovou zpra´vou a po jeho uzavrˇenı´ se kurzor nastavı´ do textove´ho pole, ve ktere´m se chyba nacha´zı´. Pravidla, ktera´ jsou soucˇa´stı´ pra´veˇ editovane´ gramatiky, jsou zobrazena v seznamu v leve´m dolnı´m rohu okna. V neˇm je mozˇno pravidlo oznacˇit a smazat kla´vesou Delete, stiskem tlacˇ´ıtka Smazat nebo stejnou volbou v menu Pravidlo. Pokud je pravidlo vybra´no a stiskne se tlacˇ´ıtko Upravit (poprˇ. volba Upravit v menu Pravidlo), je pravidlo take´ ze seznamu i z gramatiky vymaza´no. Objevı´ se vsˇak rozdeˇlene´ v textovy´ch polı´ch pro zada´va´nı´ pravidla. Zde ho mu˚zˇe uzˇivatel upravit a znovu prˇidat do gramatiky stejneˇ, jako nove´. Textove´ pole s nadpisem Pocatecni slouzˇ´ı k zada´nı´ startovacı´ho netermina´lu. Pokud nenı´ pole vyplneˇno, automaticky se do neˇj dosadı´ leva´ strana prvnı´ho prˇidane´ho pravidla. I potom je mozˇne´ pocˇa´tecˇnı´ netermina´l kdykoliv zmeˇnit. Pokud je gramatika hotova´, potvrdı´ se stiskem tlacˇ´ıtka OK nebo stejnou volbou v menu Gramatika. Nejprve se provede kontrola. Musı´ by´t vyplneˇn pocˇa´tecˇnı´ netermina´l a vsˇechna pravidla uvedena´ v polı´ch u´speˇchu a neu´speˇchu musı´ existovat. Pokud to nenı´ splneˇno, zobrazı´ se chybove´ okno a v editaci se mu˚zˇe pokracˇovat. Jinak se okno editace gramatiky zavrˇe a pro derivaci se nastavı´ pra´veˇ zadana´ gramatika. Soucˇasneˇ se prˇerusˇ´ı prˇ´ıpadna´ probı´hajı´cı´ automaticka´ derivace. Pokud jizˇ probeˇhly neˇjake´ kroky derivace, budou zapomenuty a veˇtnou formu bude tvorˇit pocˇa´tecˇnı´ netermina´l nove´ gramatiky. Editaci gramatiky je mozˇne´ kdykoliv prˇerusˇit, anizˇ by se zmeˇny projevily. Po stisku Zrusit nebo po zvolenı´ Zrusit v menu Gramatika se okno editace zavrˇe a probı´hajı´cı´ derivace ani gramatika, podle ktere´ se pravidla pouzˇ´ıvajı´, se nezmeˇnı´. Gramatiku je mozˇne´ ulozˇit do souboru. Provede se to volbou Ulozit v menu Gramatika. Nejprve se gramatika zkontroluje na stejne´ podmı´nky, jako prˇi stisku OK. Potom je zobrazen dialog pro vy´beˇr souboru. Ovla´da´nı´ v tomto dialogu je stejne´ jako v jiny´ch programech pracujı´cı´ch se soubory. Stisk tlacˇ´ıtka Cancel ukla´da´nı´ prˇerusˇ´ı. Po Save se provede vlastnı´ za´pis. Pokud je vybra´n existujı´cı´ soubor, je bez varova´nı´ prˇepsa´n. Po ulozˇenı´ je aplikace ve stejne´m stavu, jako prˇed nı´m. K nacˇtenı´ gramatiky ze souboru slouzˇ´ı volba Nacist v menu Gramatika. Opeˇt je ve standardnı´m okneˇ (viz. obra´zek 1.3) vybra´n soubor. Cancel nacˇ´ıta´nı´ prˇerusˇ´ı. Open nacˇte gramatiku ze souboru. Editovana´ gramatika je zapomenuta a nahrazena noveˇ nacˇtenou. Tu je mozˇne´ editovat a pote´ pouzˇ´ıt k derivaci stiskem OK.
1.3.3
Polozˇky menu Gramatika
Nacist – Umozˇnı´ vy´beˇr souboru a nacˇtenı´ gramatiky z neˇj. Nacˇtena´ gramatika je zobrazena. Ulozˇit – Pra´veˇ editovana´ gramatika bude ulozˇena do souboru. Konkre´tnı´ soubor vybere v okneˇ uzˇivatel. Prˇi vy´beˇru je stiskem Cancel ukla´da´nı´ zrusˇeno a program se vra´tı´ do situace prˇed volbou ulozˇenı´. Po stisku Save prˇi vy´beˇru souboru je gramatika ulozˇena a program se take´ vra´tı´ do situace prˇed ukla´da´nı´m. 7
Obra´zek 1.3: Okno pro vy´beˇr souboru s gramatikou
Zrusit – Okno editace gramatiky bude zavrˇeno a vsˇechny zmeˇny v gramatice provedene´ budou zapomenuty. Nema´ vliv na probı´hajı´cı´ derivaci. OK – Okno editace bude zavrˇeno a editovana´ gramatika se nastavı´ pro derivaci. Prˇ´ıpadna´ probı´hajı´cı´ automaticka´ derivace bude prˇerusˇena a vsˇechny kroky derivace budou zapomenuty. Polozˇky menu Pravidlo Pridat – Prˇida´ pravidlo popsane´ v textovy´ch polı´ch v hornı´ cˇa´sti okna do gramatiky. Pravidlo musı´ splnˇovat neˇktere´ za´kladnı´ pozˇadavky na tvar, ktere´ jsou popsane´ v cˇa´sti 1.2 te´to prˇ´ırucˇky. Pokud neˇjaka´ podmı´nka nenı´ splneˇna, zobrazı´ se chybova´ zpra´va a pravidlo nenı´ prˇida´no. Upravit – Pokud je v seznamu pravidel vybra´n neˇktery´ rˇa´dek, je odpovı´dajı´cı´ pravidlo vymaza´no a nastaveno do textovy´ch polı´ v hornı´ cˇa´sti okna. Pokud nenı´ vybra´no nic, nema´ volba zˇa´dny´ u´cˇinek. Smazat – Pokud je v seznamu pravidel vybra´n neˇktery´ rˇa´dek, je odpovı´dajı´cı´ pravidlo vymaza´no. Pokud nenı´ vybra´no nic, nema´ volba zˇa´dny´ u´cˇinek. Polozˇky menu Napoveda Editace gramatiky – Zobrazı´ okno se strucˇny´m popisem ovla´da´nı´ editace gramatiky. Tlacˇ´ıtko v tomto okneˇ umozˇnı´ prˇepnutı´ na informaci o programu. 8
O programu – Zobrazı´ okno se strucˇnou informacı´ o programu. Tlacˇ´ıtko v tomto okneˇ umozˇnı´ prˇepnutı´ na na´poveˇdu k ovla´da´nı´ editace gramatiky. Prvky uzˇivatelske´ho rozhranı´ v okneˇ Pridat – Prˇida´ pravidlo popsane´ v textovy´ch polı´ch v hornı´ cˇa´sti okna do gramatiky. Pravidlo musı´ splnˇovat neˇktere´ za´kladnı´ pozˇadavky na tvar, ktere´ jsou popsane´ v cˇa´sti 1.2 te´to prˇ´ırucˇky. Pokud neˇjaka´ podmı´nka nenı´ splneˇna, zobrazı´ se chybova´ zpra´va a pravidlo nenı´ prˇida´no. Upravit – Pokud je v seznamu pravidel vybra´n neˇktery´ rˇa´dek, je odpovı´dajı´cı´ pravidlo vymaza´no a nastaveno do textovy´ch polı´ v hornı´ cˇa´sti okna. Pokud nenı´ vybra´no nic, nema´ volba zˇa´dny´ u´cˇinek. Smazat – Pokud je v seznamu pravidel vybra´n neˇktery´ rˇa´dek, je odpovı´dajı´cı´ pravidlo vymaza´no. Pokud nenı´ vybra´no nic, nema´ volba zˇa´dny´ u´cˇinek. Zrusit – Okno editace gramatiky bude zavrˇeno a vsˇechny zmeˇny na gramatice provedene´ budou zapomenuty. Nema´ vliv na probı´hajı´cı´ derivaci. OK – Okno editace bude zavrˇeno a editovana´ gramatika se nastavı´ pro derivaci. Prˇ´ıpadna´ probı´hajı´cı´ automaticka´ derivace bude prˇerusˇena a vsˇechny kroky derivace budou zapomenuty. Pocatecni – Pocˇa´tecˇnı´ netermina´l gramatiky. Ozn. – Oznacˇenı´ pravidla. Pravidlo – Jedno pole slouzˇ´ı pro levou stranu pravidla a druhe´ pro pravou. Uspech – Pole u´speˇchu pravidla. Zada´vajı´ se oznacˇenı´ pravidel patrˇ´ıcı´ch do tohoto pole. Neuspech – Pole neu´speˇchu pravidla. Zada´vajı´ se oznacˇenı´ pravidel patrˇ´ıcı´ch do tohoto pole. T – Seznam termina´lu˚, ktere´ se nacha´zejı´ v pravidlech a tedy i gramatice. V tomto poli se nevypisuje termina´l la zastupujı´cı´ λ. N – Seznam netermina´lu˚, ktere´ se nacha´zejı´ v pravidlech a tedy i gramatice.
1.3.4 Chybove´ okno Pokud nastane beˇhem programu chyba, zobrazı´ se jejı´ strucˇny´ popis v okneˇ zobrazene´m na obra´zku 1.4. Dokud nenı´ tato zpra´va zavrˇena, je okno, ve ktere´m k chybeˇ dosˇlo, neaktivnı´. Zavrˇ´ıt okno s chybovou zpra´vou je mozˇne´ ru˚zneˇ - beˇzˇny´m zpu˚sobem zavı´ra´nı´ oken v pouzˇite´m operacˇnı´m syste´mu, stiskem kla´vesy Enter nebo stiskem tlacˇ´ıtka OK.
9
Obra´zek 1.4: Chybove´ okno
Obra´zek 1.5: Okno na´poveˇdy
1.3.5
Okno na´poveˇdy
Okno na´poveˇdy je zobrazeno na obra´zku 1.5. Program pouzˇ´ıva´ dva druhy na´poveˇdnı´ch oken. Kazˇde´ mu˚zˇe by´t zobrazeno jen jednou, ale ru˚zne´ druhy soucˇasneˇ zobrazene´ by´t mohou. Jeden druh zobrazuje na´poveˇdu o derivaci a druhy´ o gramatice. Oba umozˇnˇujı´ i strucˇnou informaci o programu. Prˇepı´na´nı´ mezi hlavnı´ na´poveˇdou a informacı´ o programu se prova´dı´ stiskem prˇ´ıslusˇne´ho tlacˇ´ıtka v hornı´ cˇa´sti okna.
10
1.4
Forma´t souboru s programovanou gramatikou
Soubor vznikne automaticky prˇi ukla´da´nı´ gramatiky. Je mozˇne´ ho vytvorˇit take´ rucˇneˇ jaky´mkoliv editorem textovy´ch souboru˚. V souboru se mohou vyskytovat na libovolne´m mı´steˇ rˇa´dky pouze s bı´ly´mi znaky (mezera, tabela´tor) nebo rˇa´dky s komenta´rˇi (prvnı´ viditelny´ znak je #). Tyto rˇa´dky jsou prˇi zpracova´nı´ souboru vynecha´ny. Na prvnı´m platne´m rˇa´dku musı´ by´t pocˇa´tecˇnı´ netermina´l. Kazˇdy´ dalsˇ´ı rˇa´dek obsahuje jedno pravidlo. Na rˇa´dku s pravidlem je nejprve oznacˇenı´ pravidla, za nı´m dvojtecˇka, netermina´l tvorˇ´ıcı´ levou stranu, znaky „− >“, termina´ly a netermina´ly prave´ strany, ve slozˇeny´ch za´vorka´ch oznacˇenı´ pravidel z pole u´speˇchu a pole neu´speˇchu. Za polem neu´speˇchu mu˚zˇe by´t do konce rˇa´dku cokoliv. Termina´ly, netermina´ly a oznacˇenı´ musı´ splnˇovat podmı´nky uvedene´ v cˇa´sti 1.2 te´to prˇ´ırucˇky. K oddeˇlenı´ symbolu˚ na prave´ straneˇ pravidla a oznacˇenı´ v polı´ch u´speˇchu a neu´speˇchu slouzˇ´ı oddeˇlovacˇe popsane´ ve stejne´ cˇa´sti. Prˇ´ıklad souboru s gramatikou: #Gramatika pro jazyk L={ww|w nalezi do {a,b}ˆ+} S r1: r2: r3: r4: r5: r6:
1.5
S A A B A A
-> -> -> -> -> ->
A a b A a b
A {r2, r3, r5, r6} {} B {r2} {r4} B {r3} {r4} {r4} {r2, r3, r5, r6} {r5} {} {r6} {}
Uka´zkove´ prˇ´ıklady
Soucˇa´stı´ programu jsou uka´zkove´ prˇ´ıklady programovany´ch gramatik. Nacha´zejı´ se v podadresa´rˇi example adresa´rˇe simulator. Tyto soubory mohou by´t nacˇteny zpu˚sobem popsany´m drˇ´ıve a gramatiky z nich pouzˇity k derivaci. Konkre´tneˇ jde o: example1.gra – Gramatika bez testova´nı´ vy´skytu pro jazyk L = {ww|w ∈ {a, b}+ } example2.gra – Gramatika pro jazyk L = {an bn cn |n ≥ 1} example3.gra – Gramatika s testova´nı´m vy´skytu pro jazyk L = {ww|w ∈ {a, b}+ } example4.gra – Gramatika pro jazyk L = {an bm cn dm |m, n ≥ 1} example5.gra – Gramatika pro jazyk L = {an bm an |0 ≤ m ≤ n} 2
example6.gra – Gramatika pro jazyk L = {an |n ≥ 0}
11
Prˇ´ıloha 2. Programa´torska´ prˇ´ırucˇka k programu Simula´tor programovane´ gramatiky 2.1
Zada´nı´
Vytvorˇte program pro simulaci derivace podle programovane´ gramatiky. Programovana´ gramatika bude obsahovat bezkontextova´ pravidla vcˇetneˇ vypousˇteˇjı´cı´ch a bude umozˇnˇovat aplikaci pravidel ve smyslu testova´nı´ vy´skytu. Pokud bude pru˚beˇh jednoznacˇny´, umozˇneˇte automaticke´ prova´deˇnı´ derivace. Mezi jednotlivy´mi kroky prˇi automaticke´m pru˚beˇhu bude prodleva, aby mohl uzˇivatel jednotlive´ kroky dobrˇe sledovat. Pokud nenı´ pokracˇova´nı´ jednoznacˇne´, umozˇneˇte na´hodny´ vy´beˇr pravidla bez za´sahu uzˇivatele. V derivaci se bude mozˇne´ vra´tit ke ktere´mukoliv kroku. Gramatiky bude mozˇne´ ulozˇit a zase nacˇ´ıst, aby je nemusel uzˇivatel vzˇdy znovu zada´vat.
2.2
Analy´za
2.2.1 Objektovy´ model
1
Obra´zek 2.1: Objektovy´ model - reprezentace derivace
2
Obra´zek 2.2: Objektovy´ model - reprezentace gramatiky
3
Obra´zek 2.3: Objektovy´ model - graficke´ uzˇivatelske´ rozhranı´
4
2.2.2 Dynamicky´ model
Obra´zek 2.4: Interakcˇnı´ diagram - na´vrat v derivaci
Obra´zek 2.5: Interakcˇnı´ diagram - aplikace pravidla
5
Obra´zek 2.6: Stavovy´ diagram trˇ´ıdy DerivationFrame prˇi automaticke´ derivaci
Obra´zek 2.7: Stavovy´ diagram zna´zornˇujı´cı´, kdy jsou v okneˇ derivace aktivnı´ tlacˇ´ıtka zpeˇt, aplikuj, nova´ gramatika, nova´ derivace a zmeˇna gramatiky
6
2.2.3 Funkcˇnı´ model
Obra´zek 2.8: DFD - 0. u´rovenˇ
Obra´zek 2.9: DFD - 1. Editace gramatiky
7
Obra´zek 2.10: DFD - 2. Derivace
Obra´zek 2.11: DFD - 3. Pra´ce se souborem
Obra´zek 2.12: DFD - 2.2. Posun v derivaci
8
Obra´zek 2.13: DFD - 2.1. Provedenı´ kroku derivace
2.3
Zdrojove´ ko´dy
Kompletnı´ zdrojove´ ko´dy v jazyce JAVA je mozˇne´ nale´zt v adresa´rˇi simulator/src na prˇilozˇene´m CD (prˇ´ıloha 3). Jsou rozdeˇleny do dvou podadresa´rˇu˚ podle prˇ´ıslusˇnosti do dvou balı´ku˚ (package v JAVeˇ). Jeden obsahuje trˇ´ıdy rozhranı´ (adresa´rˇ a balı´k gui) a druhy´ trˇ´ıdy reprezentujı´cı´ gramatiky a prova´deˇjı´cı´ derivaci (grammar).
2.4
Popis trˇ´ıd, metod a atributu˚
V zdrojove´m textu byly pouzˇity komenta´rˇe umozˇnˇujı´cı´ vygenerova´nı´ dokumentace programem javadoc. Kompletnı´ vygenerovana´ dokumentace ve forma´tu HTML je na prˇilozˇene´m CD v adresa´rˇi simulator/doc. Komenta´rˇe byly psa´ny cˇesky, ale bez diakriticky´ch zname´nek. Pouzˇ´ıva´nı´ diakritiky ve zdrojove´m ko´du nenı´ u´plneˇ nejvhodneˇjsˇ´ı a ztratila by se neza´vislost zdrojove´ho ko´du na ko´dova´nı´ pouzˇ´ıvane´m v operacˇnı´m syste´mu. Text, ktery´ generuje automaticky javadoc je anglicky.
9
2.5
SW pozˇadavky
Program je psa´n v programovacı´m jazyce JAVA. Pro spusˇteˇnı´ proto potrˇebuje interpret nazvany´ JVM (Java Virtual Machine), ktery´ je soucˇa´stı´ volneˇ sˇ´ırˇene´ distribuce jazyka JAVA. JVM je mozˇne´ sta´hnout na internetove´ adrese www.sun.com jako soucˇa´st distribucı´ JRE (Java Runtime Environment) nebo JDK (Java Development Kit). JRE slouzˇ´ı pouze ke spousˇteˇnı´ aplikacı´, JDK poskytuje navı´c tvu˚rcu˚m prostrˇedky pro vy´voj. Pro spusˇteˇnı´ Simula´toru programovane´ gramatiky je potrˇeba JRE ve verzi 1.2 nebo vysˇsˇ´ı. Operacˇnı´ syste´m mu˚zˇe by´t libovolny´, pro ktery´ existuje JRE. Program vyzˇaduje existenci graficke´ho prostrˇedı´ (naprˇ. v linuxovy´ch syste´mech je nutne´ spustit XWindow, v operacˇnı´ch syste´mech firmy Microsoft Windows od verze 95 je graficke´ prostrˇedı´ automaticky).
2.6
HW pozˇadavky
Program je mozˇne´ spustit na kazˇde´m pocˇ´ıtacˇi, na ktere´m beˇzˇ´ı graficky´ operacˇnı´ syste´m a splnˇuje hardwarove´ na´roky pro spusˇteˇnı´ JRE. Konkre´tnı´ popis pozˇadovane´ho hardware pro JRE je mozˇne´ najı´t na www.sun.com. Lisˇ´ı se podle operacˇnı´ho syste´mu. Pro ovla´da´nı´ programu je nutne´ mı´t mysˇ.
2.7
Na´meˇty pro rozsˇ´ırˇenı´
Za´kladnı´ struktura trˇ´ıd je navrzˇena obecneˇ. Pravidla mohou mı´t na leve´ straneˇ sekvenci symbolu˚ a tak je mozˇne´ bez zmeˇny implementace pouzˇ´ıvat kontextova´ nebo obecna´ pravidla. Programovana´ gramatika je specializacı´ gramatiky stejneˇ jako programovane´ pravidlo beˇzˇne´ho pravidla. Stejny´m zpu˚sobem by mohly by´t vytvorˇeny dalsˇ´ı podtrˇ´ıdy pro jine´ typy gramatik. Pro kazˇdou by stacˇilo dodat mechanismus rˇ´ızenı´ a vhodneˇ prˇedefinovat funkce nalezenı´ aplikovatelny´ch pravidel. Pro jiny´ typ gramatiky by bylo nutne´ vytvorˇit nove´ uzˇivatelske´ rozhranı´ pro zada´nı´ pravidel, protozˇe je rˇ´ızenı´ zajisˇteˇno jinak, nezˇ polem u´speˇchu a neu´speˇchu. Trˇ´ıda DerivationFrame zajisˇt’ujı´cı´ ovla´da´nı´ derivace je z velke´ cˇa´sti obecna´. Na programovanou gramatiku jsou va´za´ny jen funkce vyvola´vajı´cı´ editaci gramatiky. Musel by se vyrˇesˇit mechanismus vy´beˇru konkre´tnı´ho typu gramatiky.
10
