Gramatică fără context

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 3 ianuarie 2022; verificarea necesită 1 editare .

Gramatica fără context ( CS-gramatică , gramatică fără context ) este un caz special de gramatică formală (tip 2 conform ierarhiei Chomsky ), în care părțile din stânga tuturor producțiilor sunt unice non -terminale (obiecte care denotă orice esență a limba (de exemplu: o formulă, o expresie aritmetică, o comandă) și neavând o semnificație simbolică specifică). Sensul termenului „fără context” este că este posibil să se aplice producția unui non-terminal și, în plus, indiferent de contextul acestui non-terminal (spre deosebire de cazul general al gramaticii Chomsky nerestricționate ).

Un limbaj care poate fi specificat de un CFG se numește limbaj fără context sau CFL.

De fapt, gramatica KS este o altă formă de BNF .

Aplicație

Gramaticile COP au o mare utilizare în informatică . Acestea stabilesc structura gramaticală a majorității limbajelor de programare , datele structurate etc. (vezi analiza gramaticală )

Pentru a analiza o gramatică COP, este suficient un automat push-down , pentru a analiza gramatici non-COP, poate fi necesară o mașină completă Turing .

Tipuri de gramatici CS

Gramatica LL
Gramatica LALR (vezi: LALR(1) )
gramatica LR
Gramatica SLR (vezi: SLR(1) )

Recunoașteri

Există două clase diferite de recunoaștere (automate pentru recunoaștere) a limbajelor CF. Numele lor sunt legate de ordinea în care este construit arborele de ieșire. De regulă, toți recunoaștetorii citesc șirul de caractere de intrare de la stânga la dreapta, deoarece o astfel de notație este așteptată în scrierea codului sursă al programelor.

Rezolvatori din aval

Rezolutoare de sus în jos care generează lanțuri de ieșire din stânga și construiesc arborele de ieșire de sus în jos.

Ei folosesc modificări ale algoritmului cu selecția alternativelor. Când le creați, este utilizată o metodă care vă permite să selectați în mod unic una și o singură alternativă la fiecare pas al automatului MP (pasul de „ejectare” din acest automat este întotdeauna efectuat în mod unic).

Recunoașteri ascendenți

Rezolvatoare de jos în sus care generează lanțuri de ieșiri dreptaci și construiesc arborele de ieșire de jos în sus.

Recunoaștetorii din amonte folosesc modificări ale algoritmului shift-fold (sau shift-fold, care este același). Atunci când le creați, sunt utilizate metode care vă permit să alegeți fără ambiguitate între efectuarea unei „schimbări” („transfer”) sau „convoluție” la fiecare pas al automatului MP extins, iar când se efectuează convoluția, puteți alege fără ambiguitate regula prin care se va executa circumvolutia. Algoritmul „shift-convolution”.

Exemple

Exemple de gramatici SF și limbi SF corespunzătoare:

Întoarce cuvântul

Dată prin formulă $L=\{w\in \Sigma ^{*}|w=w^{R}\}$

Terminale: litere ale alfabetului ; $\Sigma$
Neterminal: ; $S$
Produse: $S\rightarrow \alpha S\alpha \,|\,\alpha \,|\,\varepsilon ,\alpha \in \Sigma$
Non-terminalul inițial este . $S$

Paranteze imbricate

Terminale: și ; $($ $)$
neterminal: ; $S$
produse: ; $S\rightarrow (S)\mid \varepsilon$
initial neterminal - . $S$

Această gramatică specifică limbajul parantezelor imbricate . $\{\left(^{n}\right)^{n}\mid n\geq 0\}$

Limba lui Dick

Expresie aritmetică

Terminale: '+', '-', '*', '/', '(', ')', 'x'
nonterminale: <expresie>, <termen>, <multiplicator>
produse:

<expresie> → <expresie> + <termen>, <expresie> → <expresie> - <termen>, <expresie> → <termen>, <term> → <term> * <multiplicator>, <term> → <term> / <multiplicator>, <term> → <multiplicator>, <multiplicator> → ( <expresie> ), <multiplicator> → x,

initial neterminal: <expresie>.

Această gramatică definește o expresie aritmetică care conține cele mai simple operații aritmetice asupra variabilei x. Dacă înlocuim terminalul „x” cu <numărul> neterminal, obținem o gramatică care specifică o expresie aritmetică constând din operații de adunare, scădere, înmulțire și împărțire pe numere întregi.

Limitările COP-gramatici

Nu toate limbile pot fi definite folosind gramatici CF. Cel mai simplu mod de a demonstra acest lucru este următorul: COP-gramaticile formează un set numărabil, în timp ce cardinalitatea setului tuturor limbilor este un continuum . O dovadă constructivă a aceluiași fapt poate fi obținută, de exemplu, pe baza faptului că limbajul { a n b n c n | n ≥1} nu este lipsit de context; totuși, nu pare să existe o dovadă scurtă a ultimei afirmații: dovezile publicate se bazează pe teorema de creștere pentru limbaje fără context.

Generalizări

Gramatica de adăugare a arborelui generalizează gramatica fără context prin faptul că unitatea elementară din regulile de inferență sunt arborii, nu caracterele individuale.

Vezi și

Literatură

John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Introducere în teoria automatelor, limbaje și calcul. - M .: „Williams” , 2002. - S. 528. - ISBN 0-201-44124-1 .
Belousov A. I., Tkachev S. B. Matematică discretă. — M .: MGTU , 2006. — 743 p. — ISBN 5-7038-2886-4 .

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