Zadání úlohy č. 3

[Dokumentace] [Soubory v Javě (NetBeans)] [Soubory v C#]
[Řešení v Javě] [Řešení v C#]

Výpočty nad bezkontextovou gramatikou I

S využitím balíku grammar, který je součástí materiálů k této úloze, implementujte v jazyce Java funkci compute_empty(), která vypočte množinu všech neterminálních symbolů generujících prázdné slovo.

Algoritmus spočívá v iteračním výpočtu, kdy na počátku tuto množinu nastavíme jako prázdnou. V každém kroku pak do ní přidáme ty nonterminály, které se přepíšou na posloupnost symbolů, které jsou již v množině obsaženy. Výpočet opakujeme, dokud nastává nějaká změna.

Specifikace vstupu:

Vstupem programu je jméno souboru obsahujícího pravidla bezkontextové gramatiky ve formátu podle dokumentace k balíku grammar.

Specifikace výstupu:

Program vypíše na standardní výstup seznam neterminálních symbolů generujících prázdné slovo. Symboly budou odděleny mezerou.

Příklad:

Vstup:

   {Testovaci gramatika c. 1}
   A : b C | B d;
   B : C C | b A;
   C : c C | {e};

Výstup:

   B C