# XBUP - Specifikace bloků: Gramatiky

### Úvod

Tento dokument je součástí dokumentace projektu eXtensible Binary Universal Protocol. Obsahuje způsob kódování matematických automatů do protokolu XBUP.

O úroveň výše

### Obsah

1. Gramatiky
1.1. Chomského hierarchie gramatik a jazyků
1.2. Regulární gramatika
1.3. Bezkontextová gramatika
1.4. Kontextová gramatika
1.5. Gramatika typu 0
2. Rozšířené informace
3. Operace s gramatikami

### 1. Gramatiky

Tato skupina bloků slouží pro definici matematických gramatik. Gramatika je čtveřice (N, Σ, P, S), kde:

N je neprázdná konečná množina neterminálních symbolů
Σ je je konečná množina terminálních symbolů disjunktní s N
V označujeme sjednocení N a Σ
P je konečná množina pravidel, podmnožina V* N V* x V*, píšeme ve tvaru α → β
S je počáteční neterminální symbol

Z tohoto plyne základní struktura gramatiky:

Regulární gramatika
- množina terminálů
- množina neterminálů
- množina pravidel

Zřejmě hodnota S by mohla být vhodným kandidátem na atribut, případně by bylo možné ji stanovit napevno na první neterminál. Stejně tak je možné množiny terminálů a neterminálů degradovat na jediný atribut, tedy počet prvků.

Přidělená adresa v katalogu: XBUPProject/Math/Grammar

### 1.1. Chomského hierarchie gramatik a jazyků

Na základě omezení na tvar pravidel, jsou gramatiky obvykle děleny do následujích čtyř skupin:

- Typ 0 - Libovolná gramatika: Na pravidla nejsou kladena žádná omezení
- Typ 1 - Kontextová gramatika: Pro každé pravidlo platí, že (α → β) => |α| < |β|.
- Typ 2 - Bezkontextová gramatika: Pravidla jsou tvaru A → α, kde |α| >= 1, případně s výjimkou S → ε, pokud S není na levé straně žádného pravidla.
- Typ 3 - Regulární gramatika: Pravidla jsou tvaru A → aB, případně s výjimkou S → ε, pokud S není na levé straně žádného pravidla.

### 1.2. Regulární gramatika

Jelikož jsou pravidla uvedeného tvaru, můžeme pravidla gramatiky definovat následně:

Blok pravidlo gramatiky RegularRule:

UBNatural LeftNonterminal - Index neterminálu
UBNatural RightTerminal - Index terminálu
UBNatural RightNonterminal - Index neterminálu (0 = žádný neterminál, ostatní posunutá)

Regulární gramatika RegularGrammar:

UBNatural NonterminalCount - Počet neterminálů
UBNatural TerminalCount - Počet terminálů (znaků abecedy)
UBBoolean IncludeEmptyString - Indikace, zda gramatika zahrnuje prázdné slovo

### 1.3. Bezkontextová gramatika

Bezkontextová gramatika definuje pravidlo a jeho jednotlivé položky jako podbloky. Podbloky jsou dvou typů, terminál a neterminál a oba jsou odkazem do odpovídajících množin.

### 1.4. Kontextová gramatika

Kontextová gramatika je rozšířením bezkontextové o sekvenci vstupní strany.

### 1.5. Gramatika typu 0

.

### 1.6. Další gramatiky

Mezi další gramatiky je možné zahrnout například deterministickou bezkontextovou gramatiku, či gramatiku rekurzivních jazyků.

### 1.x. Validace gramatiky

Jelikož není možné zaručit platnost některých pravidel, je nutné zavést algoritmus na ověření platnosti gramatiky. Ověřit je nutné především následující podmínky:

- Indexy terminálů a neterminálů jsou v platném rozsahu
- Pokud je zahrnuto pravidlo S → ε, pak u bezkontextových a regulárních gramatik nesmí být S obsaženo na levé straně pravidka
- Pravidla tvoří množinu (neobsahují stejné pravidlo dvakrát)

### 2. Rozšířené informace

Kromě základní informace o gramatice je možné zahrnout další pomocné údaje týkající se především zobrazení struktury gramatiky, jako je například textové vyjádření terminálů a neterminálů

### 3. Operace s gramatikami

S gramatikami je možné provádět řadu operací a transformací. Lze například ověřovat náležitost řetězce do gramatiky, generovat množinu všech slov či transformovat gramatiku na ekvivalentní vyjádření jiným typem matematického stroje. Tyto operace je pak možné i nechat zpracovat i např. pomocí vzdáleného volání funkcí.

### 3.1. Operace nad více gramatikami

Gramatiky je možné porovnávat, vytvářet sjednocení, průnik, rozdíl, doplněk a další operace. Některé z těchto operací nejsou pro některé gramatiky proveditelné, nebo mají velkou časovou složitost.

### 4. Reference

Seznam zdrojů, literatury a relevantních odkazů.

Formální gramatiky [http://en.wikipedia.org/wiki/Formal_grammar]

Homepage: http://xbup.sf.net
License: GNU Free Documentation License (FDL)
Latest update: 2007-06-05