V tomto roce vedu cvičení (9:20 - 11:00) i přednášky (čtvrtek, 8:25 - 11:00)
Předmět je zaměřen na pochopení základních konceptů funkce překladačů, zejména těch pracujících s bezkontextovými gramatikami.
Materiály ke cvičení, stejně jako užitečné odkazy jsou k dispozici na stránkách předmětu v univerzitním courseware. Zde alespoň shrnu užitečné odkazy týkající se předmětu:
Užitečné odkazy
Následující odkazy vedou na zajímavé stránky týkající se formálních jazyků.
- Návody a nástroje pro práci s lex a yacc
- ANTLR - nástroj pro tvorbu parserů
- Seriál o překladačích na ABCLinuxu
- Turingův stroj na Wolfram Alpha - můžete si vyzkoušet jak funguje.
- Algortimy - české stránky s přehledem mnoha algoritmů, mimo jiné i převod deterministického KA na nedeterministický, funkcí FIRST a FOLLOW pro LL1 gramatiky a transformace gramatiky na LL1.
Studijní materiály z jiných univerzit dostupné online
- Masarykova univerzita - Formální jazyky a automaty I - na stránce jsou k dispozici obsáhlá skripta v elektronické podobě
- Slezská univerzita - předměty Teorie jazyků a automatů I a II - na stránkách jsou jak skripta tak přednášky
- Vysoká škola báňská - Teorie jazyků a automatů - obsáhlé materiály k přednáškám
- Vysoké učení technické v Brně - Teoretická informatika 1 - k dispozici skripta
Volně dostupné překladače
- Freepascal - překladač Pascalu, volně ke stažení je i IDE podobné Delphi, Lazarus.
- GCC - sada překladačů pro C, C++, Objective C, Adu a Fortran, pro Windows existuje distribuce MinGW.
- Varianty Eclipse s podporou pro C a C++.
- Volně dostupné Microsfot Visual Studio 2010 Express s podporou pro C#.
- Mono - překladač a interpret C# pro Linux, Solaris, Windows a další platformy.
Materiály ke cvičení
Pozor! Aktuální informace o cvičeních jsou na courseware, zde je jen předběžný nástin programu a přehled užitečných odkazů. Je možné, že se během semestru náplň jednotlivých cvičení lehce změní nebo posune.
- Cvičení 1 - opakování gramatik, regulárních výrazů a konečných automatů
- Cvičení 2 - opakování gramatik, Backus-Naurova forma zápisu
Software pro práci s gramtikami a automaty
- Převod regulárních výrazů na konečné automaty, lze si vyzkoušet chování automatu zadáním testovacího vstupu.
- Qfsm - editor konečných automatů, umožňuje snadno naklikat automat, zkontrolovat jestli je deterministický, bez slepých větví a exportovat ho (do obrázku nebo textových popisů které lze přeložit do programovacích jazyků - viz manuál). Krom zdrojových textů si můžete stáhnout hotovou distribuci pro Windows, program je i v repozitářích openSUSE.
- JFLAP - velmi univerzální nástroj schopný pracovat s gramatikami a automary všech tříd, převádět automaty na gramatiky, testovat jejich chování a tak dále - rozhodně stojí za vyzkoušení. Atomaty lze navrhovat a testovat v grafickém režimu.
- Cvičení 3 - lexikální analýza pomocí LEXu
Software pro lexikální analýzu
- Flex - volně dostupná implementace Lexu, pro C.
- JLex - volně dostupná implementace Lexu, pro Javu.
- C# CUP - varianta JLex pro C#.
- Překladače v Javě - stránka s přehledem různých nástrojů pro tvorbu překladačů v Javě (často založených na Lex a Yacc).
- Bumble-Bee Parser Generator - IDE s implementací Lex a Yacc, pro C, C++ a Javu, pro akademické účely zdarma.
- GOLD Parsing System - IDE pro generování parserů, překladačů a interpretů pro C, C#, Delphi, Javu, Python a řadu dalších jazyků, zápis gramatiky v Backus-Naurově formě. K dispozici zdarma.
- UltraGram - IDE pro generování parserů pro C++, C#, Javu a VB.NET, podobná syntaxe jako Lex, placené s trialem na 15 dní.
Ukázky použití Lexu
- Pascal - použití Lexu a Yaccu pro tvorbu překladače Pascalu.
- Příklad zpracování souboru s daty - ukázka použití Lexu pro zpracování datového souboru s informacemi o studentech.
- Cvičení 4 - překladač jazyka PL/0
- Compiler Construction - návrh a tvorba překladače pro jazyk Oberon, podobný PL/0 (Niklaus Wirth). Sice je to anglicky, ale nic lepšího asi nenajdete, obsahuje konkrétní postup jak navrhnout a implementovat překladač, včetně ukázek zdrojových textů, algoritmů a jejich fungování a podrobného popisu. Neobsahuje příliš teorie, spíš praktické rady jak a co implementovat.
- PL/0 - srovnání PL/0 a dalších podobných jazyků. Na stránkách se můžete podívat na velmi jednoduché programy (Hello world, výpočet mocniny a podobně) ve velkém mnosžtví různých jazyků.
- Cvičení 5 - zadání semestrálních prací; snažte se na toto cvičení přijít.
- Cvičení 6 - interpret jazyka PL/0.
- Cvičení 7 - SED.
- SED - distribuce SED pro Windows.
- Seriál o SEDu na Rootu.
- Cvičení 8 - Yacc
- Yacc: Yet Another Compiler-Compiler - původní článek s návrhem Yaccu.
- A Compact Guide to Lex & Yacc - stručný návod na používání Lexu a Yaccu (anglicky).
- Byacc - varianta Yaccu umožňující pracovat s Javou.
- Bumble-Bee Parser Generator - IDE s implementací Lex a Yacc, pro C, C++ a Javu, pro akademické účely zdarma.
- jacc - varianta yaccu v Javě pro Javu, na začátku odkazy na další podobné nástroje.
- Cvičení 9 - Transformace bezkontextových gramatik
- The Context Free Grammar Checker - ověřování vlastností gramatik a generování rozkladových tabulek online (i tak ale doporučuji si probírané algoritmy vyzkoušet na papír, u zkoušky tenhle software mít nebudete :-) ).
- Cvičení 10 - Zásobníkové automaty a LL gramatiky
- Cvičení 11 - LL(k) gramatiky
- Vysoké učení technické v Brně - Teoretická informatika 1 - k dispozici skripta, obsahují popis LL(k) gramatik. analýzy a výpočtu first a follow funkcí.
- Cvičení 12 - SLR gramatiky
