Zadání projektů
do předmětu Překladače


 

Smyslem celého projektu je procvičit si programovací techniky, které se probírají na přednáškách a cvičeních předmětu Překladače. Je třeba, aby projekt splňoval všechny náležitosti uvedené na této stránce. Je to do značné míry tvořivá činnost, žádné dva projekty by proto neměly být stejné! Naprogramujete jednoduchý interpretační překladač.

Lexikální analýza

Tato část projektu je součástí zápočtu, má být odevzdána do konce listopadu daného akademického roku. Dejte si záležet, protože na této části projektu postavíte celý zbytek. Nepodceňujte to, zvláště pokud jste zatím nepracovali na žádném podobně rozsáhlém projektu.

Co dělat, jak postupovat:

  1. Vymyslete si jakýkoliv jazyk. Ke konci této stránky máte ukázky pro inspiraci, může jít o značně zjednodušený běžný jazyk typu Pascal nebo C, nebo třeba jazyk, jehož příkazy mají grafický výstup (inspirujte se například u programů Logo a Karel, což jsou jednoduché programovací jazyky pro děti). Základní požadavky na jazyk jsou uvedeny níže.
  2. Určete základní strukturu jazyka - jaké příkazy je možné zadávat, co se dá napsat do jejich parametrů, zda a jak se deklarují proměnné, jaká jsou klíčová slova, jaké závorky se kde používají, jak začíná a končí program, zda použijete určitý symbol (obvykle středník) pro ukončení příkazu nebo oddělení dvou příkazů (to není totéž z hlediska syntaxe), případně jak vypadají podmíněné příkazy, apod.
  3. Vytvořte nejdřív symbolickou lexikální analýzu jazyka, tj. na papír nebo ve Wordu/Excelu vytvořte potřebné struktury a tabulku, postup je v druhé kapitole ve skriptech.
  4. Programujte (v některém jazyce, který vcelku ovládáte, například v Pascalu, Delphi, C, C++, apod.) podle struktur, které jste vytvořili v předchozím bodu. Nezapomeňte na komentáře a podrobná chybová hlášení, obojí vám usnadní ladění programu.
  5. Ve vlastním zájmu (kvůli ladění i z důvodu snadnější návaznosti další části projektu) naprogramujte lexikální analýzu tak, aby šlo o funkci či proceduru, která při každém svém zavolání načte ze vstupu právě jeden symbol (a vypíše ho do souboru, okna či na obrazovku) a je cyklicky volána, dokud nedojde na konec zdroje.
  6. Při programování je nutné používat programovací techniky, které probíráme, protože účelem projektu je procvičit si učivo. Zvláště ad-hoc techniky nebudou akceptovány.
  7. Odevzdejte mailem:
    • zdrojový kód vašeho programu,
    • spustitelný soubor, který je funkční,
    • dokumentaci (informaci o tom, co program dělá, jaké příkazy přijímá, co jsou jejich parametry, zda je jazyk case-sensitive, dále všechny struktury a tabulky vytvořené pro lexikální analýzu např. ve Wordu či Excelu nebo naskenované či vyfocené),
    • ukázkový vstup, na kterém jste překladač testovali.
    Počítejte s tím, že při případných připomínkách bude lexikální analýza vrácena k přepracování.

V této fázi bude mít program zjednodušený výstup, zatím stačí, aby prostě vypsal do okna nebo na obrazovku seznam všech symbolů, které se v zadaném zdroji vyskytují, aby byla lexikální analýza důkladně odladěná.

Náležitosti jazyka:

V jazyce můžete používat i podmíněné příkazy (například if-then-else), ale nedoporučuji používat cykly (for, while, atd.), protože implementace jejich sémantiky je složitější (ale jestli chcete, klidně můžete, nebudu protestovat).

Postupujte tak, aby byl překladač co nejsnadněji rozšiřitelný. Budete přidávat syntaktickou a sémantickou analýzu, syntaktická bude podle potřeby volat lexikální analýzu jako proceduru (funkci), která ze vstupu načte vždy jeden symbol. Z důvodů snadnějšího ladění při psaní lexikální analýzy budeme chtít, aby zpracovala celý vstup, ale je lepší do budoucna počítat s tím, že její činnost bude "rozkouskovaná", a tak ji můžeme napsat rovnou jako funkci, která při svém zavolání načte ze vstupu jeden symbol a v počátku je z hlavního programu v cyklu volaná, dokud nedojde ke konci vstupu.

Neměli byste zapomenout, že je třeba vytvořit příslušný datový typ (výčtový typ, enum, posloupnost konstant apod.) pro typy symbolů, tento datový typ pak bude využíván v rámci celého překladače. Z praktických důvodů doporučuji vytvořit funkci, která bude prvky tohoto výčtového typu převádět na řetězec, aby bylo možné je vypisovat (při ladění lexikální analýzy na výstup, později při ošetření chyb v syntaktické a sémantické analýze).

Syntaxe a sémantika

Až budete mít hotovou, odladěnou a schválenou lexikální analýzu, můžete začít pracovat na zbytku projektu. Dále předpokládáme, že máte naprogramovanou funkci nebo proceduru, která zatím načtený symbol prostě někam vypsala. Teď v této funkci proveďte změnu:

Takže změna původního kódu je jen drobná.
Odevzdat nejpozději do konce zkouškového období zimního semestru, ideálně však už v prosinci, později nebudete mít dostatek času.

Případné dodatečné změny jazyka:

Teď už budete znát více z teorie překladu, takže možná budete chtít svůj původní koncept trochu pozměnit.

Syntaktická analýza:

Pro ty, kdo pozapomněli, jak se programuje rekurze:

Sémantická analýza:

Odevzdejte mailem:

Počítejte s tím, že při případných připomínkách bude projekt vrácen k přepracování.

Příklady projektů pro inspiraci

Fantazii se meze nekladou, pokud ovšem vymyslíte něco proveditelného. Obecně volte to, co dokážete naprogramovat (také po grafické stránce). Může to být textový program, jednoduchá 2D grafika, 3D grafika, grafy, klasický nebo funkcionální jazyk. Je možné zpracovávat vstup "vlastního" jazyka na vstup jiného jazyka (HTML, LaTeX apod.), ale musíte přidat ještě nějaké zpracování (například interpretaci výrazů na konstanty), nestačí pouhý překlad syntaxe.

Silně zjednodušený Pascal se změněnými klíčovými slovy:

Program pracuje pouze s celočíselnými proměnnými, proto není nutné zadávat jejich datový typ. Proměnné jsou deklarovány před začátkem programu. Blok programu je ohraničen příslušnými klíčovými slovy. Jsou přijímány příkazy:

Ukázka vstupu: prom x, vysl; zacatek vypisretezec("Program na výpočet druhé mocniny kladného čísla."); vypisretezec("Zadej číslo: "); nacti(x); if (x<=0) vypisretezec("Toto číslo není kladné!"); if (x>0) vystup(x*x); konec Fantazii se meze nekladou, můžete si například vymyslet nějaký speciální příkaz, který vypočítá a vypíše druhou mocninu či odmocninu z výsledku zadaného výrazu, apod. Překladač vždy načte zdrojový soubor s něčím podobným, co je uvedeno výše, a interpretuje. Případně je možné využít grafické prostředí (zdroj je v jednom podokně, v dalším se vypisují výsledky).

Grafický editor:

Jeden příkaz na jednom řádku, po stisknutí klávesy ENTER se vždy vyhodnotí a provede. Příkazy:

Obrazovka (okno programu) je rozdělena na dvě části. Ve spodní části se zadává příkaz (může být viditelný jen ten, který se momentálně zadává nebo několik posledních), v horní části se vykresluje výsledek. Pokud je vykreslovaný objekt mimo vyznačené hranice, na příkaz se nereaguje nebo se vykreslí jen část objektu.

Kalkulačka pracující s výrazy a proměnnými:

Jeden příkaz na jednom řádku, po stisknutí ENTER se vždy vyhodnotí a provede, ale je schopen také načíst dávku ze souboru stejně jako Příkazový řádek ve Windows. Příkazy:

Vytváření dialogů pod DOSem:

Textový vstup těchto příkazů (vhodně je pojmenujte):

Proměnné budou pouze celočíselné, pokud se v parametrech příkazů vyskytují řetězce, vždy bude nutné použít konstantní hodnotu (např. řetězec uzavřený do uvozovek nebo apostrofů). Překladač bude interpretační, může být konverzační.

Interpretace matematických výrazů:

Hilbertovská výroková logika:

S ::= A [implikace] S | A
A ::= (S) | [negace] (S) | p | [negace] p | true | false

Interpretace logických výrazů v Pascalu:

S ::= S or A | A
A ::= A and B | B
B ::= (S) | C relop C
C ::= i | n
(nejdřív přidáme zbytek syntaxe a upravíme na LL(1) gramatiku)

Kreslení:

Pokud znáte program Logo, tento příklad je podobný.

L = {doprava, doleva, nahoru, dolu, krok(počet) } – pohyb kurzoru

Chodící robot/strom/dort/auto/kruh s vyznačeným čelem/atd.:

Zvolíme nějaký element podle vlastního vkusu, co dokážete rychle vygenerovat. Je to obdoba známého programu Karel, dá se naprogramovat podobně jako předchozí příklad (prostě příkazy řídíme pohyb daného elementu), nezapomeňme, že do definice jazyka musíme nějak vpašovat matematické výrazy.

Interpretace hudby:

Jazyk obsahuje tyto příkazy:

Kdo se hodně nudí, může podle zadaného vstupu vytvořit třeba i notový záznam :-)

Implementace grafových algoritmů:

Například se rozhodnete pro implementaci algoritmu obchodního cestujícího. Příkazy zahrnují možnost zadávání souřadnic pro "města", a dále třeba příkazy zjišťující, zda existuje cesta mezi městy kratší než xxx (parametr příkazu). Dále je samozřejmě nutné vytvořit příkazy pro práci s proměnnými jako výše, případně větvení.

Jednoduchý značkovací jazyk pro dokumenty s překladem do HTML:

Příkazy pro odstavec, nadpis, barvu textu, deklarování proměnných, načítání hodnoty proměnné apod., veškeré číselné údaje (včetně barvy textu) lze zadat jako matematický výraz s využitím proměnných. Výstupem je soubor ve formátu HTML s tím, že veškeré matematické výrazy jsou vypočteny a do HTML kódu jsou dosazena pouze čísla (proměnné se ve výstupu nebudou vyskytovat).