Ierarhia Chomsky

Ierarhia Chomsky este o clasificare a limbilor formale și a gramaticilor formale , conform căreia acestea sunt împărțite în 4 tipuri în funcție de complexitatea lor condiționată. Propus de profesorul MIT , lingvistul Noam Chomsky .

Clasificarea gramaticilor

Potrivit lui Chomsky, gramaticile formale pot fi împărțite în patru tipuri. Pentru a atribui o gramatică unui anumit tip, este necesar ca toate regulile (producțiile) acesteia să corespundă anumitor scheme.

Tip 0 - Nelimitat

O gramatică cu o structură de frază G este o structură algebrică , un cvadruplu ordonat (V T , V N , P, S), unde [1] :

$V_{T}$ — alfabet (set) de simboluri terminale — terminale ,
$V_{N}$ — alfabet (set) de simboluri non-terminale — non -terminale ,
$V=V_{T}\cup V_{N}$ - dicționar , în plus $G$ $V_{T}\cap V_{N}=\varnothing$
$P$ este un set finit de producții (reguli) ale gramaticii, $P\subseteq V^{+}\time V^{*}$
$S$ - caracterul de început ( sursa ).

Aici este setul tuturor șirurilor peste alfabet și este setul de șiruri nevide peste alfabet . $V^*$ $V$ $V^{+}$ $V$

Tipul 0 conform clasificării lui Chomsky include gramaticile nerestricționate - gramaticile cu structură de frază , adică toate gramaticile formale fără excepție. Regulile pot fi scrise astfel:

\alpha \rightarrow \beta

unde este orice șir nevid care conține cel puțin un simbol non-terminal [2] și este orice șir de simboluri din alfabet. $\alpha \in V^{+)$ $\beta \in V^{*}$

Datorită complexității lor, astfel de gramatici nu au nicio aplicație practică.

Tip 1 - sensibil la context

Acest tip include gramaticile dependente de context (KZ) și gramaticile care nu se scurtează. Pentru gramatică , toate regulile sunt [3] : $G(V_{T},V_{N},P,S),V=V_{T}\cup V_{N}$

$\alpha A\beta \rightarrow \alpha \gamma \beta$ , unde . Astfel de gramatici sunt denumite sensibile la context. $\alpha ,\beta \in V^{*},\gamma \in V^{+},A\in V_{N}$
$\alpha \rightarrow \beta$ , unde . Astfel de gramatici sunt clasificate ca non-scurtare. $\alpha ,\beta \in V^{+},1\leq |\alpha |\leq |\beta |$

Aceste clase de gramatici sunt echivalente. Ele pot fi folosite în analiza textelor în limbaje naturale, dar practic nu sunt folosite în construcția compilatoarelor din cauza complexității lor. Pentru gramaticile dependente de context, se demonstrează afirmația: printr-un algoritm, într-un număr finit de pași, este posibil să se determine dacă un lanț de simboluri terminale aparține sau nu unui anumit limbaj.

Tip 2 - fără context

Acest tip include gramaticile fără context (CS) . Pentru gramatică , toate regulile sunt: $G(V_{T},V_{N},P,S),V=V_{T}\cup V_{N}$

$A\săgeată la dreapta\beta$ , unde (pentru gramatici CF care nu se scurtează) sau (pentru cele care scurtează), . Adică, gramatica permite să apară doar un simbol non-terminal în partea stângă a regulii . $\beta \in V^{+}$ $\beta \in V^{*}$ $A\în V_{N}$

Gramaticile COP sunt utilizate pe scară largă pentru a descrie sintaxa limbajelor de calculator (vezi analizarea ).

Tip 3 - obișnuit

Al treilea tip include gramaticile obișnuite (automate) - cea mai simplă dintre gramaticile formale. Sunt fără context, dar cu funcționalitate limitată.

Toate gramaticile obișnuite pot fi împărțite în două clase echivalente, care, pentru o gramatică de tip III, vor avea reguli de următoarea formă:

$A\rightarrow B\gamma$ sau , unde (pentru gramatici liniare stânga). $A\săgeată la dreapta\gamma$ $\gamma \in V_{T}^{*},A,B\in V_{N}$
$A\săgeată la dreapta\gama B$ ; sau , unde (pentru gramatici liniare dreapta). $A\săgeată la dreapta\gamma$ $\gamma \in V_{T}^{*},A,B\in V_{N}$

Gramaticile obișnuite sunt folosite pentru a descrie cele mai simple constructe: identificatori , șiruri de caractere , constante , precum și limbaje de asamblare , procesoare de comandă etc.

Clasificarea limbilor

Limbile formale sunt clasificate în funcție de tipurile de gramatici care le definesc. Cu toate acestea, aceeași limbă poate fi definită prin gramatici diferite aparținând unor tipuri diferite. În acest caz, se consideră că limba aparține celor mai simple dintre ei. Deci, un limbaj descris de o gramatică cu o structură de frază, gramatici sensibile la context și fără context va fi fără context.

Ca și în cazul gramaticilor, complexitatea unei limbi este determinată de tipul acesteia. Cele mai complexe sunt limbile cu o structură de frază (aceasta include limbile naturale), apoi - limbile KZ, limbile KS, iar cele mai simple - limbile obișnuite.

Note

↑ Cook, Baze, 1990 , p. 258.264.
↑ Serebryakov V. A., Galochkin M. P., Gonchar D. R., Furugyan M. G. Teoria și implementarea limbajelor de programare. - M. : MZ-Press, 2006. - S. 21. - ISBN 5-94073-094-9 .
↑ Cook, Baze, 1990 , p. 268.

Literatură

Molchanov A. Yu. Software de sistem. Sankt Petersburg: Peter, 2006.
John Hopcroft , Rajiv Motwani , Jeffrey Ullman . CAPITOLUL 5. Gramatici și limbaje fără context // Introducere în teoria automatelor, limbaje și calcul. - M .: „Williams” , 2002. - S. 528. - ISBN 0-201-44124-1 .
Serebryakov V. A. , Galochkin M. P., Gonchar D. R., Furugyan M. G. Teoria și implementarea limbajelor de programare - M.: MZ-Press, 2006, ed. a 2-a. — ISBN 5-94073-094-9
Robin Hunter . Concepte de bază ale compilatorului = Esența compilatorilor. - M . : „Williams” , 2002. - S. 256. - ISBN 5-8459-0360-2 .
Cook D., Baze G. Capitolul 8. Limbi și gramatici // Computer Mathematics = Computer Mathematics. - M .: Știință. Fizmatlit, 1990. - 384 p. — ISBN 5-02-014216-6 .

Limbi formale și gramatici formale
Concepte generale	Ierarhia Chomsky Alfabet Cuvânt
Tip 0	Gramatică nelimitată mașină Turing limbaj enumerat Limbajul rezolvabil
Tipul 1	Gramatică sensibilă la context Limbaj sensibil la context Automat delimitat liniar
Tip 2	Gramatică fără context Gramatică ambiguă Limbaj fără context Automat Pushdown ( determinist ) Lema de creștere Lema lui Ogden Teorema lui Cook
Tip 3	Gramatica obișnuită limbaj obișnuit Expresie uzuala Mașină de stări ( deterministă , nedeterministă ) Minimizarea DFA Determinarea NFA Teorema Myhill-Nerode
analizare	Analizor LL Analizor LR Metoda coborârii recursive Algoritmul Kok-Younger-Kasami