Návrh algoritmů pro sémantické akce při výstavbě interpretu metodou rekurzivního sestupu

Mendelova zemědělská a lesnická univerzita v Brně Provozně ekonomická fakulta

Návrh algoritmů pro sémantické akce při výstavbě interpretu metodou rekurzivního sestupu Diplomová práce

Vedoucí práce: RNDr. Ing. Milan Šorm, Ph.D.

Bc. Michal Růžička

Brno 2006

Na tomto místě bych rád poděkoval RNDr. Ing. Milanovi Šormovi, Ph.D. za odbornou přípravu a podporu při tvorbě mé diplomové práce.

Prohlašuji, že jsem tuto diplomovou práci vyřešil samostatně s použitím literatury, kterou uvádím v seznamu.

Brno 2. května 2006

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

4

Abstract Růžička, M. Algorithm design for semantic actions in interpreter building using the method of recursive descent. Diploma thesis, Brno, 2006. The thesis is dealing with construction of own language interpreter. It describes successive development of the solution of lexical analysis, syntactic analysis and semantic actions implementation. In the thesis is solved developing of Chomsky grammar, generation of regular grammar and finite state machine construction. Syntactic analysis is design using the method of recursive descent witch improve the syntax graph and pushdown automaton. The thesis describe the semantic actions implementation.

Abstrakt Růžička, M. Návrh algoritmů pro sémantické akce při výstavbě interpretu metodou rekurzivního sestupu. Diplomová práce. Brno, 2006. Práce se zabývá konstrukcí interpreta vlastního programovacího jazyka. Popisuje postupný vývoj řešení lexikální analýzy, syntaktické analýzy a implementaci sémantických akcí. V práci je postupně řešen návrh gramatik typu 3 Chomského klasifikace, regularizace gramatiky a konstrukce deterministického konečného automatu. Syntaktická analýza je prováděna metodou rekurzivního sestupu za využití grafů syntaxe a zásobníkového automatu. Práce popisuje implementaci sémantických akcí.

5

OBSAH

Obsah 1 Úvod a cíl práce 1.1 Úvod do problematiky . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Cíl práce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8 8 8

2 Použitá literatura

10

3 Teoretická analýza problému 3.1 Základní pojmy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Pojem gramatika . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Jazyky typu 3 Chomského klasifikace . . . . . . . . . . . . . . . . 3.3.1 Lineární a regulární gramatika . . . . . . . . . . . . . . . . 3.3.2 Konečný automat . . . . . . . . . . . . . . . . . . . . . . . 3.3.3 Ekvivalence konečných automatů a gramatik typu 3 . . . . 3.3.4 Převod nedeterministického automatu na deterministický . 3.4 Bezkontextové gramatiky a jazyky . . . . . . . . . . . . . . . . . . 3.4.1 Syntaktická analýza . . . . . . . . . . . . . . . . . . . . . . 3.4.2 Grafy syntaxe . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.3 Zásobníkový automat . . . . . . . . . . . . . . . . . . . . . 3.5 Deterministické bezkontextové jazyky . . . . . . . . . . . . . . . . 3.5.1 Deterministický zásobníkový automat . . . . . . . . . . . . 3.5.2 LL jayzky a gramatiky . . . . . . . . . . . . . . . . . . . . 3.5.3 Levá rekurze . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5.4 Množiny FIRST a FOLLOW . . . . . . . . . . . . . . . . . 3.5.5 Gramatika typu LL(1) . . . . . . . . . . . . . . . . . . . . 3.5.6 Algoritmus syntaktické analýzy pro gramatiku typu LL(1) 3.6 Sémantické akce . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.7 Programovací jazyk C . . . . . . . . . . . . . . . . . . . . . . . . 3.8 Textový editor VIM . . . . . . . . . . . . . . . . . . . . . . . . . .

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

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

11 11 13 15 15 16 17 17 18 19 19 20 22 23 23 24 25 26 26 27 27 28

4 Implementace lexikálního analyzátoru 4.1 Návrh . . . . . . . . . . . . . . . . . . . . 4.2 Abeceda . . . . . . . . . . . . . . . . . . . 4.3 Lineární gramatiky . . . . . . . . . . . . . 4.4 Významové a nevýznamové jazyky . . . . 4.5 Lineární gramatika lexikálního analyzátoru 4.6 Regularizace lineární gramatiky . . . . . . 4.7 Nedeterministický konečný automat . . . . 4.8 Deterministický konečný automat . . . . . 4.9 Programování lexikálního analyzátoru . . .

. . . . . . . . .

. . . . . . . . .

30 30 31 31 35 36 37 39 39 40

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

6

OBSAH

5 Implementace syntaktického analyzátoru 5.1 Rozklad věty pomocí grafů syntaxe . . . . . . . . . . . 5.2 Návrh deterministické bezkontextové gramatiky . . . . 5.3 Ověření LL(1) gramatiky . . . . . . . . . . . . . . . . . 5.4 Konstrukce deterministického zásobníkového automatu 5.5 Syntaktický analyzátor . . . . . . . . . . . . . . . . . . 6 Implementace sémantických akcí 6.1 Výrazy . . . . . . . . . . . . . . . 6.2 Příkaz přiřazení . . . . . . . . . . 6.2.1 Inicializace proměnné typu 6.2.2 Inicializace proměnné typu 6.2.3 Inicializace proměnné typu 6.3 Příkaz větvení . . . . . . . . . . . 6.4 Příkaz cyklu . . . . . . . . . . . . 6.5 Podprogramy . . . . . . . . . . . 7 Dokumentace 7.1 Základní struktura 7.2 Výrazy . . . . . . . 7.3 Přiřazení . . . . . . 7.4 Větvení . . . . . . 7.5 Cykly . . . . . . . 7.6 Podprogramy . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . . . . . . . . . . . . . . konstanta nebo pole . . . . . . pointer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . .

. . . . . . . . řetězec . . . . . . . . . . . . . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . .

. . . . . . . .

. . . . . .

. . . . .

. . . . . . . .

. . . . . .

. . . . .

. . . . . . . .

. . . . . .

. . . . .

. . . . . . . .

. . . . . .

. . . . .

. . . . . . . .

. . . . . .

. . . . .

. . . . . . . .

. . . . . .

. . . . .

45 45 49 52 52 53

. . . . . . . .

55 55 57 58 59 60 60 61 63

. . . . . .

67 67 67 67 68 68 69

8 Závěr

71

9 Literatura

73

Přílohy

74

A Přechodová funkce

75

B Deterministický konečný automat

77

C Syntaktické diagramy

79

D Bezkontextová deterministická gramatika LL(1)

84

E Ověření gramatiky typu LL(1)

85

F Vypočítané množiny FIRST a FOLLOW

91

G Deterministický zásobníkový automat

93

OBSAH

7

H Dynamické struktury

97

I

99

Sémantické akce

J Ukázkový program jazyka Ruzin

101

1

ÚVOD A CíL PRÁCE

1 1.1

8

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

Současná doba již delší dobu vykazuje podstatný růst významu technických a technologických prostředků. Pojmy hardware a software začínají být naprosto běžnými slovy, kterým rozumí i laická veřejnost. Osobní počítač začíná vlastnit stále více lidí a stále více lidí chce proniknout do tajů strojových kódů ve snaze pochopit způsob, jakým počítače pracují. Aby mohl člověk pracovat s počítačem, musí být schopný s ním nějakým způsobem komunikovat. Veškeré aplikace nebo programy používané člověkem pro dorozumění se s počítačem, musel nejprve nějaký jiný člověk – programátor – zkonstruovat. Tak, jako lidé mezi sebou komunikují prostřednictvým jazyka, tak i jádrem dorozumění s počítačovým programem je nějaký jazyk. Počítač však s lidmi nehovoří jejich mateřským jazykem, nebo nějakým jiným, světově uznávaným lidským jazykem. Počítač dokáže zpracovávat dvě různě velké hodnoty elektrického napětí. Podle stavu napětí, pak dokáže rozpoznat nuly a jedničky, respektive binární kód. Počítač tedy rozumí pouze jazyku v binární podobě, tzv. strojovému kódu. Jazyk složený z nul a jedniček je však z pochopitelných důvodů obtížně čitelný pro člověka. Také zapisování sekvence nul a jedniček může přerůst v marné hledání případné chyby v záznamu. I když v počátcích programování byli programátoři nuceni opravdu zapisovat své programy ve strojovém kódu, rychle přišli na to, jak si ulehčit práci. Mnohem jednodušší formou práce s binárními instrukcemi je použití překladače. Jak již název napovídá, jedná se o „tlumočeníÿ konkrétního zápisu instrukce do strojového kódu. Překladač používá přesně definovanou sadu výrazů, které reprezentují strojové instrukce. Pomocí překladačů lze tedy počítači nařídit, aby provedl právě to, co programátor chce. Zvyšující se nároky programátorů a zvyšování složitosti zpracovávaných úkolů mají za následek růst nároků na samotné programovací jazyky. Postupný vývoj v této oblasti přináší počítačové jazyky vyšší úrovně.

1.2

Cíl práce

Cílem této diplomové práce je navrhnout funkční interpret jazyka Ruzin, zasazený do mého kraje – Jižní Moravy. Klíčová slova představující příkazy pro vykonání potřebných instrukcí nejsou standardně používané anglické synonyma, jako jsou například if nebo while, ale slova vyskytující se v hovorovém nářečí. Interpret je provozován na platformě jazyka C, ve kterém je samotný interpret naprogramován. Přímý překlad do binárního kódu neprovádí samotný překladač, ale děje se tak prostřednictvím použitého programovacího jazyka C. Konstrukce jayzka se skládá ze tří základních částí, které na sebe navazují. Nejdříve je nutné vytvořit lexikální analyzátor potřebný pro identifikaci slov užíva-

1.2

Cíl práce

9

ných jazykem. Návaznost na něj má konstrukce syntaktyckého analyzátoru, který určuje správnou syntaxi jazyka. Posledním krokem je vytvoření sémantických akcí, na jejichž základě bude jazyk provádět operace definované ve zdrojovém kódu. Programovací jazyk má podporovat dávkové programy. Programy tohoto typu se typicky spouštějí z příkazového řádku. Zpracovávaná data se zadávají přímo na obrazovku pomocí klávesnice, nebo jsou umístěna v datovém souboru.

2

2

POUŽITÁ LITERATURA

10

Použitá literatura

Celá diplomová práce, na které pracuji, vychází z obsahu předmětu Teorie programovacích jazyků vyučovaného na Ústavu informatiky Mendelovy zemědělské a lesnické univerity v Brně. Cílem předmětu je naučit studenta teoretickou část problematiky formálních jazyků, na základě které je schopen zkonstruovat vlastní překladač. Podklady pro výuku jsou studentovy předkládány formou poznámek a komentářů k vysvětlované látce. Podle těchto poznámek se v mé diplomové práci řídím a jsou páteří mé práce. Učební pomůckou při studiu i při tvorbě mé diplomové práce je podpůrný text Úvod do teorie formálních jazyků (Rybička, 1999), který velmi stručně a věcně charakterizuje problematiku formálních jazyků a kde jsou uvedeny příklady základních implementačních technik. Z této brožury velmi často cituji v části teoretická analýza problému, protože je zde velice přehledně a výstižně popsaná problematika, o kterou se zajímám. Velice dobrý popis formálních jazyků a gramatik, regulárních jazyků, bezkontextových gramatik a jazyků, zásobníkových automatů a popisu syntaktické analýzy obsahuje učebnice Gramatiky a Jazyky (Molnár, Češka, Melichar, 1987). Původ této učebnice sahá sice až do minulého století, ale zákonitosti formálních jazyků popsané v knize stále zůstávají neměnnými a pro mou diplomovou práci jsou dostačující. Učebnice je velice kvalitním zdrojem informací nejen pro mou práci, ale obecně velmi dobře analyzuje problematiku formálních jazyků a jejich gramatik. V některých případech citací čerpám z internetových zdrojů, uvedených v kapitole literatura. Jazyk Ruzin je programovaný v jazyce C. Jednotlivé použité příkazy a popisy struktur jsem čerpal z Učebnice jazyka C (Herout, 2001). Tyto knihy jsou dostatečným materiálem pro popis programovacích technik použitých v diplomové práci. Zdrojový kód jazyka jsem zapisoval v textovém editoru VIM. Podrobné instrukce a návody, jak pracovat s tímto nástrojem, lze nalézt na www stránkách zabývajících se podrobným popisem tohoto textového editoru (Satrapa, 2001). Veškerá, zde zmíněná literatura, je použita jako zdroj informací při práci vynaložené na tvorbě jazyka Ruzin a psaní mé diplomové práce.

3

TEORETICKÁ ANALÝZA PROBLÉMU

3

11

Teoretická analýza problému

Popsaná literatura je dostatečným podkladem pro teoretické vypracování interpreta. Důležitým aspektem pro správné pochopení řešeného problému je vyjasnění používaných pojmů. Přesný předpis pro výkon nějaké činnosti, prováděné procesorem počítače, se nazývá program. Program je procesoru předkládán ve tvaru kódu, tj. jako posloupnost instrukcí procesoru — elementárních příkazů, které je daný procesor schopen přímo provádět. Autor formuluje program pomocí vhodného (a jemu známého) programovacího jazyka, ve tvaru zdrojového textu programu, jehož konverzi na proveditelný kód příslušného procesoru zajišťuje překladač. Podle celkové strategie překladu lze překladače klasifikovat kompilační a interpretační — kompilátory a interprety. Kompilátor je konverzní program, který přeloží hotový zdrojový text programu na cílový kód. Podmínkou získání spustitelného programu je bezchybné ukončení překladu v celém jeho rozsahu. Cílový kód je pak provozován nezávisle na kompilátoru, pokud však je třeba jeho činnost modifikovat, je nutné znovu přeložit celý zdrojový text. Interpret má pro spouštěný program funkci operačního prostředí — postupně čte, překládá a ihned vykonává jednotlivé příkazy (nebo větší jednotky) zdrojového textu. Výskyt jakékoliv chyby v textu je zjištěn až v okamžiku překladu chybného příkazu za běhu programu. Pokud se tentýž (bezchybný) příkaz provádí vícekrát, je před každým provedením znovu přeložen. Výhody a nevýhody obou koncepcí překladu jsou zřejmé. Interpretovaný program umožňuje interaktivní modifikaci rozsahu dat nebo dokonce zdrojového textu přímo za běhu, je však relativně pomalý a spustitelný pouze prostřednictvím překladače. Kompilátor připraví efektivní nezávislý program, který udržuje v operační paměti počítače pouze svůj kód a svá data, jehož prostředky pro interaktivní změny jsou však značně omezené (Polách, 2006). Programovací jazyk Ruzin je na základě předchozího vysvětlení interpretem. Zdrojový kód programu, psaného pro můj jazyk, je postupně zpracováván a případná chyba v kódu je zjištěna až v průběhu zpracování. Fakt, že se jedná o interpret deklaruje informace, že program lze spustit pouze prostřednictvím překladače. Samotný jazyk Ruzin se skládá z několika částí. Prvním krokem tvorby jazyka je konstrukce lexikálního analyzátoru, načítajícího jednotlivé tokeny. Syntaktickou správnost kódu ověřuje syntaktický analyzátor doplněný sémantickými akcemi. Teoretická východiska těchto jednotek jsou popsána v následujících kapitolách.

3.1

Základní pojmy

Tím, jak se člověk začíná učit mateřskou řeč, využívá písmena a hlásky, ze kterých vytváří slova a z nich věty. V problematice formálních jazyků je také vycházeno z prvotních znaků, tvořících abecedu jazyka. Ze symbolů jsou tvořena slova a celé věty.

3.1

12

Základní pojmy

Definice 3.1.1. Abeceda je konečná množina prvků, které nazýváme symboly. Libovolnou konečnou posloupnost skládající se ze symbolů dané abecedy nazýváme řetězec nebo slovo. Délkou slova w rozumíme počet symbolů ve slově, značíme ji |w|. Slovo s nulovou délkou nazýváme prázdné slovo a budeme ho označovat ε. Definice 3.1.2. Mějme abecedu Σ, pak libovolnou podmnožinu množiny Σ∗ nazýváme formální jazyk nad abecedou Σ. Uvedená definice jazyka je příliš všeobecná. Vniká přirozená otázka, jak jazyk popsat a jak ho specifikovat. Ze specifikace množin víme, že je lze specifikovat buď vyjmenováním všech prvků, nebo pomocí definice vlastnosti, kterou každý prvek musí mít. Jestliže jazyk je množinou prvků – slov, je možné ho specifikovat jedním z uvedených způsobů. Je-li množina slov daného jazyka konečná, nazýváme ho konečný jazyk, pokud je tato množina prázdná, nazýváme ho prázdný jazyk, je-li tato množina nekonečná, nazýváme jazyk nekonečný. Definice 3.1.3. Nechť L1 a L2 jsou jazyky, jejich zřetězením dostaneme jazyk L, přičemž L = {xy/x ∈ L1 ∧ y ∈ L2 } Definice 3.1.4. Nechť L je jazyk, tak jeho n-tou mocninu definujeme takto: L0 = {ε}Ln = LLn−1

pro n ≥ 1

iterací jazyka L nazýváme množinu L∗ , kde [ L∗ = Ln n≥0

pozitivní iterací jazyka L nazýváme množinu L+ , kde [ L+ = Ln n≥1

Lehce zjistíme, že L+ = LL∗ = L∗ L L∗ = L+ ∪ {ε} Kromě uvedených operací nás budou zajímat i zobrazení, definované nad jazyky. Definice 3.1.5. Nechť Σ1 a Σ2 jsou abecedy. Potom libovolné zobrazení h : Σ1 → Σ∗2 budeme nazývat homomorfizmus. Je možné ho rozšířit z množiny symbolů na množinu slov Σ∗1 , a to takto: h(ε) = ε, h(ua) = h(u)h(a) pro všechna u ∈ Σ∗1 , a ∈ Σ1 . Aplikací homomorfismu h na jazyk L dostaneme nový jazyk h(L), kde h(L) = {h(w)/w ∈ L}. ∗ Definice 3.1.6. Pokud h : Σ1 → Σ∗2 je homomorfizmus, tak h−1 : Σ∗2 → 2Σ1 je inverzní homomorfizmus, který je definovaný takto: Pokud v ∈ Σ∗2 , tak h−1 (v) je množina slov nad Σ1 , které se homomorfizmem h zobrazují na v, tedy h−1 (v) =

3.2

13

Pojem gramatika

{u/h(u) = v}. Pokud L je jazyk nad Σ2 , tak h−1 (L) je jazyk nad Σ1 skládající se ze slov, které h zobrazuje na slova z L. [ h−1 (L) = h−1 (v) = {u/h(u) ∈ L} v∈L

Aby specifikace jazyka měla praktický význam, musí být konečná. Požadavek konečnosti splňují minimálně dva systémy, které se často používají. První systém, automaty, je založený na principu „proceduryÿ, která po předložení slova, po konečném počtu kroků rozpozná, zda toto slovo patří nebo nepatří do daného jazyka. Druhý systém, gramatiky, je schopný generovat pouze ta slova, která patří do daného jazyka a je schopný generovat všechna slova daného jazyka (Molnár, Češka, Melichar, 1987, s. 12–14).

3.2

Pojem gramatika

Gramatika jazyka je tvořena množinou všech gramatických pravidel. Gramatika jazyka umožňuje generovat věty jazyka, které jsou gramaticky správně. Gramatickými pravidly – gramatikou – je určena pouze syntaxe jazyka, to znamená, že je určena přípustná struktura vět jazyka a prvotní jednotky, které je možné na daném místě použít. Pokud libovolná věta splňuje podmínky definované gramatikou, patří do daného jazyka. Význam vět určuje sémantika. Syntaxe a sémantika navzájem souvisí. Syntaxe definuje strukturu věty, která je zase základem pro určení jejího významu. Syntaktická správnost věty však ještě nezaručuje její sémantickou správnost. Analýza formálního jazyka a gramatiky vyžaduje specifikaci objektů, se kterými budeme pracovat. Jedná se o prvotní symboly nazývané terminální symboly nebo terminály, jednotky specifikované pomocí jiných jednotek neterminální symboly nebo neterminály gramatická pravidla nazývané přepisovací pravidla. Kromě uvedených objektů je třeba zmínit ještě jeden specifický neterminální symbol, pomocí kterého generování vět začíná. Jedná se o startovací symbol. Nyní je možné definovat gramatiku. Gramatika G jazyka L je čtveřice GL = (N, Σ, P, S), kde 1. N je konečná množina neterminálních symbolů, 2. Σ je konečná množina terminálních symbolů, 3. P je množina přepisovacích pravidel, je to konečná podmnožina kartézského součinu (N ∪ Σ)∗ N (N ∪ Σ)∗ × (N ∪ Σ)∗ , 4. S ∈ N je startovací (počáteční, výchozí) symbol gramatiky. Prvek (α, β) množiny P budeme zapisovat ve tvaru α → β. Řetězec α je levá strana, řetězec β je pravá strana přepisovacího pravidla. Gramatika je produkční systém, v němž lze aplikací přepisovacích pravidel ze startovacího symbolu generovat věty patřící do jazyka L. V průběhu generování postupně vynikají řetězce složené ze slovníku gramatiky – větné formy, tj. prvky (N ∪

3.2

14

Pojem gramatika

Σ)∗ . Cílem generování je vytvoření řetězce w ∈ Σ∗ , který neobsahuje neterminální symboly. Gramatika sama ještě neposkytuje způsob, jak z ní získat slova specifikovaného jazyka. Základem pro generování vět jsou přepisovací pravidla, na základě kterých nad množinou řetězců vytvořených z množiny neterminálních a terminálních symbolů definujeme relaci derivace. Přímá derivace – relace mezi větnými formami daná pravidly gramatiky. Jsou-li γλδ, γµδ větné formy, mezi nimiž je přímá derivace, pak musí existovat λ → µ ∈ P dané gramatiky. Značíme ⇒. Nepřímá derivace – libovolná mocnina přímé derivace ⇒n . Tranzitivní uzávěr přímé derivace se nazývá jen derivace, označíme ⇒+ . Je-li věta w ∈ L, pak platí S ⇒n w. Příklad generování věty: Je dána abeceda Σ = {a, b, c} a gramatika G nad touto abecedou, jejíž množina neterminálních symbolů je N = {S, A}, množina pravidel je P = {(S, b), (S, aAc), (A, bA), (A, ε)} a startovací symbol je S. Pravidla přepíšeme do přehlednější podoby a pro usnadnění orientace očíslujeme: (1) (2) (3) (4)

S→b S → aAc A → bA A→ε

Generování věty se sestává z posloupnosti větných forem a začíná startovacím neterminálem. U každé derivace je použití příslušného pravidla gramatiky naznačeno číslem. (2) (3) (3) (4) S ⇒ aAc ⇒ abAc ⇒ abbAc ⇒ abbc. Výsledná věta abbc patří do jazyka generovaného uvedenou gramatikou G (Rybička, 1999, s. 8–9). Podle tvaru přepisovacích pravidel gramatiky lze usoudit i na obecnost jazyka generovaného touto gramatikou. Klasifikace gramatik pocházející od Chomského je založena na tvaru přepisovacích pravidel a provádíme ji takto (Rybička, 1999, s. 9): • Typ 0 – neomezené gramatiky, na přepisovací pravidla není kladeno žádné omezení. Pravidla mají tvar α → β; α ∈ (N ∪ Σ)∗ N (N ∪ Σ)∗ , β ∈ (N ∪ Σ)∗ • Typ 1 – kontextové gramatiky, pravidla ve tvaru αAβ → αγβ; A ∈ N, α, β ∈ (N ∪ Σ)∗ , γ ∈ (N ∪ Σ)+ nebo S → ε • Typ 2 – bezkontextové gramatiky, pravidla ve tvaru A → α; A ∈ N, α ∈ (N ∪ Σ)∗

3.3

Jazyky typu 3 Chomského klasifikace

15

• Typ 3 – lineární gramatiky, pravá lineární gramatika má pravidla ve tvaru A → wB nebo A → w; A, B ∈ N, w ∈ Σ∗ levá lineární gramatika má pravidla ve tvaru A → Bw nebo A → w; A, B ∈ N, w ∈ Σ∗ Při navrhování jazyka Ruzin je nutné popsat pravidla gramatiky, aby bylo možné nějakým způsobem určit, zda zkoumané slovo patří nebo nepatří do daného jazyka. V mé práci je základním kamenem navržení linární gramatiky jazyka typu 3, konkrétně pak pravé lineární gramatiky, díky níž je možné exaktně a jednoduše popsat gramatiku jazyka.

3.3


Gramatika jazyka typu 3 je použita při návrhu jazyka, který popisuji v této diplomové práci. Konstrukce gramatiky začíná návrhem gramatik pro jednotlivé implementované struktury, použité v jazyce Ruzin. Jedná například o implementaci gramatiky čísel, proměnných pole apod. Podrobný popis navrhovaných struktur následuje v kapitole implementace lexikálního analyzátoru. Konstrukce lexikálního analyzátoru vyžaduje zápis gramatiky v konkrétní podobě. Pro vyjádření jazyků této kategorie lze využít: • lineární gramatiku (pravou, levou), • regulární gramatiku (pravou, levou), • regulární výraz (regulární množinu), • konečný automat (nedeterministický, deterministický). Všechny uvedené prostředky jsou navzájem ekvivalentní a algoritmicky navzájem převoditelné. V mé práci je postupně navržena lineární gramatika, kterou regularizuji do podoby regulární gramatiky. Na základě regulární gramatiky je vytvořena přechodová funkce nedeterministického konečného automatu, ze kterého postupnou úpravou vznikne konečný automat deterministický. Z výkladu je zřejmé, že regulární výrazy nejsou podstatné pro mou práci, nebudu je tedy podrobně popisovat1 . 3.3.1

Lineární a regulární gramatika

Návrh gramatik představuje proces, kdy je postupnou úpravou získána z lineární gramatiky gramatika regulární. Definici gramatik a proces regularizace je vhodné uvést. G3 = (N, Σ, P, S) je pravá lineární gramatika, mají-li pravidla tvar A → wB nebo A → w kde A, B ∈ N, w ∈ Σ∗ . G3 = (N, Σ, P, S) je regulární gramatika, mají-li pravidla tvar A → aB nebo A → a kde A, B ∈ N, a ∈ Σ. Navíc může existovat pravidlo S → ε, je-li ε ∈ LG . 1

Bližší informace v (Rybička, 1999) nebo (Molnár, Češka, Melichar, 1987)

3.3


16

I když je tvar pravidel regulární gramatiky zúžením tvaru pravidel lineární gramatiky, existuje ke každé lineární gramatice odpovídající regulární gramatika. Převod je algoritmický a probíhá v několika krocích. V následujících kapitolách se budu na tento postup odvolávat, proto se mi zdá vhodné označit algoritmus názvem a pojmenuji ho algoritmus 1 : 1. převedení A → wB na řetězec pravidel A → a1 A1 , A1 → a2 A2 , . . . , An−1 → an B, kde w = a1 a2 . . . an , 2. odstranění ε-pravidel (ε-pravidel, pravidel typu A → ε, 3. odstranění jednoduchých pravidel (pravidel typu A → B). Aplikací uvedených pravidel je získána regulární gramatika, která je podkladem pro sestavení přechodové funkce a vytvoření konečného automatu. 3.3.2

Konečný automat

Konečný automat (KA) je virtuální stroj skládající se z řídící jednotky, která se může nacházet v konečném počtu vnitřních stavů, a ze čtecího zařízení, schopného snímat jednotlivé symboly vstupní věty ze vstupní pásky. Vstupní páska je čtena zleva doprava. Zatímco gramatiku lze chápat jako generativní systém, který postupnými derivacemi ze startovacího neterminálu vygeneruje výslednou větu, automat je systém akceptační, jehož vstupem je věta a výstupem informace, zda tato věta patří nebo nepatří do jazyka L. Nedeterministický KA je definován jako pětice M = (Q, Σ, δ, q0 , F ), kde 1. Q je konečná množina stavů automatu, 2. Σ je konečná vstupní abeceda, 3. δ je zobrazení 4. Q × Σ → 2Q , 5. qS ∈ Σ je počáteční stav, 6. F ⊆ Q je množina koncových stavů. Činnost automatu lze znázornit posloupností konfigurací. Konfigurace definuje situaci, v níž se automat nachází, pomocí aktuálního vnitřního stavu qi a dosud nepřečtené části vstupní věty. Přechod automatu od jedné konfigurace k následující definuje přechodová funkce δ, a to na základě přečteného terminálního symbolu ze vstupní pásky. Počáteční konfigurace automatu je definována dvojicí (qS , w), kde qS je počáteční stav automatu a w je celá vstupní věta. Koncová konfigurace je definována jako (qFb , ε), kde qFb ∈ F . Dostane-li se automat během své činnosti do této konfigurace, je vstupní věta přijata (akceptována), tedy patří do daného jazyka. V opačném případě věta není akceptována. Přechodová funkce δ určuje na základě současného vnitřního stavu a čteného symbolu následující vnitřní stav. Je-li těchto následujících stavů více, jedná se o nedeterministický konečný automat. Je-li následující stav nejvýše jeden, jde o deter-

3.3


17

ministický konečný automat. Nedeterministický konečný automat lze algoritmicky převést na deterministický. Obvyklým způsobem znázornění přechodové funkce je tabulka, jejíž řádky jsou označeny všemi stavy Q a sloupce všemi symboly Σ. Pole tabulky obsahují výsledky přechodové funkce, tj. podmnožiny množiny stavů. Pro člověka je přehlednější grafický způsob vyjádření přechodové funkce. Jednotlivé stavy jsou znázorněny jako uzly grafu, mezi nimiž jsou orientované spojnice ohodnocené příslušným terminálním symbolem. Koncové stavy jsou vyznačeny dvojitým kroužkem (Rybička, 1999, s. 12–14). 3.3.3

Ekvivalence konečných automatů a gramatik typu 3

Třída jazyků generovaných gramatikami typu 3 je ekvivalentní třídě jazyků akceptovatelných konečnými automaty. Z této věty vyplývá, že ke každé gramatice typu 3 lze algoritmicky zkonstruovat konečný přijímající stejný jazyk. Tato konstrukce je použita v mé práci, proto ji uvedu. Je dána pravá regulární gramatika G = (N, Σ, P, S). Úkolem je vytvořit automat M = (Q, Σ, δ, qS , F ) takový, aby LG = LM . Převod regulární gramatiky na konečný automat pracovně nazvu algoritmus 2. Jednotlivé prvky automatu se získají takto: 1. Q = N ∪ {qFb }– stavy automatu odpovídají neterminálům gramatiky, k nim je dodán nový stav qFb , který je zároveň koncovým stavem. Stavy automatu se pracovně označí písmenem q s indexem v podobě odpovídajícího neterminálu gramatiky, 2. Abeceda gramatiky i automatu je identická, 3. Konstrukce přechodové funkce na základě pravidel gramatiky: Je-li A → aB ∈ P , pak δ(qA , a) obsahuje qB . Je-li A → a ∈ P , pak δ(qA , a) obsahuje qFb . 4. Počátečním stavem automatu je stav qS odpovídající startovacímu neterminálu gramatiky S. 5. Množina koncových stavů F obsahuje vždy prvek qFb . je-li však S → ε ∈ P ,pak počáteční stav automatu je také koncový (aby bylo možno přijímat i prázdný řetězec), pak tedy F = {qS , qFb } (Rybička, 1999, s. 16). Aplikací jednotlivých částí algoritmu 2 vzniká nedeterministický konečný automat. Další postup zpracování je převod nedeterministického konečného automatu na deterministický. 3.3.4

Převod nedeterministického automatu na deterministický

Deterministický konečný automat má definovanou přechodovou funkci jako zobrazení δ : Q × Σ → Q. Principem převodu nedeterministického automatu na deterministický je takové rozšíření množiny Q, aby několik původních stavů tvořilo jeden nový stav. Tento nový kompozitní stav přebírá vazby a vlastnosti stavů, z nichž vznikl. Kompozitní stav je použit právě tam, kde výsledek přechodové funkce není

3.4

18

Bezkontextové gramatiky a jazyky

jediný stav, ale množina. V tabulce přechodové funkce není pak nutné psát množinové závorky (Rybička, 1999, s. 15). Cílem je najít neterminální stavy, pro které platí |δ(qi , a)| > 1, a z nich se vytváří kompozitní stavy. Poté je možné odstranit složené závorky z tabulky nedeterministického konečného automatu. n [ δ(qi , a) = {(q0 , . . . , qn ) ⇒ q0...n Pro ∀α ∈ Σ : δ(qi...n , α) = qi i=0

Posledním krokem tohoto procesu je nalezení a odstranění nepoužitých stavů, do kterých není možné přejít. Nemožnost použití některých stavů vzniká právě zavedením kompozitních stavů. Činnost deterministického konečného automatu lze implementovat programovým modulem. V mé práci konstruuji programový modul lex.h, který je popsán dále. Deterministický konečný automat rozpoznává lexikální jednotky patřící do daného jazyka. Nedokáže však rozpoznat, zda jsou jednotky syntakticky správně uspořádány. Syntaktickou analýzu vstupního souboru je možné provádět až podle pravidel bezkonextové gramatiky, podle jazyků typu 2.

3.4


Regulární gramatiky a jazyky mají celou řadu dobrých vlastností, ale jejich praktické použití v oblasti programovacích jazyků a překladačů je velmi omezené. Na specifikaci vyšších konstrukcí programovacích jazyků se používají bezkontextové gramatiky, které postačují pro specifikaci většiny konstrukcí programovacích jazyků. Při specifikaci programových jazyků je třeba mít na paměti i skutečnost, že programy bude potřebné přeložit, že pro daný jazyk je potřeba vytvořit překladač. Zde už vystupuje do popředí i význam slov jazyka. Existují slova jazyka, jejichž význam nemusí být jednoznačný. Z hlediska překladu to má dalekosáhlý význam, protože se může uskutečnit jiným způsobem, než zamýšlel programátor. Kromě toho je při specifikaci programovacích jazyků požadována taková specifikace, která umožňuje jednoduchý a rychlý překlad. Samozřejmě, ne všechny bezkontextové gramatiky tuto vlastnost mají. Většina vlastností bezkontextových gramatik závisí na derivaci, kterou se generuje dané slovo. Proto je vhodné použít na popis derivace takový formální zápis, který poskytuje o derivaci co nejvíce informací. Takovým zápisem může být znázornění konstrukce věty pomocí bezkontextové gramatiky – derivační strom. Strom je konečná množina vrcholů nebo uzlů, spojených orientovanými hranami, které splňují následující podmínky: 1. existuje právě jeden vrchol, do kterého nevstupuje žádná hrana. Tento vrchol je nazýván kořen stromu, 2. ke každému vrcholu existuje posloupnost orientovaných hran z kořene stromu. Strom je tedy souvislý,

3.4


19

3. do každého vrcholu, s výjimkou kořene stromu, vstupuje právě jedna hrana. Ve stromu neexistují cykly (Molnár, Češka, Melichar, 1987, s 47–48). 3.4.1

Syntaktická analýza

Proces vytváření derivace nebo derivačního stromu věty daného jazyka se nazývá rozklad (rozbor) a nebo syntaktická analýza věty. Účelem tohoto procesu je nejen zjištění, že řetězec nad danou abecedou jazyka je větou jazyka, tj. že neobsahuje syntaktické chyby, ale neméně důležité je i nalezení syntaktické struktury věty, podle které lze potom udělat překlad do jiného jazyka. Ta část překladače, která realizuje syntaktickou analýzu, se nazývá syntaktický analyzátor. Jeden z největších praktických přínosů teorie bezkontextových jazyků je právě v oblasti konstrukce syntaktických analyzátorů, protože dodává nejen efektivní algoritmy syntaktické analýzy, ale umožňuje i automatizaci výstavby syntaktických analyzátorů. Algoritmy syntaktické analýzy lze rozdělit podle způsobu, jakým je vytvářený derivační strom věty, na dvě skupiny: • shora dolů, • zdola nahoru. V této práci použiji způsob vytváření derivačního stromu metodou shora dolů. Při syntaktické analýze shora dolů se začíná vytvářet derivační strom od kořene – začátečního symbolu gramatiky a postupnou aplikací přepisovacích pravidel na nejlevější neterminální symbol získávaných větných forem se dojde na ke koncovým vrcholům derivačního stromu – symbolům analyzované věty. Při syntaktické analýze shora dolů je tedy vytvářena levá derivace analyzované věty. Výběr levé derivace je náhodný. Systematická náhrada nejlevějšího neterminálního symbolu větné formy umožňuje v procesu syntaktické analýzy porovnávat generované terminální symboly větné formy se symboly analyzované věty co nejdříve, jak to vyplývá z vlastností levé derivace (Molnár, Češka, Melichar, 1987, s. 75). Derivačního strom tedy analyzuje věty daného jazyka a pomáhá tak pochopit fungování syntaktického analyzátoru. Samotnou syntaxy jazyka je však potřeba nejprve specifikovat konkrétními pravidly. Přehledným způsobem navržení pravidel bezkontextové gramatiky je návrh syntaktických diagramů. 3.4.2

Grafy syntaxe

Grafy syntaxe představují grafické vyjádření pravidel bezkontextové gramatiky. Uzly tohoto grafu jsou buď obdélníky (představují odkazy na jiný graf, tj. neterminální symbol), nebo ovály – terminální symboly (obr. 1). Spojnice představují možné posloupnosti symbolů ve větné formě. Grafy syntaxe se často používají k popisu programovacích jazyků a jsou pro člověka přehlednější, než pravidla gramatiky. Grafy syntaxe lze rozložit na elementy, které lze vyjádřit pomocí pravidel gramatiky, a to zřetězení symbolů, varianta a ite-

3.4


20

Obr. 1: Zřetězení symbolů.

race. Vyjádření jednotlivých prvků pomocí pravidel bezkontextové gramatiky definují následující případy (Rybička, 1999, s. 23–25): • Zřetězení symbolů (obr. 2)

Obr. 2: Zřetězení symbolů.

Odpovídající pravidlo gramatiky: A → α1 α2 . • Varianta (obr. 3)

Obr. 3: Varianta.

Odpovídající pravidlo gramatiky: A → α1 |α2 • Iterace (obr. 4) Odpovídající pravidlo gramatiky musí vyjadřovat skutečnost, že prvek α1 se musí vyskytovat alespoň jedenkrát, a musí odrážet iteraci, musí tedy být rekurzivní. Výhodné je, aby pravidla obsahovala pravou rekurzi. A → α1 A0 A0 → α1 A0 |ε • Seznam oddělovačů (obr. 5) Často se vyskytujícím prvkem syntaktických grafů je iterace prvků s oddělovači v podobě terminálního symbolu a. Odpovídající pravidla gramatiky jsou odvozena od tvaru v předcházejím případě: A → α1 A0 A0 → aα1 A0 |ε Ze syntaktických diagramů je možné jednoduchým způsobem odvodit bezkontextovou gramatiku, potřebnou pro sestavení zásobníkového automatu. 3.4.3

Zásobníkový automat

Zásobníkové automaty představují třídu abstraktních matematických strojů, které jsou z hlediska reprezentace jazyků rovnocené bezkontextovým gramatikám. Podobně jako konečné automaty v třídě regulárních jazyků zásobníkové automaty umožňují modelovat syntaktickou analýzu bezkontextových gramatik.

3.4


21

Obr. 4: Iterace.

Obr. 5: Seznam oddělovačů.

Zásobníkový automat je jednosměrný nedeterministický automat, který má pomocnou, potenciálně nekonečnou paměť organizovanou jako zásobník. Vstupní páska je rozdělená na elementární záznamy, ze kterých každý obsahuje právě jeden vstupní symbol. Obsah každého záznamu je postupně načítán čtecí hlavou, ale není možné ho změnit. V každém kroku, taktu, se čtecí hlava posune o jeden záznam vpravo, nebo zůstává na stejné pozici (jednosměrný automat). Konečné stavové řízení, předepsané přechodovou funkcí automatu, realizuje v závislosti na vnitřním stavu čteného vstupního symbolu a řetězce na vrcholu zásobníku akci změny vnitřního stavu, posuvu čtecí hlavy a změny obsahu zásobníku. Zásobníkový automat je všeobecně nedeterministický stroj. Přechodová funkce může předepisovat několik alternativních akcí, a to vzhledem na následující stav a obsah zásobníku, nebo také na to, zda se čtecí hlava posune na další symbol nebo ne. Zásobníkový automat je definován jako sedmice P = (Q, Σ, Γ, δ, q0 , Z0 , F ) kde 1. 2. 3. 4.

Q je konečná množina vnitřních stavů, Σ je vstupní abeceda, Γ je konečná množina zásobníkových symbolů – zásobníková abeceda, δ je přechodová funkce daná zobrazením z množiny Q × (T ∪ {ε}) × Γ∗ do množiny podmnožin množiny Q × Γ∗ přičemž δ(q, a, α) 6= 0 pouze pro konečný počet trojic δ(q, a, α), 5. q0 ∈ Q je počáteční stav, 6. Z0 ∈ Γ je počáteční symbol, určující počáteční obsah zásobníku, 7. F ⊆ Q je množina koncových stavů.

Činnost zásobníkového automatu spočívá v přechodu mezi jednotlivými konfiguracemi tohoto automatu. Konfigurace zásobníkového automatu P představuje trojice (q, w, γ) z množiny Q × T ∗ × Γ∗ , kde q je momentální stav stavového řízení, w je doposud nepřečtená část vstupního řetězce ze vstupní pásky; první symbol řetězce w se nachází pod čtecí hlavou. Pokud w = ε, tak byly přečtené všechny symboly ze vstupní pásky. γ je obsah zásobníku; pokud γ = ε, tak je zásobník prázdný.

3.5

22

Deterministické bezkontextové jazyky

Počáteční konfigurace zásobníkového automatu má tvar (q0 , w, Z0 ), w ∈ T ∗ , což znamená, že automat je v počátečním stavu q0 , čtecí hlava je nastavená na první symbol řetězce w a v zásobníku je počáteční symbol Z0 . Koncová konfigurace má tvar (q, ε, γ), q ∈ F ,γ ∈ Γ∗ , tedy obsah celé vstupní pásky byl přečtený a automat je v koncovém stavu. Obsah zásobníku může být libovolný. Přechod zásobníkového automatu P z jedné konfigurace do druhé je reprezentován binární relací ` na množině všech konfigurací automatu takto: df

(q, aw, αγ) ` (q 0 , wβγ) ⇔ (q 0 , β) ∈ δ(q, a, α) q, q 0 ∈ Q, a ∈ (Σ ∪ {ε}), w ∈ Σ∗ , α, β, γ ∈ Γ∗ Definovanou relaci ` lze interpretovat takto: pokud se zásobníkový automat P nachází ve stavu q, pod čtecí hlavou je symbol a a na vrcholu zásobníku je uložený řetězec α, tak po přečtení vstupního symbolu a, a 6= ε, může automat přejít do stavu q 0 , čtecí hlava se posune o jeden symbol vpravo a na vrchol zásobníku se uloží, po odstranění řetězce α, řetězec β. Pokud α = ε, tak se ze zásobníku neodstraňuje žádný symbol, pokud β = ε, tak se do zásobníku žádný symbol nevkládá. Pokud α = ε, tak se přechod do nové konfigurace neurčuje vstupním symbolem a čtecí hlava se proto neposouvá (Molnár, Češka, Melichar, 1987, s. 86–87). Definovaný zásobníkový automat je nedeterministický stroj, tzn. že v každé situaci nemusí být možné jednoznačně přejít do následující konfigurace. Při výběru konfigurace, která se ve výsledku ukáže být jako chybná, je nutné vrátit proces rozkladu do místa volby, zvolit jinou konfiguraci a pokračovat v analýze. Nedeterminismus znamená použití syntaktické analýzy s návraty. Bohužel neexistuje algoritmus převádějící nedeterministickou bezkontextovou gramatiku na ekvivalentní gramatiku deterministickou. Sestrojení syntaktického analyzátoru bez návratů vyžaduje vlastní návrh deterministické bezkontextové gramatiky.

3.5


Deterministické bezkontextové jazyky tvoří vlastní podmnožinu bezkontextových jazyků. Množina detreministických bezkontextových jazyků zahrnuje všechny regulární jazyky a tvoří velmi důležitou třídu formálních jazyků. K nejvýznamějším vlastnostem deterministických bezkontextových jazyků z hlediska jejich aplikace v překladačích a programovacích jazycích patří: • efektivita syntaktické analýzy, • automatizovatelnost konstrukce syntaktického analyzátoru, • jednoduchá lokalizace syntaktických chyb. Pro deterministické bezkontextové gramatiky je možné sestrojit syntaktický analyzátor bez návratů. To je možné pouze na základě třídy zásobníkových automatů, které mohou v každém kroku přecházet pouze do jediné konfigurace – deterministických zásobníkových automatů.

3.5


23

Zavedení pojmu deterministický zásobníkový automat umožňuje tvrzení, že jazyk L se nazývá deterministický bezkontextový jazyk, pokud existuje deterministický zásobníkový automat P takový, že L(P ) = L (Molnár, Češka, Melichar, 1987, s. 103). 3.5.1

Deterministický zásobníkový automat

Pojem deterministický zásobníkový automat vyžaduje přesnou definici. Zásobníkový automat P = (Q, Σ, Γ, δ, q0 , Z0 , F ) je nazván deterministický zásobníkový automat pokud splňuje následující podmínky: 1. |δ(q, a, α)| 5 1 pro všechna q ∈ Q, a ∈ Σ ∪ {ε}, α ∈ Γ∗ . 2. Pro libovolný stav q, symbol a ∈ Σ ∪ {ε}, a řetězec α, β zásobníkových symbolů platí: a) jestliže δ(q, a, α) 6= 0 a zároveň δ(q, ε, β) 6= 0, pak α není předponou řetězce β, ani β není předponou řetězce α, b) jestliže δ(q, a, α) 6= 0 a zároveň δ(q, a, β) 6= 0, pak α není předponou řetězce β, ani β není předponou řetězce α (prázdný řetězec je předponou každého řetězce)(Molnár, Češka, Melichar, 1987, s. 102). Rozdíly mezi bezkontextovými gramatikami se projevují i ve specifikaci zásobníkových automatů. Libovolný bezkontextový jazyk nemůže být přijímán deterministickým zásobníkovým automatem a ani není možné každý zásobníkový automat upravit na ekvivalentní deterministický zásobníkový automat podobně, jako je to v třídě konečných automatů. 3.5.2

LL jayzky a gramatiky

Skupina algoritmů syntaktické analýzy, které vytvářejí derivační strom analyzovaného řetězce směrem shora dolů se nazývají algoritmy LL(k) analýzy. Je to proto, protože čtou vstupní řetězec zleva doprava, vytváří levý rozklad a přitom používají informaci o nejbližších k symbolech z doposud nepřečtené části vstupního řetězce. Gramatiky, pro které je tyto algoritmy možné vytvořit, se nazývají LL(k) gramatiky. Základní princip syntaktické analýzy pro LL gramatiky je možné definovat takto: Daná je bezkontextová gramatika G = (N, Σ, P, S) a řetězec w = a1 , a2 , . . . an , který je větou jazyka L(G). Potom existuje levá derivace S = γ1 , ⇒ γ2 ⇒ . . . ⇒ γm = w. Vzhledem k tomu, že derivace je levá, má každá větná forma γi tvar γi = a1 a2 . . . aj Ai βi , kde a1 , a2 , . . . , aj jsou terminální symboly, A je neterminální symbol, β je řetězec terminálních a neterminálních symbolů. Přitom řetězec a1 a2 . . . aj je předponou věty w. Předpokladem je, že A → α1 |α2 | . . . |αp jsou všechna pravidla z množiny pravidel P s neterminálním symbolem A na levé straně. Potom základní problém syntaktické analýzy metodou shora dolů spočívá v nalezení toho pravidla A → αk , kterého aplikací dostaneme z větné formy γi větnou formu γi+1 .

3.5


24

Modelem syntaktického analyzátoru je nedeterministický zásobníkový automat, ale pro syntaktický analyzátor bez vracení je potřeba sestavit deterministický automat, který řeší problém výběru. Pro bezkontextovou gramatiku vytvoříme zásobníkový automat, který má definované zobrazení δ takto: 1. δ(q, ε, A) = {(q, α)/A → α ∈ P }, 2. δ(q, a, a) = {(q, ε)}. Operace podle bodu 1 se nazývá expanze, operace podle bodu 2 porovnání. Zobrazení podle bodu 2 vyhovuje definici deterministického zásobníkového automatu. Problémem je zobrazení podle bodu 1. Zobrazení δ(q, ε, A) dává množinu, která má tolik prvků, kolik pravidel pro neterminální symbol A v gramatice existuje. Je potřeba si všimnout, že problém výběru pravidla tato konstrukce neřeší. Deterministický zásobníkový automat vznikne touto konstrukcí pouze tehdy, když pro každý neterminální symbol je v gramatice pouze jedno pravidlo. Tyto gramatiky (LL(0) gramatiky) nemají praktický význam z toho důvodu, že generují pouze jednu větu a nebo prázdný jazyk. Pro většinu bezkontextových gramatik vznikne tedy uvedenou konstrukcí nedeterministický zásobníkový automat. Přitom je třeba si všimnout, že pro výběr pravidla na expanzi tento automat nevyužívá žádnou informaci. Při syntaktické analýze existují dva zdroje informací, které je možné použít při rozhodování o dalším postupu: • informace o doposud nepřečtené části vstupního řetězce, • informace o průběhu analýzy. Při syntaktické analýze metodou shora dolů se využívá především informace o k nejbližších symbolech v doposud nepřečtené části vstupního řetězce. To znamená, že podle tohoto dopředu prohlédnutého řetězce se vykonává rozhodnutí o tom, jaké pravidlo má být použito při expanzi (Molnár, Češka, Melichar, 1987, s. 106–107). Informace o k následujících symbolech vstupní věty se uplatňuje v LL(k) gramatikách, generujících jazyk typu LL(k). Speciálním případem je gramatika typu LL(1), kdy k rozlišení pravých stran A-pravidel postačuje jediný následující terminální symbol analyzované věty. 3.5.3

Levá rekurze

Někdy se mohou v bezkontextových gramatikách vyskytnout případy, kdy se na začátku pravé strany A-pravidla vyskytne neterminální symbol z levé strany pravidla. Tomuto jevu se říká levá rekurze, která je pro některé metody syntaktické analýzy nežádoucí a je potřeba ji odstranit. Levá rekurze má dvě podoby, přímá levá rekurze a nepřímá levá rekurze. Jsou-li všechna pravidla pro neterminální symbol A zapsána jako A → Aα1 | Aα2 | . . . | Aαn | β1 | β2 | . . . | βm

3.5


25

kde A ∈ N ; αi , βj ∈ (Σ ∪ {N − {A}})∗ , jedná se o přímou levou rekurzi, kterou lze odstranit následovně (Lobaz, 2006): A → β1 | β2 | . . . | βm | β1 A | β2 A | . . . | βm A A → α1 | α2 | . . . | αn | α1 A | α2 A | . . . | αn A nebo pomocí ε-pravidel: A → β1 A | β2 A | . . . | βm A A → α1 A | α2 A | . . . | αn A | ε V regulární gramatice jsou sice ε-pravidla odstraňována kvůli dosažení regularity. Je nutné si uvědomit, že regulární jazyky tvoří podmnožinu jazyků bezkontextových, na které nejsou kladeny tak vysoké nároky. Jak je v předešlém tvrzení ukázáno, zavedení ε-pravidla do bezkontextové gramatiky může být dokonce přínosem pro zjednodušení pravidel gramatiky. Další rekurentní zacyklení mohou nastat gramatikou, ve které se vyskytuje nepřímá levá rekurze. Nepřímá rekurze vzniká z definovaných pravidel například způsobem A → B . . . , B → A . . .. Její odstranění funguje podobně jako u přímé rekurze, kdy za neterminální symbol na pravé straně prvního pravidla nahradíme celým pravým pravidlem tohoto neterminálního symbolu. 3.5.4

Množiny FIRST a FOLLOW

Problémem při rozhodování o variantě na pravé straně A-pravidel je tedy zjistit, kterým terminálním symbolem jednotlivé varianty začínají. K tomuto zjištění slouží výpočet množiny FIRST(α) dané gramatiky G = (N, Σ, P, S) podle následujícího algoritmu: 1. Předpokládáme, že α = X1 X2 . . . Xm , kde Xi ∈ (N ∪ Σ). 2. Je-li X1 ∈ Σ, pak FIRST(α) = {X1 }. 3. Je-li X1 ∈ N a X1 ⇒∗ αβ, pak k množině FIRST(α) přidej terminál a. 4. Je-li X1 ∈ N a X1 ⇒∗ ε, pak k množině FIRST(α) přidej symboly množiny FIRST(γ), kde γ = X2 . . . Xm . Množinu FIRST je nutné vypočítat pro všechny varianty pravých stran Apravidla. Je-li však některé αi = ε, je potřeba ještě vypočítat množinu FOLLOW(A) takto: 1. FOLLOW(S) obsahuje ε. 2. Je-li A → αBβ ∈ P a β 6= ε, pak FOLLOW(B) obsahuje všechny prvky FIRST(β). 3. Je-li A → αBβ ∈ P a β ⇒∗ ε, pak všechny prvky FOLLOW(A) jsou v množině FOLLOW(B).

3.5

26


3.5.5

Gramatika typu LL(1)

Při syntaktické analýze je někdy potřeba pracovat s bezkontextovou gramatikou která obsahuje pravidla libovolného tvaru. Znamená to, že na pravé straně výrazu A → α se mohou vyskytovat výrazy, které nezačínají terminálním symbolem. Zpracování takových bezkontextových gramatik je možné zavedením již zmíněných funkcí FIRST a FOLLOW. Díky nim je možné definovat LL(1) gramatiky následujícím způsobem (Molnár, Češka, Melichar, 1987, s. 115). Bezkontextová gramatika G = (N, Σ, P, S) se nazývá LL(1)gramatika, pokud platí následující podmínka pro každé A ∈ N : pokud A → α a A → β jsou různé pravidla v P , tak 1. pro řetězce α, β musí platit FIRST(α) ∩ FIRST(β) = 0 2. pokud je možné z řetězce α derivovat prázdný řetězec a z řetězce β není možné derivovat prázdný řetězec, tak musí platit FOLLOW(A) ∩ FIRST(β) = 0 Předcházející definici je možné zkráceně formulovat takto (Rybička, 1999, s. 28): Je dána bezkontextová gramatika G = (N, Σ, P, S). Obsahuje-li množina P nějaká A-pravidla tvaru A → α1 |α2 | . . . αn , pak FF(αi ) ∩ FF(αj ) = 0

∀i, j ∈ {1 . . . n}, i 6= j,

přičemž symbol FF(αi ) značí množinu FIRST(αi ), je-li αi 6= ε a množinu FOLLOW(A) v případě αi = ε. 3.5.6

Algoritmus syntaktické analýzy pro gramatiku typu LL(1)

Analýzu věty jazyka popsaného gramatikou typu LL(1) provádí zásobníkový automat, řízený rozkladovou tabulkou. Tento automat provádí rozklad věty v zásobníku na základě symbolů čtených ze vstupní pásky. Rozkladová tabulka reprezentuje zobrazení M : (Γ ∪ {#}) × (Σ ∪ {ε}) → R, kde R nabývá pro každou dvojici (X, Y ) následující hodnoty: 1. řetězec β ∈ Γ∗ , je-li X ∈ N a zároveň A → βinP a zároveň Y ∈ FF(β), 2. prvek pop, je-li X = Y, X, Y ∈ Σ, 3. prvek accept, je-li X = # a zároveň Y = ε, 4. prvek error v ostatních případech. Počáteční konfigurace automatu je definována tak, že v zásobníku se nachází startovací symbol gramatiky a speciální symbol # a na vstupní pásce je celá analyzovaná věta. Koncová konfigurace předpokládá v zásobníku jediný symbol # a na vstupní pásce prázdný řetězec.

3.6

Sémantické akce

27

Činnost automatu určují prvky rozkladové tabulky takto: Je-li vrcholem zásobníku neterminál, vybere se z rozkladové tabulky podle aktuálního symbolu na vstupní pásce příslušný řetězec β, kterým se nahradí neterminál v zásobníku. Je-li vrcholem zásobníku terminál a na vstupu je tentýž terminál, provede se operace pop, která znamená odstranění vrcholu zásobníku a přečtení (odstranění) téhož terminálu ze vstupní pásky. Je-li vrcholem zásobníku # 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, tj. ohlášení syntaktické chyby (Rybička, 1999, s. 28). Vytvoření rozkladové tabulky deterministického zásobníkového automatu je předpokladem pro implementaci syntaktického analyzátoru. Syntaktický analyzátor dokáže poskytnout informaci, zda syntaxe jazyka je správná či nikoliv. Aby interpret daného jazyka byl schopen vykonávat nějaké akivity, musí mít implementovány sémantické akce.

3.6

Sémantické akce

Sémantické akce jsou aktivity implementované ve vhodném místě syntaktického analyzátoru. Během sémantické analýzy se provádějí některé kontroly zajišťující správnost programu z hlediska vazeb, které nelze provádět v rámci syntaktické analýzy (např. kontrola deklarací, typová kontrola, atd.). Implementace sémantických akcí znamená přidání specifických operací do gramatiky syntaktického analyzátoru. Jak již bylo řečeno, syntaktická analýza znamená přechod mezi jednotlivými konfiguracemi syntaktického analyzátoru. Pokud se na některém místě průchodu vyskytne příkaz pro vykonání sémantické akce, tato akce se provede, a pokračuje se dále v přechodu na další konfiguraci analyzátoru. Technicky jsou sémantické akce reprezentovány funkcemi, které provedou danou operaci, podle toho, na jakém místě se v dané gramatice jazyka vyskytují.

3.7

Programovací jazyk C

Interpret jazyka Ruzin je programován v programovacím jazyce C, je tedy vhodné tento programovací jazyk čtenáři přiblížit. Jazyk C je univerzální programovací jazyk nízké úrovně (low level language). Má velmi úsporné vyjadřování, je strukturovaný, má velký soubor operátorů a moderní datové struktury. Není specializovaný na jednu oblast používání. Pro mnoho úloh je efektivnější a rychlejší než jiné jazyky. C byl navržen a implementován pod operačním systémem UNIX a téměř celý UNIX je v C napsán. C se ale na UNIX nijak neváže a neváže se ani na jiný konkrétní počítač či operační systém. „Jazyk nízké úrovněÿ znamená, že C pracuje přímo pouze se standardními datovými typy jako jsou znaky, celá a reálná čísla atd. C neumožňuje přímo práci s řetězci a poli ani přímo neobsahuje nástroje pro vstupy a výstupy. Tyto všechny akce je nutné provádět pomocí volání funkcí, což přináší určité výhody např.:

3.8

Textový editor VIM

28

• jednoduchost jazyka, • jeho nezávislost na počítači. Z výše uvedených výhod vyplývá: • snadné vytvoření překladače pro konkrétní počítač a konkrétní operační systém (a přeneseně tedy i velké rozšíření jazyka C), • velká efektivita kódu – program C se téměř vyrovná programu v jazyce assembleru. Je vhodné také popsat, jakým vývojem jazyk C procházel. Prvním standardem jazyka byla verze jeho autorů – Brian W. Kernighan a Denis M. Ritchie – popsaná ve famózní knize The C Programming Language. Tato kniha vyšla v roce 1978 a kromě jiného se stala základní učebnicí jazyka C. Popisovaný standard jazyka C se běžně označuje jako K&R. Dnešní oficiání standard je tzv. ANSI C z roku 1990, který z K&R vychází. Jeho součástí je i přesná specifikace množiny knihovních funkcí a hlavičkových souborů (.H), které musí každá implementace ANSI C kompilátoru obsahovat. Této normě by měla vyhovovat naprostá většina dnešních překladačů a další text popisuje právě ANSI C. Neocenitelnou výhodou ANSI C je, že program napsaný podle tohoto standardu a pouze s využitím standardních knihovních funkcí (v ANSI C specifikovaných) je téměř 100% přenositelný na libovolný počítač pod libovolný operační systém. Pokud je nutná nějaká změna, pak je to změna opravdu minimální. Dnes je jazyk C velmi populární programovací jazyk. Jednak díky tomu, že je to „mateřský jazykÿ UNIXu a pak také díky zdařilé Turbo (Borland2 ) implementaci na PC. Programovat v C je móda a tato móda občas způsobuje příliš kritický pohled na jiné jazyky. Opovržlivý pohled na všechny, kteří C nepoužívají, ale není ten nejlepší přístup, protože každý programovací jazyk má „to svojeÿ (Herout, 2001).

3.8

Textový editor VIM

Psaní velkého množství zdrojových kódů vyžaduje dodržování určitých nepsaných pravidel. Kód by měl být zapisován přehledně tak, aby jej mohli pochopit i jiní programátoři. K tomu mi posloužil textový editor VIM, nabízející širokou sadu nástrojů pro zpracování textu. VIM je open source textový editor, který lze spustit v prostředí většiny operačních systémů. Je oblíbený zejména mezi zkušenými uživateli operačních systémů unixového typu. Kromě klasického VIMu existuje celá řada editorů, které jsou založeny na principu VIMu, ale mají nějaké specifické vlastnosti např. KVim pro prostředí KDE. V roce 1988 napsal Bram Moolenaar obdobu editoru Vi pro Amigu, tento program byl založen na kódu (editoru Vi SteVIe), proto byl pojmenován Vi IMitation. 2

Pro PC existují ovšem i kvalitní překladače jazyka C od jiných firem

3.8

Textový editor VIM

29

Roku 1991 byla uveřejněna první veřejná verze tohoto editoru – VIM 1.14. Tato verze byla stále dostupná pouze pro Amigy, na UNIX byla přenesena až verze 1.22, kdy došlo k celé řadě vylepšení a editor byl přejmenován na Vi IMproved. Další přelomovou verzí byla verze 3 (1994), kdy se objevila podpora více oken a verze 4 z roku 1996, kdy byla do editoru zapracována možnost grafického rozhraní. Další verzí byla verze 5 (1998), kde největší změnou bylo zvýrazňování syntaxe. Nyní (2005) je poslední verzí verze 6 (z roku 2001). Roku 2002 byla změněna licence směrem k licencím typu GPL, což umožnilo využít VIM jako základní editor v některých linuxových distribucích. Tato změna licence byla umožněna faktem, že z původního kódu, který Bram Moolenaar využil, již ve Vimu nezůstalo nic. Editor VIM má tři režimy práce: • základní, neboli příkazový režim, tento režim se objeví po spuštění, v tomto režimu lze pomocí klávesových zkratek zadávat příkazy pro práci s textem, • vkládací režim, jedná se o režim v němž se edituje text, • režim ex. V tomto režimu lze zadávat příkazy pomocí příkazového řádku. Tento režim slouží k zadání jednoho příkazu, po jeho provedení se VIM vrátí do základního režimu. Textový editor VIM má jako každý produkt své výhody a nevýhody. Mezi výhody lze zařadit: • snadná a logická ovladatelnost, • existuje verze pro mnoho operačních systémů, • rychlost, • zpracování nápovědy, • neomezené možnosti. Nevýhody: • z dnešního pohledu poněkud nestandardní ovládání, • delší doba zaučení začátečníka. (Wikipedie, 2006)

4

IMPLEMENTACE LEXIKÁLNíHO ANALYZÁTORU

4

30

Implementace lexikálního analyzátoru

Důležitým aspektem pro korektní činnost každého překladače je správná identifikace konkrétních slov tzv. tokenů. Lexikální analyzátor načítá ze vstupní pásky jednotlivé znaky a sestavuje je do lexikálních jednotek – tokenů. Vlastní páska má svůj počátek, od kterého se odvíjí čtení vstupních znaků. Čtecí hlava se pohybuje pouze jedním směrem bez možnosti vracet se zpět proti směru načítání. Základním úkolem lexikálního analyzátoru je tedy načítat znaky ze vstupní pásky, rozpoznat jednotlivá slova a vyhodnotit, zda programovací jazyk může s těmito lexikálními jednotkami pracovat. Podstatnou záležitostí pro sestavení překladače je tedy definice jazyka, který bude navrhovaný překladač podporovat. V této fázi se nekladou přílišné překážky fantazii programátora. Nyní je čas navrhnout vhodná slova jazyka, s nimiž bude pozdější uživatel pracovat tzn. programovat.

4.1

Návrh

Před definicí klíčových slov je nutné definovat, jaké struktury budou implementovány v programovacím jazyce. Nelze si představit programování bez použití cyklů, procedur, nebo bez základních prvků jako jsou čísla nebo řetězce. Jazyk Ruzin bude schopen zpracovávat a pracovat s následujícími strukturami umožňujícími běžné programátorské operace: • celá čísla, desetinná čísla, • standardní operátory včetně logických, • příkazové bloky, • řetězce, • identifikátory, • bílé znaky, • přiřazení, • ukončovací znak příkazu, • komentáře, • proměnné, • uvození, • opakování, • ukazatele, • další. Všechny uvedené struktury jsou základní komponentou každého programovacího jazyka. Bez těchto nástrojů se neobejde žádný programátor.

4.2

31

Abeceda

4.2

Abeceda

Navržené struktury nabízí programátorovi slušnou základnu pro uplatnění jeho kreativity při programování. Je však nezbytné definovat, z jakých „písmenÿ se budou jednotlivé tokeny charakterizující různé struktury skládat. Nejprve je nutné definovat abecedu programovacího jazyka, popisující všechny navržené struktury. Abeceda programovacího jazyka Ruzin bude obsahovat nejen písmena české abecedy a čísla, ale budou v ní zakomponovány i znaky dostupné na počítačové klávesnici včetně některých tzv. bílých znaků. Výsledná podoba je tedy následující: Σ = {č, p, +, −, ∗, /, ., , , &, |, !, ?, $, @, #, %, §, (, ), <, >, =, :, ”, \, {, }, [, ], , 7→, ←-, ; } Kde: č – jsou čísla 0–9 p – jsou písmena české abecedy a–ž, A–Ž.

4.3

Lineární gramatiky

Abeceda je základem každého jazyka, nejen programovacího. Vysázení několika písmen za sebe, však ještě neznamená vytvoření smysluplného slova. Aby slovo dávalo smysl, musí se znaky skládat podle daných pravidel určených gramatikou. Různé druhy gramatik jsem již popsal výše3 a je zřejmé, že chci vytvářet gramatiku klasifikovanou podle Chomského, konkrétně pak pravou lineární gramatiku typu 3 ve tvaru: A → wB nebo A → w; A, B ∈ N, w ∈ Σ∗ Každá struktura představuje v podstatě konkrétní jazyk, pro který je potřeba navrhnout samostatnou lineární gramatiku, splňující zmíněná pravidla. Gramatika jazyka čísel Lcis – Definuje v jaké podobě bude jazyk akceptovat zadaná čísla. V mém případě nebudu experimentovat a zavedu standardní znázornění celých a desetinných čísel. Jejich tvar bude mít například podobu: +12, 32, -3.14 Takto zadaná čísla budou srozumitelná pomocí následující gramatiky. Gcis = {Ncis , Σcis , Pcis , Scis } Σcis = {č , +, −, .} Pcis : Scis → +A | − A | A A →č A | č | č .B B →č B | č Ncis = {Scis , A, B} 3

Kapitola 3.2 Pojem Gramatika

4.3

32


Gramatika jazyka aritmetických a logických operátorů Lop – Práce s čísly a nejen s nimi vyžaduje zavedení operátorů. Gop = {Nop , Σop , Pop , Sop } Σop = {+, −, ∗, /, &, |, !, (, ), <, >, =, } Pop : Sop → + | − | ∗ | / | && | || | ! | ( | ) | < | > | == | <= | >= | <> Nop = {Sop } Gramatika jazyka příkazových bloků Lpb – Každý programovací jazyk musí umět seskupit několik příkazů do jednoho bloku. Je to nutné například pro správnou funkci cyklů, kdy se vykonává blok příkazů uvedených v jeho těle. Po splnění podmínky teprve program pokračuje dál v plnění dalších instrukcí. V mém případě jsem za označení začátku a konce bloku zvolil složené závorky. Gpb = {Npb , Σpb , Ppb , Spb } Σpb = {{, }} Ppb : Spb → { | } Nret = {Spb } Gramatika jazyka řetězců Lret – Řetězec představuje několik znaků ohraničených uvozovkami. Navržená gramatika řeší problém zápisu uvozovek zahrnutých do řetězce jako zobrazitelný znak. V případě, že se mají uvozovky v řetězci zobrazit, musí jim předcházet znak \. Zápis řetězce pak vypadá následovně: "řetězec s \"uvozovkami\"" Bez zpětného lomítka by uvozovky byli chápány jako ukončení řetězce. Gret = {Nret , Σret , Pret , Sret } Σret = {Σ} Pret : Sret → ”C C → C | ” | \D D → C | ”C | \C Nret = {Sret , C, D}

kde: = Σret − {”, \}

Gramatika jazyka identifikátorů Li – Tato gramatika definuje identifikátory funkcí, klíčových slov příkazů větvení a cyklů nebo klíčové slovo struktury pole. Při sestavování gramatiky by již mělo být jasné, jaká klíčová slova budou použita pro jednotlivé příkazy. Například pro příkaz větvení použiji klíčová slova pokavad – tak – inac. Gi = {Ni , Σi , Pi , Si } Σi = {č , p} Pi : Si → pE | p E → pE | č E | č | p Ni = {Si , E} Gramatika jazyka bílých znaků Lbz – Každý programátor by měl psát nejen fungující zdrojové kódy, ale také přehledné kódy. Je to dáno určitou etikou programování. Přehledně napsaný kód vyžaduje použití tzv. bílých znaků. Jsou

4.3


33

to znaky mezera, tabulátor a enter. Díky nim lze vytvořit přehledný zdrojový kód. Gbz = {Nbz , Σbz , Pbz , Sbz } Σbz = { , 7→, ←-} Pbz : Sbz → | 7→ | ←Nbz = {Sbz } Gramatika jazyka přiřazení Lpri – Přiřazovací příkaz je nezbytnou součástí programovacích jazyků. V různých typech jazyků se používá různých značení pro tento příkaz. Já jsem si pro přiřazovací příkaz zvolil znak jednoduchého =. Gpri = {Npri , Σpri , Ppri , Spri } Σpri = {=} Ppri : Spri →= Nbz = {Spri } Gramatika jazyka ukončení příkazu Lup – Potřebu zápisu několika příkazů za sebou řeší ukončovací příkaz. Jazyk Ruzin pro tento příkaz použije standardní znak ;. Gup = {Nup , Σup , Pup , Sup } Σup = {; } Pup : Sup →; Nbz = {Sup } Gramatika jazyka komentářů Lkom – Komentáře jsou pro každý programovací jazyk užitečnou pomůckou. Nabízí možnosti komentovat text do konce aktuálního řádku nebo víceřádkový komentář. # Toto je poznámka platná pouze do konce řádku /# Tímto způsobem lze napsat poznámku na více řádků #/ Jazyk Ruzin používá pro jednořádkový komentář znak #. Víceřádkový komentář začíná dvojicí znaků /#, konec komentáře pak označují stejné znaky v obráceném pořadí #/. Gramatika jazyka komentářů má následující tvar: Gkom = {Nkom , Σkom , Pkom , Skom } Σkom = {Σ} Pkom : Skom → #F | /#G F → F | #F | /F | ←kde: = Σ − {←-, #, /} G → G | #H | /G | ←- G H → G | #H | ←- G | / Nkom = {Skom , F, G, H} Gramatika jazyka proměnných Lprom – Programovací jazyky se neobejdou bez proměnných. Navržená gramatika rozpozná sekvenci znaků na vstupní pásce jako proměnnou podle klíčového znaku $. V názvu samotné proměnné mohou být obsaženy pouze písmena, nebo čísla.

4.3


34

$prom, $prom1, $2 Jazyk nebere ohled na první znak za znakem určující proměnnou, jak je to například ve skriptech CGI. Na tomto místě může být jak písmeno, tak i číslo: Gprom = {Nprom , Σprom , Pprom , Sprom } Σprom = {$,č , p} Pprom : Sprom → $I I →č I | pI | č | p Nprom = {Sprom , I} Gramatika jazyka uvození Luvo – Použití polí a ukazatelů v mém programovacím jazyce si vyžaduje vytvoření dodatečné gramatiky vyjadřující schopnost přidělit poli, nebo ukazateli, jeho atributy. Atributy pole jsou uvozeny hranatými závorkami [, ]. Stejné je to také v případě ukazatelů. Guvo = {Nuvo , Σuvo , Puvo , Suvo } Σuvo = {[, ]} Puvo : Suvo → [ | ] Nuvo = {Suvo } Gramatika jazyka opakování Lopa – Pole nemusí obsahovat pouze jeden atribut. Oddělení atributů v zápisu pole je naznačeno čárkou ,. Hodnoty pole budou indexovány automaticky. Výsledná podoba zápisu pole může vypadat například následně: pole[-1, "ahoj", pole[1, "nazdar", +3], $abc] Opakování atributů bude také využito při zápisu podprogramů, u kterých se může také vyskytovat více parametrů najednou. Gopa = {Nopa , Σopa , Popa , Sopa } Σopa = {, } Popa : Sopa →, Nopa = {Sopa } Gramatika jazyka ukazatelů Luka – Gramatika pointerů je dána klíčovým slovem *poi. Toto klíčové slovo inicializuje proměnnou pomocí příkazu přiřazení, např.: $ukazatel = *poi[] Inicializace proměnné typu ukazatel znamená přiřazení automaticky generované hodnoty do proměnné. Hodnota uložená v proměnné, simuluje adresu v paměti počítače, na které je prostor pro uložení konkrétní hodnoty. Guka = {Nuka , Σuka , Puka , Suka } Σuka = {*, p, o, i} Puka : Suka →*poi Nuka = {Suka }

4.4

Významové a nevýznamové jazyky

35

V tomto případě je nutno rozlišovat klíčové slovo *poi. Skládá se ze čtyř konkrétních znaků, z nichž např. písmeno p nelze zaměnit s písmenem p4 reprezentující písmena celé abecedy. Gramatika jazyka další Ldal – Tato gramatika je úzce spojená s gramatikou ukazatelů, konkrétně s přímým zapisováním hodnot do struktury ukazatele. Automatická indexace hodnot, podobně jako u struktury pole, zajistí přístup k požadovaným hodnotám právě pomocí tokenu ->. Gdal = {Ndal , Σdal , Pdal , Sdal } Σdal = {−, >} Pdal : Sdal → − > Ndal = {Sdal } Navržené gramatiky jsou základním stavebním kamenem pro zjišťování správné syntaxe zdrojového kódu psaného v jazyce Ruzin. Popisují různé struktury použité v jazyce, se kterými bude programátor pracující s jazykem Ruzin disponovat. Vytvoření lexikálního analyzátoru vyžaduje tyto gramatiky zkloubit do jedné, postihující globálně celou problematiku načítání vstupních dat. Je nutné brát v úvahu rozdíly významu jednotlivých gramatik. Některé gramatiky popisují oddělovací jazyky, jiné gramatiky jsou významové.

4.4

Významové a nevýznamové jazyky

Jak jsem se již zmínil, je určitým etickým pravidlem psát kód tak, aby se v něm jiný programátor vyznal. Pomocníky při psaní přehledných programů jsou mezera, tabulátor a enter sloužící pro zarovnávání kódu. Vysvětlení programátorských nuancí přinášejí popisné komentáře. Přínos těchto znaků a struktur je jednoznačný pro člověka, ale programovací jazyk se bez nich zřejmě obejde. Pro programovací jazyk nemají podstatný význam. Možná pouze v tom, že je musí umět identifikovat, aby je mohl ignorovat. Ostatní načítané tokeny však již význam mají, a to dost podstatný. Na základě nich se překladač rozhoduje, jaké sémantické akce bude provádět, jak bude vlastně reagovat. Důležitou činností je tedy zjišťování významu tokenů přicházejících ze vstupní pásky. Rozpoznání, zda lexikální jednotky mají či nemají význam pro překladač, přináší rozlišení jazyků na významové a nevýznamové. Jazyk významových tokenů – pomocí množinového operátoru sjednocení ∪ je možné vyjádřit výsledný jazyk významových tokenů, z něhož lze jednoduše vydedukovat i zápis jejich gramatiky. Lvt = Lcis ∪ Lop ∪ Lpb ∪ Lret ∪ Li ∪ Lpri ∪ Lup ∪ Lprom ∪ Luvo ∪ Lopa ∪ Luka ∪ Ldal Gvt = {Nvt , Σvt , Pvt , Svt } Σvt = Σ − { , 7→, ←-} 4

Definice písmen viz. kapitola 4.2 Abeceda

4.5

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

36

Pvt : Svt → Scis | Sop | Spb | Sret | Si | Spri | Sup | Sprom | Suvo | Sopa | Suka | Sdal Nvt = {Svt , Scis , Sop , Spb , Sret , Si , Spri , Sup , Sprom , Suvo , Sopa , Suka , Sdal } Jazyk nevýznamových tokenů – jedná se v podstatě o jazyk oddělovačů, který opět vznikne sjednocením nevýznamových jazyků, konkrétně jazyka bílých znaků a jazyka komentářů. Lod = Lbz ∪ Lkom Pod : Sod → Sbz | Skom Zároveň je však potřeba si uvědomit, že nevýznamové tokeny se mohou rekurzivně opakovat před začátkem významového tokenu. Gramatika bude vypadat následovně. L∗od :

Sod → Skom Sod | Sbz Sod | Skom | Sod | ε

Rozvinutím gramatiky vznikne definitivní podoba jazyka nevýznamových tokenů L∗od . God = {Nod , Σod , Pod , Sod } Σod = {Σ} Pod : Sod → #F | /#G | Sod | 7→ Sod | ←- Sod | ε F → F | #F | /F | ←- Sod G → G | #H | /G | ←- G H → G | #H | ←- G | /Sod Nod = {Sod , F, G, H} Kde: = Σ − {←-, #, /}. Pravidla F → . . . , G → . . . a H → . . . nemohou být v tomto případě definitivně ukončena, protože neobsahují samostatný terminální symbol. Znamená to rekurzivní opakování nevýznamových tokenů. Tím je zajištěno, že jazyk oddělovačů bude zakončen až tehdy, načte-li se významový token. Do gramatiky je zapsán znak ε znázorňující konec jazyka oddělovačů v případě, že významový token nenásleduje. Lexikální analyzátor, respektive lineární gramatika jazyka Ruzin pak vznikne konkatenací rekurzivního jazyka oddělovačů a jazyka významových tokenů. lex ∼ L∗od .Lvt

4.5

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

Dokončená definice gramatiky oddělovačů umožňuje přejít k dalšímu kroku, kterým je vytvoření celkové lineární gramatiky lexikálního analyzátoru. Pro větší přehlednost si předdefinujeme start významových tokenů na neterminální symbol J, který zajišťuje konkatenaci. Neterminální symbol J bude vložený do pravidel startu oddělovačů.

4.6

Regularizace lineární gramatiky

37

Gramatika zaručuje opakovené načítání oddělovačů zakončené načtením významového tokenu, nebo načtením konce vstupního souboru v podobě znaku ε. L : GL = ({A, B, C, D, E, F, G, H, I, J, S}, Σ, P, S) P : S → #F | /#G | S | 7→ S | ←- S | ε | J A →č A | č | č .B B →č B | č C → 4C | ” | \D | /C | #C | ←- C D → 4C | ”C | \C | /C | #C | ←- C E → pE | č E | č | p F → 4F | #F | /F | ←- S | ”F | \F G → 4G | #H | /G | ←- G | ”G | \G H → 4G | #H | ←- G | /S | ”G | \G I →č I | pI | č | p J → +A | − A | A | + | − | ∗ | / | && | || | ! | ( | )| < | > | == | <= | >= | <> | { | } | ”C | pE | p | = | ; | $I | [ | ] | , | ∗poi | − > Kde: č – jsou čísla 0–9 p – jsou písmena české abecedy a–ž, A–Ž. 4 = Σ − {”, \, ←-, #, /}.

4.6


Vytvoření konečného automatu z lineární gramatiky jazyka předchází regularizace. Ke každé lineární gramatice existuje vždy odpovídající gramatika regulární. Převod bude proveden aplikací tří kroků algoritmu 15 . Problém regularizace se v největší míře týká pravidel gramatiky, proto finální zápis regulární gramatiky bude proveden na konci výpočtu. Nyní se zaměřím na úpravu samotných pravidel. Algoritmus 1.1 – převedení A → aB. S → #F | /#G | S | 7→ S | ←- S | ε | J A →č A | č | č.B B →č B | č C → 4C | ” | \D | /C | #C | ←- C D → 4C | ”C | \C | /C | #C | ←- C E → pE | č E | č | p F → 4F | #F | /F | ←- S | ”F | \F G → 4G | #H | /G | ←- G | ”G | \G H → 4G | #H | ←- G | /S | ”G | \G I →č I | pI | č | p 5

Kapitola 3.3.1 Lineární a regulární gramatika

4.6

38


J → +A | − A | A | + | − | ∗ | / | && | || | ! | ( | )| < | > | == | <= | >= | <> | { | } | ”C | pE | p | = | ; | $I | [ | ] | , | ∗poi | − > ⇓ S → #F | /K | S | 7→ S | ←- S | ε | J A →č A | č | čL B →č B | č C → 4C | ” | \D | /C | #C | ←- C D → 4C | ”C | \C | /C | #C | ←- C E → pE | č E | č | p F → 4F | #F | /F | ←- S | ”F | \F G → 4G | #H | /G | ←- G | ”G | \G H → 4G | #H | ←- G | /S | ”G | \G I →č I | pI | č | p J → +A | − A | A | + | − | ∗ | / | &M | |N | ! | ( | )| < | > | = P | < P | > P | < R| { | } | ”C | pE | p | = | ; | $I | [ | ] | , | ∗T | − R K → #G L → .B M →& N →| P →= R →> T →pU U →oV V →i Algoritmus 1.2 – odstranění ε pravidel. Gramatika obsahuje znak ε pouze ve startovací části pravidel. Podle pravidel regularizace je však povoleno přepsání startovacího symbolu na ε, tudíž je vše v pořádku. Algoritmus 1.2 nemusí být aplikován a bude přistoupeno k algoritmu 1.3. Algoritmus 1.3 – odstranění jednoduchých pravidel. V gramatice jsou samostatné neterminální symboly pouze J a A. Nahrazením neterminálů vzniká finální podoba regulární gramatiky lexikálního analyzátoru. GR = ({A, B, C, D, E, F, G, H, I, J, K, L, M, N, P, R, T, U, V, S}, Σ, P, S) P : S → #F |/K| S | 7→ S | ←- S | ε |+A|−A|čA | č | čL |+|−|∗|/| &M | |N | ! | ( | )| < | > | = P | < P | > P | < R|{ | } | ”C | pE | p | = | ; | $I | [ | ] | , | ∗ T | − R A → čA | č | čL B → čB | č C → 4C | ” | \D | /C | #C | ←- C D → 4C | ”C | \C | /C | #C | ←- C E → pE | č E | č | p F → 4F | #F | /F | ←- S | ”F | \F

4.7

Nedeterministický konečný automat

39

G → 4G | #H | /G | ←- G | ”G | \G H → 4G | #H | ←- G | /S | ”G | \G I →č I | pI | č | p J → +A | −A | čA | č | čL | + | − | ∗ | / | &M | |N | ! | ( | )| < | > | = P | < P | > P | < R|{ | } | ”C | pE | p | = | ; | $I | [ | ] | , | ∗ T | − R K → #G L → .B M →& N →| P →= R →> T →pU U →oV V →i Správně regularizovaná gramatika je předpokladem pro sestavení konečného nederministického automatu.

4.7

Nedeterministický konečný automat

Slovo „nedeterministickýÿ naznačuje, že není jasně dáno ve všech stavech, který stav bude následovat. V nedeterministickém automatu je v každém stavu celá množina cílových stavů, nikoliv právě jeden cílový stav. v každém nastoleném stavu je jasné, jaké stavy budou následovat. Z jednoho stavu je možné přejít do jednoho z několika definovaných stavů. vlastnost procesu, jehož každý stav je určen předcházejícím Prerekvizitou pro vytvoření nedeterministického konečného automatu je sestavení přechodové funkce. Přechodová funkce je vytvořena na základě pravoregulární gramatiky aplikací algoritmu 2 (viz. příloha A, tabulka 1 a 2). Záhlaví tabulky tvoří jednotlivé znaky abecedy Σ použité při návrhu gramatiky. Levý sloupeček obsahuje stavy, které v podstatě představují neterminální symboly obsažené v pravoregulární gramatice. Kombinace znaku a stavu říká, pod jakým symbolem, do jakého dalšího stavu je možné z výchozího stavu postoupit. Nederministický konečný automat má tedy přechodovou fci: M = (Q, Σ, δ, qS , qFb ) Kde: Q = {qS , qA , qB , qC , qD , qE , qF , qG , qH , qI , qJ , qK , qL , qM , qN , qP , qR , qT , qU , qV , qFb }

4.8

Deterministický konečný automat

Na základě nedeterministického konečného automatu je možné postoupit k procesu determinizace. Principem determinizace je takové rozšíření původní množiny

4.9

Programování lexikálního analyzátoru

40

stavů Q, aby několik původních stavů tvořilo jeden stav nový (viz. příloha B, tabulka 3). Například z množiny stavů {qA , qL , qFb } je vytvořen jeden stav qALFb . Po korekturuře stavů v celé tabulce lze vydedukovat cesty překlápění stavů. Nevyužité stavy, do kterých nevede cesta, nejsou potřebné a tudíž je odstraním. Týká se to stavů qA , qE , qJ , qK , qL , qP , qR , qT . Postupnou úpravou pak vznikne výsledná podoba deterministického konečného automatu (viz. příloha B, tabulka 4). Navržený determinizovaný konečný automat je podkladem pro naprogramování samotného lexikálního analyzátoru. Jeho funkce bude spočívat v načítání lexikálních jednotek ze vstupní pásky a vyhodnocení, zda je taková jednotka součástí jazyka Ruzin.

4.9


Teoretické zpracování lexikálního analyzátoru je nezbytným předpokladem pro samotné naprogramování správně fungující jednotky, načítající odpovídající tokeny. Tabulka deterministického automatu je nyní nejdůležitějším podkladem pro sestavení logického systému stavů, znaků a cest mezi nimi. Zdrojový kód všech součástí jazyka Ruzin vytvářím v textovém editoru vim. Kód je pak zpracováván jazykem C. Nyní stručně popíšu důležité součásti samotného kódu lexikálního analyzátoru. Velmi důležitým aspektem v této problematice jsou přechodové stavy. Abych mohl pracovat s názvy stavů, musím definovat jejich množinu. Jazyk C to umožňuje výčtovým typem. Výčtový typ dovoluje velmi zpřehlednit program a zvýšit jeho modularitu. Pomocí něho lze snadno definovat seznam symbolických konstant, které mohou být – a nejčastěji jsou – vzájemně závislé (Herout, 2001, s. 245). Samotné názvy stavů jsou převzaty z tabulky deterministického automatu. Symbol koncového stavu Fb v tomto případě nahradím symbolem X. Přechodové stavy definované výčtovým typem mají následnou podobu. typedef enum { QS, QB, QC, QD, QF, QG, QH, QI, QM, QN, QU, QV, QX, QEX, QALX, QAX, QARX, QTX, QKX, QPRX, QPX, QBX, QIX } stav; Na začátku načítání každé nové lexikální jednotky potřebuji nastavit proměnnou určující aktuální stav do stavu QS. Další důležitou položkou, kterou musím sledovat, je typ načteného tokenu. Usnadní to identifikaci tokenu při zpracování syntaktickým analyzátorem, kdy tak mám k dispozici nejenom samotnou lexikální jednotku, ale také její typ. Názvy typů ukládám do pole řetězců.

4.9


41

Pole řetězců je asi nejčastěji využívané dvourozměrné pole s různou délkou jednotlivých řádek. Téměř každý program pracující s textem6 využívá pole řetězců (Herout, 2001, s. 224). Na tomto místě je tedy vhodné ukázat, jakým způsobem definuji v jazyce Ruzin názvy typů jednotlivých lexikálních jednotek. char *nazev_typu[]={ "promenna", "cislo", "arit.oper", "rel.oper", "prirazeni", "retezec", "prik.blok", "ukonc.prik", "identifikator", "uvozeni", "opakovani", "ukazatel", "dalsi","pole", "cyklus", "vetveni", "podprogram" }; Definice a inicializace proměnné nazev_typu je provedena jako pole pointerů na statické položky tohoto pole. Přístup do pole se provádí standardním způsobem pomocí notace hranatých závorek s udaným číslo typu mezi nimi. Je nutné si uvědomit, že položky pole začínají položkou s indexem 0. Hodnota typu je pak zjišťována při průchodu jednotlivými stavy podle načítaného tokenu. Zmínil jsem se o poli pointerů. Při programování překladače jsou pointery nezbytnou pomůckou, bez které by tato práce byla minimálně velice složitá, ne-li nemožná. Pointer je proměnná jako každá jiná, pouze hodnota v této proměnné uložená, má odlišný význam, od hodnot proměnných, na které jsme dosud zvyklí. Pointer představuje adresu v paměti a na této adrese se teprve ukrývá příslušná hodnota. Jinak řečeno, pointer je proměnná uschovávající paměťovou adresu (Herout, 2001, s. 146). Lexikální analyzátor využívá pointeru při skládání slova z jednotlivých načítaných znaků. Sestavení slova ze znaků znamená sestavení lexikální jednotky – tokenu, základní stavební jednotkou celého interpreta. Vytvoření tokenu z načítaných znaků technicky představuje sestavování znaků do řetězce. Definice a inicializace řetězce je provedena přiřazením ukončovacího znaku *slovo=’\0’;. Protože se jedná o pointer, musíme alokovat dostatečný prostor pro načítaný token slovo=(char *) malloc(10000 * sizeof(char));. Přiřazení znaku popsaným způsobem však ještě neznamená, že je tak možné přidávat do slova jiné znaky. Proměnná slovo ukazuje pouze na začátek pole řetězce. Je nutné rozlišovat nulový pointer a nulový řetězec. Nulový pointer má hodnotu NULL (což je většinou 0), zatímco nulový řetězec je řetězec, jehož první znak je ’\0’. Je nutné dávat pozor na rozdíl mezi "x" a ’x’. • "x" – je řetězcová konstanta délky vždy 2 Byte (znak ’x’ + znak ’\0’). • ’x’ – je znaková konstanta typu int, která ale může v paměti zabírat jen 1 Byte, ale také 2 nebo 4 Byte (Herout, 2001, s. 197). Přidávání znaku do řetězce se tedy provádí tak, že nejprve za pozici ukončovacího znaku řetězce je vložen druhý ukončovací znak slovo [strlen(slovo)+1]=’\0’;, takže dva znaky ukončení řetězce následují za sebou (to je možné provést díky alokoci dostatečného prostoru). Nyní je potřeba si uvědomit, že délka řetězce je daná 6

Typickým představitelem je textový editor

4.9


42

počtem znaků předcházejících prvnímu ukončovacímu symbolu. Pokud situace vyžaduje přidat znak do řetězce, přepíše se první ukončovací symbol načteným znakem z pásky slovo[strlen(slovo)]=znak; a druhý ukončovací symbol přebere úlohu zakončení řetězce. Vstupní znaky jsou opakovaně načítány z pásky do doby, než je načten ukončovací symbol souboru EOF, který představuje znak ε v regulární gramatice. Podstata správné funkce vytváření tokenů spočívá v periodickém načítání znaků, které jsou podle nastavených pravidel zpracovávány. Základní konstrukcí lexikálního analyzátoru je tedy výběrový příkaz switch zapouzdřený do příkazu cyklu while. Je tím vystižen předpoklad opakovaného načítání znaku ze vstupní pásky do doby, než je ukončeno načítání aktuálního tokenu. V případě výskytu chyby, musí být načítání ukončeno chybovou hláškou, obsahující číslo řádku, na kterém se chyba vyskytla. Načítání znaku je prováděno jako první krok v těle cyklu. Dále se provádí analýza stavu, který bude načtený znak zpracovávat. Stavy obsahující koncový stav, např. stav ALX, mohou načítání tokenu ukončit. Každému tokenu může předcházet jeden nebo více bílých znaků. Začátek tokenu tedy nemusí začínat přímo počátečním znakem lexikální jednotky, naznačující její význam. Bílé znaky slouží pouze jen jako oddělovače mezi tokeny, nemají pro samotný významový token žádný smysl. V každém zdrojovém kódu jsou však obsaženy kvůli jeho přehlednosti. Vyskytují-li se oddělovací znaky na vstupní pásce, budou sice načítány, ale do řetězce určujícího načítané slovo se nepřidají. Na základě definované gramatiky je také zřejmé, že načítání oddělovačů nelze ukončit, ale načítání musí pokračovat přidáváním významových znaků do řetězce. Přiřazením posledního významového znaku do řetězce ze vstupní pásky končí vytváření tokenu, identifikace konce načítání se nastaví na hodnotu 1, podmínka cyklu není splněna a program postupuje načítáním dalších instrukcí. Provedením zbylých instrukcí je činnost lexikálního analyzátoru prozatím ukončena. Problém nastává při zjišťování dalšího tokenu. Předchozí lexikální jednotka sice obsahuje všechny svoje znaky, ale ukončení cyklu nastane až tehdy, načte-li se z pásky znak nepatřící do tohoto tokenu. Čtecí hlava v tomto momentu načetla znak umístěný bezprostředně za posledním znakem tokenu a posune se na znak další. Čtecí hlava čeká na příkaz čtení. Pro méně zdatnější čtenáře popíšu chronologický sled načítání a vznik problému. Důležité je uvědomovat si pozici čtecí hlavy. Nechť na vstupu pásky je řada znaků +-3. Lexikální analyzátor musí rozpoznat 2 tokeny s obsahem + a -3. Výchozí pozice čtecí hlavy je na znaku +. Zanořením do cyklu se načte aktuální znak, který je vložen do řetězce. Pozice hlavy se posune na znak -, kde vyčkává na další příkaz čtení. Pracovní znak + je následně zpracován stavy v příkazu switch. Následně je tělo cyklu správně dokončeno, tudíž se opět vyhodnocuje podmínka ukončení cyklu. Prozatím je vše v pořádku, je tedy možné další zanoření do cyklu, kde je načten další zpracovávaný znak -. Pozice čtecí hlavy načtením tohoto znaku přechází do další pozice na znak 3. Pracovním znakem však stále zůstává znak -. Příkaz switch pracovní znak vyhodnotí jako nesprávný znak a naznačí konec načítání lexikální jednotky. Podmínka cyklu tím není splněna. Při

4.9


43

opětovném zjišťování dalšího tokenu znamená zanoření do cyklu načtení dalšího znaku. Pozice čtecí hlavy je však na pozici znaku 3. Je evidentní, že znak - posloužil jako ukončení načítání tokenu +, ale při načítání dalšího tokenu již není akceptován, což je nežádoucí. Problém vynechávání znaku lze jednoduše ošetřit zavedením pomocné proměnné zjišťující konec slova int endword=0. Zjištění konce znamená nastavení proměnné na hodnotu 1. Načítání znaku pak podléhá příkazu větvení. if (endword == 1) { endword = 0; } else { znak = getc(f); }; Pokud je nastaven konec slova na 1, proměnná konce se vynuluje, jinak pokračuje načítání dalšího znaku. Podobný problém nastává v situaci načítání sekvence znaků např. 5+3. Standardním postupem lexikání analyzátor načte dva tokeny 5 a +3. Rozdělení na tři samostatné tokeny však evidentně přináší výhodnější postavení pro další zpracování syntaktickým analyzátorem, který by ohlásil syntaktickou chybu způsobenou dvěma po sobě následujícími čísly s absencí operátoru mezi nimi. Problém řeším opět zavedením pomocné proměnné operator, která zajišťuje ukončení načítání operátoru, následuje-li ten po číslu, nebo proměnné, protože jenom v těchto případech vystupuje aritmetický operátor jako samostatný token. Identifikaci čísla a proměnné zařizuje příkaz switch vybráním správných stavů. Mluvím-li o stavech, rád bych se zmínil o jedné odlišnosti oproti tabulce deterministického automatu. Stavy QC, QD, QF, QG, QH, jsou přístupné pod všemi znaky abecedy. Ve zdrojovém kódu však uvádím pouze určité vybrané znaky. Je to z toho důvodu, že pod ostatními znaky z těchto stavů přecházím do stavu pro drtivou většinu znaků stejného. Jelikož abeceda jazyka Ruzin používá všechny dostupné znaky klávesnice, mohu si dovolit defaultně přecházet na další stav v části default příkazu switch. Nevznikne tak nepředpokládaná chyba, ani není nastaven jiný typ tokenu. V této souvislosti musím poznamenat, že komentáře vlastní typ nemají, protože při načítání jsou znaky komentářů ignorovány, tudíž je bezpředmětné typ zjišťovat. Jiná situace nastává u identifikátorů. Identifikátorem mohu označit klíčová slova příkazu větvení, příkazu cyklu, pole nebo hodnotu NULL u pointerů. Zde určování typů hraje důležitou roli pro další zpracování. Například hodnotě NULL je přiřazen typ pointer následující instrukcí. if (strcmp(ct,"NULL") == 0){ typ = 11; };

4.9


44

Typování identifikátoru provádím po proběhnutí cyklu lexikálního analyzátoru, kdy už je jasné, jakou má načtený token přesnou podobu. Číslo typu určuje pozice pole, na které se řetězec vyskytuje v proměnné nazev_typu. Lexikální analyzátor je reprezentován funkcí lex(). Větší přehlednost při dalším psaní zdrojového kódu zaručí zapouzdření funkce lexikálního analyzátoru do programového balíku, který implementuji příkazem #include lex.h. Správná funkčnost lexikálního analyzátoru dává předpoklad pro konstrukci syntaktického analyzátoru.

5

IMPLEMENTACE SYNTAKTICKÉHO ANALYZÁTORU

5

45

Implementace syntaktického analyzátoru

Rozklad věty, neboli syntaktická analýza, se provádí pomocí konstrukce derivačního stromu. Derivační strom zaručuje, že řetězec nad danou abecedou jazyka je větou jazyka, tj. že neobsahuje syntaktické chyby, ale neméně důležité je i nalezení syntaktické struktury věty. Již jsem se zmínil, že syntaktickou analýzu je možné provádět dvěma způsoby. Pro obecné bezkontextové gramatiky se provádí syntaktická analýza s vracením do výchozí konfigurace, ve které se vyskytla volba postupu do dalších konfigurací rozkladu. Pro deterministické bezkontextové gramatiky se provádí analýza bez vracení. Cílem této práce je vytvořit deterministickou bezkontextovou gramatiku, ve které je v každé fázi rozkladu dané věty dopředu znám jeden terminální symbol – token, a tím vytvářet analýzu bez vracení. Derivační strom vytvářím pomocí syntaktických diagramů způsobem shora dolů. Výchozí konfigurací je start programu napsaného v jazyce Ruzin podle daných lexikálních pravidel. Z výchozí konfigurace je možné přejít do jiné konfigurace na základě syntaktických pravidel, které zvolím pro daný jazyk pomocí grafů syntaxe. Je-li v každé konfiguraci znám alespoň jeden rozhodovací token, je možné provést rozklad věty bez vracení pomocí syntaktických diagramů tak, že výstup provedené analýzy dává možnost vytvořit deterministickou bezkontextovou gramatiku typu LL(k). V případě, že se analýza provádí se znalostí pouze jednoho terminálního symbolu, lze vytvořit deterministickou gramatiku typu LL(1). Postup, jakým provádím syntaktickou analýzu pomocí grafů syntaxe (viz. příloha C) je popsán v následující části.

5.1

Rozklad věty pomocí grafů syntaxe

Syntaktické diagramy jsou rychlou, efektivní a velice přehlednou metodou rozkladu věty. V této fázi dostávám prostor pro definici použití implementovaných struktur do jazyka Ruzin. Nyní nastává situace, kdy specifikuji, jak bude vypadat struktura zdrojového kódu, kdy a jak mohou být zapsány jednotlivé použité struktury jazyka nebo jakým způsobem se bude používat zápis například polí nebo ukazatelů. Lexikální analyzátor načítá jednotlivé tokeny a syntaktická analýza určuje, zda je možné použití tokenu v aktuální konfiguraci. Při konstrukci derivačního stromu vycházím z toho, jakým způsobem se může rozvíjet vstupní věta, zdrojový kód jazyka Ruzin, od startovacího symbolu. Postupným rozkladem věty získávám jednotlivé grafy syntaxe, znázorňující možné přechody mezi konfiguracemi. Grafy syntaxe obsahují dva druhy značení. V případě, že nastává situace, kdy z aktuální konfigurace je možné přejít do několika jiných konfigurací, je označena tato situace obdélníkem, který znázorňuje neterminální symbol. V případě, že situace vyžaduje konkrétní token pro zachování syntaktické správnosti, je tato situace

5.1


46

naznačena oválem, znázorňujícím symbol terminální. Popis grafů syntaxe je tedy následný: Program je vrchol derivačního stromu – začátek programu. Program může začínat pouze dvěmi situacemi, deklarací podprogramů a hlavním tělem programu – blokem příkazů. Jiné nastavení konfigurace je nežádoucí a musí následovat ohlášení chyby. Deklarace je pasáž programu, kde je možné definovat podprogramy použité v hlavní části programu. Deklarace tedy obsahuje definici jednotlivých podprogramů. V některých jazycích je deklarační část určena také pro specifikaci typů proměnných, použitých v těle programu. Jazyk Ruzin je netypový jazyk, kde jsou všechny proměnné inicializovány přiřazením konkrétní hodnoty. Není tedy třeba specifikovat typ proměnné v deklarační části programu. Může také nastat situace, že v programu není definován žádný podprogram a přechází se přímo na část hlavního bloku příkazů. Část deklarace tedy obsahuje v grafickém znázornění také linii, jenž volně prochází diagramem a není na ní umístěn žádný neterminální, ani terminální symbol. V gramatice tato konstrukce představuje prázdný znak ε a znamená to, že část deklarace je v tomto případě vynechána. Tato konstrukce je často použita i u dalších grafů syntaxe. V případě, že program obsahuje definici podprogramu je nutné analyzovat další rozklad věty tímto směrem. Definice podprogramu musí vždy začínat klíčovým slovem ppr, za kterým následuje token, identifikující název podprogramu. Za identifikátorem funkce, nebo procedury pokračuje pasáž zadávání lokálních parametrů prom ohraničená kulatými závorkami. Specifikace názvu podprogramu a jeho parametrů je důležitá, ale podstatou procedur a funkcí je vykonání definovaného bloku příkazů. Blokppr je tělo podprogramu, ve kterém může být uveden sled příkazů. Struktura těla podprogramu a samotného těla celého programu je stejná. Začíná levou složenou závorkou označující začátek bloku, pokračuje zadáním příkazu, které je možné opakovat. Jako oddělovač mezi příkazy je použit klasický středník. Konec bloku představuje pravá složená závorka. Jak už jsem říkal, struktura příkazového bloku je stejná jak u podprogramu, tak i u těla celého programu. Musím pro ně však navrhnout odlišné diagramy syntaxe. Je to kvůli jednomu příkazu, který se vyskytuje poze v těle podprogramu, jen tam a nikde jinde. Je to příkaz return, kvůli kterému je nutné definovat neterminál prikazppr. Prikazppr je neterminál definující všechny standardní příkazy obohacené o příkaz return, za kterým následuje neterminální symbol výraz. Samotné příkazy v tomto diagramu není zatím vhodné z důvodu duplicity diagramů rozepisovat, ale stačí je naznačit neterminálním symbolem prikaz, který je popsán dále v samostatném diagramu. Tímto diagramem jsem vyčerpal všechny možnosti rozvoje věty podprogramu. Nyní je nutné vrátit se na začátek derivace, do diagramu program, a pokračovat rozkladem netermináního symbolu blok.

5.1


47

Blok je hlavním tělem samotného programu. Jak je již popsáno, struktura hlavního bloku příkazů je stejná, jako struktura bloku příkazů podprogramu. Jediným rozdílem je použití neterminálního symbolu prikaz, který je znázorněn odlišným syntaktickým diagramem, než je znázorněn diagram prikazppr. Prikaz je reprezentován diagramem specifikujícím všechny možné příkazy, které je možné v jazyce Ruzin použít. Tyto příkazy jsou reprezentované neterminálními symboly pro příkazy přiřazení, cyklu, větvení a volání funkce. Je však nutné si uvědomit, že pokud příkazový blok nebude obsahovat žádný příkaz, neukončí se syntaktická analýza chybou. Absence jakéhokoliv příkazu v příkazovém bloku sice nevyvolá žádnou reakci, ale proces překladu musí stále pokračovat dál. Prirazeni je syntaktický diagram znázorňující pravidla pro zápis přiřazovacího příkazu, reprezentovaného znakem =. Jakékoliv přiřazení probíhá do nějaké konkrétní proměnné. Jelikož jsem již v části prom říkal, že zápis proměnné ovlivňuje implementace struktury pole a pointerů, je nutné rozdělit proces přiřazení do tří základních větví. První větev popisuje přiřazení do standardně zapsané proměnné bez žádného rozšíření. Do takové proměnné je možné přiřadit hodnotu NULL v případě, že se jedná o proměnnou ukazující na strukturu ukazatele. Dále je možné do proměnné přiřadit výraz, definici ukazatele nebo definici pole. Druhá větev řeší, jaké hodnoty lze přiřadit do proměnné rozšířené o terminály definované v části rozšíření-ukazatel. Za symbolem přiřazení do takové proměnné se mohou vyskytovat jen symbol NULL nebo výraz. Poslední třetí větev ošetřuje možnost přiřazení hodnoty do pole. V tomto případě je hodnota reprezentována výrazem. Definice-ukazatel znázorňuje, jaká syntaktická pravidla platí při inicializaci proměnné typu ukazatel. Inicializace se provádí přiřazením do proměnné, jak jsem již popsal v předchozí části. Při definici ukazatele je nutné nejprve naznačit terminálem *poi, že se jedná o pointer. Následuje pasáž uzavřená hranatými závorkami, ve které jsou uvedeny názvy záznamů, které se mají uchovat ve struktuře pointeru. Ukazatel se nedefinuje přímým uložením hodnot, ale nejdříve je nutné identifikovat názvy, pod kterými budou konkrétní hodnoty uloženy. Na místě identifikátoru se může vyskytnout opět definice ukazatele, ale pouze z jedním parametrem, což znamená, že zde není povolena rekurze. Tento zápis naznačuje, že struktura záznamů bude obsahovat ukazatel na jiný prvek. Identifikátorů se v definici může vyskytovat tolik, kolik je potřeba vytvořit záznamů ve struktuře ukazatele. Definice-pole je diagram strukturou podobný předchozímu diagramu s menšími rozdíly. Identifikace definice pole je zaručena klíčovým slovem pole, za kterým je opět pasáž ohraničena hranatými závorkami. Rozdíl v definici pointerů a polí je hlavně v tom, že pole narozdíl od pointerů jsou inicializovány přímým vložením konkrétních hodnot do příslušných buněk polí. Hodnoty jsou zaznamenány v pasáži mezi závorkami, kde lze do pole přiřadit buď určitý výraz nebo další

5.1


48

definici pole. Dalším rozdílem oproti ukazatelům je, že pole je možné rekurzivně definovat jako prvek jiného pole. Cyklus je diagram příkazu pro opakované provádění bloku příkazů. Klíčovým slovem cyklu jsem zvolil slovo dokavad za nímž následuje podmínka v podobě neterminálu výrazu. Za podmínkou je další klíčové slovo delej za nímž je příkazový blok. Z popisu je zřejmé, že diagram reprezentuje klasický cyklus while, pouze s pozměněnou syntaxí. Vetvení je další diagram příkazu s pozměněnou syntaxí oproti standardnímu zápisu. V tomto případě jsem zvolil za klíčová slova pokavad – tak – inac. Pravidla pro zápis tohoto příkazu vyžadují po prvním klíčovém slově uvedení podmínky následovanou dalčím klíčovým slovem a blokem příkazů. Dále může příkaz končit, nebo následuje poslední klíčové slovo s příkazovým blokem. Volani-funkce představuje jakým způsobem probíhá volání podprogramu. Nejprve musí být terminál definován v části deklarace. Následuje část zadaných parametrů, kterých se může v daném místě vyskytnout i víc. Vyraz je popisem pravidel asi nejdůležitějšího segmentu programovacího jazyka – výrazů. Správné navržení derivačního stromu pro výrazy je alfou a omegou celé mé diplomové práce. Syntaktické diagramy výrazu určují, jakým způsobem je možné provádět číselné nebo řetězcové operace, jak se dají použít funkce ve výrazu, určují prioritu jednotlivých operátorů a v neposlední řadě umožňují požití proměnných jako ekvivalentu konkrétních hodnot. Samotný diagram vyraz obsahuje rekurzi v podobě neterminálního symbolu vyraz, dvou operátorů and a or následovaných neterminálem T. Jelikož ne vždy se ve výrazech používají logické operátory, je nutné naznačit v grafu možnost jejich vynechání. T je syntaktický graf pro znázornění zpracování rozhodovacích pravidel v situaci, kdy se ve výrazu zobrazí znak negace !. Zde také není podmínkou výskyt negačního znaménka, proto lze pokračovat přímo neterminálem F. F je znázorněním pravidel zpracování relačních operátorů porovnání. Na každé straně takového operátoru se může vyskytovat nejen konkrétní hodnota, ale také i celý aritmetický výraz. Opět je zde naznačeno možné vynechání operátorů a pokračování neterminálním symbolem AV. AV ukazuje, jakým způsobem jsou zpracovány aritmetické operátory. Zde je pořeba si uvědomit, že operátory sčítání a odčítání mají menší prioritu než operátory násobení a dělení. Proto je nutné pro obě skupiny operátorů vytvořit separovaná pravidla. T1 představuje diagram analýzy aritmetických operátorů násobení a dělení. Opět je zde naznačeno pravidlo vynechání operátoru, znamenající přímý přístup k hodnotě popsané diagramem F1. F1 je konečným znázorněním pravidel výrazu. Všechny diagramy rozkladu výrazu musely obsahovat linii, která nechávala pravidla jednotlivých diagramů „mimo hruÿ. Příčina je prostá. Kdyby diagramy linii neobsahovaly, pokračoval by rozklad derivačního stromu do nekonečna, protože by se nikdy nemohly načíst

5.2

Návrh deterministické bezkontextové gramatiky

49

konkrétní hodnoty, se kterými výraz pracuje. Množina možných použití hodnot je specifikována až na samotném dně derivačního rozkladu diagramem F1. Zde je popsáno, jaký terminální symbol bude na aktuálním místě ve výrazu použit. Jedná se o kulaté závorky uvozující další výraz, konstantu, řetězec, proměnnou definovanou diagramem prom, nebo se může jednat o identifikátor popsaný diagramem volanifunkce. Prom v podstatě popisuje možný zápis proměnné. V programu Ruzin je zápis proměnné specifikován úvodním speciálním symbolem $, po kterém následuje název proměnné, např. $promenna. Zavedením struktur pole a pointerů, musím také zavést formu zápisu proměnné, umožňující práci s těmito strukturami. Je nutné rozšířit standardní zápis proměnné o neterminály rozšíření-pole a rozšířeníukazatel. Rozšíření-pole udává způsob zápisu, jakým je možné přistupovat do jednotlivých buňek pole. Standardní zápis, který je ponechán i v jazyce Ruzin, se skládá z číselné konstanty uvozené do hranatých závorek. Sekvence znaků se může i vícekrát opakovat u definice přístupu do konkrétní buňky matice nebo vícerozměrného pole. Zápis pro přístup do matice pak může vypadat například $promenna[2][1]. Rozšíření-ukazatel je zaveden ze stejného důvodu jako předchozí neterminál rozšíření-pole, jen s tím rozdílem, že obsahuje terminály specifikující způsob zápisu ukazatele pomocí. Těmito terminály jsou šipka a identifikátor. Podoba zápisu proměnné pak může vypadat např. $promenna->identifikator, kde identifikátor určuje konkrétní záznam ve struktuře pointeru. Syntaktické diagramy rozšíření končí větev rozkladu parametrů funkce nebo procedury. Nyní je potřeba se vrátit zpět do diagramu definice a pokračovat neterminálním symbolem blokppr, pro který je navržen samostatný syntaktický diagram. Veškeré možné rozklady věty jsem popsal. Jiné metody nebo metodiky zpracování dat nejsou v programu Ruzin povoleny. Nyní je jasně definováno, jaké konfigurace syntaktické analýzy mohou nastat a do jakých jiných konfigurací je možné přejít.

5.2


Díky grafickému znázornění derivačního stromu pomocí grafů syntaxe lze dosáhnout přehledné struktury, ze které je možné jednoduchým způsobem odvodit pravidla deterministické bezkontextové gramatiky. Přepisování grafů syntaxe se provádí tak, že nadpis každého grafu je dán jako levá část přepisovacího pravidla gramatiky. Pravou stranu pravidel tvoří jednotlivé terminální a neterminální symboly. Grafy syntaxe se čtou zleva do prava což je dost důležitý fakt. Postupným čtením grafu zleva do prava je totiž vytvářen tvar pravé strany pravidel zápisem terminálních nebo neterminálních symbolů v pořadí, v jakém jsou čteny. V místě, kde je v grafu linka rozdvojená, je do pravé strany

5.2


50

pravidel přidána logická spojka nebo |. Rozdvojení může znamenat zavedení nového neterminálního symbolu, který je nutný pro přesné popsání situace. Celkovým přepsáním grafů syntaxe pak vzniká bezkontextová gramatika. V gramatice jsem nahradil neterminály rozšíření-pole a rozšíření-ukazatel kratšími zápisy pro zvýšení přehlednosti postupně neterminály exparr a exppoi. P ROGRAM → DEKLARACE BLOK DEKLARACE → DEF IN ICE A | ε A → DEF IN ICE A | ε DEF IN ICE → ppr identif ikator ( B ) BLOKP P R B → promenna C | ε C → , promenna C | ε BLOKP P R → { P RIKAZP P R G } G → ; P RIKAZP P R G | ε P RIKAZP P R → return V Y RAZ | P RIKAZ BLOK → { P RIKAZ H } H → ; P RIKAZ H | ε P RIKAZ → P RIRAZEN I | CY KLU S | V ET V EN I | V OLAN IF U N KCE | ε P RIRAZEN I → promenna J J → = K | EXP P OI = L | EXP ARR = V Y RAZ K → V Y RAZ | DEF ARR | DEF P OI | null L → V Y RAZ | null DEF P OI → ∗poi [ M ] M → HODN OT Y N | ε N → , HODN OT Y N | ε HODN OT Y → identif iktor | ∗ poi [ identif iktor ] DEF ARR → pole [ P Q ] P → V Y RAZ | DEF ARR Q→, P Q|ε CY KLU S → dokavad ( V Y RAZ ) delej BLOK V ET V EN I → pokavad ( V Y RAZ ) tak BLOK R R → inac BLOK | ε V OLAN IF U N KCE → identif ikator ( S ) S → V Y RAZ V | ε V → , V Y RAZ V | ε V Y RAZ → V Y RAZ and T | V Y RAZ or T | T T →!F |F F → AV == AV | AV <> AV | AV < AV | AV > AV | AV <= AV | AV >= AV | AV AV → AV + T 1 | AV − T 1 | T 1 T1 → T1 ∗ F1 | T1 / F1 | F1 F 1 → ( V Y RAZ ) | konstanta | retezec | P ROM | V OLAN IF U N KCE P ROM → promenna D D → EXP ARR | EXP P OI | ε

5.2

51


EXP ARR → [ U ] E E→[U ]E |ε U → konstanta | promenna EXP P OI → − > W W → identif ikator | ε Ve vytvořené gramatice se ovšem vyskytuje nežádoucí levá rekurze u pravidel, na jejichž levých stranách jsou neterminální symboly V Y RAZ, AV , T 1. Levá rekurze by ztěžovala práci syntaktickému analyzátoru, proto je vhodné ji odstranit. Odstranění přímé levé rekurze předvedu na pravidla obsahující na levé straně pravidla neterminální symbol V Y RAZ. Při procesu odstraňování rekurze vzniká další neterminál, který je pojmenován stejně jako neterminál ze kterého vzniká s přidaným pruhem nad neterminálem, např. V Y RAZ. Z důvodu přehlednosti nahradím tento zápis novým názvem neterminálu RV . V Y RAZ → V Y RAZ |and or T | |{z} T {z T} | V Y RAZ |{z} α1

α2

β

⇓ V Y RAZ → |{z} T RV β

RV → and T RV | ε | {z T} RV | or |{z} α1

α2

Ostatní případy výskytu levé rekurze jsou upraveny stejným způsobem. Jelikož zbytek gramatiky zůstává v nezměněném stavu, není potřeba ostatní pravidla přepisovat a stačí si ukázat jen pravidla, která jsou změněna. V gramatice odstraním pravidla, na jejichž levé straně jsou neterminální symboly V Y RAZ, AV a T 1. Místo nich jsou do gramatiky přidány pravidla V Y RAZ → T RV RV → and T RV | or T RV | ε AV → T 1 AV 1 AV 1 → + T 1 AV 1| − T 1 AV 1 | ε T 1 → F 1 T 11 T 11 → ∗ F 1 T 11| / F 1 T 11 | ε Gramatika ještě obsahuje pravidlo, které by při výpočtu množin FIRST a FOLLOW nesplňovalo podmínku gramatiky LL(1). Jde o pravidlo, které má na levé straně neterminální symbol F . Toto pravidlo je třeba také celé odstranit a nahradit ho dvojicí pravidel F → AV X X →== AV | <> AV | < AV | > AV | <= AV | >= AV | ε Předtím, než začnu provádět výpočet množin FIRST a FOLLOW, upravím gramatiku tak, aby obsahovala méně pravidel. Podle algoritmu 17 , odstraním vybraná 7

Kapitola 3.3.1 Lineární a regulární gramatika

5.3

Ověření LL(1) gramatiky

52

jednoduchá pravidla, ne však všechna. Dosáhnu tím redukci pravidel a tím zjednodušenou orientaci v nich. Výsledná podoba bezkontextové gramatiky je znázorněna v příloze D. Navržená gramatika na pravé straně přepisovacích pravidel obsahuje v některých případech derivaci neterminálních symbolů. Z toho je jasné, že se nejedná o regulární gramatiku, ale o gramatiku bezkontextovou. Syntaktickou analýzu bez vracení je však možné provádět pouze nad deterministickou bezkontextovou gramatikou. Provedené úpravy by měly zaručovat, že vytvořená bezkontextová gramatika je deterministická, tzn. že v každé konfiguraci lze přejít pod danými symboly do jiné, jediné konfigurace. Není možné, aby se pod jedním symbolem bylo možné vydat dvěmi, nebo více směry derivačního stromu.

5.3

Ověření LL(1) gramatiky

Gramatika vytvořená ze syntaktických diagramů, je podkladem pro navržení bezkontextové gramatiky. Odstraněním levé rekurze, přímé i neřímé, a drobnou kosmetickou úpravou jsem navrhl gramatiku, která by měla být bezkontextovou gramatikou typu LL(1). Jistotu do této úvahy dodá ověření gramatiky výpočtem množin FIRST a FOLLOW. Výpočet množin FIRST a FOLLOW ověřuje, zda je možné přecházet z konfigurace do konfigurace pod určitým tokenem pouze jednou cestou. Nebylo-li by tomu tak, byla by se muset syntaktická analýza provádět s vracením, což je v mém případě nežádoucí. Proto musí být dodržena podmínka LL(1) gramatiky FF(αi ) ∩ FF(αj ) = 0; ∀i, j ∈ {1 . . . n}, i 6= j pro pravidla, ve kterých se na pravé straně vyskytuje více možností derivace. Výpočet množin FIRST a FOLLOW je proveden v příloze E. V případě, že se výpočet FF pro některá pravidla opakuje ve výpočtech FF pro jiná pravidla, je uveden pouze výsledek tohoto výpočtu a celý proces výpočtu již není opakován.

5.4

Konstrukce deterministického zásobníkového automatu

Výpočet množin FIRST a FOLLOW nejen ověřil, že gramatika vyhovuje podmínce dané pro gramatiku typu LL(1), ale také pro každé pravidlo stanovil konečnou množinu zásobníkových symbolů. Pomocí těchto vypočítaných symbolů pro každé pravidlo je možné zkonstruovat zásobníkový automat ve formě tabulky. Záhlaví tabulky tvoří množina zásobníkových symbolů, včetně prázdného znaku ε. Levý sloupeček tabulky obsahuje všechny neterminální symboly gramatiky, za které je ještě přidaná množina zásobníkových symbolů a ještě jeden symbol Z0 , který označuje počáteční obsah zásobníku. Konstrukce tabulky je prováděna na základě vypočítané množiny symbolů množinami FF (viz. příloha F) pro každé pravidlo zvlášť. Například pro pravidlo P ROGRAM → DEKLARACE BLOK je vypočítána množina symbolů {ppr, {}. Ve sloupečcích, v jejichž záhlaví jsou obsaženy tyto zásobníkové znaky, a v řádku

5.5

Syntaktický analyzátor

53

tabulky, ve kterém je neterminální symbol P ROGRAM , se zapíše sekvence z pravé strany zmíněného pravidla. Stejným způsobem se postupuje pro všechna ostatní pravidla. Sestavená tabulka zásobníkového automatu (viz. příloha G) je podkladem pro naprogramování programového modulu – syntaktického analyzátoru.

5.5


Modul syntaktické analýzy je v podstatě soubor procedur, které reprezentují pravidla bezkontextové gramatiky. Každá procedura je pojmenována názvem konkrétního neterminálního symbolu, vyskytujícího se na levé straně pravidla gramatiky. Pro všechny neterminály jsou vytvořeny jednotlivé procedury. Obsahem každé procedury je pravá strana daného pravidla. Simulaci větvení derivačního stromu v proceduře provádím pomocí příkazu if. Je zřejmé, že přechod mezi konfiguracemi derivačního stromu se děje na základě aktuálního tokenu. Pro syntaktickou analýzu je nutné nejprve načíst první token a zavolat proceduru program(), která reprezentuje startovací neterminální symbol gramatiky. Tato procedura rekurzivně spustí další proceduru deklarace(), po jejímž správném dokončení je spuštěna procedura blok(). V těle procedur se mohou ověřovat a načítat aktuální tokeny, nebo spouštět další procedury, a to vše na základě jasně daných pravidel bezkontextové gramatiky. Tímto způsobem je programově vytvářen derivační strom. Pro názornost uvedu příklad rozvoje derivačního stromu pro prázdný program, který je ve zdrojovém kódu naznačen pouze ohraničením těla programu složenými závorkami { }. Nejdříve je nutné načíst první token {, pomocí funkce lex(), kterou jsem definoval dříve při implementaci lexikálního analyzátoru. Dalším krokem je volání procedury program(), která již začne postupný proces rozvoje derivačního stromu následujícím způsobem: program( deklarace() blok( over_cti(}) prikaz () h() over_cti(}))) Z příkladu je zřejmé, jakým způsobem probíhá syntaktická analýza. Funkce over_cti() ověřuje, zda je aktuální token opravdu tím slovem, se kterým je možné do procedury přijít, a zároveň načítá další token v pořadí. Při programování syntaktického analyzátoru je velice důležité mít správně vypočítané množiny FIRST a FOLLOW. Díky vypočítaným množinám znaků, pro každé přepisovací pravidlo, je možné určit, jaká konfigurace (procedura), pod jakým znakem (tokenem) bude následovat. Správný chod programu ovlivňují zejména správné výpočty množin znaků pro pravidla přepisující se na ε. V těchto pravidlech se sice nespouští žádná další procedura, ale je velice důležité vědět, pod jakým znakem se do dané konfigurace lze dostat. Správně sestavený syntaktický analyzátor je schopen detekovat chybnou syntaxi napsaného zdrojového kódu. V případě, že v některé proceduře není možné provádět další rozvoj derivačního stromu, ohlásí tato procedura chybu v syntaxi.

5.5


54

Syntaktický analyzátor tedy postupně prochází zdrojový kód programu a analyzuje jeho správnost. Aby byly provedeny instrukce zdrojového kódu, musí být do procedur přidány sémantické akce, které se při průchodu syntaktického analyzátoru provedou.

6

IMPLEMENTACE SÉMANTICKÝCH AKCí

6

55

Implementace sémantických akcí

Potřeba provádět sémantické akce na určitém místě znamená, vykonat určitou programovou akci. Vkládání algoritmů přímo do syntaktického analyzátoru by znamenalo přinejmenším znepřehlednění kódu a ztrátu orientace v modulu analyzátoru. Proto jsou syntaktické akce reprezentovány funkcemi, které se při průchodu kódem provádějí. Každá sémantická akce musí provádět určitou operaci, která je nutná pro vyhodnocení instrukce dané zdrojovým kódem jazyka Ruzin. Je zřejmé, že instrukce mohou být různé a jsou dané zápisem zdrojového kódu. V textu kódu se mohou vyskytovat například příkazy cyklu, větvení, přiřazení a spousta jiných instrukcí. Podle toho, jaké slovo (instrukce) je v kódu obsaženo, se provádí přechod do určité konfigurace a zároveň je nutné v konkrétní konfiguraci, pod konkrétní instrukcí provést sémantickou akci. Lze tedy tvrdit, že sémantická akce je spojena s konkrétním tokenem, který ve správné konfiguraci vyvolá konkrétní sémantickou akci. Problematiku vkládání sémantických akcí vysvětlím na příkladu načítání podprogramů. Syntaktickou analýzou je například zjištěno, že ve vstupním souboru je na prvním místě slovo „pprÿ. Tento fakt je důležitý pro syntaktický analyzátor, který na základě tohoto tokenu rozhodne, do jaké konfigurace přejde, neboli jakou další proceduru spustí. Z hlediska sémantiky je však tento token bezvýznamný, není potřeba provádět žádnou akci. Token „pprÿ způsobí rozvoj derivačního stromu až do pravidla DEF IN ICE → ppr identif ikator (B) blokppr, kde je načten další token obsahující název podprogramu. Jelikož ještě není známo, jakou operaci bude podprogram provádět nebo zda se jedná o funkci či proceduru, je nutné si název podprogramu zapamatovat. Název je uložen do odpovídající struktury8 , což znamená vyvolání operace uložení. Operace uložení názvu podprogramu je tedy sémantická akce, vyvolaná v přesném místě daným tokenem. Token ppr je jen světlou výjimkou mezi ostatními tokeny. Většina ostatních tokenů nějakou sémantickou akci vyvolává. Důležité je si však uvědomit, na kterém místě je nutné danou akci implementovat. Většinou je to v pravidlech, kde se ověřuje a načítá další token v pořadí. Díky sémantickým akcím je možné při průběhu syntaktické analýzy vykonávat instrukce dané vstupním souborem. Je možné provádět podprogramy, příkazy cyklů, větvení nebo vypočítat různé výrazy.

6.1

Výrazy

Jednou z nejdůležitějších komponent každého programovacího jazyka je schopnost vyhodnocovat výrazy. Každý další příkaz jazyka se bez výrazů nemůže obejít. Příkazy cyklu obsahují podmínku, což je výraz. Příkazy větvení obsahují také podmínku. Nelze si snad ani představit, která nedokáže vyhodnocovat matematické 8

Přesný pois provádění podprogramů a ukládání názvů je popsán v kapitole 6.4

6.1

Výrazy

56

operace. Proto je velice vhodné navrhnout sémantické akce pro vyhodnocení výrazu, aby bylo možné pokračovat dále v konstrukci interpreta. Jazyk Ruzin musí umět vyhodnocovat několik druhů výrazů: • aritmetické výrazy – dané aritmetickými operátory +, −, ∗, /, • relační výrazy – dané relačními operátory <, >, <=, >=, ==, <>, • logické výrazy – dané logickými operátory &&, ||, !, • řetězcové výrazy – konkatenace řetězců je prováděna operátorem +, V běžném životě je pro výpočet matematických operací používána tzv. infixová notace. Každý ze základní školy ví, jaké operátory mají přednost při výpočtu, že obsah závorky má vyšší prioritu než okolí závorky. Tento fakt však počítač nezná, proto je nutné při vyhodnocování výrazu převést výraz do tvaru, který je možné strojově zpracovat. Při zpracování výrazů je nutné brát zřetel na aritu operátorů, neboli rozlišovat operátory na nulární (např. konstanta), unární (např. negace) a binární (např. a+b). Vyšší arita není v jazyku Ruzin použita. Obecně jsou dané tři druhy notace: • infixová – využívaná v běžném životě, např. 7 + 4 ∗ 3 ∗ (6 + 2) • prefixová – nejdříve následuje operátor, za ním jsou v závorce uvedeny hodnoty, které má operátor zpracovat, např. +(7, ∗(4, ∗(3, +(6, 2)))). Výraz se vyhodnocuje zezadu, • postfixová – operátor zpracovává podle arity operandu, uvedené před tímto operátorem, např. 743 ∗ 62 + ∗+. Strojově nejefektivněji zpracovatelné jsou výrazy psané v postfixové notaci. Zde je vhodné podotknout, že pokud lexikální analyzátor při čtení záporného čísla vrátí token, který již obsahuje znaménko zápornosti nebo kladnosti, nelze již zpracovávat unární operátory + a −. Tyto operátory se zpracovávají už pouze jen jako binární operátory. Pro výpočet postfixového výrazu je vhodné implementovat zásobník, do kterého se ukládají operandy přicházející ze vstupního výrazu, nazvu ho „výsledekÿ. Výpočet je prováděn v několika krocích: • Je-li na vstupu opernad, uloží se do zásobníku, • Je-li na vstupu operátor, ze zásobníku se vybere podle arity určitý počet operndů, provede se výpočet a výsledek je uložen zpět do zásobníku, • Po skončení výpočtu je výsledek uložen v zásobníku. Výpočet výrazu zapsaného v postfixové notaci je tedy velice jednoduchý. Problém tkví v tom, že málokdo dokáže výraz v postfixové notaci zapsat. Je tedy nezbytné, zavést algoritmus pro převod notace infixové na postfixovou. Implementace převodu notací vyžaduje vytvoření dalšího zásobníku, který dočasně uchovává operátory, přicházející ze vstupního výrazu a podle níže popsaných pravidel je aplikuje na operandy uložené v zásobníků operandů. Tento postup se někdy nazývá slepá kolej, proto zásobník pojmenuju „slepá kolejÿ. Je-li potřeba převést vstupní soubor z notace infixové na notaci postfixovou, aplikují se následující pravidla: • je-li na vstupu operand, „projíždíÿ do zásobníku výsledek,

6.2

Příkaz přiřazení

57

• je-li na vstupu operátor, projíždí na slepou kolej v případě, že slepá kolej je prázdná, nebo je na ní levá kulatá závorka, nebo je na ní operátor s nižší prioritou, • na vstupu je operátor nižší nebo stejné priority, než je na slepé koleji. Operátor ze slepé koleje je převeden do zásobníku výsledek a na slepou kolej je převeden vstupní operátor, • je-li na vstupu levá závorka, projíždí na slepou kolej, kde tvoří „zarážkuÿ, • je-li na vstupu pravá závorka, všechny operátory na slepé koleji před zarážkou postupně projíždí do zásobníku výsledek. Levá a pravá závorka jsou odstraněny, • není-li na vstupu již žádný operand ani operátor, je zbytek operátorů postupně přemístěn ze slepé koleje do zásobníku výsledek. Po převodu notací je možné aplikovat postup výpočtu postfixové notace na zásobník výsledek. Pokud se ovšem aplikace výpočtu aplikuje již při převodu notací, je po převodu na postfixovou notaci na zásobníku výsledek přímo výsledek výrazu. Výpočet výrazu se provádí vždy, když je do zásobníku výsledek převáděn operátor. Ten se neuloží do zásobníku, ale přímo provede operaci s příslušným počtem operandů v zásobníku9 , tyto operandy vyjme a výsledek vloží zpět do zásobníku výsledek. Díky implementaci vyhodnocování výrazů lze přistoupit k implementaci základních příkazů přiřazení, větvení, cyklů a provádění procedur.

6.2


Každý program musí umět pracovat s proměnnými, jejichž použití si vyžaduje např. v jazyce Pascal jejich deklaraci, kde se uvádí jakého typu proměnná je. Programovací jazyk Ruzin je konstruován jako netypový jazyk, tudíž není nutné před hlavním tělem programu uvádět deklarační část. Definice proměnné se zde provádí tak, že kdekoliv v hlavním těle programu stačí do proměnné přiřadit nějakou hodnotu. Ani v tomto případě není nutné žádným způsobem deklarovat typ proměnné, jako je tomu například v jazyce C. Jak jsem se již zmínil, jazyk Ruzin je netypový jazyk a nemusí se uvádět typ proměnné. Pro zpracování výrazů je však nutné vědět, zda je požadovaná operace přípustná či nikoliv, což je možné pouze za předpokladu, že jsou typy všech proměnných a konstant známy. Pro vnitřní zpracovávání tedy typy proměnných uchovávám. Příkaz přiřazení je definován pomocí operátoru = na jehož levé straně se musí vyskytovat proměnná, do které je přiřazena hodnota výrazu na pravé straně operátoru. Tuto situaci znázorňuje pravidlo P RIKAZ → promenna J. Terminální symbol pravé strany pravidla určí směr rozvoje derivačního stromu a následně se načítá další token, který určuje, kterým směrem se rozvoj bude ubírat při spuštění procedury J. Pravidlo J má několik variant rozvoje. Zde se analyzuje problém při9

Počet je dán aritou operátoru.

6.2


58

řazení do konkrétní buňky pole nebo do pointeru. V případě že se nejedná o takové přiřazení, provede se inicializace proměnné podle toho, jaké další tokeny následují. Inicializace proměnných probíhá podle pravidla K. Zde jsou uvedeny sémantické akce, které zakládají proměnné do zásobníku. Při zakládání proměnné, se nejdříve ověří, zda proměnná v zásobníku proměnných již neexistuje. Pokud existuje, je vytvořena s dočasným typem pracovně označeným typ 0. Tento proces zaručuje integritu proměnných a jejich typů. Zatím není známo, jaký výsledek výrazu se do proměnné přiřadí a jakého bude typu. Kdybych tuto operaci neprovedl a rovnou do proměnné přiřadil výsledek výrazu, mohlo by se například v proměnné typu řetězec vyskytovat číslo, což je nežádoucí. Podoba struktury zásobníku proměnných je uvedena v příloze H Po založení proměnné v zásobníku je možné tuto proměnou naplnit hodnotou a typem. Opět záleží na tom, jaký další token bude následovat. Jedinou výjimku, kdy nelze proměnnou naplnit, tvoří pokus přiřazení do již definované proměnné typu pole. Uvedený příklad ukazuje, jakým způsobem provádím inicializaci a naplnění proměnných. Typ 13 je typ pole. if (!(exist(promenne,nazev_prom,scope))){ zaloz_prom(&promenne, nazev_prom, curtyp, scope); }; if (!(typ_prom(nazev_prom,scope) == 13)){ vyraz(); vymet(); napln_prom(promenne, nazev_prom, vysledek->hodnota, vysledek->typ, scope); vem_zas(&vysledek); }; Z příkladu je zřejmé, že do proměnné v zásobníku proměnných se naplní typ a hodnota získaná ze zásobníku výsledek, který byl naplněn provedením výrazu. Proměnná scope vyjadřuje úroveň zanoření, která je důležitá při implementaci podprogramů a její účel vysvětlím později. Sémantická akce vymet() znamená dopočítání zbylých operátorů na slepé koleji. Tento princip je využíván jak pro přiřazení hodnoty do proměnné, tak pro inicializaci proměnné hodnotou vzniklou vypočítáním výrazu. Ve výrazu se může vyskytovat konstanta, řetězec, proměnná nebo funkce. 6.2.1

Inicializace proměnné typu konstanta nebo řetězec

Inicializace proměnné typu konstanta nebo řetězec je prováděna přepisovacím pravidlem K → V Y RAZ. Následuje-li po tokenu přiřazení = konstanta nebo řetězec, rozvíjí se derivační strom do přepisovacího pravidla V RAZ a dále až do pravidla F 1. Je zřejmé, že konstanta i řetězec jsou součástí výrazu. Mohou inicializovat proměnnou jako samostatné symboly, ale také jako součást matematického výpočtu nebo konkatenace.

6.2


59

V každém případě se při načtení konstanty i řetězce přesune jejich hodnota do zásobníku výsledek. V případě výrazu, se po jeho vyhodnocení vyskytuje v zásobníku výsledek výsledná hodnota výrazu. Hodnota zásobníku výsledek poté díky dalším sémantickým akcím naplní inicializovanou proměnnou. Vyskytuje-li se na pravé straně přiřazovacího příkazu již definovaná proměnná, nebo volání funkce, je postup inicializace podobný. Nejprve je potřeba zapamatovat si název inicializační proměnné, nebo podprogramu, podle kterého je daná orientace v dalších konfiguracích. Jedná-li se o přiřazení pomocí inicializační proměnné, je nutné ověřit, zda je tato proměnná již založena či nikoliv. Neexistující proměnná nemůže předat svou hodnotu proměnné inicializované. Pokud inicializační proměnná existuje, musí se dalším rozvojem derivačního stromu zjistit, zda se jedná o proměnnou typu číslo, řetězec, pole nebo pointer, přenést hodnotu a typ hodnoty do zásobníku výsledek, odkud je naplněna inicializovaná proměnná hodnotou a typem proměnné. V případě, že proměnná je inicializovaná funkcí, provede se výpočet funkce a opět se předá hodnota a typ na zásobník výsledek, odkud se naplní inicializovaná proměnná. 6.2.2

Inicializace proměnné typu pole

Protože je jazyk Ruzin netypový jazyk a nedeklarují se v něm typy proměnných, je nutné nějakým způsobem definovat pole. Definice pole je prováděna prostým přiřazením do proměnné podle pravidla K → pole[P Q]. Zápis definice pak může vypadat například následovně: $array = pole[ 1, pole[2, 3], 4, 5] Pod názvem $array je založena v zásobníku proměnných proměnná typu pole. Následuje derivační rozvoj věty až po klíčové slovo pole. V tento moment se inicializují sémantické akce pro uložení jednotlivých hodnot do proměnné. Samotná struktura proměnné neobsahuje prostor pro uložení hodnoty, ale obsahuje ukazatel na strukturu nazvanou hodnota. V této struktuře je prostor pro uložení hodnoty, typu, indexu, úrovně a ukazatele na další strukturu. Načítáním jednotlivých tokenů, vytvářím nové hodnoty v proměnné. První slovo pole vynuluje proměnné index a level. S každou levou hranatou závorkou se zvyšuje hodnota proměnné level o 1 a s každou pravou hranatou závorkou je level o 1 snížen. Oddělovací čárka zvyšuje o 1 pomocnou proměnnou index. Načtení hodnoty znamená provedení výrazu a uložení hodnoty a typu ze zásobníku výsledek do struktury proměnné s aktuálními hodnotami levelu a indexu. Výsledná podoba uložené struktury je znázorněna v příloze H. Přístup k hodnotě pole je prováděn pomocí pomocného ukazatele na hodnotu pole. Například zápis $x = $array[2][1] inicializuje proměnnou x do které přiřadí výsledek výrazu. Načtením proměnné array se nastaví pomocný ukazatel na první hodnotu uložené v proměnné a vynulují se pomocné proměnné level a index. S každou levou hranatou závorkou ze zvyšuje hodnota levelu. Hodnota indexu je daná číslem

6.3

Příkaz větvení

60

(výrazem) v závorkách. Posun ukazatele je tedy nejprve na hodnotu s indexem dva na úrovni jedna. Další sekvence znaků přesměruje ukazatel na hodnotu s indexem jedna, ale na úrovni 2. Při implementaci tohoto principu přístupu k hodnotě pole je nezbytné, zabezpečit správné přesměrování pomocného ukazatele na hodnotu pole, protože se v proměnné typu pole může vyskytovat několik hodnot se stejnými indexy i levely. 6.2.3

Inicializace proměnné typu pointer

Způsob inicializace proměnné typu pointer je podobný jako v případě inicializace konstantou nebo řetězcem. Jediný rozdíl je v tom, že místo výrazu na pravé straně přiřazení je obsažena formule *poi[]. Znamená to, že místo hodnoty výrazu, se do proměnné uloží náhodně vygenerované číslo, představující adresu, na kterou proměnná typu pointer ukazuje. Inicializace proměnné však ještě neznamená naplnění pointeru hodnotou. Naplnění ukazatele hodnotou se provádí pomocí příkazu přiřazení, například $ukazatel-> = 3. Proměnná ukazatel již musí být definovaná. Pokud tomu tak je, založí se nový zásobník, nazvu ho adresy, do kterého se vloží samotná adresa, která je zjištěna v zásobníku proměnné z obsahu proměnné ukazatel, a také přiřazovaná hodnota 3. Tím simuliji funkci pointerů. V případě, že inicializuji nějakou proměnnou jinou proměnnou typu pointer, přiřadím do hodnoty inicializované proměnné pouze adresu, na které je v zásobníku adresy uložena požadovaná hodnota. Struktura pointeru je uvedena v příloze H.

6.3

Příkaz větvení

Je-li jazyk schopen zpracovávat aritmrtické, relační a logické výrazy, je možné přistoupit k řešení implementace příkazu větvení. Pomocí výrazu je totiž možné konstruovat podmínku větvení. Pro úplnost zatím ještě chybí implementace funkcí, které vracejí hodnotu, ale ty jsou vysvětleny dále. Pravidlo pro definici příkazu větvení je vyjádřeno v bezkontextové gramatice formulí P RIKAZ → pokavad (V Y RAZ) tak BLOK R. Provedení příkazu si nevyžaduje konstrukci zvláštních dynamických struktur. Vyhodnocená podmínka, hodnota na zásobníku výsledek, se uloží do pomocné proměnné, která je vyhodnocena před dalším větným rozvojem neterminálů BLOK a R. Pokud je podmínka TRUE, neboli má hodnotu 1, provede se rozvoj neterminálu BLOK a neterminál R se vynechá, pokud podmínka je FALSE, neboli 0, provede se rozvoj opačně. Jediným problémem je fakt, že kód programu je napsán pro obě varianty a čtecí hlavu nelze žádným způsobem přesouvat na požadované místo. Problém je řešen sémantickou akcí preskoc, která vyvolává načítání lexikálních jednotek do té doby, než narazí na pravou složenou závorku představující konec bloku příkazu ve větvi příkazu větvení. Při této operaci je však nutné si uvědomit, že příkazový blok může obsahovat příkazy, které vyžadují použití dalších příkazo-

6.4

Příkaz cyklu

61

vých bloků, např. cyklus, tudíž je nutné zabezpečit, aby přeskakování přes nepotřebné lexikální jednotky skončilo na správném místě. Je to zabezpečeno zavedením pomocné proměnné, která se zvyšuje při načtení každé levé složené závorky a při načtení pravé složené závorky se snižuje. V momentě, kdy je načtena pravá složená závorka, a pomocná proměnná má výchozí hodnotu, přeskakování tokenů vstupního souboru končí a pokračuje se v syntaktické analýze a provádění sémantických akcí. Implementace příkazu větvení má v mém případě následující podobu: over_cti(15,"pokavad"); over_cti(2,"("); vyraz(); vymet(); podm = atoi(vysledek->hodnota); vem_zas(&vysledek); if (podm != 1) { podm = 0; }; vloz_podm(&z_podminek, podm ); over_cti(2,")"); over_cti(15,"tak"); if (z_podminek->index == 1) { blok(); } else { preskoc(); over_cti(6,"}"); }; r(); Protože vypočítané hodnoty výrazu jsou do zásobníku výsledek zapisovány pomocí implementované funkce jazyka C sprintf(),která zapisuje hodnotu do řetězce, je i hodnota výsledku ve formě řetězce. Musím tedy výsledek výrazu převést pomocí fce atoi() na hodnotu typu integer, abych mohl vyhodnocovat podmínku příkazu větvení. V případě, že podmínka obsahuje jakoukoliv jinou hodnotu, než je 1, vyhodnotí se výraz jako FALSE.

6.4

Příkaz cyklu

Příkaz cyklu si oproti příkazu větvení vyžaduje konstrukci dynamické struktury. Je to způsobeno již samotnou logickou povahou cyklení. Prováděný příkaz větvení provádí buď jednu, nebo druhou část příkazu. Čtecí hlava se však posouvá stále na další tokeny dopředu a nemusí se tedy vracet. Příkaz cyklu však vyžaduje při splnění podmínky opakované provádění příkazového bloku. Již jsem říkal, že není možné přesouvat čtecí hlavu po pásce (vstupním souboru) jakýmkoliv směrem. Vždy načte aktuální znak a posune se o jednu pozici doprava. Abych byl schopen opětovného provedení příkazového bloku v cyklu, je nutné nejprve načíst podmínku cyklu a příkazový blok do zásobníku, ze kterého si v případě

6.4

Příkaz cyklu

62

potřeby již mohu načítat příslušné tokeny. Načtením tokenů do zásobníku je změněn příznak načítání a čtení není prováděno ze vstupní pásky, ale z dynamicky vytvořené struktury zásobníku. Čtecí hlava je mezitím nachystána na znaku za posledním tokenem vloženým do zásobníku (pravou složenou závorkou). Systém nalezení správné koncové závorky jsem již popsal výše. Struktura cyklu je konstruována tak, aby poslední prvek ve struktuře ukazoval zpět na první prvek struktury. Vzniká tak smyčka, kdy při dopředném čtení zásobníku není určen konec struktury pointerem na hodnotu NULL. Při založení prvního prvku struktury je spolu s ním založen pomocný ukazatel označující začátek cyklu a pomocný ukazatel směřující na aktuálně načítaný prvek (token). Ukazatel na začátek plní orientační funkci ve struktuře, aby bylo možné určit počáteční token. Sémantické akce v pravidle příkazu cyklu mají následující podobu: over_cti(14,"dokavad"); over_cti(2,"("); trubkuj(); aktivni_trubka++; lex(); vyraz(); vymet(); over_cti(2,")"); podminka_cyklu = atoi(vysledek->hodnota); vem_zas(&vysledek); while (podminka_cyklu == 1){ over_cti(11,"delej"); blok(); vyraz(); vymet(); over_cti(2,")"); podminka_cyklu = atoi(vysledek->hodnota); vem_zas(&vysledek); }; aktivni_trubka--; zrus_trubku(&cykly); lex(); Syntaktický analyzátor načtením tokenu dokavad rozvíjí derivační strom do pravidla P RIKAZ → dokavad (V Y RAZ) delej BLOK a načte levou kulatou závorku. Levá kulatá závorka je ověřena a načítá se další token. Zároveň se spouští proces načítání tokenů do dynamické struktury zásobníku cyklů. Následuje sémantická akce trubkuj, která provádí operaci načítání tokenů ze vstupní pásky do zásobníku cyklů až do příslušného symbolu ukončení bloku příkazu cyklu. Systém určení správného konce bloku jsem popsal v předchozí kapitole. Po založení a naplnění dynamické struktury se vydá pokyn pro zvýšení hodnoty proměnné aktivní trubka. Je-li tato proměnná vyšší, nebo rovna 1, aktivuje čtení aktuálního tokenu z dynamické struktury. Zjišťování faktu, zda je proměnná „vyššíÿ nebo rovna jedné je nutné z důvodu výskytu dalšího cyklu v příkazovém bloku cyklu. Pokud by se v bloku příkazů cyklu vyskytl další cyklus, zvedla by se opět hodnota proměnné aktivní trubka a v případě, že by se vyhodnocovala pouze rovnost proměnné s číslem 1, tak by se začaly aktivní tokeny načítat opět ze vstupního souboru, což je v těle cyklu nepřípustné. Aktivováním pomocné proměnné se začne načítat sekvence tokenů výrazu z dynamické struktury. Výsledek výrazu převedu na hodnotu integer do proměnné podmínka cyklu a odstraním výslednou hodnotu výrazu ze zásobníku výsledek. Simulace cyklu se nejlépe provádí opět cyklem. Je-li tedy vyhodnocena podmínka cyklu kladně, jako hodnota TRUE, začne se provádět tělo cyklu. Po provedení těla cyklu je nutné vyhodnotit opět podmínku. Zde je oproti pravidlu bezkontextové

6.5

Podprogramy

63

gramatiky změna. Jelikož je nutné podmínku opět vyhodnotit, musím vložit sekvenci ověřování a vyhodnocení podmínky cyklu, kdy v případě negativního vyhodnocení je možné pokračovat v načítání tokenů ze vstupní pásky. Opuštění vykonávání těla cyklu znamená deaktivování načítání tokenů z dynamické struktury cyklu, zrušení samotného zásobníku cyklu a načtení prvního tokenu ze vstupní pásky. Načtení tokenu je důležité. Při zakládání cyklu jsou totiž načteny všechny znaky těla cyklu, které končí pravou složenou závorkou. Tato závorka je ze vstupní pásky načtena, čtecí hlava se posouvá na první znak následující za cyklem, ale tento znak nenačte, ale pouze čeká na příkaz pro čtení. Dokončením cyklu je pak nutné tento znak (token) načít, aby mohl pokračovat rozvoj derivace správným směrem. Zásobník cyklů je znázorněn v příloze H.

6.5

Podprogramy

Největším problémem v mé práci asi byla implementace podprogramů. Jelikož pravidlo přepisu identif ikator(S) je použito jak v pravidle P RIKAZ, tak v pravidle F 1, je nutné tato pravidla rozlišovat. V prvním případě je evidentní, že není žádoucí, aby podprogram vracel hodnotu, protože by tato hodnota nemohla naplnit žádnou proměnnou, jedná se tedy o proceduru. Ve druhém případě naopak podprogram vrátit hodnotu musí, což plyne z principu rozvoje výrazu, a tato hodnota je vložena do některé proměnné10 . Jedná se tedy o funkci vracející hodnotu. Implementace podprogramů je ale i přes popsané rozdíly téměř stejná. Jediný rozdíl je v tom, že sémantické akce funkce jsou obohaceny o založení prvku ve struktuře proměnných, a naplnění této proměnné hodnotou ze zásobníku výsledek, kde se nachází výsledek funkce. Inicializace podprogramů je pro oba typy stejná a provádí se podle pravidla DEF IN ICE → ppr identif ikator (B) BLOKP P R. V obou případech musí být založena dynamická struktura – zásobník podprogramů. Struktura je znázorněna v příloze H. Každý prvek zásobníku je nositelem informace o typu a názvu podprogramu a dále obsahuje ukazatele na parametry podprogramu a na zásobník prvků, kam se ukládají tokeny z těla podprogramu. Při načítání těla podprogramu se situace podobá načítání cyklů. Opět je potřebné nejprve podprogram uložit do dynamické struktury, a až při volání podprogramu aktivovat čtení ze zásobníku podprogramů. Prvky zásobníku, ze kterých se načítají tokeny, však netvoří uzavřenou smyčku, ale poslední prvek zásobníku ukazuje na hodnotu NULL. Struktura parametrů podprogramu je také generována dynamicky, protože podprogram nemívá stabilní počet argumentů. Přístup k jednotlivým argumentům je pomocí dalšího zásobníku aktivních ukazatelů na argumenty prom ppr, zapsaných v podobě proměnných. Dynamická struktura podprogramů je znázorněna v příloze H. Plnění této struktury si vyžaduje konstrukci sémantických akcí, které jsou následovné: 10

Viz kapitola 6.2.

6.5

Podprogramy

64

over_cti(16,"ppr"); zaloz_ppr(&podprogramy, ct); over_typ_cti(8); over_cti(2,"("); b(); over_cti(2,")"); podprogramuj(); Ověřením klíčového slova ppr je načten další token, který představuje název podprogramu. Sémantická akce zaloz ppr vytvoří strukturu podprogramu, a naplní ji názvem. Dalším krokem je načtení parametrů podprogramu, které se provádí podle pravidla B, kdy jsou načítány proměnné, představující argumenty funkce. Tyto proměnné vkládám do zásobníku parametry11 spolu s číslem označujícím pořadí parametru. Ukončené načítání parametrů znamená pokračování v načítaní tokenů. V místě, kdy začíná tělo podprogramu je nutné převádět tokeny do dalšího zásobníku12 , o což se postará akce podprogramuj. Tato akce má ještě jeden úkol. Při načtení klíčového slova return, změní hodnotu typu podprogramu, který je primárně nastaven na typ procedury, na typ funkce. Pozorný čtenář si všiml, že v uvedeném kódu chybí rozvoj derivačního stromu do neterminálního symbolu BLOKP P R. Je to z toho důvodu, že není vhodné při načítání podprogramu postupovat podle pravidel syntaktické analýzy, což by znamenalo současné vykonávání sémantických akcí. V tento okamžik je potřeba pouze načíst tělo podprogramu, ale nevykonávat žádnou akci. Tělo podprogramu se bude syntakticky kontrolovat a sémanticky realizovat až při volání podprogramu v hlavním těle celého programu. Založení dynamických struktur je základem pro práci s podprogramy. Založení však v tomto případě ještě neznamená vykonání podprogramu. Podprogram se aktivuje až tehdy, je-li zavolán z těla hlavního programu s příslušnými parametry. Implementace podprogramů vypadá následovně: if ( (defin_ppr(ct)) && (typ_ppr(ct) == 1) ){ zaloz_prom(&promenne, ct, curtyp, scope); //pouze u funkce vloz_zas(&kolej, "_", curtyp); vloz_nazvy_ppr(&nazvy_ppr, ct); over_typ_cti(8); over_cti(2,"("); zaloz_poradi(&poradi); zaloz_prom_ppr(&prom_ppr,podprogramy, nazvy_ppr->hodnota); s(); vem_prom_ppr(&prom_ppr); vem_indexaci(&poradi); 11 12

Ukazatel na strukturu parametry je součástí struktury podprogramy. Ukazatel na tuto strukturu je také součástí struktury podprogramy.

6.5

Podprogramy

65

scope++; over_cti(2,")"); vloz_zas (&rem_tokeny, ct, curtyp); strcpy(ct,"{"); curtyp = 6; priprav_cteni_ppr(&aktivni_ppr, nazvy_ppr->hodnota); aktivuj_ppr++; blokppr(); scope--; aktivuj_ppr--; vem_zas(&kolej); vloz_zas_hod(&vysledek, nazvy_ppr->hodnota, scope); //pouze u funkce vem_akt_ppr(&aktivni_ppr); vem_zas(&nazvy_ppr); curtyp = rem_tokeny->typ; strcpy(ct,rem_tokeny->hodnota); vem_zas(&rem_tokeny); } else { printf("Chyba na radku %d. ’%s’ bud neexistuje, nebo je to procedura a nelze zde pouzit.\n",count, ct); }; Znázorněný příklad ukazuje použití sémantických akcí při vykonávání funkce. Drobné rozdíly oproti proceduře jsem již popsal, ale ještě budou zmíněny v následujícím textu. Základním kamenem provedení sémantické akce pro oba dva druhy podprogramů je vyhodnocení typu podprogramu. Podmínka vyhodnocuje druh podprogramu a zda je vůbec podprogram založen ve struktuře podprogramy. Následuje akce, která pouze v případě funkce, založí v zásobníku proměnných proměnnou, s názvem podprogramu. Podprogram je zde zatím pouze založen, zatím není naplněn hodnotou. Důležitou sémantickou akcí je vložení zarážky do zásobníku slepá kolej. Tato akce je velice důležitá z hlediska rekurzivních funkcí. Pokud je potřeba například počítat hodnotu faktoriálu n ∗ f akt(n), je nutné rozlišovat výpočet výrazu na všech úrovních zanoření. Zarážka slouží k diferenciaci operátorů pro různé úrovně zanoření, nemůže se tedy stát, že hodnoty výrazu z jedné úrovně, budou zpracovány operátory z úrovně jiné. Následuje sekvence „provozníchÿ sémantických akcí, které jsou důležité z hlediska udržení konzistence dynamické struktury podprogramů. Pro zachování integrity je potřebné pamatovat si název podprogramu, inicializovat sledování pořadí argumentů a inicializovat aktivní ukazatel směřující na parametry podprogramu. Pravidlo S je důležité pro práci s argumenty. V tomto pravidle se zjišťují hodnoty předávané do podprogramu. Správný počet argumentů vyvolá vytvoření pro-

6.5

Podprogramy

66

měnných, jejichž názvy jsou zatím uloženy ve struktuře parametry, ve struktuře proměnné s aktuální úrovní zanoření(rekurze). Tyto proměnné jsou naplněny hodnotamy uvedenými jako argumenty podprogramu ve vstupním souboru v hlavním těle programu. Práce s parametry podprogramu je po provedení pravidla S již skončena, není tedy potřebné udržovat všechny provozní struktury a některé jsou zrušeny. Velice důležitým aspektem při řešení podprogramů je sledování úrovně zanoření při rekurzi. Už pouhé volání podprogramu a vykonávání jeho instrukcí znamená změnu úrovně zanoření, která se zvyšuje s každým rekurzivním voláním podprogramu jako sama sebe. Sledovat úroveň zanoření (rekurze) má za úkol proměnná scope, jenž je globální proměnná a má platnost pro celý syntaktický analyzátor a všechny sémantické akce v něm použity. Dalším velice důležitým krokem je inicializace ukazatele na aktivní prvek. Sémantická akce zakládá prvek do zásobníku ukazatelů na strukturu načtených tokenů a nastaví směr aktivního ukazatele na začátek struktury. Odtud se načítají tokeny ke zpracování a ukazatel se posunuje ve struktuře směrem ke konci struktury. Každé další zanoření (rekurze), znamená vytvoření nového aktivního ukazatele a jeho nasměrování na začátek struktury tokenů. Nyní přichází příprava na avizovanou změnu pravidel kdy je na konec pravidla identif ikator (S) přidáno pravidlo pro vykonání těla podprogramu BLOKP P R. Aby bylo možné tělo podprogramu vykonat, je opět nutné zavést několik provozních operací pro udržení integrity struktur. Nejprve je zapamatován poslední aktuální token, poté se aktivuje načítání ze struktury a do aktuálního tokenu se vloží levá složená závorka, se kterou se pokračuje v rozvoji derivačního stromu do pravidla BLOKP P R. Ukončení vykonávání těla podprogramu znamená to, že na zásobníku výsledek je uložena hodnota provedené funkce, kterou je potřeba přenést do odpovídající proměnné v zásobníku proměnné. Tato akce se provede pouze v případě, že se jedná o funkci. V případě procedury je tato akce vynechána. Ukončení těla podprogramu dále znamená snížení hodnoty zanoření a operaci zjišťování, zda se má pokračovat v načítání ze vstupní pásky, nebo v případě rekurze, hodnotou danou původním aktivním ukazatelem. Zapamatovaný token v zásobníku rem tokeny je předán do aktuálního tokenu a tím je zajištěn správný směr dalšího derivačního rozvoje.

7

67

DOKUMENTACE

7

Dokumentace

Vysvětlení implementace sémantických akcí přináší otázku, jakým způsobem je možné samotné příkazy realizovat. Následující text slouží jako stručná dokumentace k jednotlivým příkazům a jsou zde také uvedeny vzorové příklady jejich použití.

7.1

Základní struktura

Základní struktura programovacího jazyka Ruzin je stejná jako u většiny programovacích jazyků. V programu se může vyskytovat deklarační část, ve které jsou definovány podprogramy, za kterou je povinná část – samotné hlavní tělo programu. Deklarační část začíná klíčovým slovem ppr a je ukončena pravou složenou závorkou. Tato část se nemusí vyskytovat vůbec, nebo v jakémkoliv počtu. Hlavní blok programu se ve zdrojovém kódu vyskytovat musí. Blok je značen složenými závorkami, ve kterých se vyskytují další příkazy oddělené středníkem. Příkazový blok nemusí obsahovat žádný příkaz, může být prázdný. Příklad struktury: ppr podprogram(){ } ppr podprogram(){ } {}

7.2

Výrazy

Výrazy jsou standardní součástí každého programovacího jazyka. Jazyk Ruzin zpracovává výrazy stejně, jako většina ostatních programovacích jazyků. Veškeré výrazy jsou zapisovány infixovou notací. Jsou podporovány algebraické operace sčítání(+), odečítání(−), násobení(∗) a dělení(/). Dále je možné používat výrazy relační pro porovnání dvou hodnot (<, >, <=, >=, <>, ==) a logické výrazy obsahující logickou spojku and (&&), logickou spojku or (||) a negaci (!). Příklady užití výrazu jsou následovné: 7 + $a * $b-> * ($c[1][$d] + 2) ($a * $b[$c->]) <= 8 !(($a < 4) && ($b > 8))

7.3

aritmetický výraz relační výraz logický výraz

Přiřazení

Příkaz přiřazení je vyjádřen operátorem „=ÿ a vkládá do existující proměnné hodnotu výrazu na pravé straně přiřazení. V případě, že proměnná, do které je hodnota výrazu přiřazována, neexistuje, je tato proměnná vytvořena. Přiřazením lze definovat pole nebo pointer. Do proměnné typu pole nelze vkládat hodnotu přímo, ale

7.4

Větvení

68

pouze prostřednictvím závorkové notace. Přiřazení do proměnné typu ukazatel uloží do proměnné hodnotu, která představuje adresu, na které může být uložena samotná hodnota. Hodnotu do pointeru lze vložit pomocí operátoru − >, který se uvede za proměnnou. Příklady použití příkazu přiřazení: $a = 2 $b = $a * (3 + 2) $c = pole [ pole["ahoj", 2] pole["Karle" , 2 , 8], 4 + 2, $b] $c[2][$a] = $b $d = *poi[] $d-> = "ahoj" $e = $d $f = $e->

7.4

Větvení

Příkaz větvení je označen klíčovým slovem pokavad, za kterým je vyhodnocen výraz, který může být aritmetický, relační, logický nebo jejich kombinace. Na základě vyhodnocení výrazu se buď vykonává příkazový blok za klíčovým slovem tak, nebo je zde možnost pokračování příkazového bloku za klíčovým slovem inac. Větev za klíčovým slovem nemusí být v příkazu uvedena. V případě, že alternativní větev příkazu za klíčovým slovem inac uvedená je, nevkládá se za ukončovací znak příkazového bloku větve tak oddělovací symbol ;. Znak odělovače se používá pro oznámení ukončení příkazu a v případě vložení tohoto znaku mezi větve by došlo k chybné syntaktické interpretaci a program by byl při překladu ukončen chybou. Příklady použití příkazu větvení: pokavad ( $a > $b) tak { $c = $c + 1 }; Příkaz větvení obsahující oba bloky příkazů, z nichž se provede právě jeden, na základě vahodnocení výrazu v podmínce: pokavad ( $a > $b) tak { $c = $c + 1 } inac { $c = $c - 1 };

7.5

Cykly

Příkaz cyklu je konstruován jako obecný příkaz while používaný ve většině programovacích jazyků. Klíčovým slovem je slovo dokavad, za kterým je opět vyhodnocován výraz, stejně jako v příkazu větvení. Následuje klíčové slovo delej, za kterým je příkazový blok programu. Dokud není splněna podmínka cyklu, opakovaně se provádí

7.6

Podprogramy

69

příkazy uvedené v těle cyklu. Příklady použití příkazu cyklu: $a = 1; dokavad ( $a < 5) delej { $a = $a + 1 };

7.6

Podprogramy

Podprogramy je nutné rozdělovat do tří skupin. Procedury, funkce a implementované podprogramy. Procedury jsou podprogramy nevracející žádnou hodnotu. V těle procedury se nevyskytuje klíčové slovo return a jsou určeny pouze k vykonávání určitých operací. Příklad definice procedury a její volání: ppr linka($pocet, $znak){ dokavad ($pocet > 0) delej { $pocet = $pocet - 1; pis($znak); } pis(br) } { linka(50, "*") } Dalším typem podprogramů jsou funkce. Funkce nemůže být volána samostatně jako příkaz, stejně jako procedura. Musí se vyskytovat vždy jako součást výrazu. To znamená, že může být užita jako parametr jiné funkce, nebo sama sebe, čímž vzniká rekurzivní volání funkce. Rozpoznání funkce je prováděno na základě toho, zda tělo podprogramu obsahuje klíčové slovo return. Příklad definice funkce a její volání: ppr secti($a, $b){ $c = $a + $b; return $c } { $d = secti(4, 5) } Interpret Ruzin, má implementované dvě základní procedury pro komunikaci s okolním světem. Jde o procedury in a out, které umožňují uživateli zadávat hodnoty do proměnných pomocí klávesnice a vypisovat požadované hodnoty na obrazovku. Jsou to procedury pis() pro vypisování na obrazovku a cti() pro načítání hodnot. Procedura pis() může obsahovat speciální atributy br a tab které postupně znamenají přesun na začátek nového řádku a vložení prodloužené mezery. Procedura cti() je schopna načítat jak do jedné proměnné, tak řetězově do většího

7.6

Podprogramy

70

počtu proměnných, které jsou uvedeny v závorce a odděleny čárkou. Příklad použití implementovaných procedur: cti($a, $b); pis("Proměnná $a: ", $a, tab, "Proměnná $b: ", $b, br)

8

8

ZÁVĚR

71

Závěr

Cílem diplomové práce je popsat průběh výstavby interpreta programovacího jazyka Ruzin. Konstrukce interpreta je v počátku spojena v teoretickým návrhem lexikálního analyzátoru, který je schopen identifikovat jednotlivá slova na vstupní pásce. Lexikální analýza vyžaduje definici abecedy znaků akceptovatelných interpretem, ze kterých jsou složena slova dané věty. Nad abecedou je dále možné navrhnout regulární gramatiku jazyka. Navržená regulární gramatika dává předpoklad pro konstrukci konečného deterministického automatu, jenž podle načítaných vstupních znaků dokáže rozpoznat slova ve vstupním souboru, a také dokáže rozhodnout o tom, zda dané slovo může či nemůže jazyk akceptovat. Slovo získané ze vstupní věty je základem pro syntaktickou analýzu. Díky rozpoznanému slovu je možné rozvíjet derivační strom daným směrem až do poslední větve. Syntaktická správnost je důležitá k tomu, aby bylo možné správně sestavit program. Je to podobné jako v běžném životě. Existuje tisíce slov, ale teprve když se slova správně poskládají za sebe, dostávají význam a lidé dokážou rozpoznat smysl celé věty. Syntaktická analýza věty určuje, jakým směrem se bude rozvíjet derivační sestup. Průchod určitou linií ve stromu postupně spouští připravené sémantické akce. Sémantické akce vykonávají předepsané operace v průběhu syntaktické analýzy a představují část interpreta, která vykonává předepsané instrukce dané vstupní větou. V případě že jsou slova ve větě nesprávně sestavena, nebo slovo vůbec neexistuje, ztrácí věta schopnost předat svou informaci a dochází ke kolizi. V programovacím jazyku Ruzin tato situace vyvolá chybový stav. Obsah chyby vypsaný na obrazovce oznamuje příčinu a číslo řádku, na kterém se chyba vyskytuje. Činnost programu případná chyba ukončí. Správný průchod derivačním stromem a provedení všech potřebných akcí znamená interpretování instrukcí daných vstupním souborem. Záměrně jsem použil slovo interpretování, protože nejde o doslovný překlad jazyka do řeči počítačů, do jedniček a nul strojového kódu. Jazyk Ruzin je programován v jazyce C. Díky tomuto programovacímu jazyku je možné načítat slova vstupní věty, provádět lexikální a syntaktickou analýzu. Sémantické akce jsou na základě instrukcí vykonávány pomocí příkazů jazyka C. Znamená to tedy, že instrukce vstupního souboru jsou interpretovány jazykem C, který tyto instrukce teprve dokáže převést do strojového kódu. Převedení vstupního souboru v programovým kódem napsaným v jazyce Ruzin do proveditelné podoby vyžaduje překlad veškerých komponent jazyka, psaných v programovacím jazyku C. Překlad vytvoří soubor, který vyžaduje připojení vstupního souboru se zdrojovým kódem psaným v jazyku Ruzin. Tento soubor pak vykonává postupně veškeré instrukce dané zdrojovým kódem.

8

ZÁVĚR

72

Výsledek celé práce je shrnut do jednoho souboru v názvem ruzin, který představuje samotný interpret. Je tedy možné konstatovat, že cíl diplomové práce, vytyčený v úvodní kapitole, byl splněn. Přiložené CD dává možnost ověřit si správou činnost interpreta. Na CD jsou umístěny tři soubory. Interpret ruzin, soubor s ukázkovým zdrojovým kódem program.ruz a soubor s návodem na spuštění read.me. Programovací jazyk Ruzin je spustitelný na platformě operačního systému UNIX. Nyní už zbývá jenom sestavit nějaký program, který má být proveden. Všem uživatelům mého produktu chci na závěr popřát, aby vždy měli Radost z UŽívání INterpreta RUZIN.

9

9

LITERATURA

73

Literatura

Rybička, J. Úvod do teorie programovacích jazyků. Brno: Konvoj, 1999. 39 s. ISBN 80-85615-25-8. Molnár, Ľ. Češka, M. Melichar, B. Gramatiky a jazyky. Bratislava: Alfa, 1987. 188 s. Herout, P. Učebnice jazyka C. České Budějovice: Koop, 2001. 269 s. ISBN 8085828-21-9. Lobaz, P. Formální jazyky & překladače. Plzeň: Katedra informatiky a výpočetní techniky [cit. 5. března 2006]. Dostupné na internetu. http://www.kiv.zcu.cz/~lobaz/fjp/fjp9.html Wikipedie. Vim. Internetový zdroj [cit. 3. března 2006]. Dostupné na internetu. http://cs.wikipedia.org/wiki/Vim Satrapa, P. Vim, skutečný editor textů. Internetový zdroj [cit. 5. března 2006]. Dostupné na internetu. http://www.kai.vslib.cz/~satrapa/docs/vim/ Polách, E. Programování v jazyku Turbo Pascal. České Budějovice: Katedra informatiky [cit. 22. února 2006]. Dostupné na internetu. http://home.pf.jcu.cz/~edpo/program/kap01.html

Přílohy

p č + − ∗ / {qE , qFb } {qA , qL , qFb } {qA , qFb } {qA , qR , qFb } {qT , qFb } {qK , qFb } {qA , qL , qFb } {qB , qFb } {qC } {qC } {qC } {qC } {qC } {qC } {qC } {qC } {qC } {qC } {qC } {qC } {qE , qFb } {qE , qFb } {qF } {qF } {qF } {qF } {qF } {qF } {qG } {qG } {qG } {qG } {qG } {qG } {qG } {qG } {qG } {qG } {qG } {qS } {qI , qFb } {qI , qFb } {qE , qFb } {qA , qL , qFb } {qA , qFb } {qA , qR , qFb } {qT , qFb } {qFb } {qF } {qG } {qG }

{qF } {qF } {qF } {qG } {qG } {qG } {qG } {qG } {qG }

{qF } {qG } {qG }

{qC } {qC }

{qFb }

{qFb } {qFb }

{qM } {qN } {qFb } {qP , qR , qFb } {qP , qFb }

{qC } {qC }

{qC } {qC } {qC } {qC } {qC } {qC }

& | ! < > {qM } {qN } {qFb } {qP , qR , qFb } {qP , qFb }

A

δ qS qA qB qC qD qE qF qG qH qI qJ qK qL qM qN qP qR qT qU qV qFb

A PŘECHODOVÁ FUNKCE

75

Přechodová funkce

Tab. 1: Přechodová funkce — část 1.

δ = ↔ qS {qP , qFb } qA qB qC {qC } qD {qC } qE qF {qF } qG {qG } qH {qG } qI qJ {qP , qFb } qK qL qM qN qP {qFb } qR qT qU qV qFb

.

, # {qFb } {qF }

\

” { } ←- 7→ t {qC } {qFb } {qFb } {qS } {qS } {qS } p

o

i

$ [ ] 4 ε {qI } {qFb } {qFb } {qFb }

{qFb } {qFb } {qFb } {qB }

{qFb } {qG }

{qC } {qFb } {qFb }

{qU } {qV } {qFb }

{qI } {qFb } {qFb }

{qF } {qF } {qF } {qF } {qF } {qF } {qF } {qF } {qF } {qF } {qS } {qF } {qF } {qF } {qF } {qF } {qF } {qF } {qF } {qF } {qG } {qG } {qG } {qG } {qG } {qH } {qG } {qG } {qG } {qG } {qG } {qG } {qG } {qG } {qG } {qG } {qG } {qG } {qG } {qG } {qG } {qG } {qG } {qG } {qG } {qH } {qG } {qG } {qG } {qG } {qG } {qG } {qG } {qG } {qG } {qG } {qG } {qG } {qG } {qG }

{qC } {qC } {qC } {qC } {qC } {qC } {qD } {qFb } {qC } {qC } {qC } {qC } {qC } {qC } {qC } {qC } {qC } {qC } {qC } {qC } {qC } {qC } {qC } {qC } {qC } {qC } {qC } {qC } {qC } {qC } {qC } {qC } {qC } {qC } {qC } {qC } {qC } {qC } {qC } {qC }

( ) ; {qFb } {qFb } {qFb }

A PŘECHODOVÁ FUNKCE

76

Tab. 2: Přechodová funkce — část 2.

qB Fb qI Fb qI Fb

qE Fb qE Fb qALFb qALFb qALFb

qFb

p č + − ∗ / & qE Fb qALFb qAFb qARFb qT Fb qK Fb qM qALFb qB Fb qC qC qC qC qC qC qC qC qC qC qC qC qC qC qE Fb qE Fb qF qF qF qF qF qF qF qG qG qG qG qG qG qG qG qG qG qG qG qS qG qI Fb qI Fb qE Fb qALFb qAFb qARFb qT Fb qFb qM

qFb

qFb qFb qFb

qFb

qFb

qFb

qB

qB

qFb

qG

qG

qC qFb qFb

qU

qU qV qFb

qI qFb qFb

qF qF qF qF qF qF qF qF qF qF qF qF qS qF qF qF qF qF qF qF qF qF qG qG qG qG qG qG qG qH qG qG qG qG qG qG qG qG qG qG qG qG qG qG qG qG qG qG qG qG qG qH qG qG qG qG qG qG qG qG qG qG qG qG qG qG

qF qF qF qG qG qG qG qG qG qN qFb qP RFb qP Fb qP Fb qFb qFb qFb

qC qC qC qC qC qC qC qC qD qFb qC qC qC qC qC qC qC qC qC qC qC qC qC qC qC qC qC qC qC qC qC qC qC qC qC qC qC qC qC qC qC qC qC qC

qC qC qC qC qC qC

| ! < > = ( ) ; . , # \ ” ←- 7→ t p o i $ [ ] 4 ε qN qFb qP RFb qP Fb qP Fb qFb qFb qFb qFb qF qC qFb qFb qS qS qS qI qFb qFb qFb

B

δ ↔ qS qA qB qC qD qE qF qG qH qI qJ qK qL qM qN qP qR qT qU qV qFb qE Fb qALFb qAFb qARFb qT Fb qK Fb qP RFb qP Fb qB Fb qI Fb

B DETERMINISTICKÝ KONEČNÝ AUTOMAT

77

Deterministický konečný automat

Tab. 3: Deterministický konečný automat.

δ ↔ qS qB qC qD qF qG qH qI qM qN qU qV qFb qE Fb qALFb qAFb qARFb qT Fb qK Fb qP RFb qP Fb qB Fb qI Fb

qB Fb qI Fb qI Fb

qE Fb qE Fb qALFb qALFb qALFb

p č qE Fb qALFb qB Fb qC qC qC qC qF qF qG qG qG qG qI Fb qI Fb qC qC qF qG qS qFb

qC qC qF qG qG

qFb

qC qC qF qG qG

qC qC qF qG qG

qC qC qF qG qG

qFb

qFb

qC qC qF qG qG

qFb qFb

qC qC qF qG qG

qC qC qF qG qG

qC qC qF qG qG

qC qC qF qG qG

qB

qC qC qF qG qG

qC qC qF qG qG

qG

qC qC qF qH qH

qD qC qF qG qG

qFb qC qF qG qG

qC qC qF qG qG

qC qC qF qG qG

qC qC qS qG qG

qC qC qF qG qG

qC qC qF qG qG

qU

qC qC qF qG qG

qV

qC qC qF qG qG

qC qC qF qG qG

qC qC qF qG qG

qC qC qF qG qG

o

+ − ∗ / & | ! < > = ( ) ; . , # \ ” ←- 7→ t p qAFb qARFb qT Fb qK Fb qM qN qFb qP RFb qP Fb qP Fb qFb qFb qFb qFb qF qC qFb qFb qS qS qS

qFb

qC qC qF qG qG

i

qC qC qF qG qG

qC qC qF qG qG

qC qC qF qG qG

qC qC qF qG qG

$ [ ] 4 ε qI qFb qFb qFb

B DETERMINISTICKÝ KONEČNÝ AUTOMAT

78

Tab. 4: Deterministický konečný automat bez nadbytečných stavů.

C

79

SYNTAKTICKÉ DIAGRAMY

C

Syntaktické diagramy

program deklarace deklarace

blok

definice

definice

ppr

identifikator

(

blokppr

) blokppr

promenna ,

prikazppr { ;

}

prikazppr

blok

prikaz

return vyraz

prikaz } { ;

C

80


prikaz prirazeni

cyklus

vetveni

volanifunkce

prirazeni

promenna

NULL =

vyraz

definice-ukazatel

definice-pole

vyraz = NULL = vyraz

rozšíření-ukazatel

rozšíření-pole

definice-ukazatel

*poi

[

]

hodnoty

hodnoty

,

identifikator *poi [ identifikator ]

C

81


definice-pole

pole

]

vyraz [ definice-pole

cyklus

dokavad ( vyraz vetveni

pokavad

(

vyraz

,

)

delej

blok

)

tak

blok

inac blok

volanifunkce

identifikator

)

( vyraz

vyraz vyraz

T ! F

,

and T or

C

82


F AV

AV == <> < > <= >=

AV AV

T1 +

T1 T1

* F1 /

F1 ( vyraz ) konstanta retezec prom

volanifunkce

C

83


prom

promenna

rozšíření-pole

rozšíření-ukazatel

rozšíření-pole konstanta ] [ promenna

rozšíření-ukazatel identifikator ->

D

D

BEZKONTEXTOVÁ DETERMINISTICKÁ GRAMATIKA LL(1)

Bezkontextová deterministická gramatika LL(1)

P ROGRAM → DEKLARACE BLOK DEKLARACE → DEF IN ICE A | ε A → DEF IN ICE A | ε DEF IN ICE → ppr identif ikator ( B ) BLOKP P R B → promenna C | ε C → , promenna C | ε BLOKP P R → { P RIKAZP P R G } G → ; P RIKAZP P R G | ε P RIKAZP P R → return V Y RAZ | P RIKAZ BLOK → { P RIKAZ H } H → ; P RIKAZ H | ε P RIKAZ → promenna J | dokavad ( V Y RAZ ) delej BLOK | pokavad ( V Y RAZ ) tak BLOK R | identif ikator ( S ) | ε J → = K | − > W = L | [ U ] E = V Y RAZ U → konstanta | promenna K → V Y RAZ | pole [ P Q ] | ∗ poi [ M ] | null P → V Y RAZ | pole [ P Q ] Q→, P Q|ε M → HODN OT Y N | ε N → , HODN OT Y N | ε HODN OT Y → identif iktor | ∗ poi [ identif iktor ] L → V Y RAZ | null E→[U ]E |ε R → inac BLOK | ε S → V Y RAZ V | ε V → , V Y RAZ V | ε V Y RAZ → T RV RV → and T RV | or T RV | ε T →!F |F F → AV X X →== AV | <> AV | < AV | > AV | <= AV | >= AV | ε AV → T 1 AV 1 AV 1 → + T 1 AV 1| − T 1 AV 1 | ε T 1 → F 1 T 11 T 11 → ∗ F 1 T 11| / F 1 T 11 | ε F 1 → ( V Y RAZ ) | konstanta | retezec | promenna D | identif ikator ( S ) D→[U ]E |−> W |ε W → identif ikator | ε

84

E

E

OVĚŘENí GRAMATIKY TYPU LL(1)

85

Ověření gramatiky typu LL(1)

PROGRAM: F F1 (P ROGRAM → DEKLARACE BLOK) = F I1 (DEKLARACE → DEF IN ICE A) ∪ F I1 (DEKLARACE → ε) = F I1 (DEF IN ICE → ppr identif iktor ( B ) BLOKP P R) ∪ F O1 (DEKLARACE) = {ppr} ∪ F I1 (BLOK → { P RIKAZ H }) = {ppr} ∪ {{} = {ppr, {} DEKLARACE: F F1 (DEKLARACE → DEF IN ICE A) = F I1 (DEF IN ICE → ppr identif ikator ( B ) BLOKP P R) = {ppr} F F1 (DEKLARACE → ε) = F O1 (DEKLARACE) = F I1 (BLOK → { P RIKAZ H }) = {{} {ppr} ∩ {{} = 0 . . . OK A: F F1 (A → DEF IN ICE A) = F I1 (DEF IN ICE → ppr identif ikator ( B ) BLOKP P R) = {ppr} F F1 (A → ε) = F O1 (A) = F O1 (DEKLARACE) = {{} {ppr} ∩ {{} = 0 . . . OK DEFINICE: F F1 (DEF IN ICE → ppr identif ikator ( B ) BLOKP P R) = {ppr} B: F F1 (B → promenna C) = {promenna} F F1 (B → ε) = F O1 (B) = {)} {promenna} ∩ {)} = 0 . . . OK C: F F1 (C → , promenna C) = {, } F F1 (C → ε) = F O1 (C) = F O1 (B) = {)} {, } ∩ {)} = 0 . . . OK BLOKPPR: F F1 (BLOKP P R → { P RIKAZP P R G }) = {{} G: F F1 (G → ; P RIKAZP P R G) = {; } F F1 (G → ε) = F O1 (G) = {}} {; } ∩ {}} = 0 . . . OK

E


86

PRIKAZPPR: F F1 (P RIKAZP P R → return V Y RAZ) = {return} F F1 (P RIKAZP P R → P RIKAZ) = F I1 (P RIKAZ → promenna J) ∪ F I1 (P RIKAZ → dokavad ( V Y RAZ ) delej BLOK) ∪ F I1 (P RIKAZ → pokavad ( V Y RAZ ) tak BLOK) ∪ F I1 (P RIKAZ → identif ikator ( S )) ∪ F I1 (P RIKAZ → ε) = {promenna} ∪ {dokavad} ∪ {pokavad} ∪ {identif ikator} ∪ F O1 (P RIKAZ) = {promenna, dokavad, pokavad, identif ikator} ∪ F O1 (P RIKAZP P R) ∪ F I1 (H → ; P RIKAZ H)∪F I1 (H → ε) = {promenna, dokavad, pokavad, identif ikator}∪ F I1 (G → ; P RIKAZP P R G) ∪ F I1 (G → ε) ∪ {; } ∪ F O1 (H) = {promenna, dokavad, pokavad, identif ikator, ; } ∪ {; } ∪ F O1 (G) ∪ {}} = {promenna, dokavad, pokavad, identif ikator, ; , }} {promenna, dokavad, pokavad, identif ikator, }, ; } ∩ {return} = 0 . . . OK BLOK: F F1 (BLOK → { P RIKAZ H }) = {{} H: F F1 (H → ; P RIKAZ H) = {; } F F1 (H → ε) = F O1 (H) = {}} {; } ∩ {}} = 0 . . . OK PRIKAZ: F F1 (P RIKAZ → promenna J) = {promenna} F F1 (P RIKAZ → dokavad ( V Y RAZ ) delej BLOK) = {dokavad} F F1 (P RIKAZ → pokavad ( V Y RAZ ) tak BLOK R) = {pokavad} F F1 (P RIKAZ → identif ikator ( S )) = {identif ikator} F F1 (P RIKAZ → ε) = F O1 (P RIKAZ) = F O1 (P RIKAZP P R) ∪ F I1 (H → ; P RIKAZ H) ∪ F I1 (H → ε) = F I1 (G → ; P RIKAZP P R G)∪F I1 (G → ε)∪{; }∪F O1 (H) = {; }∪F O1 (G)∪{}} = {; , }} {promenna} ∩ {dokavad} ∩ {pokavad} ∩ {identif ikator} ∩ {; , }} = 0 . . . OK J: F F1 (J → = K) = {=} F F1 (J → − > W = L) = {− >} F F1 (J → [ U ] E = V Y RAZ) = {[} {=} ∩ {− >} ∩ {[} = 0 . . . OK U: F F1 (U → konstanta) = {konstanta} F F1 (U → promenna) = {promenna} {konstanta} ∩ {promenna} = 0 . . . OK

E


K: F F1 (K → pole [ P Q ]) = {pole} F F1 (K → ∗ poi [ M ]) = {∗poi} F F1 (K → null) = {null} F F1 (K → V Y RAZ) = F I1 (V Y RAZ → T RV ) = F I1 (T → ! F ) ∪ F I1 (T → F ) = {!} ∪ F I1 (F → AV X) = {!} ∪ F I1 (AV → T 1 AV 1) = {!} ∪ F I1 (T 1 → F 1 T 11) = {!} ∪ F I1 (F 1 → ( V Y RAZ )) ∪ F I1 (F 1 → konstanta) ∪ F I1 (F 1 → retezec) ∪ F I1 (F 1 → promenna D) ∪ F I1 (F 1 → identif ikator ( S )) = {!, (, konstanta, retezec, promenna, identif ikator} {!, (, konstanta, retezec, promenna, identif ikator} ∩ {pole} ∩ {∗poi} ∩ {null} = 0 . . . OK P: F F1 (P → V Y RAZ) = F I1 (V Y RAZ → T RV ) = {!, (, konstanta, retezec, promenna, identif ikator} F F1 (P → pole [ P Q ]) = {pole} {!, (, konstanta, retezec, promenna, identif ikator} ∩ {pole} = 0 . . . OK Q: F F1 (Q → , P Q) = { , } F F1 (Q → ε) = F O1 (Q) = {]} {, } ∩ {]} = 0 . . . OK M: F F1 (M → HODN OT Y N ) = F I1 (HODN OT Y → identif ikator) ∪ F I1 (HODN OT Y → ∗ poi [ identif ikator ]) = {identif ikator, ∗poi} F F1 (M → ε) = F O1 (M ) = {]} {identif ikator, ∗poi} ∩ {]} = 0 . . . OK N: F F1 (N → , HODN OT Y N ) = { , } F F1 (N → ε) = F O1 (N ) = F O1 (M ) = {]} {, } ∩ {]} = 0 . . . OK HODNOTY: F F1 (HODN OT Y → identif ikator) = {identif ikator} F F1 (HODN OT Y → ∗ poi [ identif ikator ]) = {∗poi} {identif ikator} ∩ {∗poi} = 0 . . . OK L: F F1 (L → null) = {null} F F1 (L → V Y RAZ) = F I1 (V Y RAZ → T RV ) = {!, (, konstanta, retezec, promenna, identif ikator} {!, (, konstanta, retezec, promenna, identif ikator} ∩ {null} = 0 . . . OK

87

E


88

E: F F1 (E → [ konstanta ] E) = {[} F F1 (E → ε) = F O1 (E) = {=} ∪ F O1 (D) = {=} ∪ F O1 (F 1) = {=} ∪ F I1 (T 11 → ∗ F 1 T 11) ∪ F I1 (T 11 → / F 1 T 11) ∪ F I1 (T 11 → ε) = {=, ∗, /} ∪ F O1 (T 11) = {=, ∗, /} ∪ F O1 (T 1) = {=, ∗, /} ∪ F I1 (AV 1 → + T 1 AV 1) ∪ F I1 (AV 1 → − T 1 AV 1) ∪ F I1 (AV 1 → ε) = {=, ∗, /, +, −} ∪ F O1 (AV 1) = {=, ∗, /, +, −} ∪ F O1 (AV ) = {=, ∗, /, +, −} ∪ F I1 (X → == AV ) ∪ F I1 (X → <> AV ) ∪ F I1 (X → < AV ) ∪ F I1 (X → > AV ) ∪ F I1 (X → <= AV ) ∪ F I1 (X → >= AV ) ∪ F I1 (X → ε) ∪ F O1 (X) = {=, ∗, /, +, −, ==, <>, <, >, <=, >=} ∪ F O1 (F ) = {=, ∗, /, +, −, ==, <>, <, >, <=, >=} ∪ F O1 (T ) = {=, ∗, /, +, −, ==, <>, <, >, <=, >=} ∪ F I1 (RV → and T RV ) ∪ F I1 (RV → or T RV ) ∪ F I1 (RV → ε) = {=, ∗, /, +, −, ==, <>, <, >, <=, >=, and, or, } ∪ F O1 (RV ) = {=, ∗, /, +, −, ==, <>, <, >, <=, >=, and, or, } ∪ F O1 (V Y RAZ) = {=, ∗, /, +, −, ==, <>, <, >, <=, >=, and, or, } ∪ F O1 (P RIKAZP P R) ∪ {)} ∪ F O1 (J) ∪ F O1 (K) ∪ F O1 (L) ∪ F O1 (P ) ∪ F I1 (V → , V Y RAZ V ) ∪ F I1 (V → ε) = {=, ∗, /, +, −, ==, <>, <, >, <=, >=, and, or, ; , }, ), , } ∪ F O1 (P RIKAZ) ∪ F I1 (Q → , P Q) ∪ F I1 (Q → ε) ∪ F O1 (S) = {=, ∗, /, +, −, ==, <>, <, >, <=, >=, and, or, ; , }, ), ,, ]} {=, ∗, /, +, −, ==, <>, <, >, <=, >=, and, or, ; , }, ), ,, ]} ∩ {[} = 0 . . . OK R: F F1 (R → inac BLOK) = {inac} F F1 (R → ε) = F O1 (R) = F O1 (P RIKAZ) = {; , }} {inac} ∩ {; , }} = 0 . . . OK S: F F1 (S → V Y RAZ V ) = F I1 (V Y RAZ → T RV ) = {!, (, konstanta, retezec, promenna, identif ikator} F F1 (S → ε) = F O1 (S) = {)} {!, (, konstanta, retezec, promenna, identif ikator} ∩ {)} = 0 . . . OK V: F F1 (V → , V Y RAZ V ) = {, } F F1 (V → ε) = F O1 (V ) = F O1 (S) = {)} {, } ∩ {)} = 0 . . . OK VYRAZ: F F1 (V Y RAZ → T RV ) = {!, (, konstanta, retezec, promenna, identif ikator} RV: F F1 (RV → and T RV ) = {and} F F1 (RV → or T RV ) = {or} F F1 (RV → ε) = F O1 (RV ) = F O1 (V Y RAZ) = F O1 (P RIKAZP P R)∪{)}∪F O1 (J)∪F O1 (K)∪ F O1 (L)∪F O1 (P )∪F I1 (V → , V Y RAZ V )∪F I1 (V → ε)∪ = {; , }, )}∪F O1 (P RIKAZ)∪ F F1 (Q → , P Q) ∪ F F1 (Q → ε) ∪ {, } ∪ F O1 (V ) = {; , }, ), , } ∪ F O1 (Q) = {; , }, ), ,, ]} {; , }, ), ,, ]} ∩ {and} ∩ {or} = 0 . . . OK

E


89

T: F F1 (T →! F ) = {!} F F1 (T → F ) = F I1 (F → AV X) = F I1 (AV → T 1 AV 1) = F I1 (T 1 → F 1 T 11) = F I1 (F 1 → ( V Y RAZ )) ∪ F I1 (F 1 → konstanta) ∪ F I1 (F 1 → retezec) ∪ F I1 (F 1 → promenna D) ∪ F I1 (F 1 → identif ikator ( S )) = {(, konstanta, retezec, promenna, identif ikator} {!} ∩ {(, konstanta, retezec, promenna, identif ikator} = 0 . . . OK F: F F1 (F → AV X) = F I1 (AV → T 1 AV 1) = {(, konstanta, retezec, promenna, identif ikator}

X: F F1 (X F F1 (X F F1 (X F F1 (X F F1 (X F F1 (X F F1 (X

→== AV ) = {==} →<> AV ) = {<>} →< AV ) = {<} →> AV ) = {>} →<= AV ) = {<=} →>= AV ) = {>=} → ε) = F O1 (X) = {and, or, ; , }, ), ,, ]}

{==} ∩ {<>} ∩ {<} ∩ {>} ∩ {<=} ∩ {>=} ∩ {and, or, ; , }, ), ,, ]} = 0 . . . OK AV: F F1 (AV → T 1 AV 1) = F I1 (T 1 → F 1 T 11) = {(, konstanta, retezec, promenna, identif ikator} AV1: F F1 (AV 1 → + T 1 AV 1) = {+} F F1 (AV 1 → − T 1 AV 1) = {−} F F1 (AV 1 → ε) = F O1 (AV 1) = F O1 (AV ) = {==, <>, <, >, <=, >=, and, or, ; , }, ), ,, ]} {==, <>, <, >, <=, >=, and, or, ; , }, ), ,, ]} ∩ {+} ∩ {−} = 0 . . . OK T1: F F1 (T 1 → F 1 T 11) = {(, konstanta, retezec, promenna, identif ikator} T11: F F1 (T 11 → ∗ F 1 T 11) = {∗} F F1 (T 11 → /F 1 T 11) = {/} F F1 (T 11 → ε) = F O1 (T 11) = F O1 (T 1) = {+, −, ==, <>, <, >, <=, >=, and, or, ; , }, ), ,, ]} {+, −, ==, <>, <, >, <=, >=, and, or, ; , }, ), ,, ]} ∩ {∗} ∩ {/} = 0 . . . OK F1: F F1 (F 1 F F1 (F 1 F F1 (F 1 F F1 (F 1 F F1 (F 1

→ → → → →

( V Y RAZ )) = {(} konstanta) = {konstanta} retezec) = {retezec} promenna D) = {promenna} identif ikator ( S )) = {identif ikator}

{(} ∩ {konstanta} ∩ {retezec} ∩ {promenna} ∩ {identif ikator} = 0 . . . OK

E


D: F F1 (D → [ U ] E) = {[} F F1 (D → − > W ) = {− >} F F1 (D → ε) = F O1 (D) = {∗, /, +, −, ==, <>, <, >, <=, >=, and, or, ; , }, ), ,, ]} {∗, /, +, −, ==, <>, <, >, <=, >=, and, or, ; , }, ), ,, ]} ∩ {[} ∩ {− >} = 0 . . . OK W: F F1 (W → identif ikator) = {identif ikator} F F1 (W → ε) = F O1 (W ) = {=} ∪ F O1 (D) = {=, ∗, /, +, −, ==, <>, <, >, <=, >=, and, or, ; , }, ), ,, ]} {=, ∗, /, +, −, ==, <>, <, >, <=, >=, and, or, ; , }, ), ,, ]} ∩ {identif ikator} = 0 . . . OK

90

F

VYPOČíTANÉ MNOŽINY FIRST A FOLLOW

F

Vypočítané množiny FIRST a FOLLOW

F F1 (P ROGRAM → DEKLARACE BLOK) = {ppr, {} F F1 (DEKLARACE → DEF IN ICE A) = {ppr} F F1 (DEKLARACE → ε) = {{} F F1 (A → DEF IN ICE A) = {ppr} F F1 (A → ε) = {{} F F1 (DEF IN ICE → ppr identif ikator ( B ) BLOKP P R) = {ppr} F F1 (B → promenna C) = {promenna} F F1 (B → ε) = {)} F F1 (C → , promenna C) = {, } F F1 (C → ε) = {)} F F1 (BLOKP P R → { P RIKAZP P R G }) = {{} F F1 (G → ; P RIKAZP P R G) = {; } F F1 (G → ε) = {}} F F1 (P RIKAZP P R → return V Y RAZ) = {return} F F1 (P RIKAZP P R → P RIKAZ) = {promenna, dokav., pokav., ident., ; , }} F F1 (BLOK → { P RIKAZ H }) = {{} F F1 (H → ; P RIKAZ H) = {; } F F1 (H → ε) = {}} F F1 (P RIKAZ → promenna J) = {promenna} F F1 (P RIKAZ → dokavad ( V Y RAZ ) delej BLOK) = {dokavad} F F1 (P RIKAZ → pokavad ( V Y RAZ ) tak BLOK R) = {pokavad} F F1 (P RIKAZ → identif ikator ( S )) = {identif ikator} F F1 (P RIKAZ → ε) = {; , }} F F1 (J → = K) = {=} F F1 (J → − > W = L) = {− >} F F1 (J → [ U ] E = V Y RAZ) = {[} F F1 (U → konstanta) = {konstanta} F F1 (U → promenna) = {promenna} F F1 (K → pole [ P Q ]) = {pole} F F1 (K → ∗ poi [ M ]) = {∗poi} F F1 (K → null) = {null} F F1 (K → V Y RAZ) = {!, (, konstanta, retezec, promenna, identif ikator} F F1 (P → V Y RAZ) = {!, (, konstanta, retezec, promenna, identif ikator} F F1 (P → pole [ P Q ]) = {pole} F F1 (Q → , P Q) = { , } F F1 (Q → ε) = {]} F F1 (M → HODN OT Y N ) = {identif ikator, ∗poi} F F1 (M → ε) = {]} F F1 (N → , HODN OT Y N ) = { , } F F1 (N → ε) = {]} F F1 (HODN OT Y → identif ikator) = {identif ikator}

91

F

VYPOČíTANÉ MNOŽINY FIRST A FOLLOW

F F1 (HODN OT Y → ∗ poi [ identif ikator ]) = {∗poi} F F1 (L → null) = {null} F F1 (L → V Y RAZ) = {!, (, konstanta, retezec, promenna, identif ikator} F F1 (E → [ U ] E) = {[} F F1 (E → ε) = {=, ∗, /, +, −, ==, <>, <, >, <=, >=, and, or, ; , }, ), ,, ]} F F1 (R → inac BLOK) = {inac} F F1 (R → ε) = {; , }} F F1 (S → V Y RAZ V ) = {!, (, konstanta, retezec, promenna, identif ikator} F F1 (S → ε) = {)} F F1 (V → , V Y RAZ V ) = {, } F F1 (V → ε) = {)} F F1 (V Y RAZ → T RV ) = {!, (, konstanta, retezec, promenna, identif ikator} F F1 (RV → and T RV ) = {and} F F1 (RV → or T RV ) = {or} F F1 (RV → ε) = {; , }, ), ,, ]} F F1 (T →! F ) = {!} F F1 (T → F ) = {(, konstanta, retezec, promenna, identif ikator} F F1 (F → AV X) = {(, konstanta, retezec, promenna, identif ikator} F F1 (X →== AV ) = {==} F F1 (X →<> AV ) = {<>} F F1 (X →< AV ) = {<} F F1 (X →> AV ) = {>} F F1 (X →<= AV ) = {<=} F F1 (X →>= AV ) = {>=} F F1 (X → ε) = {and, or, ; , }, ), ,, ]} F F1 (AV → T 1 AV 1) = {(, konstanta, retezec, promenna, identif ikator} F F1 (AV 1 → + T 1 AV 1) = {+} F F1 (AV 1 → − T 1 AV 1) = {−} F F1 (AV 1 → ε) = {==, <>, <, >, <=, >=, and, or, ; , }, ), ,, ]} F F1 (T 1 → F 1 T 11) = {(, konstanta, retezec, promenna, identif ikator} F F1 (T 11 → ∗ F 1 T 11) = {∗} F F1 (T 11 → /F 1 T 11) = {/} F F1 (T 11 → ε) = {+, −, ==, <>, <, >, <=, >=, and, or, ; , }, ), ,, ]} F F1 (F 1 → ( V Y RAZ )) = {(} F F1 (F 1 → konstanta) = {konstanta} F F1 (F 1 → retezec) = {retezec} F F1 (F 1 → promenna D) = {promenna} F F1 (F 1 → identif ikator ( S )) = {identif ikator} F F1 (D → [ U ] E) = {[} F F1 (D → − > W ) = {− >} F F1 (D → ε) = {∗, /, +, −, ==, <>, <, >, <=, >=, and, or, ; , }, ), ,, ]} F F1 (W → identif ikator) = {identif ikator} F F1 (W → ε) = {=, ∗, /, +, −, ==, <>, <, >, <=, >=, and, or, ; , }, ), ,, ]}

92

G

G

DETERMINISTICKÝ ZÁSOBNíKOVÝ AUTOMAT

Deterministický zásobníkový automat

93

ppr { } ; return PROGRAM DEKLARACE BLOK DEKLARACE BLOK DEKLARACE DEFINICE A ε A DEFINICE A ε DEFINICE ppr ident. (B) BLOKPR B C BLOKPPR PRIKAZPPR G G ε ; PRIKAZPPR G PRIKAZPPR PRIKAZ PRIKAZ return VYRAZ BLOK {PRIKAZ H} H ε ; PRIKAZ H PRIKAZ ε ε J K P Q M N HODNOTY L E ε ε R ε ε S V VYRAZ RV ε ε T F X ε ε AV AV1 ε ε T1 T11 ε ε F1 D ε ε U W ε ε ,

ε

ε

ε

ε

ε

ε

,VYRAZ V

ε

ε

ε

,HODNOTY N

,PQ

ε ε , promenna C

)

VYRAZ ε ε T RV ε F AV X ε T1 AV1 ε F1 T11 ε (VYRAZ) ε

VYRAZ

VYRAZ VYRAZ

(

–>

ε

ε

–> W

= K –> W = L

=

G DETERMINISTICKÝ ZÁSOBNíKOVÝ AUTOMAT

94

Tab. 5: Deterministický zásobníkový automat — část 1.

[ ] < > <> <= >= == pole ∗poi dokavad pokavad PROGRAM DEKLARACE A DEFINICE B C BLOKPPR G PRIKAZPPR PRIKAZ PRIKAZ BLOK H PRIKAZ dok.(VYRAZ)delej BLOK pok.(VYRAZ)tak BLOK R J [U]E=VYRAZ K pole[PQ] ∗poi[M] P pole[PQ] Q ε M ε HODNOTY N N ε HODNOTY ∗poi[identif.] L E [U]E ε ε ε ε ε ε ε R S V VYRAZ RV ε T F X ε AV <>AV <=AV >=AV ==AV AV AV1 ε ε ε ε ε ε ε T1 T11 ε ε ε ε ε ε ε F1 D [U]E ε ε ε ε ε ε ε U W ε ε ε ε ε ε ε



95

inac && k PROGRAM DEKLARACE A DEFINICE B C BLOKPPR G PRIKAZPPR BLOK H PRIKAZ J K P Q M N HODNOTY L E ε ε R inac BLOK S V VYRAZ RV && T RV k T RV T F X ε ε AV AV1 ε ε T1 T11 ε ε F1 D ε ε U W ε ε ε ε ε

ε ε ε

ε

ε

ε

ε

∗F1 T11 /F1 T11

konstanta

konstanta

F1 T11

T1 AV1

T1 AV1 +T1 AV1 −T1 AV1

F AV X

F AV X

řetězec

F1 T11

T RV

!F

VYRAZ T RV

ε

T RV

ε

VYRAZ

VYRAZ VYRAZ

PRIKAZ

ret.

VYRAZ

ε

VYRAZ

VYRAZ VYRAZ

null konstanta

VYRAZ

ε

/

null

∗

VYRAZ

−

null

+

VYRAZ VYRAZ

!

proměnná

proměnná D

F1 T11

T1 AV1

F AV X

T RV

VYRAZ

identfikátor VYRAZ

HODNOTY N

VYRAZ VYRAZ

proměnná J

PRIKAZ

proměnná C

proměnná

identifikátor

identfikátor (S)

F1 T11

T1 AV1

F AV X

T RV

VYRAZ

VYRAZ

VYRAZ VYRAZ

identfikátor (S)

identfikátor


96


H

H

DYNAMICKÉ STRUKTURY

Dynamické struktury

Obr. 6: Dynamická struktura podprogramů a cyklů.

97

H

DYNAMICKÉ STRUKTURY

Obr. 7: Dynamická struktura proměnných a slepé koleje.

98

I

I

SÉMANTICKÉ AKCE

99

Sémantické akce

P ROGRAM → DEKLARACE BLOK DEKLARACE → DEF IN ICE A | ε A → DEF IN ICE A | ε DEF IN ICE → ppr zaloz ppr identif ikator ( B ) podprogramuj B → vloz param promenna C | ε C → , vloz param promenna C | ε BLOKP P R → { P RIKAZP P R G } G → ; P RIKAZP P R G | ε P RIKAZP P R → return V Y RAZ vymet, napln prom, vem vysledek | P RIKAZ BLOK → { P RIKAZ H } H → ; P RIKAZ H | ε P RIKAZ → pamatuj název promenna J P RIKAZ → dokavad trubkuj; aktivuj čtení trubky, načti; ( V Y RAZ vymet ) delej založ podmínku, vem výsledek, while (podmínka){ BLOK V Y RAZ ověř podmínku, vem výsledek, }; deaktivuj čtení trubky, zruš trubku, načti další P RIKAZ → pokavad ( V Y RAZ vymeť, založ podmínku, vem výsledek ) tak if (podmínka) { BLOK } else { přeskákej } R P RIKAZ → pamatuj název ppr, vlož zarážku na kolej, identif ikator ( založ pořadí, založ ukazatel na argumenty S ) zruš ukazatel na argumenty, scope++, vem pořadí, pamatuj token za ), připrav čtení trubky, aktivuj čtení trubky, BLOKP P R scope–, deaktivuj čtení trubky, vem kolej, zruš podprogram, načti token za ) P RIKAZ → ε J →= K |−> W = L J → nastav ukazatel hodnoty, zvyš level [ U ] E sniž level = V Y RAZ vymeť, vlož hodnotu do proměnné, vem výsledek U → posuň ukazatel hodnoty konstanta U → zjisti hodnotu promenne, posuň ukazatel hodnoty promenna K → if !(exist promenna){ založ proměnnou } V Y RAZ vymeť, naplň proměnnou, vem výsledek K → if (exist promenna){zruš proměnnou}, založ proměnnou pole založ indexaci, zvyš level [ P Q zruš indexaci, sniž level ] K → if (exist promenna){zruš proměnnou}, založ proměnnou generuj adresu, naplň proměnnou ∗ poi [ M ] K → if (exist promenna){zruš proměnnou}, založ proměnnou, generuj adresu naplň proměnnou null P → if !(exist promenna){ založ proměnnou } V Y RAZ vymeť, naplň proměnnou, vem výsledek

I

SÉMANTICKÉ AKCE

P → if (exist promenna){zruš proměnnou}, založ proměnnou pole založ indexaci, zvyš level [ P Q zruš indexaci, sniž level ] Q → , zvyš index P Q | ε M → HODN OT Y N | ε N → , HODN OT Y N | ε HODN OT Y → identif iktor | ∗ poi [ identif iktor ] L → V Y RAZ vymeť, vlož adresu, vem výsledek | null E → zvyš level [ U ] E | ε R → inac if !(podmínka) { BLOK } else { přeskákej } | ε S → V Y RAZ vymeť, zvyš pořadí, nastav ukazatel argumentů naplň proměnnou, vem výsledek V S→ε V → V Y RAZ vymeť, zvyš pořadí, nastav ukazatel argumentů naplň proměnnou, vem výsledek V V →ε V Y RAZ → T RV RV → spočítej and T RV | spočítej or T RV | ε T → spočítej ! F | F F → AV X X → spočítej == AV | spočítej <> AV | spočítej < AV | spočítej > AV | spočítej <= AV | spočítej >= AV | ε AV → T 1 AV 1 AV 1 → spočítej + T 1 AV 1| spočítej − T 1 AV 1 | ε T 1 → F 1 T 11 T 11 → spočítej ∗ F 1 T 11| spočítej / F 1 T 11 | ε F 1 → spočítej ( V Y RAZ spočítej ) F 1 → vlož do výsledku konstanta | vlož do výsledku retezec F 1 → pamatuj název proměnné promenna D F 1 → založ proměnnou ppr, vlož zarážku na kolej, pamatuj název ppr identif ikator( založ pořadí, založ ukazatel na argumenty S ) zruš ukazatel na argumenty, scope++, vem pořadí, pamatuj token za ), připrav čtení trubky, aktivuj čtení trubky, BLOKP P R scope–, deaktivuj čtení trubky, vem kolej, vlož hodnotu ppr do proměnné zruš podprogram, načti token za ) D → nastav na první hodnotu pole, zvyš level [ U ] E vynuluj level, vlož do výsledku, nuluj ukazatel na hodnotu pole D→−> W D → if (definovaná proměnná){ vlož hodnotu do výsledku } ε W → identif ikator W → if (definovaná proměnná){ vlož hodnotu do výsledku } ε

100

J

UKÁZKOVÝ PROGRAM JAZYKA RUZIN

J

101

Ukázkový program jazyka Ruzin

################################################################### # Ukázkový zdrojový kód pro interpreta RUZIN # ###################################################################

#------ Založení funkce -------------------------------------------ppr fakt($n){ pokavad ($n < 2) tak { $x = 1; } inac { $x = $n * fakt($n - 1); }; return $x; } #------ Založení procedury ----------------------------------------ppr pyramida($patro,$znak){ $mezera = $patro - 1; $count = 1; dokavad ($patro > 0) delej { $pom1 = $mezera; dokavad ($pom1 > 0) delej { pis(" "); $pom1 = $pom1 - 1; }; $pom2 = 0; dokavad ($pom2 < $count) delej { pis($znak); $pom2 = $pom2 + 1; }; pis(br); $mezera = $mezera - 1; $count = $count + 2; $patro = $patro - 1; }; };

J


102

#------ Práce se strukturou ’pole’ s použitím cyklů ---------------$a = pole[ pole[1 ,2,3], pole[4 ,5,6], pole[7 ,8, 9] ]; $j = 1; $k = 1; pis ("pole:",br); dokavad ($j <= 3) delej { pis(tab); dokavad ($k <= 3) delej { pis($a[$j][$k]," "); $k = $k + 1; }; $k = 1; $j = $j + 1; pis(br); }; #------ Implementované fce ’cti’a ’pis’, použití podprogramů ------pis(br,"zadej číslo pro výpočet faktoriálu: "); cti($b); pis("faktoriál čísla ", $b," je: ", fakt($b), br, br); pis(br,"zadej počet pater pyramidy: "); cti($pocet); pis("zadej znak, ze kterého mám postavit pyramidu: "); cti($znak); pis("stavím pyramidu ze znaku ’",$znak, "’ s počtem pater: ", $pocet, br, br); pyramida ($pocet, $znak); pis(br); #------ Použití pointerů ------------------------------------------$c = *poi[]; $c -> = "ahoj "; pis ("obsah $c: ", $c, tab,"hodnota adresy $c: ", $c->, br); $d = $c; $c = "předsedo"; pis ("po přiřazení do $c:",br,"obsah $c: ", $c, br, "obsah $d: ", $d, tab, "hodnota adresy $d: ", $d->, br, br);

J


103

#------ Aritmetické operace ---------------------------------------$pozdrav = $d-> + $c; $cislo = (($k + 1) * $a[1][2] / 3.14) - 24.3; pis($pozdrav,br,$cislo,br); #------ Logické operace -------------------------------------------pis(br, "Logické operace:", br); pis("0 and 0 = ", 0&&0, tab, "0 or 0 = ", 0||0, tab); pis("0 nand 0 = ", !(0&&0), tab, "0 nor 0 = ", !(0||0), br); pis("0 and 1 = ", 0&&1, tab, "0 or 1 = ", 0||1, tab); pis("0 nand 1 = ", !(0&&1), tab, "0 nor 1 = ", !(0||1), br); pis("1 and 0 = ", 1&&0, tab, "1 or 0 = ", 1||0, tab); pis("1 nand 0 = ", !(1&&0), tab, "1 nor 0 = ", !(1||0), br); pis("1 and 1 = ", 1&&1, tab, "1 or 1 = ", 1||1, tab); pis("1 nand 1 = ", !(1&&1), tab, "1 nor 1 = ", !(1||1), br); #------ Cykly a větvení -------------------------------------------pis("Zadej číslo přání (nezadávej nulu): ");cti($prani); dokavad ($prani == 0) delej{ $count1 = 1; dokavad ($count1 < 5) delej { $count1 = $count1 + 1; }; pis("Zvol jiné číslo: "); cti($prani); }; pokavad ($prani <> 0) tak { pis("přeju "); pokavad ($prani > 0) tak { pis("pěkný "); pokavad ($prani <= 10) tak { pis("den"); } inac { pis("týden");

J


}; } inac { pis("nádherný "); pokavad ($prani >= -10) tak { pis("měsíc"); } inac { pis("rok"); }; }; }; pis(". Radost UZivat INterpret - RUZIN.",br); }

104

Návrh algoritmů pro sémantické akce při výstavbě interpretu metodou rekurzivního sestupu

Recommend Documents