Gramatica formală

Gramatica formală sau doar gramatica în teoria limbilor formale este o modalitate de a descrie un limbaj formal, adică de a selecta un anumit subset din setul tuturor cuvintelor unui alfabet finit . Există gramatici generative și de recunoaștere (sau analitice ) - prima stabilește regulile cu care puteți construi orice cuvânt al limbii, iar a doua vă permite să determinați dintr-un anumit cuvânt dacă este inclus sau nu în limbă.

Termeni

Terminalul (simbolul terminalului) este un obiect care este direct prezent în cuvintele limbii corespunzătoare gramaticii și are un sens specific, neschimbabil (o generalizare a conceptului de „litere”). În limbile formale utilizate pe computer, toate sau o parte din caracterele standard ASCII - litere latine, numere și caractere speciale - sunt de obicei luate ca terminale .
Non-terminal (simbol non-terminal) este un obiect care denotă o entitate de limbaj (de exemplu: o formulă, o expresie aritmetică, o comandă) și nu are o valoare simbolică specifică.

Gramaticile generative

Cuvintele limbajului dat de gramatică sunt toate secvențele de terminale care sunt ieșite (generate) de la non-terminalul inițial conform regulilor de ieșire.

Pentru a seta gramatica, trebuie să setați alfabetele terminalelor și non-terminale, un set de reguli de inferență și, de asemenea, selectați-o pe cea inițială din setul de non-terminale.

Deci, gramatica este definită de următoarele caracteristici:

$\Sigma$ — set ( alfabet ) de simboluri terminale
N este un set ( alfabet ) de simboluri non-terminale
P este un set de reguli de forma: „partea stângă” „partea dreaptă”, unde: $\sageata dreapta$
- „partea stângă” este o secvență nevidă de terminale și non-terminale care conține cel puțin un non-terminal
- „partea dreaptă” - orice succesiune de terminale și non-terminale
S este simbolul de început (sau inițial) al gramaticii din setul de non-terminale.

Concluzie

O ieșire este o secvență de linii formată din terminale și non-terminale, unde prima linie este o linie formată dintr-un neterminal de pornire, iar fiecare linie ulterioară este obținută de la cea anterioară prin înlocuirea unui subșir în funcție de unul (orice) a regulilor. Șirul final este un șir format în întregime din terminale și, prin urmare, este un cuvânt al limbii.

Existența unei derivații pentru un anumit cuvânt este un criteriu de apartenență a acestuia la limba definită de gramatica dată.

Tipuri de gramatici

Conform ierarhiei Chomsky , gramaticile sunt împărțite în 4 tipuri, fiecare ulterioară fiind un subset mai limitat față de cel precedent (dar și mai ușor de analizat):

tip 0. gramatici nelimitate – orice reguli sunt posibile
tip 1. gramatici sensibile la context - partea din stânga poate conține un neterminal înconjurat de un „context” (secvențe de caractere care sunt prezente în aceeași formă în partea dreaptă); non-terminalul în sine este înlocuit cu o secvență nevidă de caractere în partea dreaptă.
tipul 2. gramatici fără context — partea din stânga este formată dintr-un non-terminal.
tipul 3. gramaticile obișnuite sunt mai simple, echivalente cu automatele finite .

În plus, există:

Gramaticile care nu se scurtează . Fiecare regulă a unei astfel de gramatici are forma , unde . Lungimea laturii drepte a regulii nu este mai mică decât lungimea laturii stângi [1] . $\alpha \rightarrow \beta$ $|\alpha |\leqslant |\beta |$
Gramatici liniare . Fiecare regulă a unei astfel de gramatici are forma , sau , adică partea dreaptă a regulii nu poate conține mai mult de o apariție a unui non-terminal [2] . $A\rightarrow uBv$ $A\rightarrow u$

Aplicație

Gramaticile fără context sunt aplicate pe scară largă pentru a defini structura gramaticală în analiza gramaticală .
Gramaticile obișnuite (sub formă de expresii regulate ) sunt utilizate pe scară largă ca șabloane pentru căutarea, defalcarea și înlocuirea textului, inclusiv în analiza lexicală .

Un exemplu sunt expresiile aritmetice

Luați în considerare un limbaj simplu care definește un subset limitat de formule aritmetice constând din numere naturale , paranteze și semne aritmetice. Este de remarcat faptul că aici în fiecare regulă din partea stângă a săgeții există un singur simbol non-terminal. Astfel de gramatici sunt numite fără context . $\sageata dreapta$

Alfabetul terminalului:

\Sigma

= {'0','1','2','3','4','5','6','7','8','9','+','-', '*','/','(',')'}

Alfabetul non-terminal:

{ FORMULĂ, SEMN, NUMĂR, NUMĂR }

Reguli:

1. FORMULA FORMULA SEMNE FORMULA

\la

(o formulă are două formule legate printr-un semn) 2. NUMĂR DE FORMULĂ

\la

(formula este un număr) 3. FORMULA ( FORMULA )

\la

(o formulă este o formulă între paranteze) 4. SEMNARE + | - | * | /

\la

(semnul este plus sau minus, sau înmulțire sau împărțire) 5. CIFRE NUMĂR

\la

(un număr este un număr) 6. NUMĂR NUMĂR CIFRE

\la

(un număr este un număr și un număr) 7. NUMĂRUL 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

\la

(cifra este 0 sau 1 sau ... 9)

Inițial non-terminal:

FORMULĂ

Concluzie :

Să derivăm formula (12+5) folosind regulile de inferență enumerate. Pentru claritate, părțile laterale ale fiecărei înlocuiri sunt afișate în perechi, în fiecare pereche piesa înlocuită este subliniată.

FORMULĂ (FORMULĂ)

{\stackrel {3}{\to ))

( FORMULĂ ) ( FORMULĂ SEMNE FORMULĂ )

{\stackrel {1}{\to ))

(FORMULA SEMNE DE FORMULĂ) (FORMULĂ + FORMULĂ)

{\stackrel {4}{\to ))

( FORMULA + FORMULĂ ) ( FORMULĂ + NUMĂR )

{\stackrel {2}{\to ))

( FORMULA + NUMĂR ) ( FORMULĂ + NUMĂR )

{\stackrel {5}{\to ))

(FORMULĂ + NUMĂR ) (FORMULĂ + 5 )

{\stackrel {7}{\to ))

( FORMULĂ + 5) ( NUMĂR + 5)

{\stackrel {2}{\to ))

( NUMĂR + 5) ( NUMĂR CIFRA + 5)

{\stackrel {6}{\to ))

( CIFRE NUMĂR + 5) ( CIFRE + 5)

{\stackrel {5}{\to ))

( CIFRE + 5) ( 1 CIFRE + 5)

{\stackrel {7}{\to ))

(1 CIFRE + 5) (1 2 + 5)

{\stackrel {7}{\to ))

Gramatici analitice

Gramaticile generative nu sunt singurele tipuri de gramatici, dar sunt cele mai comune în aplicațiile de programare. Spre deosebire de gramaticile generative, gramatica analitică (recunoașterea) definește un algoritm care vă permite să determinați dacă un anumit cuvânt aparține limbii. De exemplu, orice limbaj obișnuit poate fi recunoscut folosind o gramatică definită de o mașină de stări și orice gramatică fără context poate fi recunoscută folosind un automat bazat pe stivă . Dacă un cuvânt aparține unei limbi, atunci un astfel de automat își construiește rezultatul într-o formă explicită, ceea ce face posibilă analiza semantică a acestui cuvânt.

Vezi și

JFLAP - simulator de automate, mașini Turing, gramatici
analizare
Gramatică ambiguă
Problema minimă de gramatică
Gramatică cu structură a frazei

Literatură

Belousov A. I., Tkachev S. B. Matematică discretă. — M .: MGTU , 2006. — 743 p. — ISBN 5-7038-2886-4 .
Gladkiy A. V. Gramatici și limbi formale. — M .: Nauka, 1973.
Kasyanov VN Prelegeri despre teoria limbajelor formale, automate și complexitate computațională. - Novosibirsk: NGU, 1995. - 112 p.
Chomsky N., Miller J. Introducere în analiza formală a limbajelor naturale // Colecția cibernetică / Ed. A.A. Lyapunova și O.B. Lupanova. — M .: Mir, 1965.
Gross M., Lanten A. Teoria gramaticilor formale. — M .: Mir, 1971. — 296 p.

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