FJP – Formální jazyky a překladače
Podklady ke cvičením, studijní materiály a praktické úlohy z teorie formálních jazyků, gramatik, syntaktické analýzy a konstrukce překladačů programovacích jazyků.
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
- 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 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í
- 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
- 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í 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
Online interpret a krokovací debugger jazyka PL/0
Pro zkoušení instrukcí virtuálního stroje, trasování obsahu zásobníku a ladění přeložených programů v jazyce PL/0 je k dispozici aktuální webová verze interpretu. Umožňuje interaktivní krokování, inspekci registrů i registraci vlastních semestrálních rozšíření.
Analyzátor bezkontextových gramatik
Ekvivalentní transformace gramatik krok za krokem, porovnání jazyků původní a upravené gramatiky, množiny FIRST a FOLLOW, rozkladové tabulky LL(1) a LL(2), automaty LR(0), SLR(1), LALR(1) a LR(1) s interaktivním grafem LR položek a generátor syntaktického analyzátoru rekurzivním sestupem. Gramatiky z příkladů ve cvičeních 8 až 12 se v něm otevřou jedním kliknutím.
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ý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ý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.
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í.
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í.
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.
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.
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é 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(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) 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).