Gramatica formală

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

Gramatica formală , în teoria limbajelor formale , este o structură abstractă care descrie un limbaj formal într-un mod precis, adică este un sistem de reguli care delimitează matematic un set (de obicei infinit) de secvențe finite de simboluri ( șiruri ) aparținând unui alfabet de asemenea terminat.

Gramaticile formale se împart în două categorii principale: generativă și analitică .

  • O gramatică generativă , cel mai cunoscut gen, este un sistem de reguli prin care toate șirurile posibile din limbajul care trebuie descris sunt generate de rescrierea ulterioară a șirurilor începând cu un simbol inițial predefinit. O gramatică generativă, de fapt, formalizează un algoritm care generează șiruri lingvistice.
  • O gramatică analitică , pe de altă parte, este un sistem de reguli care presupune un șir arbitrar ca intrare și care ulterior reduce sau analizează șirul final de intrare acordând unui conector boolean un rezultat de tipul „da / nu” care indică dacă intrarea șirul este sau nu face parte din limbajul descris de gramatică. De fapt, o gramatică analitică descrie un analizor lingvistic.

Pe scurt, o gramatică analitică descrie cum să citești o limbă, în timp ce o gramatică generativă descrie cum să o scrii .

Gramatici generative

Pictogramă lupă mgx2.svg Același subiect în detaliu: Gramatică generativă .

O gramatică generativă constă dintr-un sistem de reguli pentru transformarea șirurilor. Pentru a genera un șir lingvistic, începem cu un șir constând dintr-un singur simbol principal și apoi aplicăm regulile (de câte ori, în orice ordine) pentru a rescrie acest șir. Limbajul constă din toate șirurile care pot fi generate în acest fel. Orice secvență particulară de alegeri juridice făcute în timpul acestui proces de rescriere garantează un anumit șir lingvistic și, dacă există mai multe moduri diferite de a genera un singur șir, atunci gramatica se numește gramatică ambiguă .

De exemplu, dacă avem un alfabet simbolul inițial și următoarele reguli de fabricație:

putem începe apoi cu „ „și alegem o regulă de aplicat. Dacă alegem regula 1, o vom înlocui cu a obtine " ". Dacă alegem din nou regula 1, vom înlocui„ 'cu' ' a obtine " „. Acest proces se repetă până când avem doar simboluri terminale. Pentru a încheia exemplul nostru, dacă alegem acum regula 2, vom înlocui„ 'cu' ' a obtine " ", și totul este gata. Putem scrie această serie de alegeri mai pe scurt, folosind simbolurile: . Limbajul gramaticii este sistemul tuturor șirurilor care pot fi generate folosind acest proces: .

Definiție formală

În formalizarea clasică a gramaticilor generative propusă pentru prima dată de Noam Chomsky în anii 1950, o gramatică constă dintr-o cvadruplă , in care

  1. sunt simbolurile non-terminale care pot fi rescrise
  2. sunt simbolurile terminale disjuncte de la
  3. axioma menționată este simbolul inițial non-terminal.
  4. sunt regulile de producție, o relație binară de cardinalitate finită pe , pe care în mod normal scriem ca
    unde este este vedeta lui Kleene și este uniunea simbolurilor cu restricția pe care o are partea stângă a unei reguli (de exemplu partea stângă a ) trebuie să conțină cel puțin un simbol non-terminal.

Limbajul generat de o gramatică formală , notat ca , este definit ca toate acele șiruri de caractere de pe care poate fi generată începând cu axioma și apoi aplicând în mod iterativ regulile de producție ale până când nu mai există simboluri non-terminale.

Se spune că două gramatici sunt echivalente între ele dacă și numai dacă generează același limbaj.

Exemplu

Luați în considerare, de exemplu, gramatica cu , , constând din următoarele reguli de producție

1.
2.
3.
4.

și simbolul non-terminal ca simbol al plecării. Câteva exemple de derivare a șirurilor în Sunt:

(unde regulile de producție utilizate sunt indicate între paranteze și partea înlocuită este indicată de fiecare dată cu caractere aldine).

Gramatica definește limbajul .

Gramaticile formative generative sunt identice cu sistemul Lindenmayer (sisteme L), cu excepția faptului că sistemele L nu sunt caracterizate printr-o distincție între terminal și non-terminal , sistemele L au restricții în ordinea în care sunt aplicate regulile și sistemele L pot funcționa pentru totdeauna, generând o secvență infinită de șiruri. De obicei, fiecare șir este asociat cu un sistem de puncte în spațiu, iar ieșirea sistemului L este definită ca granița acestor sisteme.

Ierarhia Chomsky

Pictogramă lupă mgx2.svg Același subiect în detaliu: Ierarhia Chomsky .
Chomsky-Hierarchy.jpg

Când Noam Chomsky a formalizat pentru prima dată gramaticile generative în anii 1950, le-a clasificat în patru tipuri cunoscute acum ca ierarhie Chomsky . Diferența dintre aceste tipuri este că au reguli stricte de producție și pot exprima mai puține limbaje formale. Două tipuri importante sunt: ​​gramaticile fără context (în italiană fără gramatică) și gramaticile obișnuite . Limbile care pot fi descrise cu o astfel de gramatică sunt denumite limbi fără context și , respectiv, limbi obișnuite . Deși mult mai puțin puternice decât gramaticile non-restrictive, care de fapt pot exprima orice limbaj care poate fi acceptat de o mașină Turing , aceste două tipuri restrânse de gramatică sunt cele mai utilizate, deoarece analizatorii folosiți pot fi folosiți eficient. De exemplu, pentru gramaticile non-contextuale există algoritmi binecunoscuți pentru generarea analizatorilor LL și a analizatorilor LR .

Gramatici fără context (tip 2)

Pictogramă lupă mgx2.svg Același subiect în detaliu: Context Free Grammar .

În gramaticile fără context, sau non-contextuale (în engleză context-free), partea stângă a unei reguli de producție poate fi formată numai dintr-un singur simbol non-terminal. Limbajul definit mai sus în exemplu nu este un limbaj fără context, ci limba da, deoarece poate fi definit prin gramatică cu următoarele reguli de producție:

1.
2.

În special, gramatica acestui exemplu este liniară , un subset adecvat de gramatici fără context, deoarece pe partea dreaptă există un singur simbol non-terminal, când pot avea mai multe.

Gramatici obișnuite (tip 3)

Pictogramă lupă mgx2.svg Același subiect în detaliu: Gramatică obișnuită .

În gramatica obișnuită , partea stângă este, ca și pentru gramaticile non-contextuale, doar un simbol non-terminal; mai mult, acum partea terminală este limitată în felul următor: poate fi nulă ( ), sau să fie în formă sau în formă , cu Și apartinand respectiv este la (adică poate fi nul sau un simbol terminal urmat, eventual, de un singur simbol non-terminal). Uneori se folosește o definiție mai largă: se poate da loc șirurilor mai lungi de terminale sau simbolurilor non-terminale, dar nimic altceva, în timp ce se definește aceeași clasificare lingvistică.

Limba descrisă mai sus nu este regulată, ci limba (cel puțin un „a” urmat de cel puțin un „b”, cu „a” și „b” în număr general diferit) este și poate fi definit prin gramatică cu următoarele reguli de producție:

1.
2.
3.
4.
5.

Alte forme de gramatică generativă

Mai multe extensii și variații ale ierarhiei Chomskiene originale a gramaticilor formale s-au dezvoltat recent, atât de lingviști, cât și de informaticieni, de obicei fie pentru a crește puterea expresivă, fie pentru a le simplifica pentru a le analiza sau analiza. Desigur, aceste două obiective tind spre egalitate: cu cât este mai expresiv un formalism gramatical, cu atât este mai dificil de analizat sau parsificat folosind instrumente automate. Unele forme de gramatică recent dezvoltate includ:

  • Gramatica arborelui crește expresivitatea gramaticilor generative convenționale, lăsând loc regulilor de rescriere pentru a opera pe arborii parser în loc de doar șiruri.
  • Gramatica accesorie și gramatica atributivă vă permit să rescrieți reguli pentru a fi îmbogățite cu atribute și operații semantice, utile atât pentru creșterea expresivității gramaticale, cât și pentru construirea unor instrumente practice de traducere lingvistică.

O conferință anuală este dedicată gramaticilor formale.

Gramatici analitice

Deși există o cantitate imensă de literatură cu privire la parsificarea algoritmică, majoritatea dintre ei presupun că limbajul este descris inițial prin intermediul gramaticii formale generative și că scopul este de a transforma această gramatică generativă într-un analizor funcțional. O abordare alternativă este formalizarea limbajului în termeni de gramatică analitică , care corespunde mai mult sau mai puțin direct structurii unui analizor lingvistic. Exemple de formalisme gramaticale analitice sunt următoarele:

Bibliografie

  • Giorgio Ausiello, Fabrizio D'Amore, Giorgio Gambosi, Limbaje de modelare a complexității, Milano, Franco Angeli Editore, 2003, ISBN 88-464-4470-1 .

Elemente conexe

linkuri externe

Conferință despre gramatici

Teoria automatelor : limbaje formale și gramatici formale
Ierarhia Chomsky Gramatica formală Limba Automat minim
Tipul-0 (nelimitat) Recursiv enumerabil Mașină Turing
(nelimitat) Recursiv Decider
Tipul 1 Context dependent Context dependent Automat liniar
Tipul 2 Fără context Fără context Automat cu baterie ND
Tipul 3 Regulat Regulat Stări finite
Fiecare categorie de limbă sau gramatică este un subset adecvat al categoriei imediat deasupra acesteia.
Controlul autorității GND ( DE ) 4154991-0