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. Pro rychlejší komunikaci je zřízen Discord server, pozvánku posílám mailem na začátku semestru ale je k dispozici i na CW. 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ů a překladačů.

  • Online interpret a debugger jazyka PL/0 – interaktivní webové vývojové prostředí, interpret a krokovací debugger pro výukový jazyk PL/0 (podle N. Wirtha). Umožňuje editaci kódu, překlad do instrukcí virtuálního zásobníku a krokování běhu programu včetně vizualizace stavu zásobníku a proměnných. Vytvořili Lukáš Vlček a Vojtěch Bartička, vylepšili Vladimíra Kimlová a Dominik Zappe.
  • Návody a nástroje pro práci s lex a yacc
  • 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.
Generátory parserů a související nástroje

Přehled moderních i klasických nástrojů pro generování parserů, lexikální analýzu a zpracování jazyků (včetně nástrojů analyzovaných v práci Moderní algoritmy a nástroje pro generování parserů):

  • ANTLR – moderní a široce využívaný parser generátor pro Javu, C++, Python, C# a další jazyky, založený na adaptivní prediktivní analýze ALL(*) s dynamickým lookaheadem. Podporuje přímou levou rekurzi ve výrazových gramatikách a automaticky generuje syntaktický strom včetně infrastruktury pro listenery a visitory.
  • Bison (GNU Bison) – standardní posunově-redukční generátor parserů z rodiny LALR(1) a GLR určený pro C a C++, který vznikl jako vylepšená open-source náhrada původního nástroje Yacc. Pracuje metodou zdola nahoru s lineární časovou složitostí a umožňuje spouštět sémantické akce i přímou konstrukci AST při redukci pravidel.
  • Flex – rychlý a osvědčený nástroj pro generování lexikálních analyzátorů v jazycích C a C++ převodem regulárních výrazů na deterministický konečný automat. Běžně se využívá v kombinaci s nástrojem Bison pro oddělení fáze tokenizace od samotné syntaktické analýzy.
  • Yacc – klasický unixový LALR(1) parser generátor, který stál u zrodu moderní automatické konstrukce překladačů pro jazyk C. Zavedl standardní formát zápisu bezkontextových gramatik se sémantickými akcemi a stal se předlohou pro řadu nástrojů jako Bison, Byacc či jacc.
  • jacc – čistě javovská implementace nástroje Yacc, která generuje rychlé a efektivní LALR(1) parsery přímo ve zdrojovém kódu Javy. Umožňuje přirozené začlenění do Java projektů při zachování tradiční syntaxe a sémantických akcí známých z unixového Yaccu.
  • Byacc / BYACC/J – rozšíření uznávaného Berkeley Yaccu o podporu přímého generování sémantických akcí a kódu parseru v jazyce Java. Udržuje vysokou míru kompatibility s původním Yaccem a usnadňuje vývoj překladačů pro výukové i praktické účely.
  • Tree-sitter – moderní inkrementální parser generátor v jazyce C navržený speciálně pro textové editory, IDE a nástroje statické analýzy vyžadující okamžitou odezvu. Vyniká rychlou aktualizací konkrétního syntaktického stromu při editaci textu, robustním zotavením ze syntaktických chyb a deklarativním dotazovacím systémem pro zvýrazňování syntaxe.
  • Peggy – populární parser generátor pro JavaScript a TypeScript založený na formalismu Parsing Expression Grammars (PEG) a pokračovatel projektu PEG.js. Poskytuje jednoznačné deterministické parsování s prioritizovanou volbou alternativ a dovoluje vkládat JavaScriptové akce přímo do gramatiky pro okamžitou tvorbu AST.
  • pest – moderní a elegantní parser generátor pro jazyk Rust stavějící na principech bezkontextových PEG gramatik. Důsledně odděluje formální specifikaci gramatiky od aplikačního kódu a s využitím Rust maker vytváří typově bezpečný a vysoce rychlý parser.
  • Nearley – flexibilní parser generátor pro JavaScript implementující Earleyho algoritmus pro zpracování obecných bezkontextových gramatik (CFG). Bez nutnosti úprav gramatiky zpracovává libovolnou levou rekurzi i nejednoznačné zápisy, u nichž dokáže vrátit všechny platné derivace v podobě lesa derivačních stromů.
  • nom – výkonná knihovna parser kombinátorů pro jazyk Rust, která umožňuje skládat parsery přímo v kódu jako kompozici funkcí bez externí gramatiky. Nabízí špičkovou rychlost díky nulovým alokacím (zero-copy) a nativní podporu pro proudové zpracování (streaming) textových i binárních formátů.
  • Ohm – knihovna a jazyk pro tvorbu parserů v JavaScriptu vycházející z PEG gramatik, která striktně odděluje popis syntaxe od sémantického vyhodnocení. Gramatika vytváří konkrétní syntaktický strom, nad nímž lze zcela nezávisle definovat libovolné množství sémantických operací pro interpretaci, kompilaci či analýzu.
  • Outlines – specializovaný nástroj pro řízené generování strukturovaného výstupu z velkých jazykových modelů (LLM) s využitím formálních gramatik, regulárních výrazů a schémat. Místo zpětné analýzy textu aplikuje formální syntaktická pravidla dopředně na proces výběru tokenů, čímž matematicky garantuje syntaktickou platnost výsledku.
  • JLex a CUP – akademické nástroje pro lexikální a syntaktickou analýzu v Javě vyvinuté na Princeton University, které tvoří javovský protějšek dvojice Lex a Yacc. CUP generuje deterministické LALR(1) parsery a je tradičně využíván v univerzitních kurzech konstrukce překladačů.
  • GOLD Parsing System – volně dostupný systém pro tvorbu překladačů a interpretů, který důsledně odděluje návrh gramatiky v Backus-Naurově formě od samotného běhového enginu. Vygenerované stavové tabulky LALR a DFA lze přímo načítat a spouštět v desítkách programovacích jazyků včetně C#, Javy, Pythonu a C++.
  • Bumble-Bee Parser Generator – vizuální vývojové prostředí a parser generátor integrující ekvivalent nástrojů Lex a Yacc s podporou pro jazyky C, C++ a Javu. Umožňuje interaktivní návrh, testování a ladění gramatik včetně generování zdrojových kódů pro akademické i komerční využití.

Studijní materiály z jiných univerzit dostupné online

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 se hodí unixový subsystém.
  • Varianty Eclipse s podporou pro C a C++.
  • Volně dostupné Visual Studio Code s podporou pro C a C++ / 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.

    Ukázky použití Lexu

  • 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í 6 - interpret jazyka PL/0.
  • Cvičení 7 - SED.
  • Cvičení 8 - Yacc
  • 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

Příklady a cvičení k vyzkoušení

Praktické studijní texty, gramatiky, zdrojové kódy a podklady pro procvičení jednotlivých partií předmětu bez nutnosti instalace původních nástrojů:

Formální jazykyAbecedyKonečné automaty

Množiny, abecedy, řetězce a formální jazyky

Základní pojmy teorie formálních jazyků: operace nad abecedami, uzávěry, deterministické i nedeterministické konečné automaty a konstrukce přechodových grafů.

Regulární výrazyLineární gramatikyJazyk C

Regulární výrazy a lineární gramatiky

Návrh gramatik a regulárních výrazů pro reálné syntaktické konstrukce (identifikátory v C, čísla, IP adresy, řetězce, komentáře) a Backus-Naurova forma.

Lexikální analýzaLEXFlex

Lexikální analýza a generátor LEX (Flex)

Zásady návrhu lexikálního analyzátoru, struktura konfiguračních souborů nástroje LEX (.l), detekce tokenů, počítadla a vazba na jazyk C.

PL/0Niklaus WirthZásobníkový kód

Architektura a překladač jazyka PL/0

Konstrukce Wirthova referenčního překladače PL/0: gramatika v EBNF, tabulka symbolů, zásobníkový virtuální stroj a generování instrukcí.

InterpretZásobníkTrasování

Virtuální stroj a interpret jazyka PL/0

Běhové prostředí a interpretace zásobníkových instrukcí PL/0: práce s pamětí, volání procedur, trasování registrů a online ladění.

SEDRegulární výrazyDávkové zpracování

Proudový textový editor SED

Dávkové zpracování a transformace textu pomocí nástroje sed: práce s pattern space a hold space, regulární substituce a praktické skripty.

YACCBisonSyntaktická analýza

Syntaktická analýza a generátor YACC (Bison)

Generování syntaktických analyzátorů zdola nahoru v YACCu: postfixová a infixová kalkulačka, integrace Lexu a Yaccu a překladač PL/0.

BKGCFGTransformace

Transformace bezkontextových gramatik

Algoritmy a postupy pro úpravu bezkontextových gramatik: odstranění nedostupných a zbytečných symbolů, eliminace epsilon pravidel a levé rekurze.

Zásobníkový automatPDALL(1)

Zásobníkové automaty a prediktivní LL gramatiky

Rozpoznávání bezkontextových jazyků pomocí zásobníkového automatu (PDA), derivační stromy a teoretické podmínky pro deterministické LL(1) gramatiky.

LL(1)FIRSTFOLLOW

LL(k) gramatiky a rozkladové tabulky

Metodika konstrukce deterministických syntaktických analyzátorů shora dolů: výpočet množin FIRST a FOLLOW a sestavení rozkladové tabulky.

SLR(1)LR(0)Kanonická kolekce

SLR(1) gramatiky a syntaktická analýza zdola nahoru

Konstrukce jednoduchých LR analyzátorů (Simple LR): položky kanonické kolekce, přechodové automaty pro LR(0) a rozkladové tabulky SLR(1).