Klíčová slova:

Poděkování:

Chtěl bych vyjádřit poděkování vedoucímu své bakalářské práce

Prof. RNDr. Mojmíru Křetínskému, CSc. za jeho cenné rady při tvorbě programu a za to, že moji práci usměrňoval ke zdárnému konci.

Prohlášení:

Prohlašuji, že tato práce je mým původním autorským dílem, které jsem vypracoval

samostatně. Všechny zdroje, prameny a literaturu, které jsem při vypracování používal nebo z nich čerpal v práci řádně cituji s uvedením úplného odkazu na příslušný zdroj.

_____________________

Shrnutí:

Se zvyšováním požadavků na programovací jazyky se v dnešní době zvyšují i požadavky na vytvoření bezkontextových gramatik, na jejichž základech pracují dnešní analyzátory syntaxe vstupního textu obsažené ve většině překladačů programovacích jazyků.

Cílem této práce je aplikace, která umožní uživatelům souhrnný, stručný a hlavně rychlý přehled o všech základních algoritmech fungujících nad bezkontextovými a LL(1)

gramatikami. Program umožňuje nejenom možnost vytváření jednotlivých gramatik, ale taktéž jejich zpětnou editaci nejen v programu samotném, ale i pomocí externích souborů. V práci shrnuji problematiku Bezkontextových a LL(1) gramatik, včetně popisu jednotlivých funkcí, které nad nimi program dokáže aplikovat. V závěru se zabývám způsobem tvorby gramatik a jejich využitím v praxi. Aplikace je napsána v programu Borland Delphi 7 a má grafické uživatelské rozhraní.

Klíčová slova:

Bezkontextová gramatika, FIRST, FOLLOW, Bezkontextový jazyk, Borland Delphi

Obsah

1 Úvod 3

2 Formální jazyky a jejich gramatiky 4

2.1 Reprezentace jazyka... 4

2.1.1 Abeceda jazyka ... 4

2.1.2 Gramatika ... 4

2.1.3 Formální jazyk ... 4

2.2 Chomského rozdělení formálních jazyků ... 5

2.3 Bezkontextová gramatika ... 5

2.3.1 Derivační stromy ... 5

2.3.2 Zásobníkové automaty ... 6

2.3.3 Bezkontextový jazyk ... 6

2.4 LL(1) gramatika ... 6

3 Grafické uživatelské rozhraní 7 3.1 Programové prostředí ... 7

3.2 Hlavní menu ... 7

3.3 Editace gramatiky ... 7

3.3.1 Editace gramatiky za běhu programu ... 7

3.3.2 Načtení gramatiky ze souboru ... 8

3.3.3 Tvorba pravidel gramatiky ... 8

4 Popis funkčních modulů 10 4.1 Určení prázdnosti jazyka... 10

4.2 Eliminace nedosažitelných symbolů ... 11

4.3 Eliminace nepoužitelných symbolů ... 11

4.4 Eliminace e-pravidel ... 12

4.5 Eliminace jednoduchých pravidel ... 13

4.6 Funkce FIRST ... 13

4.7 Funkce FOLLOW ... 14

5 Práce s externími soubory 15 5.1 Formát souboru ... 15

5.2 Manipulace se soubory ... 16

6 Závěr 17

7 Použitá literatura 18

8 Přílohy 19

Kapitola 1

Úvod

S rostoucími nároky na analýzu textu a rychlost jeho kontroly se v dnešních aplikacích klade častěji důraz na využití bezkontextových gramatik pro kontrolu syntaxe vstupního textu. Pro vytvoření gramatiky, která umožňuje efektivní kontrolu vstupního textu je zapotřebí nejen samotného vytvoření gramatiky, ale taktéž určitého nástroje, který převede námi vytvořenou gramatiku do tvaru, ve kterém bude efektivněji pracovat.

V následující kapitole shrnu problematiku bezkontextových gramatik. Toto uvedení do problematiky je nezbytné pro snazší pochopení textu, který se bude v pozdější části vyskytovat. V dalších kapitolách pak rozeberu vzhled grafického uživatelského prostředí a jednotlivé funkce, které dokáže program aplikovat. Na konec rozeberu možnost editace gramatik pomocí externích souborů.

Cílem této práce je aplikace, jež umožní upravovat bezkontextové gramatiky, která pomocí jednotlivých funkcí volaných v dobře zvoleném pořadí odstraní redundantní

a neefektivní pravidla, smaže přebytečné symboly gramatiky a celkově tak zvýší efektivnost algoritmu pracujícího s takto upravenou gramatikou.

Kapitola 2

Formální jazyky a jejich gramatiky

2.1 Reprezentace jazyka

V této kapitole se zaměřím na definici důležitých termínů z oblasti formálních jazyků. Nejprve se zmíním o tom co jsou formální jazyky a gramatiky, ukážu jaké typy gramatik rozlišujeme a v poslední části se zaměřím na definici bezkontextových a LL(1) gramatik.

2.1.1 Abeceda jazyka

Abecedou jazyka se rozumí libovolná konečná množina

Σ

, jejíž prvky nazýváme znaky (případně také písmena nebo symboly) abecedy.

Slovo nad abecedou je libovolná konečná posloupnost znaků z abecedy, která splňuje pravidla gramatiky. Tedy, že existuje postup, při kterém se můžeme pomocí pravidel gramatiky dostat k výslednému slovu. Prázdné slovo se ve formálních jazycích prezentuje symbolem є.

2.1.2 Gramatika

Gramatika je čtveřice (N,

Σ

, P, S), kde

• N je neprázdná konečná množina neterminálních symbolů (neterminálů)

• Σ je konečná množina terminálních symbolů (terminálů)

• P je konečná množina pravidel (př. α → β znamená řetězec α přepiš na β)

• S je speciální počáteční neterminál (nazýváný též kořenem gramatiky) 2.1.3. Formální jazyk

Každá gramatika generuje pomocí množiny pravidel slova, která patří do formálního jazyka generovaného gramatikou. Součástí pravidel můžou být pouze výše zmíněné prvky množin neterminálů a terminálů. Jazyk generovaný gramatikou je podmnožina všech vygenerovatelných slov nad abecedou

Σ

. Jazyk generovaný gramatikou může být obecně nekonečný, proto je třeba definovat přesná pravidla pro tvorbu slov v daném jazyce.

2.2 Chomského rozdělení gramatik a formálních jazyků

Koncem 50-tých let minulého století rozdělil Noam Chomsky gramatiky (formální jazyky) do jednotlivých skupin podle jejich popisné síly.

Frázové gramatiky (Typ 0):

Libovolná gramatika může být frázovou gramatikou, na tvar pravidel se nekladou žádné omezující požadavky

Kontextové gramatiky (Typ 1):

Na pravidla kontextových gramatik je kladeno omezení, že pro pravidla typu α → β musí platit |α| ≤ |β| s eventuelní výjimkou pravidla S → є, pokud se S nevyskytuje na žádné pravé straně pravidel.

Bezkontextové gramatiky (Typ 2):

Pravidla bezkontextových gramatik musí splňovat, aby pravidla typu A → α, kde

|α| ≥ 1 s eventuelní výjimkou pravidla S → є, pokud se S nevyskytuje na žádné pravé straně pravidel.

Regulární (pravolineární) gramatiky (Typ 3):

Jejich pravidla musí splňovat podmínku, aby každé její pravidlo bylo tvaru A → aB nebo A → a s eventuelní výjimkou pravidla S → є, pokud se S nevyskytuje na žádné pravé straně pravidel.

2.3 Bezkontextová gramatika

V informatice je tedy pod pojmem bezkontextová gramatika chápána gramatika, která splňuje podmínky tvorby pravidel podle Chomského rozdělení. Pro každou takovou gramatiku jsme schopni vytvořit zásobníkový automat a na základě toho určit postup pravidel, pomocí kterých jsme schopni vygenerovat slovo patřící do jazyka generovaného gramatikou.

Bezkontextové gramatiky se používají při definici syntaxe programovacích jazyků, návrhu překladu programovacích jazyků, pro tvorbu různých blokových struktur, pro různé typy uzávorkování nebo pro analýzu syntaxe vstupního textu.

2.1.1 Derivační stromy

Derivační stromy jsou speciálními druhy odvozovacích stromů, pomocí nichž tvoříme strom všech derivací, které dochází ke stejnému výsledku, ale jiným postupem aplikace pravidel.

Derivační strom tedy vyjadřuje všechny možnosti jak pomocí vybrané množiny pravidel dojít požadovaného výsledku.

2.1.2 Zásobníkové automaty

Ke každé bezkontextové gramatice můžeme zkonstruovat zásobníkový automat, který slouží pro zjištění zda dané slovo patří do jazyka tvořeného bezkontextovou gramatiku či nikoliv.

Zásobníkový automat si můžeme představit jako výpočetní systém s nekonečnou pamětí (zásobníkem), do kterého můžeme ukládat libovolné terminály či neterminály. Dále se skládá ze vstupní pásky, na které je uloženo slovo po kterém požadujeme zjistit, zda je slovem z jazyka gramatiky a v neposlední řadě je zde řídící jednotka, která aplikuje výpočetní algoritmus.

2.1.3 Bezkontextový jazyk

Je množina slov, která jsou generovatelná gramatikou (popř. akceptovatelná zásobníkovým automatem příslušné gramatiky).

2.4 LL(1) gramatika

Je speciální typ bezkontextové gramatiky, která je zbavena levé rekurze a pro kterou platí, že každý neterminál a každé dvě různá pravidla splňují následující předpis

FIRST1(β FOLLOW1(A)) ∩ FIRST1(γ FOLLOW1(A)) = Ø

kde význam funkce FIRST1 : (N ∪

Σ

)⁺ → { w ∈ Σ* | |w| ≤ 1} naznačený předpisem je FIRST1(α) = { w ∈ Σ* | (α →* w ∩ |w| ≤ 1) ∪ (α →* wβ ∩ |w| = 1)}

a funkce FOLLOW1 : N → { w ∈ Σ* | |w| ≤ 1} naznačený předpisem je FOLLOW1(A) = { w ∈ Σ* | S →* γAα , w ∈ FIRST1(α)}

Kapitola 3

Grafické uživatelské prostředí

3.1 Programové prostředí

Program je vytvořen pro rychlou a přehlednou aplikaci základních funkcí nad

bezkontextovými gramatikami, jejich snadnou komunikaci s tvorbou a se změnou pravidel nebo množin terminálů a neterminálů. Samotná tvorba gramatiky je řešena pomocí formulářů, které se mění v závislosti na tom, jakou část gramatiky právě editujeme. Spuštění většiny funkcí automaticky upravuje zadaná pravidla a symboly, takže uživatel může rychle reagovat a dynamicky tak měnit výsledný vzhled gramatiky.

Program je napsán v Borland Delphi 7, takže by měl podporovat jak operační systém Windows tak většinu druhů Unixů.

3.2 Hlavní menu

Při spuštění aplikace máme k dispozici pouze Hlavní menu, které se skládá ze záložek Soubor a Gramatika.

• záložka Soubor obsahuje základní funkce pro práci se soubory jako je otevření souboru z datového média (Otevři), uložení rozpracované gramatiky (Ulož, Ulož jako…), tvorba nové gramatiky (Nový) a ukončení programu (Konec).

• Záložka Gramatika obsahuje dvě podmnožiny Gramatika a Funkce. V Gramatice jsou umístěny funkce sloužící ke správě samotné gramatiky. Ve Funkcích jsou veškeré algoritmy, které umí program aplikovat.

3.3 Editace gramatiky

Základním funkčním jádrem programu nejsou jenom funkce, které můžeme volat nad

vytvořenou gramatikou, ale taktéž snadná editace gramatiky. Program nám umožňuje editovat gramatiku dvěma způsoby:

Editace gramatiky za běhu programu

Při spuštění programu a zmáčknutí funkce Nový, která nám otevře základní editační okno, které bude vidět po celou dobu běhu programu, až na některé situace, kdy se při výpočtu nebo zobrazení některých funkcí ztratí. Formulář pro správu gramatiky pak můžete znovu spustit při kliknutí do hlavního menu na záložku Gramatika podsložku Gramatika a funkci

Editace gramatiky.

Načtení gramatiky ze souboru

Posledním, a pro mnoho uživatelů jistě velmi výhodným, způsobem editace je nahrání dříve vytvořené gramatiky ze souboru. Soubor, ze kterého budeme danou gramatiku číst nemusí obsahovat všechny náležitosti, ale musí být napsaný ve speciálním formátu, který budu blíže popisovat v páté kapitole.

Tvorba pravidel gramatiky

Jak bylo zmíněno v předešlých odstavcích, veškeré symboly i pravidla lze vytvořit na jediném formuláři. K tvorbě všech symbolů a pravidel, které budeme při práci potřebovat nám slouží tři základní funkční tlačítka umístěné v pravé horní části programu:

Přidat terminál

- přidat terminál nám zobrazí editační okno, do kterého můžeme napsat svůj vlastní název, jak chceme aby se terminál jmenoval. Po aktivaci tlačítko, se nám původní tři tlačítka zakryjí a namísto nich se ukáží nové tři tlačítka Přidej terminál, Zpět a Resetovat, které dále slouží k následné manipulaci při tvorbě terminálů.

Tlačítko Resetovat, nám smaže aktuální hodnotu v editačním boxu a tlačítko Zpět nás vrátí do původního menu, kde jsme mohli editovat celou gramatiku. Pomocí tlačítka Přidej terminál se nám vytvoří terminál s názvem (hodnotou), kterou jsme napsali do zobrazeného editačního boxu a vytvoří nám nové tlačítko na panelu Terminálů.

Přidat neterminál

- toto tlačítko má stejnou funkčnost jako tlačítko Přidat terminál, akorát že manipuluje s množinou neterminálů

Vytvořit pravidlo

- po aktivaci tohoto tlačítka se nám zobrazí dva menší editační boxy, do kterých není povoleno zapisovat. Editace pravidla probíhá pomocí aktivací tlačítek námi

vytvořených terminálů a neterminálů. Podle Chomského rozdělení musí levá část pravidel obsahovat pouze jeden neterminál a pravá část může obsahovat zřetězení libovolné kombinace terminálů a neterminálů. Program sám kontroluje zda uživatel neporušuje pravidla Chomského hierarchie, takže se nemůže stát, že by uživatel vytvořil pravidlo gramatiky, které by nesplňovalo některé z dříve popsaných pravidel.

Editační pole nemohou být editovány pomocí vkládání textu, ale musí být vkládány pomocí tlačítek, vygenerovaných programem. Tímto se předejde výskytu možných chyb, které by mohli vzniknout manuálním opisováním pravidel.

Po úspěšném vytvoření pravidla (potvrzením pomocí nově objeveného tlačítka Přidej pravidlo), se nám ukáže nově vytvořené pravidlo v dolním části panelu, kde se zobrazují všechny pravidla. S každým nově vytvořeným pravidlem jsou vytvořeny i tři další funkční tlačítka, která slouží k manipulaci se samotným pravidlem.

Smazat

- slouží ke smazání příslušného pravidla, po aktivaci vás program vyzve ještě

k potvrzení, zda zvolené pravidlo chcete opravdu smazat, aby nedošlo k nežádoucímu smazání pravidla.

Editovat

- je tlačítko, pomocí kterého můžeme zvolené pravidlo měnit. Ukáže se shodný formulář v horní části panelu, podobný jako při tvorbě gramatiky, až na výjimku, že editační boxy jsou již vyplněny zvoleným pravidlem pro lepší přehlednost a

informovanost, které pravidlo uživatel skutečně mění. Pro úpravu postačí zmáčknout tlačítko Resetovat a navolit nové pravidlo.

Uložit

- po aktivaci tlačítka Editovat nám toto tlačítko slouží k uložení námi prováděných změn, které jsme provedli nad zadaným pravidlem gramatiky.

-

Kapitola 4

Popis funkčních modulů

4.1 Neprázdnost jazyka

Pomocí této funkce dokážeme zjistit, zda zadaná gramatika dokáže vygenerovat alespoň jedno slovo nad zadanou abecedou. V případě kladného zjištění program sdělí uživateli, že jazyk generovaný gramatikou není prázdný, v opačném případě program vypíše hlášení o tom, že z gramatiky nelze vyderivovat žádné slovo.

Předlohou pro tuto proceduru byl algoritmus na zjištění neprázdnosti gramatiky, pro ilustraci zde uvádím jeho kód.

Algoritmus 4.1. Je jazyk generovaný gramatiku neprázdný?

i := 0;

N0 := Ø;

repeat i := i + 1;

Ni := Ni-1 ∪ { A│A → α ∈ P, α ∈ ( Ni-1 ∪

Σ

)* } until Ni = Ni-1

Ne := Ni;

if S ∈ Ne then output(„ANO“) else output(„NE“)

Výsledkem této funkce je tedy množina Ne, která se dále využije při eliminaci nepoužitelných symbolů. Sama procedura má pouze informační charakter a množinu symbolů a pravidel gramatiky nijak neovlivňuje. Ke svému úspěšnému dokončení volá procedura funkci další funkce, které ji pomohou zjistit pravidla, která se dají přepsat na terminální řetězec. Pokud ano, tak jejich levou stranu uloží do množiny Ni a pokračuje dál v prohledávání.

Ni tedy vyjadřuje množinu terminálů, ze kterých můžeme v nejvýše i krocích vytvořit terminální řetězec. Pak tedy množina Ne vyjadřuje seznam všech neterminálů, ze kterých je možno vyderivovat terminální řetězec.

4.2 Eliminace nedosažitelných symbolů

Tato procedura má za úkol nalézt veškeré symboly X ∈ (N ∪

Σ), které se nevyskytují v žádné větné formě, tudíž takové neterminály a terminály pro které neexistuje způsob jak je pomocí pravidel vyderivovat z kořene gramatiky.

Algoritmus 4.2 Eliminace nedosažitelných symbolů

i := 0;

Vi := {S};

repeat

i := i + 1;

Vi := Vi-1 ∪ { X│∃A : (A → αXβ ∈ P ∩ A ∈ Vi-1} until Vi = Vi-1

Procedura v průběhu své činnosti postupně generuje množinu dosažitelných

neterminálů (V

i

). Výsledkem této funkce tedy je nový seznam pravidel eliminovaný o pravidla, do kterých se nemůžeme dostat z kořene gramatiky a množina symbolů, které se můžou vyskytnout na pravých stranách dosažitelných pravidel.

4.3 Eliminace nepoužitelných symbolů

Tato procedura využívá dvě předchozí funkce k tomu, aby za pomocí algoritmu 4.1

eliminovala všechny neterminály, které nemohou vygenerovat terminální řetězec a na takto vytvořenou gramatiku se aplikuje algoritmus 4.2.

Algoritmus 4.3 Eliminace nepoužitelných symbolů Použij algoritmus 4.1

Polož G = (N ∩ Ne,

Σ, P

1

, S

), kde P1 := P ∩ (Ne x (Ne ∪

Σ

)*) Použij algoritmus 4.2

Výstupem tohoto algoritmu je nová gramatika, která bude obsahovat pouze pravidla, které dokáží vygenerovat terminální řetězce a jsou dosažitelná z kořene gramatiky.

4.4 Eliminace ε-pravidel

Řekneme, že gramatika je bez ε-pravidel pokud neobsahuje žádné pravidlo tvaru A → ε.

Pokud nepatří prázdné slovo do jazyka generovaného gramatikou tak není žádoucí, aby gramatika obsahovala nějaké ε-pravidla. Pomocí algoritmu 4.4

Algoritmus 4.4 Eliminace ε-pravidel i := 0;

N0 := Ø;

repeat i := i + 1;

Ni := Ni-1 ∪ { A

∈

N│A →* ε}

until Ni = Ni-1

Ne = Ni

for all A → X1 … Xn do

přidej do P´všechna pravidla tvaru A → α1 … αn z P spl a) pokud Xi nenáleží Ne, pak αi = Xi

b) pokud Xi

∈

Ne, pak αi je buď Xi nebo ε c) ne všechna αi jsou ε

end for

if S

∈

Ne then přidej do P´ pravidla S´ → S a S´ → ε, kde S´ nenáleží N ∪

Σ, N := N

∪ S´

odstraníme veškerá ε-pravidla tak, že generujeme nová pravidla z pravidel, které obsahují nějaký neterminál přepsatelný na ε tak, že postupně vytváříme pravidla jako kombinace všech možností, které by mohly vzniknout, kdybychom namísto neterminálů z množiny Ne dosadili ε. Pokud S patří do množiny Ne musíme vytvořit nový neterminál S´, který nahradí původní kořen gramatiky a s ním přidáme nové pravidla S´ → S a S´ → ε.

4.5 Eliminace jednoduchých pravidel

Jednoduchá pravidla jsou pravidla tvaru A → B, taková pravidla nám nepřidávají do gramatiky žádnou funkčnost pouze nám můžou pomoci zpřehlednit gramatiku, avšak takové pravidla nejsou žádoucí, proto pomocí algoritmu 4.5

Algoritmus 4.5 Eliminace jednoduchých pravidel for all A ∈ N do

i := 0;

Ni := {A};

repeat

i := i + 1;

Ni := Ni-1 ∪ { C │B → C ∈ P, B ∈ Ni-1 } until Ni = Ni-1;

NA = Ni; end for

for all B → α ∈ P, které není jednoduché do

přidej do P pravidla A → α pro všechna A taková, že B ∈ NA

zkonstruujeme novou množinu pravidel, která upravuje původní množinu tak, že namísto pravidla A → B vytvoří množinu pravidel A → α, kde α jsou pravé strany pravidel B → α.

Vstupem tohoto algoritmu je gramatika bez ε-pravidel, proto při volání této procedury program nejdříve provede algoritmus 4.4, který odstraní veškerá ε-pravidla.

4.6 FIRST

Funkce FIRST, slouží k výpočt množiny terminálů, které se můžou vyskytnout na prvním místě při derivaci vstupního řetězce α, kde α náleží (N ∪ ∑)*.

Pro výpočet této funkce se zobrazí editační box v horní části panelu, kde opět pomocí tlačítek terminálních a neterminálních symbolů vložíme požadovaný řetězec, který chceme vyhodnotit.

4.7 FOLLOW

Funkce FOLLOW vrací množinu terminálů, které se můžou vyskytovat na prvním místě za zadaným neterminálem. Funkce FOLLOW má uvnitř algoritmu dva způsoby větvení v závislosti na tom, na jaké pozici v pravidle se vstupní neterminál vyskytuje.

- když se neterminál nachází na posledním místě pravé strany pravidla, volá funkce rekurzivně sama sebe, ale jako vstupní symbol vezme neterminál na levé straně pravidla

- když se neterminál nevyskytuje na posledním místě zavolá FOLLOW funkci FIRST, pro kterou bude vstupním řetězcem seznam symbolů, které se vyskytují za zvoleným neterminálem

Funkce FOLLOW má podobně jako FIRST pro své spuštění zobrazen editační box, kam opět pomocí využívání tlačítek neterminálních symbolů může uživatel zvolit požadovaný symbol.

Kapitola 5

Práce s externími soubory

Pro práci se soubory jsem využil zabudovaných modulů programu Borland Delphi, které nám umožňují jednoduchou a rychlou práci se soubory. Kvůli co nejmenšímu omezení uživatele ve volbě libovolných názvů pro jednotlivé terminály a neterminály jsem nastavil název

oddělovače jako -=> , který předpokládám nebude nikdy využit jako symbol gramatiky.

5.1 Formát souboru

Soubory, které aplikace využívá mají přípon *.gra a mají několik editačních pravidel, která musí uživatel dodržet, pokud bude chtít editovat gramatiku bez pomocí programu.

Soubor se skládá ze tří částí oddělených od sebe řádkem obsahujícím oddělovací znak --++--++--++--

V první části je seznam neterminálů. Na každý řádek se vkládá název jednoho neterminálů.

Struktura souborů byla navržena tak, aby co nejméně omezovala uživatele při volbě názvů symbolů gramatiky, ale i přesto se musí uživatel vyvarovat používání znaku { }, který slouží pro označení prázdného terminálu.

V druhé části za řádkem obsahujícím oddělovač se vyskytuje seznam terminálů, který je strukturován stejně jako neterminály, tedy na každém řádku je řetězec označující název terminálů a každý řádek znamená jeden terminál. Pro případ, že by měla gramatika obsahovat prázdný řetězec je potřeba napsat řádek neobsahující ani jeden znak. Tím program pozná, že se jedná skutečně o prázdný řetězec a podle toho pak nastaví pravidla gramatiky.

V třetí části, za dalším oddělovačem se nachází seznam pravidel napsaný v kódování podle pozice terminálů a neterminálů, konstrukce tohoto kódování umožní uživatelům využívat libovolnou kombinaci symbolů jako symboly gramatiky.

Terminály v pravidlech určujeme pomocí písmene T a čísla vyjadřující jeho pořadí v množině terminálů, takže například třetí terminál by byl v pravidle označen jako T3.

Neterminály jsou značeny podobně, akorát mají místo T písmeno N. Pravidla jsou pak sepsána pomocí tohoto kódu, kde namísto symbolu gramatiky (terminálu, neterminálu) vložíte toto kódové označení požadovaného symbolu. Abyste odlišili, levou a pravou stranu budete potřebovat použít druhý oddělovač -=> , který vložíte mezi levou a pravou stranu pravidla.

Opět platí zásada jedna položka na jeden řádek.

5.2 Manipulace se soubory

Jak bylo zmíněno v úvodu kapitoly, pro manipulaci se soubory jsem využil vestavěné moduly programovacího jazyka. Moduly při aktivaci otevřou všeobecně známe okno, obsahující základní vlastnosti pro procházení stromové struktury záznamových médií, vytváření nových adresářů, souborů apod.

Kapitola 6

Závěr

Vytvoření programu se skládalo z několika základních bodů. Prvním bodem bylo prostudovat detailně problematiku formálních jazyků. Druhým bylo najít nejčastěji používané algoritmy na úpravu bezkontextových gramatik. Samotná problematika formálních jazyků je poměrně rozsáhlá, proto jsem se zaměřil především na funkce, které by mohli mít vícepraktického využití.

V práci jsem vysvětlil základní problematiku formálních jazyků, objasnil jsem postupy pro tvorbu jednotlivých částí gramatiky a v neposlední řadě jsem popsal funkce, které umí

program nad zadanou gramatikou vypočítat, včetně výpisu jejich kódů pro lepší představivost.

Dále jsem pro každou funkci naznačil způsob jakým jsem konstruoval konkrétní algoritmus a případné technologie, které jsem při tom využil.

Pro ucelenost celého programu jsem naprogramoval i funkce pro práci se soubory, takže si uživatel může vytvořenou gramatiku uložit do externího souboru, ze kterého je potom může otevírat a dále nad nimi pracovat.

Kapitola 7

Použitá literatura

[1] Kozen, Dexter C. Automata and computability. New York : Springer, 1997. xiii, 400.

Undergraduate texts in computer science. ISBN 0-387-94907-0.

[2] Chytil, Michal. Automaty a gramatiky. Vyd. 1. Praha : SNTL - Nakladatelství technické literatury, 1984. 331 s. Matematický seminář SNTL, 19. Obsahuje bibliografii.

[3] Černá, I. Mojmír, K. Kučera, A. Učební text FI MU – Automaty a formální jazyky I, 2002

Kapitola 8

Přílohy

Přiložené CD obsahuje:

• zdrojové soubory programu

• text bakalářské práce ve formátu doc a pdf

• samotný program (Bakalarka.exe)