Chomského hierarchie

Chomského hierarchie je klasifikace formálních jazyků a formálních gramatik , podle které jsou rozděleny do 4 typů podle jejich podmíněné složitosti. Navrhl profesor MIT , lingvista Noam Chomsky .

Klasifikace gramatik

Formální gramatiky lze podle Chomského rozdělit do čtyř typů. Pro přiřazení gramatiky ke konkrétnímu typu je nutné, aby všechna její pravidla (produkce) odpovídala určitým schématům.

Typ 0 - Neomezeno

Gramatika s frázovou strukturou G je algebraická struktura , uspořádaná čtveřice (V T , V N , P, S), kde [1] :

$V_{T}$ — abeceda (soubor) symbolů terminálů — terminály ,
$V_{N}$ — abeceda (množina) neterminálních symbolů — neterminálové ,
$V=V_{T}\pohár V_{N}$ - navíc slovník $G$ $V_{T}\cap V_{N}=\varnothing$
$P$ je konečná množina produkcí (pravidel) gramatiky, $P\subseteq V^{+}\times V^{*}$
$S$ - počáteční znak ( zdroj ).

Zde je množina všech řetězců v abecedě a je to množina neprázdných řetězců v abecedě . $V^*$ $PROTI$ $V^{+}$ $PROTI$

Typ 0 podle Chomského klasifikace zahrnuje neomezené gramatiky - gramatiky s frázovou strukturou , tedy všechny formální gramatiky bez výjimky. Pravidla lze napsat takto:

\alpha \šipka doprava \beta

kde je libovolný neprázdný řetězec obsahující alespoň jeden neterminální [2] symbol a je libovolný řetězec symbolů z abecedy. ${\displaystyle \alpha \in V^{+))$ $\beta \in V^{*}$

Vzhledem ke své složitosti nemají takové gramatiky praktické využití.

Typ 1 – kontextově citlivý

Tento typ zahrnuje kontextově závislé (KZ) gramatiky a gramatiky bez zkrácení. Pro gramatiku jsou všechna pravidla [3] : $G(V_{T},V_{N},P,S),V=V_{T}\pohár V_{N}$

$\alpha A\beta \rightarrow \alpha \gamma \beta$ , kde . Takové gramatiky se označují jako kontextově citlivé. $\alpha ,\beta \in V^{*},\gamma \in V^{+},A\in V_{N}$
$\alpha \šipka doprava \beta$ , kde . Takové gramatiky jsou klasifikovány jako nezkrácené. $\alpha ,\beta \in V^{+},1\leq |\alpha |\leq |\beta |$

Tyto třídy gramatik jsou ekvivalentní. Lze je použít při analýze textů v přirozených jazycích, ale při konstrukci překladačů se pro svou složitost prakticky nepoužívají. U kontextově závislých gramatik je dokázáno tvrzení: pomocí nějakého algoritmu lze v konečném počtu kroků určit, zda řetězec terminálních symbolů patří k danému jazyku či nikoli.

Typ 2 - bezkontextový

Tento typ zahrnuje bezkontextové (CS) gramatiky . Pro gramatiku platí všechna pravidla: $G(V_{T},V_{N},P,S),V=V_{T}\pohár V_{N}$

$A\šipka doprava\beta$ , kde (pro nezkrácené CF-gramatiky) nebo (pro zkrácení), . To znamená, že gramatika umožňuje, aby se na levé straně pravidla objevil pouze neterminální symbol . $\beta \in V^{+}$ $\beta \in V^{*}$ $A\in V_{N}$

Gramatiky COP se široce používají k popisu syntaxe počítačových jazyků (viz parsování ).

Typ 3 - běžný

Třetí typ zahrnuje regulární gramatiky (automatické) - nejjednodušší z formálních gramatik. Jsou bezkontextové, ale s omezenou funkčností.

Všechny regulární gramatiky lze rozdělit do dvou ekvivalentních tříd, které pro gramatiku typu III budou mít pravidla v následujícím tvaru:

$A\šipka doprava B\gama$ nebo , kde (pro levolineární gramatiky). $A\šipka doprava\gama$ $\gamma \in V_{T}^{*},A,B\in V_{N}$
$A\šipka doprava\gama B$ ; nebo , kde (pro pravo-lineární gramatiky). $A\šipka doprava\gama$ $\gamma \in V_{T}^{*},A,B\in V_{N}$

Regulární gramatiky se používají k popisu nejjednodušších konstrukcí: identifikátory , řetězce , konstanty , stejně jako jazyky symbolických instrukcí , příkazové procesory atd.

Klasifikace jazyků

Formální jazyky jsou klasifikovány podle typů gramatik, které je definují. Stejný jazyk však může být definován různými gramatikami, které patří k různým typům. V tomto případě se má za to, že jazyk patří k nejjednodušším z nich. Takže jazyk popsaný gramatikou s frázovou strukturou, kontextovými a bezkontextovými gramatikami bude bezkontextový.

Stejně jako u gramatik je složitost jazyka určena jeho typem. Nejsložitější jsou jazyky s frázovou strukturou (to zahrnuje přirozené jazyky), dále - KZ-jazyky, KS-jazyky a nejjednodušší - regulární jazyky.

Poznámky

↑ Cook, Baze, 1990 , str. 258,264.
↑ Serebryakov V. A., Galochkin M. P., Gonchar D. R., Furugyan M. G. Teorie a implementace programovacích jazyků. - M. : MZ-Press, 2006. - S. 21. - ISBN 5-94073-094-9 .
↑ Cook, Baze, 1990 , str. 268.

Literatura

Molchanov A. Yu. Systémový software. Petrohrad: Petr, 2006.
John Hopcroft , Rajiv Motwani , Jeffrey Ullman . KAPITOLA 5. Bezkontextové gramatiky a jazyky // Úvod do teorie automatů, jazyků a počítání. - M .: "Williams" , 2002. - S. 528. - ISBN 0-201-44124-1 .
Serebryakov V. A. , Galochkin M. P., Gonchar D. R., Furugyan M. G. Teorie a implementace programovacích jazyků - M.: MZ-Press, 2006, 2. vyd. — ISBN 5-94073-094-9
Robin Hunter . Základní koncepty kompilátorů = The Essence of Compilers. - M .: "Williams" , 2002. - S. 256. - ISBN 5-8459-0360-2 .
Cook D., Baze G. Kapitola 8. Jazyky a gramatiky // Počítačová matematika = Počítačová matematika. - M .: Věda. Fizmatlit, 1990. - 384 s. — ISBN 5-02-014216-6 .

Formální jazyky a formální gramatiky
Obecné pojmy	Chomského hierarchie Abeceda Slovo
Typ 0	Neomezená gramatika Turingův stroj výčtový jazyk Řešitelný jazyk
Typ 1	Kontextově citlivá gramatika Kontextový jazyk Lineárně ohraničený automat
Typ 2	Bezkontextová gramatika Nejednoznačná gramatika Bezkontextový jazyk Zásobníkový automat ( deterministický ) Růstové lemma Ogdenovo lemma Cookova věta
Typ 3	Pravidelná gramatika regulární jazyk Regulární výraz Stavový stroj ( deterministický , nedeterministický ) Minimalizace DFA Stanovení NFA Myhillova-Nerodova věta
rozebrat	LL analyzátor LR analyzátor Metoda rekurzivního sestupu Kok-Younger-Kasami algoritmus