Kontakty a rozvrh

Přednášky a cvičení v předmětu překladače vede RNDr. Šárka Vavrečková, Ph.D.

• e-mail: sarka.vavreckova@fpf.slu.cz
• telefon: (+420) 553 684 366
• konzultační hodiny najdete na https://www.slu.cz/fpf/cz/layout/1018
• web: http://vavreckova.zam.slu.cz
  

Náplň předmětu

Předmět Překladače je zvláštní tím, že se v něm setkává teoretická a praktická část IT. Využíváme prostředky teoretické informatiky (gramatiky, konečný a zásobníkový automat) k tomu, abychom naprogramovali efektivní - co nejoptimálnější - překladač zvoleného jazyka.

Ve výuce se budeme zabývat tím, jak tedy navrhnout strukturu lexikální, syntaktické a sémantické analýzy pomocí gramatik, jak tyto gramatiky převést na automaty, tyto automaty naprogramovat a zařadit do celkového projektu. Osnova je následující:

• Struktura překladače.
• Lexikální analýza.
• Metody a jejich implementace.
• Syntaktická analýza, LL(1), silné LL(k) a silné LR(k) gramatiky a jejich implementace.
• Sémantická analýza. Tabulka symbolů a její implementace. Intermediální kód.
• Syntaxí řízený překlad.
• Atributovaný překlad a jeho iplementace.
• Programování pokročilejších jazykových konstrukcí.

Předmět je ukončen zápočtem a zkouškou.

Požadavky ke splnění zápočtu a zkoušky

Požadavky na zápočet:

• aktivní účast na cvičeních alespoň 75 %
• u prezenčního studia dva testy, v kombinované formě se kumuluje do jednoho, je třeba získat alespoň 50 % bodů
  
• naprogramování a odevzdání první části projektu - lexikální analyzátor zvoleného jazyka

Požadavky na zkoušku:

• písemka (může být ve formě online testu - informace podá vyučující na začátku semestru)
  
• odevzdání finální verze projektu - rozšíření první části o syntaxi a sémantiku, hotový překladač splňující stanovené podmínky.

Škála pro hodnocení zkouškové písemky je následující:

Okruhy k zápočtovým a zkouškovým testům/písemkám

Okruhy k zápočtovým testům:

• lexikální analýza (pro zadaný jazyk vytvořte tabulku přechodů a zpracujte podle ní vybraná slova),
• syntaxe (zjistěte, zda je gramatika typu LL(1); pokud ano, sestavte rozkladovou tabulku a podle tabulky zpracujte slovo patřící do jazyka, pokud ne, vypočtěte množiny Follow2 a zjistěte, zda je to silná LL(2) gramatika, v gramatice zpracujte některé slovo jazyka, vytvořte derivační strom a vypište levý rozklad),

• syntaxe: ověřte, zda je gramatika silná LL(2), vytvořte rozkladovou tabulku a zpracujte podle ní některé slovo jazyka,
• intermediální kód: převeďte daný výraz do tří různých druhů intermediálního kódu,
• syntaxí řízený překlad: sestrojte překladovou gramatiku / překladový automat daného typu,
• sémantika: sestrojte atributovou gramatiku podle zadání.

Pro usnadnějí přípravy na zkoušku máte také k dispozici orientační seznam otázek seřazený podle témat ve skriptech (pokud bude písemná část zkoušky ve formě online testu, berte tento seznam opravdu jen jako orientační):

Projekt

Projekt by měl každý student programovat sám, měl by svému kódu rozumět, kód musí splňovat všechny náležitosti. Podrobné informace o projektu jsou zde:

První část projektu je třeba odevzdat do konce listopadu. Pokud to nestihnete, jsou sankce: za každé dva další započaté týdny jedno klíčové slovo navíc.

Můžete programovat téměř v jakémkoliv jazyce, který znáte, ale některé jsou vhodnější, jiné méně vhodné.

• doporučené: například C++, Java, Delphi
• neutrální: C# (víc se "nadřete"), Pascal (problém s vývojovými prostředími)
• nedoporučené: Python, JavaScript, funkcionální jazyky (nicméně u všech se již pokusy o naprogramování překladače vyskytly)

Vývojová prostředí máte k dispozici ve škole. Dále si můžete stáhnout vývojové nástroje od Microsoftu přes projekt MS Imagine, nebo využít vývojové nástroje společnosti Embarcadero (edici Starter máte zdarma až do chvíle, než přesáhnete příjmu 1000 USD) - doporučuji, velice dobře vytvořené IDE pro C++ Builder i Delphi. Popřípadě jsou k dispozici další vývojová prostředí, jako třeba BlueJ, NetBeans, Eclipse, VS Code,... podle zvoleného jazyka.

Skripta

Hlavním studijním materiálem jsou skripta, která před lety vyšla tiskem:

VAVREČKOVÁ, Šárka. Programování překladačů. Opava: FPF SU v Opavě, 2008. ISBN 978-80-7248-493-5.

Pracuji na nové verzi (ukázkový kód bude postupně přepsán do C/C++, celková struktura a náplň kapitol taky vyžaduje aktualizaci). Prozatímní verze:

Novější verze je zatím ve stadiu rozpracování, najdete ji zde:

Zatím to jsou jen první dvě kapitoly. Další postupně přibudou, mezitím dávám k dispozici ty prezentace, kde se řeší přepis gramatiky či automatu na programový kód. Zbytek je použitelný i z původních skript, změna je jen v programovacím jazyce (nová skripta a prezentace obsahují kód v C++).

Prezentace

• Implementace LL(1) gramatik (tj. přepis LL(1) gramatiky na kód):

• Implementace silných LL(k) gramatik - v poslední části následující prezentace:

• Implementace silných LR(1) gramatik - opět v poslední části:

• A nakonec implementace atributového překladu, tedy propojení syntaxe a sémantiky, přičemž výsledkem je jednoprůchodový interpretační překladač (v prezentaci je nejdřív LL překlad a potom LR překlad):

Ukázky kódu pro lexikální analýzu

Následují přímo ukázky kódu, spíše pro lexikální analýzu (ať dokážete co nejrychleji začít).

• Pseudokód přepsatelný do některého reálného jazyka:

• Ukázku lexikálního analyzátoru pro jazyk se 4 klíčovými slovy (pozor, v projektu seminární práce musíte mít min. 5 klíčových slov). Programováno v C++. V přiložené dokumentaci najdete i základní informaci ke zprovoznění projektu, příp. stažení a instalaci Visual Studia (poněkud starší verze, tak to berte s rezervou).
  

• HTML soubory s vloženým kódem v Javě (nejsou to všechny soubory projektu, jen ty, kde jsou použity metody, které nás zajímají z hlediska překladačů), poslední soubor je archiv obsahující přímo daný projekt v Javě:

Další

Pokud ani to nestačilo, snad najdete něco dalšího užitečného na WWW stránce předmětu (například "počítací" příklady s gramatikami, obdobu toho, co můžete čekat u zkoušky):

Následující test obsahuje podobné otázky jako ten zkouškový v online verzi (ne zcela, například zde chybí otázka s volnou odpovědí typu "napište definici" apod.). Jsou zde pouze otázky, které lze vyhodnocovat automaticky, takže se výsledek dozvíte hned po odevzdání. Test můžete spustit třikrát, pokaždé dostanete jiné otázky.

Přečtěte si důkladně požadavky k zápočtu a zkoušce - jsou v jedné z předchozích sekcí této interaktivní osnovy. Zde najdete pouze část toho, co je třeba splnit k získání zkoušky - online test.

Jedna z otázek v testu je s volnou odpovědí, která není automaticky vyhodnocována, tedy celkový výsledek testu budete znát až po ručním vyhodnocení vyučujícím.