====== Chart parser ======
{{template>spolecne}}

Napište program v Perlu, který načte bezkontextovou gramatiku a řetězec terminálů a vypíše všechny analýzy řetězce podle gramatiky.

Vytvořte si zkušební gramatiku (může modelovat tvarosloví nebo větné vztahy některého přirozeného jazyka), na které parser předvedete v prosinci ostatním.

===== Vstup =====

Jak gramatika, tak analyzovaný řetězec jsou v UTF-8. Řetězec k analýze se čte ze standardního vstupu (STDIN), gramatika je uložena v souboru, jehož jméno dostaneme v $ARGV[0].

Analyzovaný řetězec je jediné slovo. Každý znak je samostatným terminálem. Mezerový znak nebo EOF ukončuje vstup. Alternativně rozšířená verze: text je delší, rozsekaný na slova, samostatně analyzovat vše od <f(>|.*?>) do <.

===== Formát gramatiky =====

Každé pravidlo je na samostatném řádku. To platí i pro více pravidel se shodnou levou stranou. Pravé strany se neshlukují (např. pomocí operátoru |), nýbrž se rozepíší jako samostatná pravidla.

Neterminál se pozná tak, že se v některém pravidle vyskytuje na levé straně. Neterminál na levé straně prvního pravidla je počáteční symbol gramatiky.

Jednotlivé symboly (terminály i neterminály) na pravé straně jsou odděleny jedním nebo více mezerovými znaky.

"->" je zvláštní znak, oddělující levou a pravou stranu pravidla. Pokud by se tyto dva znaky měly vyskytnout jako terminály na pravé straně pravidla, bude mezi nimi mezera.

===== Příklad gramatiky =====

<code>S -> C D
S -> Ab1 B C D
C -> m a t
D -> k a
D -> k y
D -> c e
D -> k u</code>

===== Formát výstupu =====

Výstupem je seznam všech nalezených složek, které jsou součástí alespoň jedné z analýz. U každé složky je uveden rozsah. U každé složky jsou také uvedeny odkazy na bezprostřední podsložky, ze kterých se může skládat. Potenciálně obrovská množina derivačních stromů je tedy sbalena do relativně malého seznamu složek.

Jestliže vstupní řetězec neodpovídá gramatice, je výstupem jediná podsložka s vyznačením této chyby. Syntaxi demonstruje následující příklad:

<code><slozka id="S02" nazev="S" od="0" do="2">
  <sloz><podsl ref="A01"/><podsl ref="B12"/></sloz>
  <sloz><podsl ref="Hugo"/></sloz>
</slozka>

<slozka id="A01" nazev="A" od="0" do="1">
  <sloz>a</sloz>
</slozka>

<slozka id="Hugo" nazev="A" od="0" do="2">
  <sloz>ab</sloz>
  <sloz>a<podsl ref="B12"/></sloz>
</slozka>

<slozka typ="negram" od="0" do="8">
  <sloz>bflmpsvz</sloz>
</slozka></code>

Komentáře k příkladu:
  * Id složky může být libovolné a nesouvisí s neterminálem, který složce odpovídá v gramatice. Jméno neterminálu totiž musí být každopádně uvedeno ve zvláštním atributu nazev.
  * <sloz> popisuje jeden možný rozklad složky nad dotyčným řetězcem. Vedle sebe může paralelně existovat několik takových rozkladů, protože celý řetězec může mít několik analýz s různými derivačními stromy.
  * Uvnitř <sloz> mohou být terminály (nejsou odděleny mezerami), odkazy na podsložky (značky <podsl>) nebo kombinace obojího.
  * Jestliže řetězec nepatří do jazyka generovaného gramatikou, je výstupem jediná složka s rozsahem pokrývajícím celý řetězec, jejímž obsahem je přímo tento řetězec (terminálů). Složka nemá atribut nazev, zato má atribut typ="negram".