Analyzátor bezkontextových gramatik
Výukový nástroj pro analýzu gramatik, transformace a konstrukci syntaktických analyzátorů
Výuková webová aplikace pro předmět Formální jazyky a překladače (FJP). Slouží k analýze bezkontextových gramatik, provádění ekvivalentních transformací, výpočtu množin FIRST a FOLLOW, konstrukci rozkladových tabulek a simulaci různých typů syntaktických analyzátorů.
Analýza gramatiky, výpočet množin FIRST a FOLLOW a sestavení rozkladové tabulky LL(1)
O projektu a kontext
Aplikace doplňuje výuku překladačů. Umožňuje zadat gramatiku v běžných formátech (šipková notace, BNF, formát pro Bison nebo ANTLR) a krok za krokem sledovat algoritmy, které se probírají na přednáškách a cvičeních: redukci gramatiky, odstranění levé rekurze, faktorizaci zleva, klasifikaci do tříd LL a LR a vyhledávání protipříkladů pro konflikty v rozkladových tabulkách.
Klíčové funkce a schopnosti
Množiny FIRST a FOLLOW
Výpočet množin FIRST a FOLLOW s podrobným rozpisem kroků a pravidel použitých při odvození.
Rozkladové tabulky LL a LR
Sestavení rozkladové tabulky LL(1), stavového grafu položek LR(0)/LR(1) a detekce konfliktů Shift-Reduce a Reduce-Reduce.
Transformace gramatik
Odstranění nedosažitelných a neterminujících symbolů, eliminace epsilon pravidel a jednoduchých pravidel, odstranění levé rekurze a faktorizace zleva.
Protipříklady konfliktů
Vyhledání konkrétních řetězců, na kterých dochází ke kolizi v rozkladové tabulce nebo k nejednoznačnosti.
Simulace parserů
Krokování syntaktické analýzy rekurzivním sestupem, prediktivním rozkladem LL(1), operátorským přednostním rozkladem a obecnými parsery (Earley, CYK, GLR).
Generování kódu parseru
Generování kódu syntaktického analyzátoru v jazycích C, Python, JavaScript, PL/0 a Oberon včetně zotavení z chyb.
Výukové využití a pedagogický přínos
Při ručním řešení úloh z formálních jazyků dělají studenti často mechanické chyby ve výpočtu množin nebo přehlédnou podmínky pro zařazení do třídy LL(1). Nástroj poskytuje okamžitou kontrolu výsledků a ukazuje mezikroky každého výpočtu.
