základů algoritmizace

Mendelova univerzita v Brně Provozně ekonomická fakulta

Punťa - vývojové prostředí pro výuku základů algoritmizace Diplomová práce

Vedoucí práce: Mgr. Tomáš Foltýnek, Ph.D.

Bc. Marek Fojtl

Brno 2010

zadání práce

Děkuji Mgr. Tomáši Foltýnkovi, Ph.D. za vedení a podporu při tvorbě této práce a umožnění nasazení vývojové verze aplikace do výuky. Chtěl bych dále poděkovat Mgr. Jitce Machalové, Ph.D., Ing. Miroslavu Ceplovi a vybraným studentům a studentkám předmětu Výpočetní technika a algoritmizace II (LS09/10) za cenné připomínky a testování aplikace.

Prohlašuji, že jsem tuto diplomovou práci vyřešil samostatně s použitím literatury uvedené v závěru práce.

V Brně dne 28. května 2010

....................................................

5

Abstract Fojtl M., Punťa - development environment for teaching of basic algorithms. Diploma thesis. Brno, 2010 This diploma thesis deals with construction of Punťa - new czech programming language and development environment for teaching of algorithms. A theoretical part discusses the meaning of a word algorithm, and important terms of programming language theory. A baseline analysis describes so far known products for teaching of algorithms. A solution consists in design and implementation Punťa language to its own development environment. Keywords algorithms, programming language, development environment, lexical analysis, syntactic analysis, semantic actions

Abstrakt Fojtl M., Punťa - vývojové prostředí pro výuku základů algoritmizace. Diplomová práce. Brno, 2010 Diplomová práce se zabývá tvorbou nového českého programovací jazyka a vývojového prostředí pro výuku algoritmizace - Punťa . V teoretické části rozebírá význam slova algoritmus a důležité pojmy z teorie programovacích jazyků. V analýze výchozího stavu jsou popsány dosud známé produkty pro výuku algoritmizice. Vlastní řešení spočívá v návrhu a implemenentaci jazyka Punťa do vlastního vývojového prostředí. Klíčová slova algoritmizace, programovací jazyk, vývojové prostředí, lexikální analýza, syntaktická analýza, sémantické akce

6

OBSAH

Obsah 1 Úvod a cíl práce 10 1.1 Úvod do problematiky . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2 Cíl práce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2 Teoretická východiska práce 2.1 Algoritmus . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1 Historická východiska . . . . . . . . . . . . . . . . . 2.1.2 Definice pojmu . . . . . . . . . . . . . . . . . . . . 2.1.3 Formalizace pojmu . . . . . . . . . . . . . . . . . . 2.1.4 Způsoby zápisu . . . . . . . . . . . . . . . . . . . . 2.1.5 Algoritmizace . . . . . . . . . . . . . . . . . . . . . 2.2 Programovací jazyky . . . . . . . . . . . . . . . . . . . . . 2.2.1 Prostředek pro zápis algoritmu . . . . . . . . . . . 2.2.2 Dělení programovacích jazyků . . . . . . . . . . . . 2.3 Formální jazyky a gramatiky . . . . . . . . . . . . . . . . . 2.3.1 Abeceda a jazyk . . . . . . . . . . . . . . . . . . . 2.3.2 Gramatika . . . . . . . . . . . . . . . . . . . . . . . 2.3.3 Chomského klasifikace gramatik . . . . . . . . . . . 2.4 Konečné automaty a jazyky typu 3 Chomského klasifikace 2.4.1 Nedeterministický konečný automat . . . . . . . . . 2.4.2 Deterministický konečný automat . . . . . . . . . . 2.4.3 Jazyky akceptované KA, konstrukce NKA . . . . . 2.4.4 Převod NKA na DKA . . . . . . . . . . . . . . . . 2.5 Bezkontextové jazyky a zásobníkový automat . . . . . . . 2.5.1 Bezkontextová gramatika . . . . . . . . . . . . . . . 2.5.2 Derivační stromy . . . . . . . . . . . . . . . . . . . 2.5.3 Rozklad věty . . . . . . . . . . . . . . . . . . . . . 2.5.4 Syntaktické diagramy . . . . . . . . . . . . . . . . . 2.5.5 Zásobníkový automat . . . . . . . . . . . . . . . . . 2.6 Deterministické bezkontextové jazyky . . . . . . . . . . . . 2.6.1 LL gramatiky . . . . . . . . . . . . . . . . . . . . . 2.6.2 Výpočet množin FIRST a FOLLOW . . . . . . . . 2.6.3 Syntaktická analýza LL(1) gramatiky . . . . . . . . 2.7 Sémantika . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12 12 12 12 13 14 14 15 15 15 17 17 17 19 21 21 22 22 23 24 24 24 25 25 26 27 28 28 29 30

7

OBSAH

3 Současný stav řešené problematiky 3.1 Pascal . . . . . . . . . . . . . . . . 3.2 Robot Karel . . . . . . . . . . . . . 3.3 Baltazar, Baltík, Baltie . . . . . . . 3.4 Petr . . . . . . . . . . . . . . . . . 3.5 Imagine Logo . . . . . . . . . . . . 3.6 Ostatní . . . . . . . . . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

4 Zvolená metodika a programové prostředky 4.1 Návrh lexikálního a syntaktického analyzátoru . . . . . 4.2 Návrh a implementace vývojového prostředí . . . . . . 4.3 Implementace lexikálního a syntaktického analyzátoru kých akcí do aplikace . . . . . . . . . . . . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

31 31 32 32 33 34 35

36 . . . . . . . . 36 . . . . . . . . 36 a sémantic. . . . . . . . 37

5 Vlastní práce 5.1 Obecné vlastnosti jazyka Punťa . . . . . . . . . . . . . . . . . . . . 5.2 Regulární gramatika lexikálního analyzátoru . . . . . . . . . . . . . 5.2.1 Abeceda jazyka . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.2 Gramatika jazyka čísel . . . . . . . . . . . . . . . . . . . . . 5.2.3 Gramatika jazyka přiřazení . . . . . . . . . . . . . . . . . . 5.2.4 Gramatika jazyka operátorů . . . . . . . . . . . . . . . . . . 5.2.5 Gramatika jazyka řetězců . . . . . . . . . . . . . . . . . . . 5.2.6 Gramatika jazyka znaků . . . . . . . . . . . . . . . . . . . . 5.2.7 Gramatika jazyka proměnných . . . . . . . . . . . . . . . . . 5.2.8 Gramatika jazyka klíčových slov . . . . . . . . . . . . . . . . 5.2.9 Gramatika ukončovacího znaku příkazu . . . . . . . . . . . . 5.2.10 Gramatika příkazových bloků . . . . . . . . . . . . . . . . . 5.2.11 Gramatika oddělovače parametrů a názvů proměnných . . . 5.2.12 Gramatika jazyka polí . . . . . . . . . . . . . . . . . . . . . 5.2.13 Gramatika bílých znaků . . . . . . . . . . . . . . . . . . . . 5.2.14 Gramatika komentářů . . . . . . . . . . . . . . . . . . . . . 5.2.15 Stanovení nevýznamových tokenů . . . . . . . . . . . . . . . 5.2.16 Stanovení významových tokenů . . . . . . . . . . . . . . . . 5.2.17 Zregularizovaný lexikální analyzátor . . . . . . . . . . . . . . 5.2.18 NKA a DKA . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Bezkontextová gramatika syntaktického analyzátoru . . . . . . . . . 5.3.1 Deterministická bezkontextová gramatika souboru s hlavním programem . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3.2 Deterministická bezkontextová gramatika modulu . . . . . .

. . . . . . . . . . . . . . . . . . . . .

38 38 38 38 38 39 39 40 40 40 41 41 42 42 42 42 43 43 44 44 45 45

. 46 . 48

8

OBSAH

5.4

5.5

5.6

5.3.3 Syntaktické diagramy . . . . . . . . . . . . . . . . . 5.3.4 Výpočet množin FIRST a FOLLOW . . . . . . . . 5.3.5 Zásobníkový automat . . . . . . . . . . . . . . . . . Vývojové prostředí . . . . . . . . . . . . . . . . . . . . . . 5.4.1 Návrh uživatelského rozhraní . . . . . . . . . . . . 5.4.2 Implementace uvítací obrazovky, editoru a console . 5.4.3 Funkce editoru . . . . . . . . . . . . . . . . . . . . 5.4.4 Zvýrazňovač syntaxe . . . . . . . . . . . . . . . . . Implementace lexikálního a syntaktického analyzátoru . . . 5.5.1 Lexikální analyzátor . . . . . . . . . . . . . . . . . 5.5.2 Syntaktický analyzátor . . . . . . . . . . . . . . . . Implementace sémantických akcí a popis příkazů . . . . . . 5.6.1 Sémantický procesor . . . . . . . . . . . . . . . . . 5.6.2 Datové typy a pole . . . . . . . . . . . . . . . . . . 5.6.3 Zpracování výrazů . . . . . . . . . . . . . . . . . . 5.6.4 Větvení . . . . . . . . . . . . . . . . . . . . . . . . 5.6.5 Cykly . . . . . . . . . . . . . . . . . . . . . . . . . 5.6.6 Matematické funkce . . . . . . . . . . . . . . . . . . 5.6.7 Standardní vstup a výstup . . . . . . . . . . . . . . 5.6.8 Práce s proměnnými typu Text . . . . . . . . . . . 5.6.9 Funkce definované uživatelem a globální proměnné 5.6.10 Práce s grafikou . . . . . . . . . . . . . . . . . . . . 5.6.11 Zpracování chyb . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

48 48 48 48 48 50 53 54 54 54 55 56 56 57 58 58 59 60 60 61 61 62 62

6 Diskuse

64

7 Závěr

68

8 Literatura

69

Přílohy

71

A Nedeterministický a deterministický konečný automat

72

B Syntaktické diagramy

73

C Výpočet množin FIRST a FOLLOW

82

D Zásobníkový automat

85

E Dotazník

86

OBSAH

F Ukázkový příklad

9 88

1

ÚVOD A CíL PRÁCE

1 1.1

10

Úvod a cíl práce Úvod do problematiky

Využití prostředků informačních technologií v našem běžném i pracovním životě zaznamenalo v posledních letech velký nárůst. Možnost zakoupení personálního počítače je dnes cenově dostupná každému. Díky tomu se otevřela další cesta pro programátory a vývojáře aplikací, kteří již v dnešní době nemusí své aplikace vyvíjet pouze pro úzkou a specializovanou skupinu lidí, ale i pro širokou veřejnost. Aby vývojář navrhl dobrý a správně fungující software, musí nastudovat moderní přístupy pro jeho tvorbu a také jednu ze základní činností řešení problémů - algoritmizaci. Někteří by se nyní mohli mylně domnívat, že cílem výuky algoritmizace je připravit budoucí programátory na jejich povolání a toto téma se ostatních vlastně netýká. Ale jejím cílem nemusí být nutně jen výchova nových programátorů. Jde o trénink mozku a logického myšlení a zdokonolování se v řešení různých problémů, které nás v životě čekají. Trénink mozku je přitom v dnešní době velmi důležitý. Trendem se totiž stává automatizace rutinních činností, kdy máme k dispozici různé softwarové aplikace a zařízení přemýšlející za nás. Mezi ně patří chytré mobilní telefony (smartphony) nebo informační systémy, které nám usnadňují práci. Lidé tak ztrácejí potřebu uvažovat a jejich schopnost řešit problémy klesá. Základním pojmem této činnosti je algoritmus, s jehož definicí se nejčastěji potkáte v podobě: „jednoznačný srozumitelný přesně specifikovaný postup (předpis) vedoucí v konečném počtu kroků k řešení určité úlohyÿ (Havelková, 2008), ale později bude vysvětleno, že za tímto pojmem se skrývá mnohem více než jen tato definice. Algoritmy můžeme zapisovat různě. Slovem, matematicky, graficky a nebo programovacím jazykem. Je jasné, že nejvhodnější zápis, kterému počítač rozumí je programovací jazyk, ale i ten se musí přeložit do tzv. strojového kódu, kterému počítač, respektive jeho operační systém, teprve plně porozumí. Jazyk tedy není pouze nástroj pro dorozumívání lidí mezi sebou, ale slouží i ke komunikaci s počítačem, jehož forma stejně jako u lidského jazyka má svá pravidla a ta se musí dodržovat. Drtivá většina programovacích jazyků disponuje pouze angličtinou a ta může být pro české uživatele problémem, přitom čeština je jazyk unikátní, bohatý, různorodý a krásný a z těchto dvou důvodů vznikla myšlenka ulehčit výuku algoritmizace právě návrhem a implementováním nového programovacího jazyka s českou syntaxí a vlastním vývojovým prostředím.

1.2

1.2

Cíl práce

11

Cíl práce

Tato práce si klade za cíl navrhnout a implementovat zcela nový interpretovaný programovací jazyk s jednoduchou českou syntaxí vhodný pro výuku algoritmizace a vytvořit pro něj takové vývojové prostředí, jehož ovládání bude jednoduché i pro úplné začátečníky. Cíle bude dosaženo postupně ve dvou fázích. V první fázi dojde k navržení regulární gramatiky lexikálního analyzátoru a sestavení deterministického konečného automatu společně s návrhem bezkontextové gramatiky syntaktického analyzátoru a sestavením zásobníkového automatu. V druhé fázi bude proveden návrh a implementace vlastního vývojového prostředí včetně zakomponování lexikálního a syntaktického analyzátoru a implementace sémantických akcí.

2

TEORETICKÁ VÝCHODISKA PRÁCE

2 2.1 2.1.1

12

Teoretická východiska práce Algoritmus Historická východiska

Historie vzniku tohoto pojmu je celkem spletitá. Jak uvádí Donald E. Knuth (2008), vyvinulo se ze slova algorism, které vzniklo ve středověku a jehož původní význam zněl: „provádění aritmetických výpočtů s arabskými číslicemiÿ (Knuth, 2008), ale historikové matematiky však nakonec objevili skutečný původ, který pocházel ze jména perského matematika 9. století Abu Jafar Muhammada ibn Musa alChwarizmího, autora slavného arabského matematického textu Kitab al-jabr wa’lmuqabala („Pravidla pro odvozování a srovnáváníÿ). (Knuth, 2008) Od původního slova algorism došlo v průběhu vývoje k několika odklonům a přeměnám, které dospěly až do jeho finální fáze, která se používá do dnes. Největší podíl na tom nese záměna arabského kořene s kořenem řeckého slova arithmos a díky tomu se z algorismu stal algoritmus. (www.manualy.net, 2006) 2.1.2

Definice pojmu

Význam slova algoritmus má hodně synonym. Mezi nejčastěji používané se řadí recept, metoda, technika, procedura nebo postup. Ale jak bylo řečeno již v úvodu, za tímto pojmem se skrývá mnohem více. Algoritmus je „konečnou množinou pravidel, která popisují posloupnost operací pro řešení jistého typu problémuÿ (Knuth, 2008) a musí splňovat 5 důležitých vlastností: 1. Konečnost. Každý algoritmus musí mít konečný počet kroků a po jejich vykonání musí skončit. Procedura, která splňuje všechny vlastnosti algoritmu, ale není konečná, se nazývá výpočetní metoda. 2. Určitost. Každý krok algoritmu musí být jednoznačně definován a za všech okolností musí být vždy jasné, co a jak se má provést. Prováděné operace musí být popsány s jednoznačností a určitostí. 3. Vstup. Algoritmus může mít jeden a více vstupů, ale také nemusí mít žádný. Jsou to veličiny zadávané do algoritmu před jeho zahájením nebo dynamicky zadávané během průběhu algoritmu. Vstupy jsou přebírány z určité množiny objektů. 4. Výstup. Algoritmus má jeden či více výstupů, což jsou veličiny, které jsou dány vztahem ke vstupům.

2.1

Algoritmus

13

5. Efektivnost. Každý algoritmus by měl být efektivní, což znamená, že všechny jeho operace musí být v rozumné míře jednoduché a jejich řešení by mělo být proveditelné i s pomocí tužky a papíru. (Knuth, 2008) Na základě Dvorského (2007) lze výše uvedené vlastnosti rozšířit o opakovatelnost (stejné vstupy musí poskytovat stejné výsledky) a rezultivnost (algoritmus poskytuje správné výsledky). (Dvorský, 2007) 2.1.3

Formalizace pojmu

Nyní vyvstává otázka, jak rozlišit, zda-li na řešený problém algoritmus existuje či nikoliv. Dříve, než bude zodpovězena, je třeba objasnit pojem Turingův stroj. Černá, Křetínský a Kučera (2002) popisují Turingův stroj jako stroj sestrojený Alanem Turingem1 s konečnou množinou stavů Q, páskou rozdělenou na jednotlivá políčka a hlavou pohybující se po pásce doleva a doprava, čímž je umožněno čtení a zápis symbolů. Na každém políčku je zapsán právě jeden páskový nebo pracovní symbol náležící do konečné množiny symbolů. Páska je jednosměrná a nekonečná. Na nultém políčku (vlevo) je zapsán speciální symbol, kterému se říká startovací a označuje levý konec pásky. (Černá, Křetínský, Kučera, 2002) Odpověď na výše uvedenou otázku poskytuje Churchova2 teze (či též jako Church-Turingova teze): „Každý proces, který lze intuitivně nazvat algoritmem, se dá realizovat na Turingově stroji.ÿ (Černá, Křetínský, Kučera, 2002) Churchova teze nám tedy dává do souvislosti pojmy algoritmicky řešitelný a řešitelný Turingovým strojem a ztotožňuje je. Obsah Churchovy teze nelze formálně dokázat, protože pojem algoritmicky řešitelný je pouze intuitivní pojem. Černá, Křetínský a Kučera (2002) však také uvádějí, že existují další systémy, které potvrzují platnost teze a jsou, co se výpočetní síly týče, ekvivaletní s Turingovým strojem. Jmenovat lze Postovy systémy, Minského stroje, µ-rekurzivní funkce, λ-kalkul a while programy. Navíc dosud nebyl nalezen algoritmus, který by na Turingově stroji nešel sestavit. Na základě těchto faktů, lze považovat tezy za platnou. (Černá, Křetínský, Kučera, 2002) 1

Alan Turing - matematik, který v roce 1936 definoval jeden z dosud nejsilnějších výpočetních modelů - Turingův stroj (Černá, Křetínský, Kučera, 2002) 2 Alonzo Church - americký matematik a profesor na Princestonské univerzitě, mezi jeho studenty patřil i Alan Turing (World of Mathematics Biography, 2006)

2.1

Algoritmus

2.1.4

14

Způsoby zápisu

Algoritmus lze zapsat několika způsoby: • slovním popisem – využití přirozeného jazyka jako prostředek zápisu algoritmu • vývojovým diagramem – pomocí jednotných značek a zkratek graficky zobrazený algoritmus řešení úlohy • strukturogramy – opět se jedná o grafické zobrazení splňující podmínky pro strukturované programování, které používá obdobné symboly jako při znázornění vývojovým diagramem • datově orientované diagramy HIPO (Hierarchy plus Input-ProcessOutput) - forma zápisu, kdy je graficky vyjádřeno funkční členění problému, struktury dat a postupu řešení problému při různém stupni podrobnosti • rozhodovací tabulky – používají se při velmi složitých větveních (www.manualy.net, 2006) • pseudokódem - kombinace kódu a přirozeného jazyka • programovacím jazykem - využití některého z dostupných programovacích jazyků k zápisu algoritmů (Beránek, 2008) 2.1.5

Algoritmizace

Algoritmizace je postup, který se uplatňuje při tvorbě programu pro počítač a pomocí kterého lze prostřednictvím algoritmu řešit daný problém. (Diviš) Tento postup lze rozdělit do několika etap: 1. Formulace problému - formulace požadavků, určení výchozích hodnot, požadovaných výsledků, jejich formu a přesnost měření 2. Analýza úlohy - ověření, zda je úloha řešitelná a vytvoření první představy o jejím řešení, zjištění zda výchozí hodnoty jsou k řešení postačující, zda má úloha více řešení a výběr nejvhodnějšího řešení 3. Vytvoření algoritmu - sestavení jednoznačného sledu jednotlivých operací pro správné vyřešení úlohy a je třeba mít na paměti, že algoritmus nedává přímo odpověď na řešený problém, ale postup, jak ji získat 4. Sestavení programu - sestavení programu na základě navrženého algoritmu v určitém programovacím jazyce a provedení překladu nebo intepretace programu

2.2

Programovací jazyky

15

5. Odladění programu - odstranění syntaktických (odhalí překladač) a sémantických chyb (musí odhalit člověk na základě získaných chybných výsledků nebo nekorektním chováním programu při určitých činnostech) (Diviš)

2.2 2.2.1

Programovací jazyky Prostředek pro zápis algoritmu

Chceme-li docílit nahrazení člověka při realizaci algoritmu počítačem, je potřeba zvolit takovou formu zápisu algoritmu, které počítač plně rozumí. Přirozený jazyk ani vývojové diagramy tuto podmínku nesplňují. Jediný jazyk, kterému počítače rozumí se nazývá strojový kód. Strojový kód je jazyk primitivní a umožňuje zapsat pouze ty nejzákladnější operace, které se nazývají strojové instrukce (např. aritmetické operace, porovnání dvou hodnot, skok aj.), zapsané v binárním tvaru. Značnou nevýhodou tohoto způsobu zápisu algoritmu je pracnost a nepřehlednost, a proto se k praktickému zápisu algoritmů příliš nehodí. Z těchto důvodů vznikají programovací jazyky, které nejsou sice pro počítač přímo srozumitelné, ale pomocí speciálního programu - tzv. překladače - je lze do strojového kódu přeložit. (Častorál, 1991) 2.2.2

Dělení programovacích jazyků

Programovací jazyky lze dělit dle nejrůznějších kritérií. Jak uvádí Josef Kadlec (2004), za nejobecnější rozdělení se dá považovat rozlišení na nižší a vyšší. Nižší programovací jazyky se vyznačují využíváním přímo příkazů procesoru. K velké výhodě těchto jazyků patří maximálně optimalizovaný program pro zvolenou platformu a vyšší rychlost při provádění programu. Mezi další výhody patří minimální omezení při programování a možnost využívat všechny funkce zařízení. Nevýhoda spočívá v nepřenositelnosti programu na jiný druh procesoru, který tyto instrukce nezná. Další vlastností, na základě které nelze k zápisu algoritmů nižší jazyky doporučit, je jistá nepohodlnost při psaní programu (větší rozsah kódu než u vyšších programovacích jazyků). Skupina nižších jazyků není příliš početná, patří sem zejména jazyk symbolických adres a strojový kód. Vyšší programovací jazyky tvoří mnohem početnější skupinu. Řadí se sem jazyky, které jsou pro člověka čitelnější a mají logicky uspořádaný kód. Pro zápis algoritmů jsou tedy lepším nástrojem. Tato skupina není závislá na strojových principech počítače. Na rozdíl od nižších programovacích jazyků se zde může stát, že některé věci, vyžadující např. přímou adresaci zařízení, zde nepůjdou zhotovit. V těchto případech musíme tuto část kódu nahradit tzv. inline vložením kódu z nižšího progra-

2.2

Programovací jazyky

16

movacího jazyku (pokud to překladač dovoluje). Mezi vyšší patří prakticky všechny ostatní jazyky (C, C++, Java, Perl, Php, Python, atd.). (Kadlec, 2004) Dalším kritériem, podle kterého můžeme jazyky rozdělit, je na interpretované a kompilované. Hlavní rozdíl spočívá ve zpracovávání zdrojového kódu. Zatímco jazyky kompilované překládají kód do spustitelné formy, kód psaný v jazyku intepretovaném potřebuje ke svému spuštění tzv. interpret, který zpracovává jednotlivé příkazy a ihned je vykonává. Zdeněk Častorál (1991) i Josef Kadlec (2004) spatřují výhody kompilovaných jazyků zejména v rychlosti provádění programu, která je několikanásobně vyšší než u jazyků interpretovaných. Největší výhodu interpretovaných jazyků vidí Častorál (1991) v pohodlném testování programu, kdy po opravě chyby v kódu lze ihned provést výpočet, zatímco Kadlec (2004) spíše vyzdvihuje fakt, že u většiny interpretovaných jazyků není nutné deklarovat proměnné, velikost paměti, kterou mají proměnné zabírat, apod. Mezi interpretované jazyky patří např. Php, Perl, Python nebo Java. Do skupiny kompilovaných řadíme např. C++, Pascal nebo Visual Basic. (Kadlec, 2004) Další dělení jazyků může probíhat na základě přístupu k řešení problému a to na procedurální a funkcionální. V procedurálních (imperativních) jazycích se využívá postupu, jak se má daná úloha (vy)řešit, tedy využívá se algoritmu. V jazycích funkcionálních se nevyjadřuje, jak daný problém řešit, nýbrž co chceme řešit. (Kadlec, 2004) Jak uvádí Dosedla (2006), celý program je v tomto případě chápán jako funkce, jejímž výsledkem je výraz. Základem je výpočtový model λ-kalkul3 . Příkladem funkcionálních jazyků je např. LISP nebo Haskell. Procedurální jazyky lze rozdělit z hlediska přístupu tvorby programu na strukturované a objektové. Strukturovaný přístup je založen na principu rozdělení algoritmu na podproblémy implementované pomocí strukturovaných datových typů a řídících struktur (posloupnost příkazů, větvení, cykly). Do jazyků se strukturovaným přístupem se řadí např. jazyk C nebo Pascal. Objektově orientované jazyky jsou založeny na objektech a vztazích mezi nimi. Základem je třída, z které vzniká objekt jakožto instance třídy. Mezi objektově orientované jazyky patří např. Java nebo Smalltalk. Některé jazyky umožňují kombinovat jak objektový, tak strukturovaný přístup. Mezi ně se řadí např. jazyk C++. (Dosedla, 2006) 3

λ-kalkul - „teorie funkcí založená na velmi jednoduchém jazyce. Základní prvky tohoto jazyka (tzv. lambda výrazy) jsou pouze tři: proměnná, aplikace a abstrakceÿ (Beneš, 2006)

2.3

Formální jazyky a gramatiky

2.3 2.3.1

17

Formální jazyky a gramatiky Abeceda a jazyk

Abecedou se rozumí neprázdná konečná množina prvků, které se nazývají symboly abecedy. Každá konečná posloupnost symbolů abecedy se nazývá řetězec (též slovo nebo věta). Formální definice řetězce podle Češky (2002) nad abecedou Σ zní: 1. Prázdný řetězec je řetězec nad abecedou Σ. 2. Je-li x řetězec nad Σ a a ∈ Σ, pak i xa ∈ Σ. 3. y je řetězec nad Σ, tehdy a jen tehdy když lze y získat pomocí aplikace pravidel 1 a 2. Konkatenací (zřetězením) se nazývá taková operace, kdy spojením řetězce x ∈ Σ a y ∈ Σ vznike řetězec xy. Operace konkatenace je asociativní, tzn. x(yz) = (xy)z, ale není komutativní, protože xy 6= yx. Nechť existuje řetězec x = a1 a2 . . . an nad abecedou Σ, ai ∈ Σ pro i = 1, . . . , n. Zápis symbolů v opačném pořadí vzhledem k řetězci x se nazývá reverzí (zrcadlovým obrazem), kdy xR = an an−1 . . . a2 a1 . Nechť w je řetězec nad abecedou Σ. Podřetězcem w se nazývá takový řetězec z, pro který při existenci řetězců x a y platí, že w = xzy. Prefixem řetězce w nazýváme takový řetězec x1 , pro který při existenci řetězce y1 platí, že w = x1 y1 . Pak se tedy analogicky sufixem řetězce w nazývá takový řetězec x2 , pro který při existenci řetězce y2 platí, že w = y2 x2 . Délkou řetězce se rozumí nezáporné číslo udávající počet symbolů řetězce. Délka řetězce x se značí |x|. Máme-li x = a1 a2 . . . an , ai ∈ Σ pro i = 1, . . . , n, pak platí |x| = n. Pro prázdný řetězec je délka řetězce nulová, tj. || = 0. Jazykem L názýváme takovou množinu L, pro kterou platí: L ⊆ Σ∗ nebo L ⊆ Σ+ , kde Σ∗ je množina všech řetězců nad abecedou Σ včetně prázdného řetězce a Σ+ množina všech řetězců nad abecedou Σ vyjma prázdného řetězce. Z toho tedy plyne, že jazyk je libovolná podmožina řetězců nad danou abecedou. (Češka, 2002) 2.3.2

Gramatika

Gramatika je nejznámější prostředek pro reprezentaci jazyků. Pokud bychom chtěli použít triviálnější způsob reprezentace, museli bychom vytvořit výčet všech vět ja-

2.3

18


zyka. Tento způsob je však nepoužitelný pro nekonečné jazyky4 a prakticky i pro rozsáhlé konečné jazyky5 . Gramatika splňuje základní požadavek kladený na reprezentaci konečných i nekonečných jazyků, který spočívá v konečnosti reprezentace. Používá konečných množin N - nonterminálních a Σ - terminálních symbolů, které jsou vzájemně disjunktní. Nonterminální symboly (nonterminály) slouží jako pomocné symboly označující syntaktické celky, zatímco množina terminálních symbolů (terminálů) je identická s abecedou, nad níž je definován jazyk. Jestliže provedeme sjednocení množin, tj. N ∪ Σ, získáváme slovník gramatiky. Základem každé gramatiky je konečná množina přepisovacích pravidel P . Pravidla tvoří uspořádanou dvojici řetězců (α, β), kde β představuje možnou substituci řetězce α, který značí podřetězec generovaného řetězce. Řetězec α obsahuje vždy alespoň jeden nonterminální symbol (kdyby neobsahoval, nebyla by možná substituce) a řetězec β patří do množiny (N ∪ Σ)∗ . Množinu přepisovacích pravidel P pak lze formálně vyjádřit pomocí kartézského součinu: (N ∪ Σ)∗ N (N ∪ Σ)∗ × (N ∪ Σ)∗ Gramatiku G lze tedy na základě předchozích poznatků definovat jako čtveřici G = (N, Σ, P, S), kde • • • •

N je konečná množina nonterminálních symbolů, Σ je konečná množina terminálních symbolů, platí, že N ∩ Σ = 0, P je konečná podmožina kartézského součinu (N ∪ Σ)∗ N (N ∪ Σ)∗ ×(N ∪ Σ)∗ , S ∈ N je startovací symbol gramatiky.

Uspořádaná dvojice (α, β), která je prvkem množiny P, se nazývá přepisovacím pravidlem a zapisuje se ve tvaru (α → β). Řetězec α představuje levou stranu přepisovacího pravidla, řetězec β pak pravou stranu. Nechť existují řetězce λ a µ, kde λ, µ ∈ (N ∪ Σ)∗ . Relace ⇒G se nazývá přímou derivac, jestliže lze řetězce λ a µ vyjádřit jako: λ = γαδ µ = γβδ 4 5

obsahují nekonečný počet slov (Černá, Křetínský, Kučera, 2002) obsahují konečný počet slov(Černá, Křetínský, Kučera, 2002)

2.3


19

kde γ, δ ∈ (N ∪ Σ)∗ a α → β ∈ P . Relace ⇒+ se nazývá derivací, jestliže existuje taková posloupnost přímých derivací υi−1 ⇒ υi , i = 1, . . . , n a n ≥ 1, že platí: λ = υ0 ⇒ υ1 ⇒ . . . ⇒ υn−1 ⇒ υn = µ Nechť existuje řetězec ϕ ∈ (N ∪ Σ)∗ . ϕ se nazývá větnou formou, jestliže platí S ⇒∗ ϕ (řetězec ϕ se generuje ze startovacího symbolu S). Větou se nazývá taková větná forma, která obsahuje pouze terminální symboly. Jazyk L(G), tedy jazyk produkovaný gramatikou G, je definován množinou všech vět: L(G) = {w|S ⇒∗ w ∧ w ∈ Σ∗ } Gramatika tedy znázorňuje generativní systém, kdy pomocí aplikace tzv. přepisovacích pravidel lze z vyznačeného nonterminálu generovat řetězce tvořené pouze terminálními symboly. Tyto řetězce představují věty definované gramatikou jazyka. (Češka, 2002) 2.3.3

Chomského klasifikace gramatik

Noam Chomský6 vymezil čtyři typy gramatik, které se liší tvarem přepisovacích pravidel, jež jsou obsaženy v množině přepisovacích pravidel P . Označují se typ 0, typ 1, typ 2 a typ 3. Češka (2002) tato pravidla rozvádí následujícím způsobem: Typ 0 Gramatika tohoto typu obsahuje nejobecnější tvar pravidel, který je shodný s definicí gramatiky popsané v předchozí sekci: α → β, α ∈ (N ∪ Σ)∗ N (N ∪ Σ)∗ × (N ∪ Σ)∗ Z definice je patrné, že zde neexistují žádná omezení, proto se gramatiky typu 0 nazývají take neomezenými. 6

Noam Chomský - americký lingvista, díky němuž vznikla teorie generativní gramatiky, kterou byla ovlivněna (nejen) americká teorie lingvistiky ve 20. století (Szabó, 2004)

2.3


20

Typ 1 Gramatika typu 1 umožňuje vytvářet pravidla tvaru: αAβ → αγβ, A ∈ N, α, β ∈ (N ∪ Σ)∗ , γ ∈ (N ∪ Σ)+ nebo S → Tento typ se nazývá gramatika kontextová, protože svým tvarem pravidla udává, že k nahrazení nonterminálu A řetězcem γ může dojít tehdy a jen tehdy, pokud jeho pravým kontextem je řetězec β a levým kontextem řetězec α. Kontextové gramatiky nepřipouštějí nahrazení nonterminálu prázdným řetězcem. Výjimku tvoří startovací pravidlo S, které umožňuje prázdný řetězec do jazyka zařadit. V tomto případě se ale symbol S pak už nesmí vyskytnout na pravé straně přepisovacího pravidla. Typ 2 Gramatika typu 2 umožňuje vytvářet pravidla tvaru: A → γ, A ∈ N, γ ∈ (N ∪ Σ)∗ Tento typ gramatiky se nazývá bezkontextová gramatika, poněvadž lze provádět substituci řetězce γ za nonterminál A bez ohledu na kontext, ve kterém je nonterminál A zapsán. Na rozdíl od gramatik typu 1, bezkontextové gramatiky umožňují zápis pravidla ve tvar A → . I zde ale platí, existuje-li S → , pak se S nesmí vyskytovat na pravé straně žádného pravidla. Typ 3 Gramatika typu 3 umožňuje vytvářet pravidla tvaru: A → xB nebo A → x; A, B ∈ N, x ∈ Σ∗ Tento typ gramatiky se nazývá pravá lineární gramatika, poněvadž na pravé straně pravidla se může vyskytovat jediný nonterminál a ten musí být umístěn navíc úplně poslední, tedy vpravo na konci řetězce. Speciální případ pravé lineární gramatiky je regulární gramatika (přesněji regulární pravá gramatika), která se zapisuje ve tvaru:

2.4

Konečné automaty a jazyky typu 3 Chomského klasifikace

21

A → aB nebo A → a; A, B ∈ N, a ∈ Σ nebo S → a z tohoto důvodu jsou gramatiky typu 3 nazývány regulárními gramatikami. Kromě pravých lineárních gramatik existují i levé lineární gramatiky. Jak uvádějí Šorm, Rybička a Haluza (2006), v tomto případě je nonterminál pravé strany umístěn jako první a pravidla se zapisují ve tvaru: A → Ba nebo A → a; A, B ∈ N, a ∈ Σ∗ Jazykem typu i, i = 0, 1, 2, 3 nazýváme jazyk generovaný příslušnou gramatikou typu i. Dle tohoto označení pak podobně jako o gramatikách mluvíme o jazycích neomezených (i = 0), kontextových (i = 1), bezkontextových (i = 2) a regulárních (i = 3).

2.4


Konečný automat (dále jen KA) patří mezi abstraktní modely s konečným počtem stavů, které lze využít pro modelování systémů. Pracuje v diskrétním čase a aktuální stav se mění na základě vnějšího podnětu, přičemž je pro daný stav a podnět určeno, do kterého stavu systém přejde. KA se obecně dělí na deterministické a nedeterministické. Deterministické se vyznačují jednoznačností, zatímco nedeterministické tuto vlastnost nemají. (Dostál, 2008) 2.4.1

Nedeterministický konečný automat

Nedeterministický KA (dále jen NKA) je definován jako 5-tice M = (Q, Σ, δ, q0 , F ), kde: • Q - konečná množina stavů, • Σ - konečná vstupní abeceda, • δ - funkce přechodu - zobrazení Q × Σ → 2Q (2Q je množina podmnožin mnnožiny), • q0 ∈ Q - počáteční stav, • F ⊆ Q - množina koncových stavů Činnost konečného automatu M lze charakterizovat jako přechod z jednoho stavu do druhého. Tento přechod řídí funkce přechodu δ, která zpracovává symboly

2.4


22

čtené ze vstupního řetězce. Na základě aktuálního stavu qi a přečteného symbolu a ∈ Σ pak funkce přechodu vyhodnotí, do kterého stavu qj automat přejde. Počet stavů, do kterých lze v té chvíli přejít, může být i více než jeden. Přechodová funkce tedy v případě NKA předepisuje množinu budoucích stavů Qj , kde Qj ∈ 2Q . Přechodová funkce se zapisuje v tabulkové formě, kde řádky reprezentují množinu stavů Q a sloupce symboly abecedy. (Češka, 2002) Konfigurací automatu M se nazývá taková dvojice C = (q, w), pro kterou platí C ∈ Q × Σ∗ . Je popsána tedy stavem, ve kterém se automat právě nachází a dosud nepřečtenou částí řetězce. (Češka, 2002) Konfigurace ve tvaru (q0 , w) označuje počáteční konfiguraci a (qF , ), qF ∈ F označuje konfiguraci koncovou (automat akceptuje řetězec). Přechod je definován jako relace na množině konfigurací a značí se `. Celou činnost automatu lze tedy popsat jako posloupnost konfigurací značící přechod z počáteční do koncové neboli (q0 , w) `∗ (qF , ). Uskutečnění přechodu z konfigurace (qi , ax) do konfigurace (qj , x) je možné pouze tehdy, je-li δ(qi , a) = {. . . , qj , . . .}. (Šorm, Rybička, Haluza, 2006) 2.4.2

Deterministický konečný automat

Deterministický KA (dále jen DKA) je definován stejně jako NKA, rozdíl však spočívá v definici funkce přechodu δ. V případě DKA se δ definuje jako zobrazení Q × Σ → Q a předepisuje pouze jediný budoucí stav qj . 2.4.3

Jazyky akceptované KA, konstrukce NKA

Mezi jazyky, které jsou akceptovány KA, patří jazyky typu 3 Chomského klasifikace7 . Nejprve je nutné převést pravou lineární gramatiku na regulární. Tohoto cíle dosáhneme následovně: 1. všechna pravidla ve tvaru A → wB převedeme na řetězec pravidel A → a1 A1 , A1 → a2 A2 , . . . , An−1 → an B, kde w = a1 a2 . . . an 2. najdeme a případně odstraníme -pravidla (A → ) 3. najdeme a případně odstraníme jednoduchá pravidla typu A → B Podobný princip funguje i u levých lineárních gramatik8 . 7

Důkaz tohoto tvrzení lze nalézt v publikaci (Češka, 2002) V této práci není nutné dále rozvádět, protože implementační část výchází z pravých lineárních gramatik. Více informací o převodu levých lineární gramatik se lze dočíst v (Češka, 2002) 8

2.4


23

Takto sestavenou regulární gramatiku lze převést na NKA dle následujících pravidel (Šorm, Rybička, Haluza, 2006): Nechť existuje gramatika G = (N, Σ, P, S). Na základě této gramatiky vytvoříme automat M = (Q, Σ, δ, qS , F ) takový, že platí LG = LM : • Q = N ∪ {qF } – stavy automatu jsou vytvořeny z nonterminálů gramatiky a k nim je přidán stav qF , který představuje koncový stav. Stavy se označují písmenem q s indexem v podobě odpovídajícího nonterminálu gramatiky • abeceda automatu je identická s abecedou gramatiky, • přechodovu funkci vytváříme na základě pravidel gramatiky; je-li A → aB ∈ P , pak δ(qA , a) obsahuje qB . Je-li A → a ∈ P , pak δ(qA , a) obsahuje qF , • za počáteční stav automatu označíme qS , což je stav odpovídající startovacímu nonterminálu gramatiky S, • prvek qF musí být vždy obsažen v množině koncových stavů F; existuje-li však pravidlo S → ∈ P , počáteční stav automatu považujeme také za koncový a platí F = {qF , qS } 2.4.4

Převod NKA na DKA

Z popisu konečných automatů plyne, že praktická implementace NKA by byla velice náročná, protože by se muselo procházet všemi směry, jelikož dopředu není jasné, který je správný. Proto je mnohem výhodnější implementovat DKA. U návrhu NKA a DKA to platí zase obráceně. DKA je mnohem náročnější na svůj návrh než NKA. V tomto případě ale existuje velice důležitý poznatek o vztahu mezi NKA a DKA, který zní: Každý NKA lze převést na ekvivaletní DKA9 . Nejprve tedy provedeme návrh NKA, převedeme na DKA a implementujeme. Princip převodu NKA na DKA spočívá v rozšíření původní množiny Q takovým způsobem, že několik původních stavů vytvoří jeden nový. Tento nově vzniklý stav přebírá vazby a vlastnosti stavů, z kterých byl vytvořen. Tento postup se používá na místech, kde výsledek přechodové funkce není jednoznačný stav, nýbrž množina stavů. Jestliže i po vytvoření kompozitního stavu vznikne opět nedeterministická množina, postup znovu opakujeme a spojením vytvoříme stav nový. Postup opaku9

Více informací o vztahu DKA a NKA se lze dočíst v (Češka, 2002)

2.5

Bezkontextové jazyky a zásobníkový automat

24

jeme do té doby, dokud se v přechodové funkci nalézá na některém místě nedeterministická množina. (Šorm, Rybička, Haluza, 2006)

2.5 2.5.1

Bezkontextové jazyky a zásobníkový automat Bezkontextová gramatika

Bezkontextové gramatiky a jazyky mají dva důležité významy. Prvním z nich je fakt, že jsme s nimi schopni popsat většinu rysů současných jak programovacích (Češka, 2002), tak i komunikačních jazyků. (Šorm, Rybička, Haluza, 2006) Druhým důležitým významem je existence algoritmů, které dokáží analyzovat věty bezkontextových jazyků. Tyto algoritmy jsou uplatňovány zejména v základech překladačů, přesněji v syntaktických analyzátorech. Bezkontextová gramatika G je definována jako čtvečice G = (N, Σ, P, S), kde: • N je konečná množina nonterminálů, • Σ je konečná množina terminálů, • P je konečná množina přepisovacích pravidel, které se zapisují ve tvaru A → α, A ∈ N a α ∈ (N ∪ Σ)∗ , • S je výchozí nonterminální symbol 2.5.2

Derivační stromy

Derivační (syntaktický) strom10 je důležitým prostředkem pro grafické vyjádření struktury věty (její derivace). Při generování věty hovoříme o tzv. levé derivaci v případech, kdy je systematicky přepisován nejlevější nonterminální symbol nebo pravé derivaci, kdy je naopak přepisován nejpravější nonterminální symbol. O jednoznačném jazyce hovoříme tehdy, jestliže ke každé větě existuje právě jeden derivační strom. Každá věta generovaná gramatikou jednoznačného jazyka má vždy právě jednu (levou) pravou derivaci. Existuje-li k větě derivačních stromů více, jazyk se nazývá víceznačný11 .(Šorm, Rybička, Haluza, 2006) 10

strom - orientovaný acyklický graf, pro který platí, že má jeden uzel, do něhož nevstupuje žádná hrana (tzv. kořen stromu) a do všech ostatních uzlů pak vstupuje hrana pouze jedna; uzly z nichž žádná hrana nevystupuje se nazývají uzly (listy) stromu (Češka, 2002) 11 např. podmíněný příkaz if-then-else umožňuje konstrukci dvou derivačních stromů; více se lze dočíst v (Češka, 2002)

2.5


25

Obr. 1: Ukázka derivačního stromu, (Češka, 2002)

2.5.3

Rozklad věty

Syntaktickou analýzou neboli rozkladem věty se nazývá proces, při kterém se vytváří derivační strom pro danou větu nebo větnou formu. Program, který tuto činnost vykonává se nazývá syntaktický analyzátor (angl. parser). Konstrukce derivačního stromu využívá dvě metody: • syntaktickou analýzu shora dolů • syntaktickou analýzu zdola nahoru Syntaktická analýza shora dolů začíná vytvářet derivační strom od výchozího symbolu (kořene) a přes postupné přímé derivace se dopracovává k terminálům12 . Metoda zdola nahoru pak začíná vytvářet derivační strom od koncových uzlů a pomocí redukcí se snaží dopracovat ke kořenu (výchozímu symbolu). (Češka, 2002) 2.5.4

Syntaktické diagramy

Syntaktické diagramy slouží k grafickému vyjádření bezkontextové gramatiky. Při kreslení diagramů používáme dva hlavní symboly: obdélník - představuje odkaz na jiný graf, tj. nonterminál a ovál - představuje terminál. K vyjádření posloupnosti symbolů ve větné formě se využívají graficky orientované linky, tzv. spojnice. Rozeznáváme čtyři druhy elementů, které můžeme při tvorbě syntaktických diagramů použít a to zřetězení symbolů, varianta, iterace a seznam s oddělovači.

12

tato metoda je použita při implementaci ve vlastní práci

2.5


26

Vztahy mezi prvky a pravidly bezkontextové gramatiky jsou následující: • zřetězení symbolů - A → α1 α2 , • varianta - A → α1 | α2 , ¯ A, ¯ → α1 A¯ | ; v tomto případě pravidla gramatiky • iterace - A → α1 A, musí vyjadřovat skutečnost, že α1 se musí vyskytovat alespoň jedenkrát, a musí odrážet iteraci, tedy být rekurzivní, ¯ A¯ → aα1 A¯ | ; iterace prvků s oddělo• seznam s oddělovači - A → α1 A, vači v podobě terminálního symbolu a; odpovídající pravidla gramatiky jsou odvozena od tvaru v předchozím případě. Využití těchto diagramů je čistě praktické, zpřehledňuje gramatiky a popisuje programovací jazyk, a proto tento způsob bývá pro člověka mnohem více čitelnější.(Šorm, Rybička, Haluza, 2006) 2.5.5

Zásobníkový automat

Zásobníkový automat je jednocestné nedeterministrické abstraktní zařízení (viz Obr. 2), které představuje model syntaktického analyzátoru bezkontextových jazyků. Je vybaven zásobníkem reprezentujícím nekonečnou paměť. Vstupní páska je rozdělena na elementární symboly. Vstupní pásku lze číst, nikoliv na ni zapisovat. V určitém časovém okamžiku může hlava setrvat nad aktuálním záznamem a nebo se posunout doprava (proto jednocestný). Řídící jednotka tak realizuje operace prováděné čtecí hlavou a ukládá informace do zásobníku prostřednictvím funkce přechodů, množinou stavů řídící jednotky a vrcholem zásobníku. (Češka, 2002)

Obr. 2: Schéma zásobníkového automatu (Češka, 2002)

2.6

Deterministické bezkontextové jazyky

27

Zásobníkový automat P je definován jako sedmice P = (Q, Σ, Γ, δ, q0 , z0 , F ) kde • • • • • • •

Q je konečná množina symbolů reprezentující vnitřní stavy automatu, Σ je konečná množina terminálů, Γ je konečná množina tzv. zásobníkových symbolů, ∗ δ je přechodová funkce, definovaná jako zobrazení δ : Q×(Σ∪{})×Γ → 2Q×Γ q0 ∈ Q je výchozí vnitřní stav, z0 ∈ F startovací symbol, který je na počátku vložen do zásobníku F ⊆ Q je množina koncových stavů.

Zásobníkové automaty, podobně jako konečné automaty, pracují na principu přecházení mezi jednotlivými konfiguracemi. Konfiguraci tvoří trojice (q, w, α) ∈ Q×Σ∗ ×Γ∗ , kde q je aktuální stav řídící jednotky, w je část vstupní věty, která nebyla dosud přečtena a α představuje obsah zásobníku. Počáteční konfiguraci nazveme takovou konfiguraci zásobníkového automatu, která má tvar (q0 , w, Z0 ). Koncovou konfiguraci zásobníkového automatu zapisujeme ve tvaru (q, , α), kde q ∈ F a, a ∈ Γ∗ . (Šorm, Rybička, Haluza, 2006)

2.6


Deterministické bezkontextové jazyky patří do skupiny bezkontextových jazyků, respektive jsou jejich podmnožinou. Jejich název koresponduje se zařízením, které tyto jazyky reprezentuje - deterministický zásobníkový automat13 . Deterministické gramatiky lze rozdělit do těchto skupin: 1. precedenční gramatiky 2. LL gramatiky14 3. LR gramatiky Tyto jazyky mají tři nejvýznačnější vlastnosti, které je třeba vyzdvihnout (Češka, 2002): 1. efektivnost rozkladu - deterministický syntaktický analyzátor pracuje s lineárním paměťovým prostorem a časem 13

Deterministický zásobníkový automat je určitý druh zásobníkového automatu. Zobrazení δ obsahuje pro každou konfiguraci pouze jeden prvek, tedy δ : Q × (Σ ∪ {}) × Γ → Q × Γ∗ (Šorm, Rybička, Haluza, 2006) 14 tato třída je použita při implementaci ve vlastní práci

2.6


28

2. automatizovatelnost výstavby analyzátoru syntaxe - realizaci lze řešit algoritmicky 3. snadnost nálezu syntaktických chyb a propojení se sémantickým zpracováním - deterministické syntaktické analyzátory pracují bez návratů (není potřeba zkoušet všechna pravidla než najdeme to správné)

2.6.1

LL gramatiky

LL gramatika patří mezi gramatiky generované deterministickými jazyky. Generuje třídu deterministických jazyků, tzv. LL jazyků, které rovněž tvoří podmmnožinu deterministických jazyků. Název LL vychází ze dvou způsobů analýzy, které využívá: Left to right parse (rozklad zleva doprava) a Left Parse (levý rozklad). Při deterministické analýze je důležité vybrat správnou variantu pravé strany z množiny přepisovacích pravidel, které mají na levé straně stejný nonterminál. Při realizaci levého rozkladu věty a existenci pravidel tvaru A → α1 | α2 | . . . | αn máme při výskytu nejlevějšího neterminálu A ve větné formě právě n možností na jeho přepis. Šorm, Rybička a Haluza (2006) popisují základní princip analýzy LL jazyka následovně: „Vzhledem k tomu, že vytváříme levou derivaci věty, má každá větná forma (s výjimkou výsledné věty) tvar ξr = a1 a2 . . . aj Aβ, kde prefix a1 a2 . . . aj je identický s prefixem analyzované věty. Při přechodu k další formě ξr+1 expanzí neterminálu A pak tedy může být tento prefix obohacen o další terminální symboly, které opět musí souhlasit s analyzovanou větouÿ. Ze všech A-pravidel je tedy potřeba vybrat tu variantu, jejíž prefix odpovídá požadovanému řetězci symbolů ve větě. Na základě toho, kolik následujících symbolů vstupní věty je potřeba znát, abychom se dokázali správně rozhodnout, hovoříme o LL(k) gramatikách, kde k je počet následujících symbolů potřebný pro výběr správné varianty. Pokud k výběru správné varianty postačuje znát jediný následující terminální symbol, hovoříme o tzv. LL(1) gramatikách15 . (Šorm, Rybička, Haluza, 2006) 2.6.2

Výpočet množin FIRST a FOLLOW

Při rozhodování o variantě na pravé straně A pravidel se setkáme s problémem, kdy potřebujeme zjistit, kterým terminálem jednotlivé varianty začínají. K tomuto účelu použijeme výpočet množiny FIRST(α) dané gramatiky G = (N, Σ, P, S) podle následujícího algoritmu (Šorm, Rybička, Haluza, 2006): 15

použity při řešení vlastní práce

2.6


29

1. Předpokládejme, že α = X1 X2 . . . Xm , kde Xi ∈ (N ∪ Σ). 2. Je-li X1 ∈ Σ, pak FIRST(α) = {X1 }. 3. Je-li X1 ∈ N a X1 ⇒∗ aβ, pak k množině FIRST(α) přidáme terminální symbol a. 4. Je-li X1 ∈ N a X1 ⇒∗ , pak k množině FIRST(α) přidáme symboly množiny FIRST(γ), kde γ = X2 . . . Xm . Množinu FIRST je potřeba vypočítat pro všechny varianty pravých stran A-pravidla. Na místech, kde αi = , potřebujeme navíc vypočítat množinu FOLLOW(A): 1. Množina vzniklá FOLLOW(S) obsahuje . 2. Je-li A → αBβ ∈ P a β 6= , pak FOLLOW(B) obsahuje všechny prvky FIRST(β). 3. Je-li A → aBβ ∈ P a β ⇒∗ , pak všechny prvky FOLLOW(A) jsou v množině FOLLOW(B). 2.6.3

Syntaktická analýza LL(1) gramatiky

Zásobníkový automat řízený rozkladovou tabulkou provádí rozklad věty v zásobníku na základě symbolů čtených ze vstupní pásky. Rozkladová tabulka reprezentuje zobrazení M : (Γ ∪ {Z0 }) × (Σ ∪ {}) → R, kde R nabývá pro každou dvojici (X, Y ) následující hodnoty (Šorm, Rybička, Haluza, 2006): 1. 2. 3. 4.

řetězec β ∈ Γ∗ , je-li X ∈ N a zároveň A → B ∈ P a zároveň Y ∈ FF(β), prvek pop, je-li X = Y pro X, Y ∈ Σ, prvek accept, je-li X = Z0 a zároveň Y = , prvek error v ostatních případech.

Na počátku se v zásobníku nachází startovací symbol gramatiky a speciální symbol Z0 . Na vstupní pásce najdeme analyzovanou větu. Na konci zpracování, tedy v místě, kdy se automat nachází v koncové konfiguraci, se předpokládá, že v zásobníku je umístěn jediný symbol Z0 a na vstupní pásce pak prázdný řetězec. Činnost automatu probíhá způsobem, který lze algoritmicky popsat. Podíváme se, jaký symbol se nachází na vrcholu zásobníku. Je-li to nonterminální symbol, vybere se z rozkladové tabulky podle aktuálního symbolu na vstupní pásce příslušný řetězec β, kterým se nahradí nonterminál v zásobníku. Je-li na vrcholu terminální

2.7

Sémantika

30

symbol a na vstupu je tentýž terminál, provede se operace pop, což znamená odstranění symbolu z vrcholu zásobníku a přečtení (odstranění) téhož symbolu ze vstupní pásky. Je-li vrcholem zásobníku Z0 a věta je přečtena, je provedena akce accept, tj. přijetí věty. V ostatních případech je provedena akce error, což znamená chybu a neakceptaci věty. (Šorm, Rybička, Haluza, 2006)

2.7

Sémantika

Abychom jazyk plně definovali, nelze skončit pouze u syntaktické analýzy. Ta pouze definuje jeho strukturu. Je nutné také specifikovat význam jednotlivých konstrukcí. Je tedy třeba, abychom statickým zápisům dali určitou formu dynamiky a význam. Ke analýze významu jednotlivých konstrukcí slouží tzv. sémantická analýza. Ta kontroluje, zda-li jsou deklarovány všechny proměnné, volané funkce existují a jsou definovány, atd. Po sémantické analýze pak přichází na řadu sémantická akce, která provede v příslušném místě danou operaci (např. přiřazení hodnoty do proměnné, výpis na obrazovku, atd.). S popisem sémantiky k danému programovacímu jazyku se lze setkat nejčastěji v manuálech a referenčních příručkách. (Elbl, 2003)

3

SOUČASNÝ STAV ŘEŠENÉ PROBLEMATIKY

3

31

Současný stav řešené problematiky

V současnosti je na trhu dostupných několik produktů, které se prezentují jako software pro výuku algoritmizace nebo programování. Tato kapitola se věnuje nejznámějším aplikacím a programovacím jazykům, popisuje jejich vlastnosti, hodnotí cenovou dostupnost, metodickou vhodnost a praktickou využitelnost. Jednotlivé produkty jsou seřazené chronologicky od doby jejich vzniku.

3.1

Pascal

Pascal je název programovacího jazyka, jehož návrh pochází ze 70. let 20. století od Niklause Wirtha, profesora na Vysoké škole technické v Curychu. Tento jazyk byl původně navržen pro studenty za účelem výuky, později se však dočkal širšího pojetí. Od svého vzniku prošel několika proměnami a inovacemi. O nejvýznačnější se postarala firma Borland (www.borland.com) a její produkt s názvem Turbo Pascal. Pascal patří mezi jazyky procedurální a obsahuje všechny základní algoritmické prvky (cykly, podmínky, std. vstup a výstup, atd.), proto je velmi vhodný pro výuku algoritmizace. Syntaxe disponuje klíčovými slovy v anglickém jazyce a i vývojová prostředí jsou pouze v angličtině. Mezi nejznámější patří již jmenovaný Turbo Pascal od firmy Borland (placený, již se nevyvíjí) a open-source kompilátor s vývojovým prostředím Free Pascal (www.freepascal.org). V praxi se spíše využívá jeho nádstavby s názvem Delphi (původně od firmy Borland, nyní vývoj převzala společnost Embarcadero), která disponuje jazykem Object Pascal. V tomto prostředí je vyvíjen např. nejznámější český editor PSPad (www.pspad.com).

Obr. 3: Prostředí Free Pascal - OS Linux (zdroj: http://www.slax.org)

3.2

3.2

Robot Karel

32

Robot Karel

Karel je programovací jazyk distribuovaný společně se svým vývojovým prostředím. S původní myšlenkou přišel na přelomu 70. a 80. let 20. století Richard E. Pattis. Patří mezi jazyky interpretované, zdarma dostupné a je určen pro výuku programování naprostých začátečníků. Princip práce spočívá v ovládání robota, který se pohybuje po čtvercové síti. Pomocí příkazů lze s robotem pohybovat, pokládat cihly a zase je zvedat. V původní verzi obsahuje klíčová slova v anglickém jazyce, existuje včak i verze počeštěná (http://xkarel.sourceforge.net). Překlad není příliš zdařilý, respektive se hodí použít spíše anglickou verzi, protože v češtině některé formulace zní poněkud krkolomně a nelogicky. Disponuje pouze elementárními povely (Krok, Polož, Zvedni, Vlevobok), podmínkami (JeCihla, JeZeď, JeSever, Jinak), cykly (Dokud, Dokud ne) a umožňuje tvorbu velice jednoduchých procedur. Tento jazyk není příliš rozsáhlý, nabízí pouze malé množství příkazů a navíc se svým pojetím od ostatních jazyků až příliš liší, proto je prakticky nevyužitelný. Je tak vhodný spíše pro rozvoj logického myšlení.

Obr. 4: Robot Karel - online verze (zdroj: http://karel.oldium.net)

3.3

Baltazar, Baltík, Baltie

Baltazar je vývojové prostředí (i jeho hlavní postava) s vlastním programovacím jazykem na bázi jazyka C vyvinuté českou firmou SGP Systems (www.sgpsys.com) v roce 1993 (poslední verze 5.0 je dostupná z roku 1998). Firma tento produkt prezentuje jako systém určený pro výuku strukturovaného programování v jazyce C, který je vhodný nejen pro dospělé, ale díky své koncepci strukturogramů, maker a česky pojmenovaných příkazů a funkcí i pro mládež a děti od 12 let.

3.4

Petr

33

Jedná se o nástroj, který obsahuje textový editor pro psaní kódů a strukturogramů, grafický editor, vlastní interpreter jazyka C (verze Profi pak i překladač) a systém nápovědy. Patří mezi produkty placené a cena se odvíjí od počtu zakoupených licencí. Baltazar je ve skutečnosti název pro 2D knihovnu implementovanou v jazyce C rozšiřující tento jazyk o nové prvky. Základní syntaxe je tedy s jazykem C totožná, funkce z knihovny jsou však již dostupné v češtině. Bohužel disponuje na dnešní dobu velmi zastaralým grafickým prostředí (na bázi DOSu). SGP systems na Baltazara navázali novým pojetím aplikace s názvem Baltík (později přejmenovaná na Baltie), který již opouští od klasického zápisu algoritmů v programovacím jazyce a přidává prvky vizuálního programování. Díky systému Drag&Drop je pomocí ikon sestavována scéna a celý program. Tento produkt se až příliš odklání od klasického způsobu zápisu algoritmů a je vhodný spíše pro děti a mládež, kteří se s počítačem teprve seznamují.

Obr. 5: Baltík 4 (zdroj: http://www.sgpsys.com)

3.4

Petr

Petr se prezentuje jako vizuální programovací nástroj určený k snadné a rychlé tvorbě programů. Jeho autorem je společnost Gemtree Software, s.r.o (www.gemtree.cz), první verze pochází z roku 1999 a vyvíjí se prakticky dodnes (i když vývoj již není tak intenzívní). Hlavní postavou je králík Petr, kterého lze ovládat pomocí vestavěných funkcí programu. Podobně jako Baltík, i Petr je založen na vizuálním stylu programování. Lze v něm vytvářet programy bez jakékoliv znalosti problematiky programovacích jazyků. Slouží tedy spíše k rozvoji logického myšlení (podobně jako Robot Karel) a představivosti, proto je vhodný pro děti a mládež. Obsahuje také podrobnou ná-

3.5

Imagine Logo

34

povědu a krom standardních vstupně výstupních funkcí, disponuje i prostředky pro práci s grafikou (2D, 3D). Tento produkt je nabízen jak v placené, tak i ve verzi zdarma. Verze zdarma není určena pro komerční použití a je značně omezena. Naproti tomu placená verze žádná omezení nemá, až na cenu, která činí 4 499 Kč za profesionál verzi a 1 499 Kč ve verzi standard a instalaci na 1 PC16 .

Obr. 6: Petr - vývojové prostředí (zdroj: http://www.gemtree.cz)

3.5

Imagine Logo

Imagine Logo (http://imagine.input.sk) je produkt poměrně nový, vznikl v roce 2001. Distributor programu v ČR je nakladatelství Computer Press, a.s. (www.cpress.cz). Logo není součástí názvu náhodou, toto prostředí totiž disponuje programovacím jazykem, který vznikl již v 60. letech 20.století a byl navržen pro výuku dětí. Hlavní postavou je želva, která se ovšem pomocí programovacího jazyka dá nahradit jinou postavou (i vlastním výtvorem). K dipozici je celé vývojové prostředí společně s interpretem jazyka. Mezi hlavní vlastnosti se řadí práce s objekty a událostmi (převládá tedy objektový přístup), podpora paralelismu, multimédií a internetu. Logo se řadí mezi jazyky funkcionální. Zařazení této aplikace tak spadá spíše do výuky umělé inteligence než do klasické algoritmizace. Imagine Logo je nabízeno celkem ve třech licencích. Domácí licence stojí 690 Kč, omezená školní licence (do 20 PC) 4 760 Kč a neomezená školní licence 9 520 Kč. Ceny17 jsou uvedeny včetně DPH. 16 17

údaje z května 2010 údaje z května 2010

3.6

Ostatní

35

Obr. 7: Imagine Logo (zdroj: http://www.root.cz)

3.6

Ostatní

Do ostatních se řadí jazyky, které nebyly primárně navrženy pro výuku algoritmizace, ale i přesto je lze k tomuto účelu využít. Mezi tyto patří např. jazyk C nebo C++. Méně vhodnými nástroji jsou pak Java, Visual Basic, Perl nebo Python. Java a Visual Basic jsou zástupci spíše objektově orientovaného přístupu řízeného událostmi. Perl a Python patří do skupiny hybridních intepretovaných jazyků, což znamená, že umožňují zápis v procedurální, objektové i funkcionální formě. Perl umožňuje psát svůj kód mnohem benevoltněji. Pro začátečníka může být tato skutečnost velmi matoucí a při přechodu na nižší jazyk může působit problémy.

4

ZVOLENÁ METODIKA A PROGRAMOVÉ PROSTŘEDKY

4

36

Zvolená metodika a programové prostředky

Návrh a implementace nového programovacího jazyka a jeho vývojového prostředí bude probíhat celkem ve třech hlavních fázích: 1. návrh lexikálního a syntaktického analyzátoru 2. návrh a implementace vývojového prostředí 3. implementace lexikálního a syntaktického analyzátoru a sémantických akcí do vývojového prostředí

4.1

Návrh lexikálního a syntaktického analyzátoru

V této fázi bude nejdříve navržena regulární gramatika pro jednotlivé lexikální prvky jazyka (čísla, řetězce, klíčová slova, atd.). Provede se konstrukce nedeterminického konečného automatu, který se převede na deterministický. Dále bude navrhnuta bezkontextová gramatika typu LL(1) pro syntaktický analyzátor. Typ LL(1) plně dostačuje pro návrh i implementaci jazyka a je mnohem jednodušší na implementaci než např. LR gramatiky. Po výpočtu množin FIRST a FOLLOW, tedy po kontrole správnosti, že daná gramatika splňuje opravdu typ LL(1), dojde k sestavení zásobníkového automatu, který slouží jako výchozí podklad pro syntaktický analyzátor.

4.2

Návrh a implementace vývojového prostředí

V této fázi dojde k vystavění editoru zdrojového kódu a tvorbě console umožňující standardní výstup na obrazovku. K tomuto účelu bude použito programové vybavení ve formě vývojového prostředí CodeBlocks (www.codeblocks.org), které je zdarma a disponuje překladačem jazyka C++. Jazyk C++ byl zvolen záměrně, protože patří mezi jazyky kompilované, umožňuje objektový přístup při tvorbě aplikací a je pro něj dostupné velké množství knihoven a funkcí. K tvorbě grafického rozhraní bude využita knihovna wxWidgets (www.wxwidgets.org), která patří mezi multiplatformní, open-source a je dostupná zdarma. K návrhu postavy psa Punti a grafických prvků bude využit vektorový grafický editor Inkscape (www.inkscape.org) také dostupný zdarma.

4.3

4.3

Implementace lexikálního a syntaktického analyzátoru a sémantických akcí do aplikace

37

Implementace lexikálního a syntaktického analyzátoru a sémantických akcí do aplikace

Implementace lexikálního analyzátoru proběhne na základě sestaveného deterministického konečného automatu. Lexikální analyzátor slouží jako vstupní krok syntaktické analýzy. Syntaktický analyzátor bude vystavěn metodou rekurzivního sestupu (analýza shoda dolů) na základě zásobníkového automatu. Syntaktický analyzátor bude obohacen již o první prvky sémantiky (kontrola existence proměnných a volaných funkcí se správným počtem parametrů) a naplní struktury potřebné pro sémantický procesor. Sémantika bude řešena odděleně (dáno stylem implementace pod OS Windows). Vstupem pro sémantický procesor bude lineární seznam proměnných, funkcí a fronta tokenů hlavního programu.

5

VLASTNí PRÁCE

5

38

Vlastní práce

5.1

Obecné vlastnosti jazyka Punťa

Při rozhodování, jakou zvolit hlavní postavu aplikace, bylo zvažováno několik faktorů. Postava by měla reprezentovat přátelského tvora, který je člověku blízký a ve kterém často nachází oporu při řešení těžkých situací. A protože ne nadarmo se říká „Pes - nejlepší přítel člověkaÿ, padla volba hlavní postavy na něj. Nově konstruovaný programovací jazyk se prezentuje jako ryze český, proto bylo zvoleno takové psí jméno, které v jiných jazycích přesně v tomto znění nenajdete - Punťa. Punťa patří mezi jazyky interpretované, procedurální, typové18 a casesensitive19 . Jeho syntaxe výchází především z jazyka C, ale podobnost lze najít i s jazykem Pascal.

5.2 5.2.1

Regulární gramatika lexikálního analyzátoru Abeceda jazyka

Abeceda jazyka v sobě zahrnuje všechny symboly, které mohou obsahovat jednotlivé lexikální prvky, tedy symboly, z kterých se mohou skládat. Σ = {p, c, e, +, −, ., ∗, &, $, ∧, /, |, !, (, ), <, >, =, :, ”,0 , {, }, T AB, ←-, , ; , , , %, [, ]} p ∼ a. .žA. .Ž c ∼ 0. .9 5.2.2

Gramatika jazyka čísel

Jazyk podporuje zápis celých i desetinných čísel oddělených tečkou v desítkové soustavě. Možný je i zápis ve vědeckém tvaru pomocí e. Unární operátory + a - jsou řešena v rámci syntaktického a sémantického procesoru. Př. 10.12 nebo 12e+2 GN = {NN , ΣN , PN , SN } ΣN = {c, +, −, e} c ∼ 0. .9 NN = {SN , N1 , N2 , N3 , N4 } 18 19

před použitím proměnné je třeba ji deklarovat s příslušným datovým typem na velikosti písmen záleží

5.2

PN SN N1 N2 N3 N4

Regulární gramatika lexikálního analyzátoru

: → → → → →

5.2.3

39

cN1 | c cN1 | c | .N2 | eN3 | eN4 cN2 | c | eN3 | eN4 +N4 | − N4 cN4 | c Gramatika jazyka přiřazení

Příkaz přiřazení je realizován pomocí znaku =. GA = {NA , ΣA , PA , SA } ΣA = {=} NA = {SA } PA : SA → = 5.2.4

Gramatika jazyka operátorů

Podporovány jsou aritmetické, logické a relační operátory. Standardní aritmetické operátory znázorňují +, -, *, /, % (zbytek po dělení neboli modulo) a ∧ pro umocňování. Mezi logické operátory patří: logický součin &&, součet || a negace !. Mezi relační pak <, >, <=, >=, ==. Nerovnost lze zapsat dvojím způsobem a to jak pomocí <>, tak i ! =. Pro určování priority výrazů lze použít kulaté závorky (). Zřetězení je provedeno přes operátor tečka a operátor přepínače reprezentuje znak dvojtečka. GO = {NO , ΣO , PO , SO } ΣO = {=, <, >, &, |, ∧, %, +, −, ∗, /, ., (, ), !} NO = {SO , O1 , O2 , O3 , O4 } PO : SO − > +| − | ∗ |/|.| < | > | < O1 | < O2 | > O2 | = O2 | ∧ |%|(|)|&O3 ||O4 |!|!O2 | : O1 →> O2 →= O3 → & O4 → |

5.2


5.2.5

40

Gramatika jazyka řetězců

Řetězce jsou uzavřeny do uvozovek. Jestliže je potřeba do řetězce uložit symbol uvozovek, stačí před symbol napsat znak \. Př. "Ahoj" nebo "\"" GS = {NS , ΣS , PS , SS } ΣS = {”, \, ♦} ♦ = Σ − {”, \} NS = {SS , S1 , S2 } PS : SS → ”S1 S1 → ♦S1 | \S2 | ” S2 → ♦S1 | \S1 | ”S1 5.2.6

Gramatika jazyka znaků

Znaky jsou uzavřeny do apostrofů. V případě, že je potřeba uložit symbol apostrofu do znakového formátu, stačí před něj uvést znak \. Př. ’a’ nebo ’\’’ GCh = {NCh , ΣCh , PCh , SCh } ΣCh = {0 , \, 4} 4 = Σ − {0 , \} NCh = {SCh , Ch1 , Ch2 , Ch3 } PCh : SCh →0 Ch1 Ch1 → 4Ch3 | \Ch2 | 0 Ch2 → 4Ch3 | 0 Ch3 Ch3 →0 5.2.7

Gramatika jazyka proměnných

Proměnná je vždy uvozena znakem $ a jméno proměnné se může skládat z písmen, číslic a podtržítka.

5.2


41

Př. $max nebo $výsledek GV = {NV , ΣV , PV , SV } ΣV = {p, c, , $} c ∼ 0. .9 p ∼ a. .žA. .Ž NV = {SV , V1 } PV : SV → $V1 V1 → pV1 | V1 | cV1 | p | c | 5.2.8

Gramatika jazyka klíčových slov

Klíčová slova se mohou skládat z písmen, čísel a podtržítek. Musí však vždy začínat písmenem nebo podtržítkem. Př. vypis nebo vrať znak GW = {NW , ΣW , PW , SW } ΣW = {p, c, } c ∼ 0. .9 p ∼ a. .žA. .Ž NW = {SW , W1 } PW : SW → W1 | pW1 | p | W1 → pW1 | cW1 | W1 | p | c | 5.2.9

Gramatika ukončovacího znaku příkazu

Ukončovací znak příkazu je požadován za příkazem přiřazení, voláním funkce a voláním vestavěných příkazů. GT = {NT , ΣT , PT , ST } ΣT = {; } NT = {ST } PT : ST →;

5.2


5.2.10

42

Gramatika příkazových bloků

Příkazové bloky jsou uzavřeny do složených závorek { }. Tento jazyk podporuje bloky u hlavního programu, cyklů, podmínek (větvení) a funkcí. Bloky nejsou ukončeny středníkem. GB = {NB , ΣB , PB , SB } ΣB = {{, }} NB = {SB } PB : SB → { | } 5.2.11

Gramatika oddělovače parametrů a názvů proměnných

Jako oddělovač parametrů a názvů proměnných při deklaraci slouží znak čárka. GD = {ND , ΣD , PD , SD } ΣD = {, } ND = {SD } PD : SD →, 5.2.12

Gramatika jazyka polí

Jednotlivé indexy pole jsou odděleny pomocí hranatých závorek. GAr = {NAr , ΣAr , PAr , SAr } ΣAr = {[, ]} NAr = {SAr } PAr : SAr → [ | ] 5.2.13

Gramatika bílých znaků

Za bílé znaky jsou považovány znaky, které jsou při tokenizaci ignorovány a slouží jako oddělovače tokenů.

5.2


43

GH = {NH , ΣH , PH , SH } ΣH = { , T AB, ←-} NH = {SH } PH : SH → 5.2.14

| T AB | ←Gramatika komentářů

Jazyk podporuje jednořádkové i víceřádkové komentáře. Jednořádkové komentáře následují za znaky // a jsou ukončeny bílým znakem ←-. Víceřádkové komentáře jsou uvozeny znaky /* a ukončeny znaky */. Př. // jednořádkový komentář nebo /* víceřádkový komentář */ GC = {NC , ΣC , PC , SC } ♠ = Σ − {∗, /} ΣC = {♠, /, ∗} NC = {SC , C1 , C2 , C3 , C4 } PC : SC → /C1 C1 → /C2 | ∗ C3 C2 → ♠C2 | /C2 | − C2 | ←C3 → ♠C3 | /C3 | ∗ C4 | ←- C3 C4 → ♠C3 | ←- C3 | ∗ C4 | / 5.2.15

Stanovení nevýznamových tokenů

Do nevýznamových tokenů patří bílé znaky a komentáře, tedy oddělovače tokenů. Jazyk nevýznamových tokenů má následující podobu: LOD = Lkom ∪ Lbz SOD → /C1 | SOD | T ABSOD | ←- SOD | C1 → /C2 | ∗ C3 C2 → ♠C2 | /C2 | − C2 | ←- SOD C3 → ♠C3 | /C3 | ∗ C4 | ←- C3 C4 → ♠C3 | ←- C3 | ∗ C4 | /SOD

5.2


5.2.16

44

Stanovení významových tokenů

Do významových tokenů patří čísla, příkaz přiřazení, operátory, řetězce, znaky, proměnné, klíčová slova, uvaděče bloků, ukončovací znak, oddělovače parametrů funkcí a pole. LV T = LN ∪ LA ∪ LO ∪ LS ∪ LCh ∪ LV ∪ LW ∪ LB ∪ LT ∪ LP ∪ LAr Svt → cN1 | c | = | + | − | ∗ | / | . | < | > | < O1 | < O2 | > O2 | = O2 | ∧ | % | ( | ) | &O3 | |O4 | ! | !O2 | : | ”S1 | 0 Ch1 | $V1 | W1 | pW1 | p | | ; | { | } | , | [ | ] N1 → cN1 | c | .N2 | eN3 | eN4 N2 → cN2 | c | eN3 | eN4 N3 → +N4 | − N4 N4 → cN4 | c O1 →> O2 →= O3 → & O4 → | S1 → ♦S1 | \S2 | ” S2 → ♦S1 | \S1 | ”S1 Ch1 → 4Ch3 | \Ch2 | 0 Ch2 → 4Ch3 | 0 Ch3 Ch3 →0 V1 → pV1 | V1 | cV1 | p | c | W1 → pW1 | cW1 | W1 | p | c | 5.2.17

Zregularizovaný lexikální analyzátor

Zregularizovaný lexikální analyzátor vzniká sjednocením jazyků významových a nevýznamových tokenů. Tento zápis pak slouží jako podklad při konstrukci nedeterministického konečného automatu. Σ = {p, c, e, +, −, ., ∗, &, $, ∧, /, |, !, (, ), <, >, =, :, ”,0 , {, }, T AB, ←-, , ; , , , %, [, ]} p ∼ a. .žA. .Ž c ∼ 0. .9 ♦ = Σ − {”, \} 4 = Σ − {0 , \} ♠ = Σ − {∗, /}

5.3

Bezkontextová gramatika syntaktického analyzátoru

45

L = LV T ∪ LOD S → cN1 |c| = |+|−|∗|/|.| < | > | < O1 | < O2 | > O2 | = O2 |∧|%|(|)|&O3 ||O4 |!|!O2 | : | ”S1 | 0 Ch1 | $V1 | W1 | pW1 | p | | ; | { | } | , | [ | ]/C1 | S | T ABS | ←- S | N1 → cN1 | c | .N2 | eN3 | eN4 N2 → cN2 | c | eN3 | eN4 N3 → +N4 | − N4 N4 → cN4 | c O1 →> O2 →= O3 → & O4 → | S1 → ♦S1 | \S2 | ” S2 → ♦S1 | \S1 | ”S1 Ch1 → 4Ch3 | \Ch2 | 0 Ch2 → 4Ch3 | 0 Ch3 Ch3 →0 V1 → pV1 | V1 | cV1 | p | c | W1 → pW1 | cW1 | W1 | p | c | C1 → /C2 | ∗ C3 C2 → ♠C2 | /C2 | − C2 | ←- S C3 → ♠C3 | /C3 | ∗ C4 | ←- C3 C4 → ♠C3 | ←- C3 | ∗ C4 | /S 5.2.18

NKA a DKA

Výchozí abeceda pro NKA je totožná s abecedou lexikálního analyzátoru a tvoří sloupec přechodové tabulky. Množina stavů je vytvořena z nonterminálních symbolů levé strany pravidel a tvoří řádky tabulky. Návrh NKA i DKA je z důvodů své rozsáhlosti a větší přehlednosti umístěn do přílohy A.

5.3


Syntaktickou gramatiku tvoří dvě části. První je určena pro soubor se zdrojovým kódem, který obsahuje hlavní program, tedy spustitelnou část. Druhá popisuje a definuje gramatiku modulu, což je soubor s funkcemi, který lze připojit do hlavního programu pomocí příkazu připoj.

5.3


5.3.1

46

Deterministická bezkontextová gramatika souboru s hlavním programem

Syntaktická gramatika určuje pravidla zápisu hlavního programu. Již byla upravena tak, aby neobsahovala přímou levou rekurzi. Tato gramatika slouží jako výchozí zdroj pro tvorbu zásobníkového automatu. ZACAT EK → P RIP OJ KON ST AN T A DEKP ROM DEF F CE hlavni program M AIN BLOK P RIP OJ → pripoj retezec ; P RIP OJ | KON ST AN T A → konstanta dat typ promenna = KON S1 ; KON ST AN T A | KON S1 → cislo | retezec | znak | log hodnota DEF F CE → f unkce nazev (DF 1) DF 4 M AIN BLOK DEF F CE | DF 1 → typ promenna DF 2 DF 3 | DF 2 → [ ] DF 2 | DF 3 →, typ promenna DF 2 DF 3 | DF 4 → vraci typ DF 5 | DF 5 → [ ] DF 5 | M AIN BLOK → { DEKP ROM P RIKAZ P RIK1 } DEKP ROM → dat typ nazev prom DEKP ROM 1 DEKP ROM 2 ; DEKP ROM | DEKP ROM 1 → [ cislo ] DEKP ROM 1 | DEKP ROM 2 →, nazev prom DEKP ROM 1 DEKP ROM 2 | P RIK1 → P RIKAZ P RIK1 | P RIKAZ → CW HILE | CF OR | CU N T IL; | P RIRAD; |V IF | V SW IT CH | V OLF CE; | V Y ST U P ; | V ST U P ; | SOU BORP RIK; | GRAF P RIK; | T EXT P RIK; | N AV RAT HOD; |ST OP ; BLOK → { P RIKAZ P RIK1 } P ROM → globalni nazev prom | nazev prom CW HILE → zatimco P ODM IN KA BLOK CF OR → pro P ROM P OLE od LOGV Y RAZ do LOGV Y RAZ CF OR1 BLOK CF OR1 → po LOGV Y RAZ | CU N T IL → opakuj BLOK dokud P ODM IN KA P RIRAD → P ROM P OLE = LOGV Y RAZ P OLE → [ LOGV Y RAZ ] P OLE | V IF → kdyz P ODM IN KA BLOK V IF 1 V IF 1 → jinak BLOK | V SW IT CH → pokud je LOGV Y RAZ { V SW IT CH1 V SW IT CH2 } V SW IT CH2 → V SW IT CH1 V SW IT CH2 | V SW IT CH1 → V SW IT CH3 : V SW IT CH4 | jine : V SW IT CH4

5.3


47

V SW IT CH3 → OP 1 cislo | znak | retezec V SW IT CH4 → P RIKAZ P RIK1 OP 1 → + | − | V OLF CE → nazev (V OLF CE1) | V OLF CE3(LOGV Y RAZ) | T EXT F CE | SOU BORF CE | P REV ED V OLF CE1 → LOGV Y RAZ V OLF CE2 | V OLF CE2 →, LOGV Y RAZ V OLF CE2 | V OLF CE3 → abs | sin | cos| tan | cotg |odmocnina | nahodne cislo T EXT F CE → delka textu (LOGV Y RAZ) | vrat znak(LOGV Y RAZ, LOGV Y RAZ) SOU BORF CE → cti(P ROM P OLE, dat typ) | cti radek(P ROM P OLE) | otevri(LOGV Y RAZ, LOGV Y RAZ) P REV ED → preved(LOGV Y RAZ, dat typ) V Y ST U P → vypis(LOGV Y RAZ) | smaz obrazovku() V ST U P → nacti(P ROM P OLE) ST OP → stop SOU BORP RIK → zapis(P ROM P OLE, LOGV Y RAZ) | dalsi radek(P ROM P OLE) | zavri(P ROM P OLE) T EXT P RIK → nastav znak(LOGV Y RAZ, LOGV Y RAZ, LOGV Y RAZ) GRAF P RIK → GRAF P RIK1() | kresli bod(LOGV Y RAZ, LOGV Y RAZ)| presun se na(LOGV Y RAZ, LOGV Y RAZ) | nastav barvu(LOGV Y RAZ) GRAF P RIK1 → zapni kresleni | vypni kresleni N AV HOD → vrat LOGV Y RAZ P ODM IN KA → (LOGV Y RAZ) LOGV Y RAZ → LV 1 LOGV Y RAZ1 LOGV Y RAZ1 → && LV 1 LOGV Y RAZ1 | || LV 1 LOGV Y RAZ1 | xor LV 1 LOGV Y RAZ1 | LV 1 → AV Y RAZ LV 1 LV 11 → rel op AV Y RAZ LV 11 | AV Y RAZ → AV 1 AV Y RAZ1 AV Y RAZ1 → + AV 1 AV Y RAZ1 | − AV 1 AV Y RAZ1 | AV 1 → AV 2 AV 11 AV 11 → ∗ AV 2 AV 11 | / AV 2 AV 11 | % AV 2 AV 11 | AV 2 → LV 2 AV 21 AV 21 → ∧ LV 2 AV 21 | . LV 2 AV 21 | LV 2 →! AV 3 | AV 3 AV 3 → (LOGV Y RAZ) | cislo | retezec | znak | log hodnota | P ROM P OLE | V OLF CE

5.4

Vývojové prostředí

5.3.2

48

Deterministická bezkontextová gramatika modulu

Syntaktická gramatika modulu je téměř totožná se syntaktickou gramatikou hlavního programu. Omezeno je pouze přepisovací pravidlo, jenž má na levé straně nonterminál ZACAT EK: ZACAT EK → KON ST AN T A DEF F CE Z tohoto pravidla plyne, že v modulu lze definovat pouze konstanty a funkce a nelze připojovat jiné soubory, definovat globální proměnné a použít blok s hlavním programem. Toto řešení bylo zvoleno z důvodu větší přehlednosti modulu a menší náchylnosti ke kolizím názvů proměnných. Z původní gramatiky je tedy vynecháno pravidlo, jenž má na levé straně nonterminál P RIP OJ. 5.3.3


Syntaktické diagramy graficky vyjadřují navrženou bezkontextovou gramatiku jazyka. Pro svou obsáhlost a komplexnost jsou uvedeny v příloze B. 5.3.4


Aby bylo možné zkonstruovat zásobníkový automat, je nejprve nuné ověřit, zdali gramatika opravdu patří do třídy LL(1) gramatik. Výpočet množin FIRST a FOLLOW je uveden v příloze C. 5.3.5


Po kontrole pomocí výpočtu množin FIRST a FOLLOW je možné zkonstruovat zásobníkový automat, který slouží jako vzor pro praktickou implementaci syntaktického analyzátoru. Zásobníkový automat je rovněž velmi rozsáhlý, a proto je umístěn v příloze D.

5.4 5.4.1

Vývojové prostředí Návrh uživatelského rozhraní

Uživatelské rozhraní je navrženo pro naprosté začátečníky takovým zpusobem, aby jejich orientace v něm nebyla složitá. Kladený důraz na jednoduchost a rychlou dostupnost funkcí patří mezi hlavní vlastnosti aplikace, a proto je potřeba dodržet tento koncept jak v návrhu, tak i při implementaci. Grafické rozhraní je rozděleno do několika sekcí:

5.4


49

Obr. 8: Kostra návrhu editoru jazyka Punťa

• Menu - slouží pro přístup ke všem funkcím editoru • Tlačítková lišta - umožňuje přístup k nejčastěji používaným funkcím • Textové pole pro zdrojový kód - určeno pro editaci a zobrazování zdrojového kódu • Rychlá nápověda - rychlé zobrazení klíčových slov • Textové pole pro chybový výstup - výstupní textové pole pro zobrazení chybových hlášek (syntaktické a lexikální chyby) • Okno pro animovanou postavu - animovaná postava slouží k pouhé vizualizaci stavů aplikace Samotná interpretace probíhá v samostatném okně, které obsahuje prostor pro interaktivní obrazovku.

5.4


50

Obr. 9: Návrh okna s výstupní obrazovkou

5.4.2

Implementace uvítací obrazovky, editoru a console

Pro tvorbu grafického rozhraní byla využita knihovna wxWidgets, která poskytuje ucelený soubor tříd pro práci s jednotlivými prvky operačního systému Windows a jeho komponentami. K použití této knihovny není potřebná podrobná znalost WinAPI20 . Uvítací okno Prvním krokem je vytvoření uvítacího okna. K tomuto účelu slouží třída WS Window nacházející se v souboru ws window.cpp, která dědí vlastnosti své rodičovské třídy wxFrame. Třída wxFrame slouží pro vykreslení základního okna a třída WS Window ji rozšiřuje o vlastní metody a atributy. Uvítací okno disponuje třemi tlačítky, které reprezentují objekty startButton, helpButton, endButton, což jsou instance třídy wxButton. První jmenované tlačítko má název Psát algoritmy a spouští okno editoru. Druhé tlačíko s názvem Jak na to poskytuje okno s krátkou nápovědou. Třetí tlačítko slouží k ukončení aplikace. 20

Windows API - aplikační vývojové rozhraní vyvinuté firmou Microsoft

5.4


51

Součástí okna je i objekt ws animPanel představující instanci třídy WS AnimPanel, která dědí metody a atributy své rodičovské třídy wxPanel a rozšiřuje je o možnost animace.

Obr. 10: Uvítací okno aplikace

Okno editoru Okno editoru implementuje třída E Window, která je potomkem třídy wxFrame. Metody a atributy třídy lze nalézt v souboru e window.h, její implemetaci pak v souboru e window.cpp. Obsah okna tvoří vrchní menu, které je vytvořeno pomocí instance třídy wxMenu. Pod hlavní nabídkou aplikace je umístěna tlačítková lišta. Tuto lištu zobrazuje instance třídy wxToolBar. Pod lištou nástrojů se nachází rozdělená plocha pomocí instance třídy wxFlexGridSizer. Ta umožňuje měnit velikosti svých jednotlivých prvků dle velikosti okna ve stanoveném poměru. Pomocí metody Add jsou do tohoto neviditelného objektu vloženy ostatní kompomenty (objekty), jejichž velikost je potřeba při změně okna přepočítávat. Jedná se o komponentu záložek (instance třídy wxNotebook), textové výstupní okno pro zobrazení chyb a varování (instance třídy E RichTextOutput), panel s rychlou nápovědou (instance třídy E QuickHelpPanel) a posledním prvkem je panel s animací Punti (instance třídy E PanelAnimation). Každá položka má svůj jednoznačný identifikátor, ke kterému se dá přiřadit reakce na událost. Toto je také základní princip tvorby aplikací pod operačním systémem Windows. Třída wxWindow, která je rodičovskou třídou téměř všech komponent ve wxWidgets, disponuje metodou Connect, která na základě parametrů přiřadí po-

5.4


52

sluchač události k vytvořenému objektu. Jakmile nastane přiřazená událost (např. stisknutí tlačítka), dojde k provedení příslušné akce (např. zobrazení jiného okna). Na tomto principu funguje veškeré zpracování akcí v aplikaci. Každý objekt má svůj jednoznačný identifikátor, který je navázán na určitou událost (událostí může být i více). V praxi to znamená, že klikneme-li například v hlavní nabídce na položku Spustit program, vyšle se událost wxEVT COMMAND MENU SELECTED, dohledá se příslušný identifikátor a provede se syntaktická analýza kódu a následně spustí okno s výstupní obrazovkou.

Obr. 11: Okno editoru zdrojového kódu

Okno console Okno console obsahuje celkem 3 komponenty. První z nich je instance třídy C DrawingPanel, která vykresluje obrázek na pozadí (vzhled console). Druhou komponentou je instance třídy C RichTextOutput zajišťující textový výstup. Třída C RichTextOutput je potomkem wxRichTextCtrl a rozšiřuje ji o vlastní metody umožňující zachytávání kláves. Je-li uživatel vyzván k zadání hodnoty z klávesnice, nastaví se proměnná activateKeyboard na hodnotu true a metoda OnKeyPressed, která přepisuje původní metodu rodičovské třídy, vstup uloží do proměnné. Uživatel má takto domnění, že píše do skutečné console. Třetí komponenta se zviditelní po zapnutí režimu kreslení (a skryje se textový výstup). Jedná se o panel, na kterém se Punťa pohybuje a zanechává za sebou stopu ve formě pixelů. Problematiku kreslení řeší třída C DrawingPanel. Implementuje

5.4


53

instanci třídy wxTimer, která zajišťuje výpočet pozice, kde se postava Punti právě nachází nebo kam se má přemístit.

Obr. 12: Okno console s grafickým výstupem

5.4.3

Funkce editoru

Editor disponuje všemi základními funkcemi, které by měl každý textový editor obsahovat. Ke všem funkcím lze přistupovat přes hlavní nabídku. Pod položkou Soubor se nacházejí operace, pomocí kterých lze organizovat zdrojové kódy (vytvářet nové, ukládat stávající soubory a zavírat karty v komponentě záložek). Po stisku položky Nový soubor se založí nová karta s textovým polem pro editaci zdrojového kódu. Pro uzavření karty stačí kliknout na položku Zavři soubor nebo pravým tlačítkem na aktuálně otevřenou záložku. Položka Úpravy obsahuje funkce pro kopírování, vyjmutí a vložení textu. Funkce Zpět a Vpřed umožňují vracení změn ve zvoleném směru. Jestliže je potřeba zvětšit písmo v editoru a nebo jej naopak změnšit, lze k tomuto účelu využít položky Přibliž text, resp. Oddal text. Nabídka Hledat obsahuje funkce pro vyhledávání a modifikaci textu. Pro hledání i nahrazení byla vytvořena speciální dialogová okna. Hledání určité fráze nebo věty je umožněno oběma směry (tedy od zdola nahoru i shora dolů) a lze rozlišovat i celá slova. Na podobném principu funguje i funkce pro nahrazování. Další v pořadí je položka Spustit, pod kterou se skrývá jediná funkce a to Spusť program. Po spuštění dojde ke zkontrolování zdrojového kódu synktaktickým analyzátorem a po úspěšné kontrole se otevře okno s výstupem.

5.5

Implementace lexikálního a syntaktického analyzátoru

54

Položky Zobrazení a Nastavení slouží k nastavení programu a vzhledu console. Pod nabídkou Nápověda se skrývají položky pro zobrazení okna s popisem programu a informacemi o autorovi. 5.4.4

Zvýrazňovač syntaxe

Pomocí knihovny wxScintilla (http://sourceforge.net/projects/wxscintilla) byl do Punti implementován zvýrazňovač syntaxe. Knihovna musela být před tímto krokem patřičně upravena. Došlo k modifikaci lexikálního analyzátoru tak, aby splňoval gramatiku jazyka Punťa. Dále musel být upraven systém pro rozpoznávání klíčových slov, neboť špatně akceptoval české znaky, zejména pokud se vyskytovaly na začátku slova. Nastavení a konfigurace je pak velmi jednoduchá. Stačí pouze definovat, jakou barvou se jednotlivé lexikální prvky budou zobrazovat. Nastaveno bylo také zobrazování řádků a implementováno automatické odsazení.

5.5 5.5.1

Implementace lexikálního a syntaktického analyzátoru Lexikální analyzátor

K realizaci lexikálního analyzátoru byla vytvořena třída P Lexical jejímž vstupem je objekt třídy wxString (uchovatel řetězce), který představuje vstupní pásku. Na základě aktuálního stavu uloženého v proměnné currentState a přečteného znaku, se aktuální stav mění. Změna stavu probíhá přes přepínací příkaz switch. Pokud analyzátor skončí v koncové konfiguraci (tedy v jednom z koncových stavů), vrátí následující strukturu: extern struct FTOKEN { wxString token; tokenType type; int countLine; wxString fileName; bool lastToken; } FToken; V proměnné token se nachází rozpoznané slovo a v proměnné type pak typ tokenu (číslo, řetězec, klíčové slovo, atd.). Proměnná countLine slouží jako uchovatel čísla aktuálně zpracovávaného řádku, fileName vrací jméno souboru, ve kterém se token nachází (použito při lexikální analýze připojeného modulu) a lastToken se nastaví

5.5

Implementace lexikálního a syntaktického analyzátoru

55

na hodnotu true v případě, že jsme na konci vstupu. Návrat nalezeného tokenu obstarává metoda s názvem GetToken(). V případě, že lex. analyzátor narazí na nepovolený znak, nastaví interně uvnitř sebe chybu. Ověřit, zda došlo nebo nedošlo k chybnému zpracování lze provést pomocí metody IsError(), která vrací v případě chyby hodnotu true. Hlášení o chybě lze získat pomocí metody GetError(). Vstupem lex. analyzátoru může být i fronta tokenů. Analyzátor pak neprovádí lex. analýzu, ale pouze vrací již rozeznaný token z vrcholu fronty. K tomuto účelu byla vytvořena metoda GetQueueToken(). 5.5.2

Syntaktický analyzátor

Klíčová slova i proměnné lze psát s diakritikou či bez diakritiky. Pro funkci syntaktického analyzátoru byly implementovány třídy P Syntax (analýza hlavního programu) a P Syntax File (analýza modulu). Vstupem je objekt třídy wxString reprezentující vstupní pásku a jméno souboru, který má být zkontrolován. Uvnitř sebe pak vytváří instanci třídy P Lexical, předává mu vstupní větu a navrácené tokeny dále zpracovává a kontroluje správnost jejich pořadí. Je vystavěn metodou rekurzivního sestupu, která simuluje činnost zásobníkového automatu a nekonečný zásobník je zde nahrazen zásobníkem systémovým. Pomocí metody Run() se spouští syntaktická analýza. Po ukončení analýzy je vhodné pomocí metody IsError(), která vrací true v případě chyby, zkontrolovat, zda-li proběhlo vše v pořádku. Jestliže nastala chyba, lze její znění získat pomocí metody GetError(). Druhý případ, který se může vyskytnout, je varování. Varování není chyba, ale spíše upozornění, že se uživatel snaží o něco, co sice na první pohled správně funguje, ale nemusí přinášet očekávaný výsledek. Jedná se zejména o volání funkcí, které vrací hodnotu, přímo v těle programu. Tato hodnota tak nebude nikdy zpracována a ztrácí se. Podobně jako u zpracování chyb, i zde existují dvě metody IsWarning() a GetWarning(), které varování zjistí a vrátí jeho znění. V případě, že nalezne příkaz připoj, otestuje existenci připojovaného souboru a pokud soubor existuje, vytvoří instanci třídy P Syntax File, která je potomkem rodičovské třídy P Syntax s pozměněným startovacím pravidlem. Soubor je načten do řetězce wxString, předán instanci a spuštěn nový syntaktický analyzátor opět pomocí metody Run(). V případě, že analýza modulu neskončí chybou, pokračuje hlavní analyzátor v místě, kde byl přerušen. Oba syntaktické analyzátory obsahují již první prvky sémantiky a připravují a naplňují struktury pro sémantický procesor. Kontrolují totiž existenci proměnných, volaných funkcí, správný počet parametrů a také možné kolize jak ve jménech funkcí, tak i proměnných. Mezi naplňované struktury patří lineární seznam funkcí

5.6

Implementace sémantických akcí a popis příkazů

56

a proměnných a fronta tokenů hlavního programu. Podrobný popis těchto struktur lze najít v souboru p structures.h.

5.6 5.6.1

Implementace sémantických akcí a popis příkazů Sémantický procesor

Implementaci sémantického procesoru řeší třída C Window. Protože styl programování pod operačním systém Windows značně komplikuje zařazení sémantických akcí přímo do syntaktického analyzátoru, byla zvolena forma jiná. Nyní je již jasné, že po průchodu syntaktickým analyzátorem je program napsaný syntakticky správně a lze se tedy zaměřit pouze na vykonávání sémantiky. Syntaktický analyzátor předává sémantickému procesoru celkem 3 struktury: lineární seznam funkcí (každý prvek seznamu obsahuje název funkce, lineární seznam parametrů, návratový typ a frontu tokenů), lineární seznam proměnných (obsahuje název, datový typ, rozměry pole a max. velikost indexů) a frontu tokenů hlavního programu. Sémantický procesor pak funguje na principu cyklu while, ve kterém jsou z vrcholu fronty tokenů postupně odebírány prvky a zásobníku, do kterého se ukládá struktura s momentálním stavem a výsledky sémantického procesoru. Tato struktura má název SEMANTIC STRUCT, je poměrně rozsáhlá a její obsah lze najít v souboru p semantic structures.h. Na počátku vykonávání hlavního programu se stav sémantického procesoru nastaví na hodnotu S ZACATEK. V tomto stavu očekává příkaz nebo volání funkce. Dle načteného tokenu a aktuálního stavu pak rozhodne do jakého stavu se má přepnout. Je-li aktuální stav S ZACATEK a vrácený token obsahuje např. příkaz vypiš, obsah aktuální struktury se uloží do zásobníku, vytvoří se struktura nová a nastaví se stav S VYPIS. V dalších průchodech cyklem provede sémantický procesor všechny operace v tomto novém stavu a po jejich vykonání (po přečtení ukončovacího znaku příkazu) vyzvedne z vrcholu zásobníku uloženou strukturu a opět se nachází ve stavu, kdy očekává příkaz nebo volání funkce. Celý tento proces je umístěn v metodě OnTimerIntepreter, která je propojena s časovačem (třída wxTimer). Aby bylo dosaženo co největší rychlosti, běží cyklus while tak dlouho, dokud není potřeba aktualizovat okno (např. výpisem na obrazovku) nebo zadat vstup od uživatele. V tomto případě dojde k pozastavení časovače a po vykonání operace opět k jeho nastartování. Dále je zde nastaveno počítadlo step counter, které hlídá počet kroků vykonaných v cyklu. Limit je nastaven na 50 000 průchodů cyklem. Po tomto počtu kroků bez přerušení je použit příkaz break; pro přerušení cyklu a provedení taktu časovače. Toto je velmi důležité,

5.6


57

neboť kdyby byl prováděn výpočet, který by trval například 20 sekund, aplikace by se jevila jako „zamrzláÿ (ale ve skutečnosti by výpočet dále probíhal). 5.6.2

Datové typy a pole

Proměnné a konstanty je nejdříve potřeba deklarovat s příslušným datovým typem. Jazyk Punťa disponuje celkem 6 datovými typy: • celé číslo - celočíselný datový typ přebírá vlasnosti typu long int v C, který může nabývat hodnot od -2 147 483 648 do 2 147 483 647 • reálné číslo - datový typ uchovávající hodnoty s desetinnou čárkou (64bitový) • znak - znaky se uvádějí do apostrofů. Např. ’a’. Hodnotou může být vždy jen 1 znak • text - text je víceznakový datový typ a uvádí se na rozdíl od znaků do uvozovek. Např. "Ahoj!". • logická hodnota - může nabývat pouze hodnot PRAVDA a NEPRAVDA. Jedná se o výsledek logického výrazu, o kterém můžeme tvrdit, že je pravdivý nebo nepravdivý. • soubor - souborová proměnná slouží pro uchování informací o souboru. Může nabývat hodnot "*KONEC*", pokud jsme na konci soubor, respektive "*KONEC RADKU*" v případě, že se v souboru nacházíme na konci řádku. V ostatních případech není nastavena žádná hodnota. Pro usnadnění práce s jednotlivými hodnotami je použita třída wxString, respektive její rozšíření o možnost polí wxArrayString. Všechny hodnoty jsou interně standardně uloženy jako řetězec, k převodu na skutečný datový typ dochází až při použití nebo manipulaci s proměnnou. Protože Punťa umožňuje deklaraci polí, pro pohodlnější práci je obyčejná proměnná interně prezentována jako jednorozměrné pole o jednom prvku. Tato implementace pak výrazně zjednodušuje práci s poli. Pole lze adresovat indexem od 1 do max, kde max je maximální velikost pole. Protože předem není jasné, kolikarozměrné pole bude deklarováno, je nutné interně ukládat vše jako pole jednorozměrné (vektor) a jednotlivé indexy vícerozměrného pole přepočítávat. K tomuto účel byl odvozen následující vzorec: (i1 ∗ maxn ∗ maxn−1 ∗ . . . ∗ max2 ) + (i2 ∗ maxn ∗ .. ∗ max3 ) + . . . + (in−1 ∗ maxn ) + in kde i1 ..in jsou požadované indexy zmenšené o 1 a max2 ..maxn jsou maximální hodnoty indexů n-rozměrného pole. Tento přepočet zajišťuje CountArrayIndex, metoda třídy C Window.

5.6


5.6.3

58

Zpracování výrazů

Ke zpracování výrazů slouží implementace algoritmu slepé koleje, kdy čtení infixu probíhá zleva doprava. Jsou využity dva zásobníky: operandů a operátorů. Před zpracováním výrazu je zavolána metoda StartPostfix, která zásobníky připraví. Je-li ze vstupu přečten operand (číslo, řetězec, proměnná, znak, log. hodnota), jeho hodnota je uložena do zásobníku operandů pomocí přetížené metody AddOperand. V případě, že je přečten operátor a v zásobníku operátorů není uložen žádný prvek, je automaticky uložen do zásobníku. V opačném případě se kontroluje priorita přečteného operátoru s prioritou operátoru na vrcholu zásobníku a pokud je menší nebo rovna, dojde k výběru určitého počtu operandů ze zásobníku na základě arity operátoru a provede se výpočet pomocí metody UtilizeOperator. Nově vzniklý výsledek se opět uloží do zásobníku operandů jako nový operand. Tímto způsobem zbyde na konci výrazu na vrcholu zásobníku operandů výsledek celého výrazu, který je uložen do proměnné postfixResult pomocí metody ClearPostfix. Tato metoda také ruší zásobník a čistí paměť. Punťa také disponuje aliasy operátorů logického součinu, součtu a negace. Místo klasického &&, || nebo ! lze použít A, AND, NEBO, OR, NE a NOT. Při zpracování jsou tato slova nahrazena jejich původními symboly. Při zpracování výrazu v parametru nebo příkazu přiřazení je navíc prováděna typová kontrola, pokud typy extrémně nesouhlasí (např. pokoušíme-li se textový výsledek uložit do proměnné typu celé číslo), interpreter je zastaven a vypsána chyba. Přetypování výrazu umožňuje příkaz převeď. 5.6.4

Větvení

Jazyk disponuje dvěma druhy větvení. Umožňuje konstruovat úplnou i neúplnou podmínku typu if, resp. if-else. Druhým typem je přepínač typu switch. Když - jinak Po zpracování výrazu v podmínce je vyhodnoceno, zda-li je splněna nebo nikoliv a výsledek se uloží do proměnné conditionResult, která je součástí struktury sémantického procesoru. Na základě toho se provede kód v bloku podmínky nebo dojde k jeho vynechání, tedy cyklus prochází na prázdno, dokud nenarazí na ukončovací znak bloku. Jestliže podmínka splněna není a za blokem následuje klíčové slovo jinak, provede se kód uvedený v bloku umístěný za tímto klíčovým slovem. V opačném případě

5.6


59

je kód ignorován. Pokud je . . . Tento přepínač nejprve vyhodnotí výraz a výsledek si uloží do proměnné tempPostfixResult, která je součástí struktury sémantického procesoru. Na základě tohoto výsledku jsou pak hodnoty uvedené uvnitř přepínače postupně porovnávány a dojde-li ke shodě, provede se kód uvedený za dvojtečkou a do proměnné conditionPassed je uložena hodnota true. Jestliže žádná hodnota nevyhovuje (v proměnné conditionPassed je uloženo false), provede se kód uvedený za výchozí hodnotou jiné. Hodnota jiné není povinná, ale pokud ji uvedeme, musí být umístěna na konci přepínače. Zanořování podmínek sleduje proměnná deepFlag, která je rovněž součástí struktury sémantického procesoru. Využívá se kvůli tomu, že podmínka, která není splněna může mít ve svém bloku jiné podmínky. Proměnná se nastaví na hodnotu 1 a postupně se inkrementuje, pokud uvnitř podmínky existuje podmínka jiná. Po přečtení znaku pro ukončení bloku podmínky se opět dekrementuje. Pokud se dostane na 0, uzavírací znak bloku patří právě prováděné ignorované podmínce. Na hodnotě 0 skončí proto, že se ignoruje první levá závorka, čili jedna pravá musí přebývat. 5.6.5

Cykly

Jazyk nabízí k použití 3 druhy cyklů: s podmínkou na začátku, s podmínkou na konci a cyklus se známým počtem opakování. Cyklus zatímco Cyklus s podmínkou na začátku. Po vyhodnocení výrazu v podmínce dojde k provedení bloku příkazů uvnitř cyklu v případě, že podmínka splněna byla a k přeskočení příkazů a opuštění cyklu v případě, že podmínka splněna nebyla. Cyklus opakuj - dokud Cyklus s podmínkou na konci. Na rozdíl od cyklu zatímco jsou provedeny příkazy v těle cyklu minimálně jednou. Teprve poté proběhne vyhodnocení podmínky a v kladném případě jsou příkazy cyklu provedeny opakovaně, v opačném nikoliv.

5.6


60

Cyklus pro Cyklus se známým počtem opakování. Rozdíl oproti dvěma výše uvedeným cyklům spočívá v tom, že známe (nebo můžeme vypočítat) přesný interval hodnot, pro které má cyklus proběhnout. Implementačně jsou cykly řešené velmi podobně jako příkazy větvení. Hlavní rozdíl spočívá v tom, že nejprve dojde k nahrání cyklu do fronty tokenů, která v případě, že podmínka byla splněna, nahradí původní frontu uvnitř lexikálního analyzátoru. Původní fronta je uložena do zásobníku a po ukončení provádění cyklu (podmínka není nesplněna) dochází ke zpětnému vložení původní fronty a program pokračuje přesně v místě, kde byl cyklus ukončen. Tento způsob umožňuje i zanořování cyklů. 5.6.6

Matematické funkce

Punťa disponuje celkem 7 vestavěnými matematickými funkcemi: abs, sin, cos, tan, cotg, náhodné číslo a odmocnina. Provede se výpočet výrazu a po typové kontrole je výsledek uložen do proměnné postfixResult. Na podobném principu fungují i ostatní vestavěné funkce. 5.6.7

Standardní vstup a výstup

Standardní výstup zajištěň pomocí příkazu vypiš, který dokáže vypsat zadaný výraz. Na tomto místě není potřeba typová kontrola, protože příkaz vypiš je univerzální. Výpis zajišťuje metoda WriteText třídy C RichtTextOutput, která představuje consoli. Ke smazání obrazovky slouží příkaz smaž obrazovku, který interně provede vymazání pomocí metody SetValue s parametrem prázdného řetězec. Standardní vstup řeší příkaz načti, který má jediný parametr a tím je proměnná nebo prvek pole. Možnost vstupu z klávesnice se aktivuje skrze metodu ActivateInputCtrl a uživatel tak může zadat hodnotu. Načtená hodnota je předána lexilánímu analýzatoru, který vyhodnotí jakého typu hodnota je. Pokud se datový typ hodnoty i proměnné extrémně neshodují, je zahlášena chyba. Práce se soubory (textovými) je také poměrně jednoduchá. Otevření souboru se zajistí přes příkaz otevři a uzavření přes příkaz zavři. Čtení ze souboru probíhá pomocí příkazu čti a chceme-li se přesunout na další řádek, je nutné použít příkaz další řádek. Při čtení se kontroluje, zda-li je načtená hodnota stejného datového typu nebo jeho podmnožinou. V případě, že požadovný datový typ a typ načtené

5.6


61

hodnoty extrémě nesouhlasí je zahlášena chyba. Funkce čti řádek načte celý řádek do textové proměnné. Zápis probíhá pomocí příkazu zapiš. 5.6.8

Práce s proměnnými typu Text

Ke zjištění počtu znaků uložených v textové proměnné nebo řetězci slouží funkce délka textu. Ta vrací celé číslo jako počet znaků výsledku výrazu uvedeného v parametru. Protože Punťa neumožňuje indexovat přímo prvky textových proměnných (jejich znaky), byla k tomu vytvořena příslušná funkce vrať znak, která vrátí požadovaný znak určený číselnou hodnotou. Pro přepis znaku slouží příkaz nastav znak, která v proměnné textového typu zamění znak na požadované pozici za nový. 5.6.9

Funkce definované uživatelem a globální proměnné

Definování funkcí probíhá tím způsobem, že za klíčové slovo funkce je uveden její název a v kulatých závorkách parametry (nepovinné). Pokud funkce bude vracet hodnotu, je třeba uvést po uzavírací kulaté zavorce klíčové slovo vrací a za ním jméno datového typu. Ve funkci se musí vyskytovat i klíčové slovo vrať a za ním výraz, který bude funkce navracet jako svůj výsledek. Příkaz vrať funkci neukončuje, ale pouze uloží interně výsledek do proměnné returnValue. Čili opětovným použitím příkazu dojde k přepsání výsledku. V případě, že klíčové slovo vrací není uvedené, z funkce se stává procedura. Chceme-li ve funkci použít globální proměnnou, napíšeme před název proměnné klíčové slovo globální. Tímto dojde k jasnému rozlišení, protože standardně se hledá proměnná pouze lokální. Definovaná funkce se volá svým jménem a v závorkách jsou uvedené čárkou oddělené parametry. Nejen počet parametrů musí být shodný, ale i jejich datové typy. Jazyk umožňuje předávání parametru pouze hodnotou, odkazem nikoliv. Volání funkcí funguje implementačně na podobném principu jako cykly. Fronta tokenů funkce je předána lexikálnímu analyzátoru a zvyší se hodnota proměnné current scope o 1, čímž se odliší proměnné funkce od proměnných hlavního programu nebo jiné funkce, ze které je volána. Formální parametry funkce jsou registrovány jako proměnné a k nim přiřazeny hodnoty ve formě výsledků výrazů skutečných parametrů.

5.6


5.6.10

62

Práce s grafikou

Režim kreslení se zapíná pomocí příkazu zapni kreslení a vypnutí probíhá pomocí vypni kreslení. Zapnutím kreslícího režimu je možné používat příkazy kresli bod a přesuň se na. Jestliže zapnutý režim kreslení není a dojde k použití těchto příkazů, interpreter zahlásí chybu. Příkaz kresli bod nejdříve přesune postavu Punti na zadané souřadnice, kde také dojde k vykreslení bodu. Příkaz přesuň se na pouze přesouvá postavu na zadané souřadnice, ale nekreslí. Slouží zejména k těm účelům, kdy chceme vypsat text na určitých souřadnicích pomocí příkazu vypiš. K výpočtu úhlu rotace Punti do směru běhu se provádí přes praktickou aplikaci transformace Kosinovy věty (Obr. 13).

Obr. 13: Využití Kosinovy věty při grafických operacích

Posledním zástupcem z příkazů pro práci s grafickou stránkou je příkaz nastav barvu, který nastavuje barvu písma v textové consoli a zároveň i barvu pixelu při kreslení. 5.6.11

Zpracování chyb

Punťa hlídá nejčastější sémantické chyby a ihned na ně přesně upozorňuje. Mezi tyto se řadí: • • • •

dělení nulou, popř. špatné použití operátorů nesouhlasící očekávaný datový typ a datový typ výsledku výrazu špatná indexace prvku pole zápis (čtení) do (z) neotevřeného souboru

5.6


63

• špatné použití příkazu další řádek • pokus o přepsání znaku mimo rozsah textu • použití grafických příkazu bez zapnutého režimu kreslení Společně s chybou je vypsáno i číslo řádku (a popřípadě jméno souboru, pokud je chyba v připojeném modulu) pro snadnou identifikaci chyby a program je ukončen.

6

6

DISKUSE

64

Diskuse

Aplikace byla v průběhu svého vývoje testována ve vybraných cvičeních předmětu Výpočetní technika a algoritmizace II vyučovaného na PEF MENDELU v Brně. Na testování se podílelo celkem 64 studentů a 3 pedagogičtí pracovníci, jmenovitě Mgr. Tomáš Foltýnek, Ph.D., Mgr. Jitka Machalová, Ph.D. a Ing. Miroslav Cepl. Cvičící sdělovali svoje i připomínky studentů skrze diskusi zřízenou na webu aplikace http://punta.pef.mendelu.cz nebo elektronickou poštou. Aby bylo nějakým způsobem možné vyhodnotit o dosavadní zkušenosti studentů a studentek, byli po ukončení vývoje vyzváni k vyplnění dotazníku (jeho celé znění je uvedeno v příloze E). Na tuto výzvu reagovalo 39 osob (12 mužů a 27 žen), což je 61 % zúčastněných. Respondenti hodnotili Punťu ve dvou hlavních aspektech. Prvním bylo srovnání s jiným programovacím jazykem a druhý se zabýval vlastnostmi, které od vývojového prostředí očekávají a zda-li tato očekávání Punťa splnil.

Obr. 14: Graf 1: Vyhodnocení předchozích zkušeností s prg. jazyky

Většina studentů neměla žádné zkušenosti s programovacím jazyky a zápisy algoritmů. Punťa byl jejich první aplikací.

6

DISKUSE

65

Obr. 15: Graf 2: Předchozí zkušenosti s jazyky

Na otázku otázku ohledně předchozích zkušeností odpovědělo 9 studentů z 10, kteří v předchozí otázce odpověděli, že mají jisté zkušenosti se zápisem algoritmů v programovacím jazyce. Nejvíce studentů zkoušelo Punťu po absolvování výuky jazyka Pascal, což je i programovací jazyk paralelně vyučovaný v předmětu, ve kterém se Punťa testoval.

Obr. 16: Graf 3: Srovnání kvality výukových nástrojů

80 % studentů z 10 respondetů, co měli již zkušenosti se zápisem algoritmů v programovacím jazyce, je přesvědčeno, že Punťa je lepší nástroj pro výuku algoritmizace než jejich předchozí jazyk.

6

DISKUSE

66

Obr. 17: Graf 4: Očekávané vlastnosti

V otázce ohledně kladených požadavků na příjemné výukové prostředí mohli respondenti označit i více možností. Nejvíce studentů vyžaduje jednoduchý přístup a intuitivnost. Na druhém místě se umístila česká syntaxe, která potvrzuje domněnku, že českým uživatelům více vyhovuje.

Obr. 18: Graf 5: Splnění požadavků

Na základě předchozí otázky byly studenti dotázáni, zda-li Punťa tato očekávání splnil. Z grafu 5 je patrné, že ve velké míře tomu tak bylo.

6

DISKUSE

67

Obr. 19: Graf 6: Spokojenost s aplikací

S aplikací bylo spokojeno 95 % (berou se v uváhu možnosti zcela spokojen(a) a spokojen(a), ale s výhradami), což je drtivá většina respondetů. Nespokojeno bylo pouhých 5 %, kteří svou nespokojenost patřičně vyjádřili v připomínkách. Nejčastěji padaly stížnosti na nedostatečné materiály a nápovědu, které v době testování byly dostupné v nepříliš propracované formě. Nyní vyvstává otázka, jakým směrem by se měla aplikace dále uplatňovat? Jedna z negativní přípomínek zněla ve smyslu nevyužitelnosti programu v praxi. Punťa je výukový program a pro tyto účely byl také navrhnut. Co se tedy týče praktické využitelnosti, pravděpodobně by se mohl uchytit na školách nebo v zájmových kroužcích věnujících se problematice algoritmizace a rozvoje logického myšlení. V implementační části má však stále ještě rezervy. Absence ukazatelů a předávání parametrů odkazem znemožňuje procvičení práce s operační pamětí a dynamickými strukturami. Problematika polí by si zasluhovala lepší řešení, které by umožňovalo adresovat prvky (znaky) textových proměnných přímo přes index pole, jako je tomu např. v jazyce C. V této oblasti je stále, co zlepšovat.

7

7

ZÁVĚR

68

Závěr

Cílem této práce bylo navrhnout a implementovat nový programovací jazyk Punťa s českou syntaxí a vlastní vývojovým prostředím určený pro výuku algoritmizace. Pro úspěšné splnění cíle bylo potřeba nastudovat problematiku teorie programovacích jazyků, která je podrobně rozebrána v teoretické části této práce a uplatnit tyto poznatky při praktickém návrhu a implementaci. Dále bylo nutné analyzovat současný stav dostupných produktů pro výuku algoritmizace. Charakteristiku jednotlivých aplikací doplňuje vyjádření ohledně jejich metodické vhodnosti a cenové dostupnosti. Těžiště vlastní práce pak spočívá v praktickém návrhu a implementaci jazyka včetně vývojového prostředí. Návrh začíná popisem gramatiky lexikálního analyzátoru a bezkontextové gramatiky syntaktického analyzátoru. Následuje návrh a implementace vývojového prostředí. Tato část je zakončena popisem implementace sémantických akcí a příkazů nově navrženého jazyka. Diskuse se zabývá problematikou budoucího vývoje aplikace a programovacího jazyka. Na základě zpětné vazby v podobě dotazníku, jehož výsledky jsou v diskusi rovněž uvedené, lze konstantovat, že svůj účel aplikace splňuje. Výsledkem praktické části je tedy funkční vývojové prostředí, které bylo po dobu svého půlročního vývoje důkladně testováno studenty předmětu Výpočetní technika a algoritmizace II vyučovaného na PEF MENDELU v Brně. Aplikace je dostupná na přiloženém CD (společně s dokumentací) nebo na internetových stránkách k tomuto účelu zřízených: http://punta.pef.mendelu.cz, kde si ji lze stáhnout a vyzkoušet.

8

8

LITERATURA

69

Literatura

Beneš, M. Kapitola 2. Lambda kalkul [online]. 2006 [cit. 2010-05-19]. VŠB — Katedra informatiky FEI VŠB-TUO. Dostupné z WWW: . Beránek, L. Algoritmy a datové struktury. 2008 [cit. 2010-05-18]. Dostupné z WWW: . Častorál, Z. Nebojte se počítače 1. vydání. Praha : Práce, 1991. 56 s. ISBN 80-208-0123-5. Černá, I.; Křetínský, M.; Kučera, A. Automaty a formální jazyky I [online]. 2002 [cit. 2010-05-16]. Dostupné z WWW: . Češka, M. Teoretická informatika : Učební texty [online]. 2002 [cit. 2010-05-19]. Dostupné z WWW: . Diviš, J. Algoritmizace [online]. [cit. 2010-05-18]. Algoritmizace. Dostupné z WWW: . Dosedla, M. DTP – Základy programování [online]. 2006 [cit. 2010-05-19]. Katedra technické a informační výchovy - PedF MU Brno. Dostupné z WWW: . Dostál, H. Teorie konečných automatů, regulárních gramatik, jazyků a výrazů [online]. 2008 [cit. 2010-05-21]. Dostupné z WWW: . Dvorský, J. Algoritmy I. [online]. Poslední aktualizace 2007-02-28 [cit. 2010-05-16]. Dostupné z WWW: . Elbl, S. Sémantika programovacích jazyků [online]. Brno, 2003. 13 s. Semestrální práce. VUT Brno. Dostupné z WWW: . Havelková, H. Algoritmy [online]. Poslední aktualizace 2008-09-30, [cit. 2010-05-16]. Dostupné z WWW: . Kadlec, J. Obecné pojednání o programovacích jazycích Linuxsoft [online]. 2004-07-16, [cit. 2010-05-18]. Dostupný z WWW: .

8

LITERATURA

70

Knuth, D. E. Umění programování : 1. díl, Základní algoritmy. Vydání první. Brno : Computer Press, a.s., 2008. 672 s. ISBN 978-80-251-2025-5. Szabó, Z. G. Noam Chomsky [online]. 2004 [cit. 2010-05-21]. Chomsky.info. Dostupné z WWW: . Šorm, M.; Rybička, J.; Haluza, P. Formální jazyky a automaty - základní kurz [online] , 2006. Elektronická opora. MZLU PEF v Brně. Dostupné z WWW: . World of Mathematics Biography . World of Mathematics on Alonzo Church. [online]. c2006 [cit. 2010-05-17]. Dostupné z WWW: . www.manualy.net Algoritmy: Teoretický úvod [online]. 2006-02-25 [cit. 2010-0516]. Dostupné z WWW: .

Přílohy

A

A

NEDETERMINISTICKÝ A DETERMINISTICKÝ KONEČNÝ AUTOMAT

72

Nedeterministický a deterministický konečný automat

NKA i DKA jsou umístěny na přiloženém CD ve složce navrhy v souboru lexical.xls.

B

B

73

SYNTAKTICKÉ DIAGRAMY


ZACATEK PRIPOJ

KONSTANTA

DEKPROM

DEFFCE

hlavni

program

MAINBLOK

PRIPOJ

pripoj

retezec

;

KONSTANTA

konstanta

dat typ

nazev

cislo ; = retezec znak log hodnota

B

74


DEKPROM

dat typ

nazev [ ; cislo ]

,

DEFFCE

funkce

dat (

nazev

typ

nazev

[ ]

,

) vraci datovy

typ

[ ]

MAINBLOK

MAINBLOK

DEKPROM

PRIKAZ

BLOK

{

{

PRIKAZ

}

}

B

75


PROMENNA globalni nazev nazev prom

prom

POLE [ LOGVYRAZ

]

PRIKAZ CWHILE

CFOR

CUNTIL

;

;

PRIRAD

VIF

VSWITCH

VOLFCE VYSTUP VSTUP

;

;

; SOUBORPRIK ; GRAFPRIK ; TEXTPRIK ; NAVRATHOD ; STOP ;

B

76


CWHILE

zatimco

PODMINKA

BLOK

CFOR

PROMENNA

pro

POLE

od

LOGVYRAZ

do

BLOK

CUNTIL

opakuj

BLOK

dokud

PODMINKA

PRIRAD

PROMENNA

POLE

=

LOGVYRAZ

VIF

kdyz

po LOGVYRAZ

LOGVYRAZ

PODMINKA

BLOK

jinak BLOK

B

77


VSWITCH

pokud

je

LOGVYRAZ

{

cislo : PRIKAZ znak retezec

jine PRIKAZ :

}

VOLFCE nazev LOGVYRAZ (

) ,

MATFCE

(

LOGVYRAZ

)

TEXTFCE

SOUBORFCE

PREVED

B

78


MATFCE abs sin cos tan cotg odmocnina nahodne cislo

TEXTFCE delka znaku ( LOGVYRAZ ) vrat znak ( LOGVYRAZ , LOGVYRAZ

)

SOUBORFCE otevri ( LOGVYRAZ cti ( PROMENNA cti radek ( PROM

LOGVYRAZ

,

POLE POLE

,

dat typ

)

PREVED

preved

(

LOGVYRAZ

,

dat typ

VYSTUP vypis ( LOGVYRAZ ) smaz obrazovku ( )

)

) )

B

79


VSTUP

nacti

PROMMENNA

(

POLE

)

SOUBORPRIK dalsi radek ( PROMMENNA POLE ) zavri zapis ( PROMENNA POLE , LOGVYRAZ )

GRAFPRIK zapni kresleni ( ) vypni kresleni kresli bod ( LOGVYRAZ , LOGVYRAZ presun se na nastav barvu ( LOGVYRAZ )

TEXTPRIK

nastav znak

LOGVYRAZ

(

POLE

NAVRATHOD vrat

LOGVYRAZ

PROMENNA

,

,

LOGVYRAZ

)

)

B

80


STOP

stop

PODMINKA

(

LOGVYRAZ

)

LOGVYRAZ && LV1 || xor

LOGVYRAZ

LV1 LV1

rel op

AVYRAZ

AVYRAZ AVYRAZ

+ AV1

B

81


AV1 AV1

* AV2 / %

AV2 AV2

∧ LV2 .

LV2 LV2

AV3 !

AV3 ( LOGVYRAZ cislo retezec znak log hodnota PROMENNA VOLFCE

)

POLE

C

C

VÝPOČET MNOŽIN FIRST A FOLLOW

82


1. FF(ZACATEK → . . . ): FI = {pripoj, konstanta, dat typ, funkce, hlavni program} 2. FF(PRIPOJ → . . . ): FI = {pripoj, }, FO = {konstanta, dat typ, funkce, hlavni program} 3. FF(KONSTANTA → . . . ): FI = {konstanta, }, FO = {dat typ, funkce, hlavni program} 4. FF(KONS1 → . . . ): FI = {cislo, retezec, znak, log hodnota} 5. FF(DEFFCE → . . . ): FI = {funkce, }, FO = {hlavni program} 6. FF(DF1 → . . . ): FI = {dat typ, }, FO = {)} 7. FF(DF2 → . . . ): FI = {[, }, FO = {, , )} 8. FF(DF3 → . . . ): FI = {dat typ, }, FO = {)} 9. FF(DF4 → . . . ): FI = {vraci, }, FO = {{} 10. FF(DF5 → . . . ): FI = {[, }, FO = {{} 11. FF(MAINBLOK → . . . ): FI = {{} 12. FF(DEKPROM → . . . ): FI = {dat typ, }, FO = {prikazy} 13. FF(DEKPROM1 → . . . ): FI = {[, }, FO = {, , ;} 14. FF(DEKPROM2 → . . . ): FI = {, , }, FO = {;} 15. FF(PRIK1 → . . . ): FI = {prikazy , }, FO = {{, +, -, cislo, znak, retezec, jine} 16. FF(PRIKAZ → . . . ): FI = {prikazy} 17. FF(BLOK → . . . ): FI = {{} 18. FF(PROM → . . . ): FI = {globalni, nazev prom} 19. FF(CWHILE → . . . ): FI = {zatimco} 20. FF(CFOR → . . . ): FI = {pro} 21. FF(CFOR1 → . . . ): FI = {po, }, FO = {{} 22. FF(CUNTIL → . . . ): FI = {opakuj} 23. FF(PRIRAD → . . . ): FI = {globalni, nazev prom} 24. FF(POLE → . . . ): FI = {[, }, FO = {{,od, do, po, log operatory, aritm operatory, rel operatory, ), , ;, =, ]} 25. FF(VIF → . . . ): FI = {kdyz} 26. FF(VIF1 → . . . ): FI = {jinak, }, FO = {prikazy, jine, +, -, cislo, retezec, znak, log hodnota, }} 27. FF(VSWITCH → . . . ): FI = {pokud} 28. FF(VSWITCH2 → . . . ): FI = {jine, +, -, cislo, retezec, znak, log hodnota, }, FO = {}} 29. FF(VSWITCH1 → . . . ): FI = {jine, +, -, cislo, retezec, znak, log hodnota} 30. FF(VSWITCH3 → . . . ): FI = {+, -, cislo, retezec, znak, log hodnota}

C


83

31. FF(VSWITCH4 → . . . ): FI = {prikazy, }, FO = {+, -, cislo, retezec, znak, log hodnota} 32. FF(OP1 → . . . ): FI = {+, -, }, FO = {cislo} 33. FF(VOLFCE → . . . ): FI = {nazev fce, abs, sin, cos, tan, cotg, odmocnina, nahodne cislo, vrat znak, delka textu, preved, otevri, cti, cti radek}, FO = {+, -, cislo, retezec, znak, log hodnota} 34. FF(VOLFCE1 → . . . ): FI = {nazev fce, abs, sin, cos, tan, cotg, odmocnina, nahodne cislo, vrat znak, delka textu, preved, otevri, cti, cti radek cislo, retezec, znak, log hodnota,-, globalni, nazev prom,!, }, FO = {)} 35. FF(VOLFCE2 → . . . ): FI = {, , }, FO = {)} 36. FF(VOLFCE3 → . . . ): FI = {abs, sin, cos, tan, cotg, odmocnina, nahodne cislo} 37. FF(TEXTFCE → . . . ): FI = {delka textu, vrat znak} 38. FF(SOUBORFCE → . . . ): FI = {cti, cti radek, otevri} 39. FF(PREVED → . . . ): FI = {preved} 40. FF(VYSTUP → . . . ): FI = {smaz obrazovku, vypis} 41. FF(VSTUP → . . . ): FI = {nacti} 42. FF(STOP → . . . ): FI = {stop} 43. FF(SOUBORPRIK → . . . ): FI = {zapis, dalsi radek, zavri} 44. FF(TEXTPRIK → . . . ): FI = {nastav znak} 45. FF(GRAFPRIK → . . . ): FI = {zapni kresleni, vypni kresleni, kresli bod, presun se na, nastav barvu} 46. FF(GRAFPRIK1 → . . . ): FI = {zapni kresleni, vypni kresleni} 47. FF(NAVHOD → . . . ): FI = {vrat} 48. FF(PODMINKA → . . . ): FI = {(} 49. FF(LOGVYRAZ → . . . ): FI = {nazev fce, abs, sin, cos, tan, cotg, odmocnina, nahodne cislo, vrat znak, delka textu, preved, otevri, cti, cti radek cislo, retezec, znak, log hodnota,-, globalni, nazev prom,!} 50. FF(LOGVYRAZ1 → . . . ): FI = {&&, ||, xor, }, FO={ ), ;, , do, po, {, ] } 51. FF(LV1 → . . . ): FI = {nazev fce, abs, sin, cos, tan, cotg, odmocnina, nahodne cislo, vrat znak, delka textu, preved, otevri, cti, cti radek cislo, retezec, znak, log hodnota,-, globalni, nazev prom, !} 52. FF(LV11 → . . . ): FI = {rel op, }, FO = {), ;, , do, po, {, ], &&, || } 53. FF(AVYRAZ → . . . ): FI = {nazev fce, abs, sin, cos, tan, cotg, odmocnina, nahodne cislo, vrat znak, delka textu, preved, otevri, cti, cti radek cislo, retezec, znak, log hodnota,-, globalni, nazev prom, !} 54. FF(AVYRAZ1 → . . . ): FI = {+, -, }, FO = {), ;, , do, po, {, ], &&, ||, xor, rel op }

C


84

55. FF(AV1 → . . . ): FI = {nazev fce, abs, sin, cos, tan, cotg, odmocnina, nahodne cislo, vrat znak, delka textu, preved, otevri, cti, cti radek cislo, retezec, znak, log hodnota,-, globalni, nazev prom, ! } 56. FF(AV11 → . . . ): FI = {*, /, %, }, FO = {), ;, , do, po, {, ], &&, ||, xor, rel op, +, - } 57. FF(AV2 → . . . ): FI = {nazev fce, abs, sin, cos, tan, cotg, odmocnina, nahodne cislo, vrat znak, delka textu, preved, otevri, cti, cti radek cislo, retezec, znak, log hodnota,-, globalni, nazev prom, ! } 58. FF(AV21 → . . . ): FI = {∧, ., }, FO = {), ;, , do, po, {, ], &&, ||, xor, rel op, +, -, *, /, % } 59. FF(LV2 → . . . ): FI = {nazev fce, abs, sin, cos, tan, cotg, odmocnina, nahodne cislo, vrat znak, delka textu, preved, otevri, cti, cti radek cislo, retezec, znak, log hodnota,-, globalni, nazev prom, ! } 60. FF(AV3 → . . . ): FI = {nazev fce, abs, sin, cos, tan, cotg, odmocnina, nahodne cislo, vrat znak, delka textu, preved, otevri, cti, cti radek cislo, retezec, znak, log hodnota,-, globalni, nazev prom} Kolize množin FI a FO ani v jednom případě nenastala, průnikem vždy vzniká prázdná množina, gramatika je typu LL(1). Výpočet pro modul není potřeba protože je podmnožinou gramatiky hlavního programu.

D

D

ZÁSOBNíKOVÝ AUTOMAT

85


Tabulka zásobníkového automatu je umístěna na přiloženém CD ve složce navrhy v souboru zas automat.xls.

E

DOTAZNíK

E

86

Dotazník

Punťa - vývojové prostředí pro výuku základů algoritmizace Vážení respondenti, chtěl bych Vás poprosit o vyplnění následujícího krátkého dotazníku. Jeho vyplnění by Vám nemělo zabrat více než 5 minut. Dotazník slouží jako zpětná vazba mezi studenty a studentkami předmětu Výpočetní technika a algoritmizace II a autorem aplikace, která byla v tomto předmětu testována. Tento průzkum je plně anonymní a jeho výsledky budou využity v diplomové práci. Průzkum bude ukončen 18. 5. 2010. Děkuji za vyplnění, Bc. Marek Fojtl 1. Setkali jste se dříve než na vysoké škole se zápisem algoritmů ve vybraném programovacím jazyce? (pokud odpovíte ne, pokračujte otázku č. 4) a) ano b) ne 2. V jakém jazyce to bylo? a) Java b) Javascript c) Jazyk C, C++ d) Pascal e) Visual Basic f) Jiný: 3. Punťa je podle Vás ve srovnání s jazykem, ve kterém jste pracovali dříve: a) lepší nástroj na naučení základů algoritmizace b) horší nástroj na naučení základů algoritmizace 4. Co byste očekával(a) od vývojového prostředí a jazyka pro výuku algoritmizace na českých školách? a) jednoduché a intuitivní ovládání b) pěkné grafické zpracování c) programovací jazyk s jednoduchou českou syntaxí d) zábavnost e) velké množství dostupných funkcí a knihoven f) Jiné:

E

DOTAZNíK

87

5. Splnil Punťa Vaše očekávání? (V případě, že odpovíte ano, pokračujte otázkou č. 6) a) ano b) ne 6. Proč nesplnil Punťa Vaše očekávání? (Na tuto otázku odpovídejte POUZE v případě, že jste na předchozí odpověděli NE.) 7. S aplikací, s příhlednutím na to, že to byla testovací verze, jste byl(a) celkově a) zcela spokojen(a) b) spokojen(a), ale s výhradami c) nespokojen(a), ale má i své kladné stránky d) zcela nespokojen(a) 8. Jste a) muž b) žena 9. Prostor pro vaše připomínky:

F

UKÁZKOVÝ PŘíKLAD

F

Ukázkový příklad

Faktoriál rekurzí funkce faktorial(cele_cislo $cislo) vraci realne_cislo { kdyz ($cislo==0) { vrat 1; } jinak { vrat $cislo * faktorial($cislo - 1); } } hlavni_program { cele_cislo $cislo; vypis("Program: Faktorial2\n\n"); vypis("Zadejte cislo, pro ktere chcete spocitat faktorial:"); nacti($cislo); vypis(faktorial($cislo)); }

Více příkladů lze nalézt společně s aplikací na přiloženém CD.

88

základů algoritmizace

Recommend Documents