Formální jazyky a překladače (FJP)
FJPGramatikySyntaktická analýzaLL(1)LR parseryPřekladače

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ů.

/fjp/grammar-analyser/index.html
Snímek rozhraní aplikace Analyzátor bezkontextových gramatik
Otevřít interaktivní simulaci

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.