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 .
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.
O gramatică cu o structură de frază G este o structură algebrică , un cvadruplu ordonat (V T , V N , P, S), unde [1] :
Aici este setul tuturor șirurilor peste alfabet și este setul de șiruri nevide peste alfabet .
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:
,unde este orice șir nevid care conține cel puțin un simbol non-terminal [2] și este orice șir de simboluri din alfabet.
Datorită complexității lor, astfel de gramatici nu au nicio aplicație practică.
Acest tip include gramaticile dependente de context (KZ) și gramaticile care nu se scurtează. Pentru gramatică , toate regulile sunt [3] :
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.
Acest tip include gramaticile fără context (CS) . Pentru gramatică , toate regulile sunt:
Gramaticile COP sunt utilizate pe scară largă pentru a descrie sintaxa limbajelor de calculator (vezi analizarea ).
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ă:
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.
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.
Limbi formale și gramatici formale | |
---|---|
Concepte generale | |
Tip 0 | |
Tipul 1 |
|
Tip 2 | |
Tip 3 | |
analizare |