Gramatică fără context

În informatică și lingvistică, o gramatică fără context (sau non-contextuală , fără context sau CFG ) este o gramatică formală în care fiecare regulă sintactică este exprimată sub forma derivării unui simbol din stânga începând de la unul sau mai multe simboluri un drept. Acest lucru poate fi exprimat cu două simbolisme echivalente (al doilea simbolism va fi folosit în următoarele):

V :: = w

V → w

unde V este un simbol non-terminal și w este o secvență de simboluri terminale și non-terminale. Termenul „fără context” se referă la faptul că simbolul non-terminal V poate fi întotdeauna înlocuit cu w , indiferent de simbolurile care îl preced sau îl urmează. Se spune că un limbaj formal este lipsit de context dacă există o gramatică fără context care o generează.

Descriere

În ierarhia Chomsky , gramaticile fără context sunt numite Tip 2.

Gramaticile fără context sunt suficient de puternice pentru a descrie sintaxa majorității limbajelor de programare ; în același timp, sunt suficient de simple pentru a permite o analiză foarte eficientă.

Notația formală Backus-Naur (BNF) este cea mai frecvent utilizată sintaxă pentru a descrie gramaticile fără context. Nu toate limbajele formale sunt libere de context - un bine-cunoscut contraexemplu este următorul $\{a^{n}b^{n}c^{n}:n\geq 0\}$ ${\ displaystyle \ {a ^ {n} b ^ {n} c ^ {n}: n \ geq 0 \}}$ ${\ displaystyle \ {a ^ {n} b ^ {n} c ^ {n}: n \ geq 0 \}}$ . Acest limbaj poate fi generat de o expresie care analizează gramatica, un formalism relativ nou urmat în special de limbaje de programare.

Definiție formală

Ca o gramatică formală , o gramatică fără context ${\mathcal {G}}$ ${\ displaystyle {\ mathcal {G}}}$ ${\ mathcal {G}}$ poate fi definit ca un cvadruplu:

${\mathcal {G}}=\left\langle N,\Sigma ,P,S\right\rangle$ ${\ displaystyle {\ mathcal {G}} = \ left \ langle N, \ Sigma, P, S \ right \ rangle}$ ${\ mathcal {G}} = \ left \ langle N, \ Sigma, P, S \ right \ rangle$

unde este

$Nu.$ ${\ displaystyle N}$ $Nu.$ este un set finit de simboluri non-terminale
$\Sigma$ ${\ displaystyle \ Sigma}$ $\ Sigma$ este un set finit de simboluri terminale
$P.$ ${\ displaystyle P}$ $P.$ este un set finit de reguli de producție (sau derivare)
$S\in N$ ${\ displaystyle S \ în N}$ $S \ în N$ este un element al $Nu.$ ${\ displaystyle N}$ $Nu.$ , care determină simbolul de pornire non-terminal
elementele de $P.$ ${\ displaystyle P}$ $P.$ Sunt în formă

N\longrightarrow (\Sigma \cup N)^{*}

{\ displaystyle N \ longrightarrow (\ Sigma \ cup N) ^ {*}}

{\ displaystyle N \ longrightarrow (\ Sigma \ cup N) ^ {*}}

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

http://polygen.org

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.

Portalul lingvistic : accesați intrările Wikipedia care se ocupă de lingvistică