Grammatica libera dal contesto

In informatica e in linguistica, una grammatica libera dal contesto (o non contestuale, context-free o CFG) è una grammatica formale in cui ogni regola sintattica è espressa sotto forma di derivazione di un simbolo a sinistra a partire da uno o più simboli a destra. Ciò può essere espresso con due simbolismi equivalenti (nel seguito verrà utilizzato il secondo simbolismo):

V ::= w

V → w

dove V è un simbolo non terminale e w è una sequenza di simboli terminali e non terminali. L'espressione "libera dal contesto" si riferisce al fatto che il simbolo non terminale V può sempre essere sostituito da w, indipendentemente dai simboli che lo precedono o lo seguono. Un linguaggio formale si dice libero dal contesto se esiste una grammatica libera dal contesto che lo genera.

Descrizione

Nella gerarchia di Chomsky le grammatiche libere dal contesto sono dette di Tipo 2.

Le grammatiche libere dal contesto sono abbastanza potenti da descrivere la sintassi della maggior parte dei linguaggi di programmazione; al tempo stesso, sono abbastanza semplici da consentire un parsing molto efficiente.

La notazione formale di Backus-Naur (BNF) è la sintassi più comunemente usata per descrivere grammatiche context-free. Non tutti i linguaggi formali sono liberi dal contesto — un conosciuto controesempio è il seguente ${\displaystyle \{a^{n}b^{n}c^{n}:n\geq 0\}}$. Questo particolare linguaggio può essere generato da una grammatica di parsing di espressione, un formalismo relativamente nuovo seguito particolarmente dai linguaggi di programmazione.

Definizione formale

Come una grammatica formale, una grammatica context-free ${\displaystyle {\mathcal {G}}}$ può essere definita come una quadrupla:

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

dove

• ${\displaystyle N}$ è un insieme finito di simboli non terminali
• ${\displaystyle \Sigma }$ è un insieme finito di simboli terminali
• ${\displaystyle P}$ è un insieme finito di regole di produzione (o derivazione)
• ${\displaystyle S\in N}$ è un elemento di ${\displaystyle N}$, il quale determina il simbolo di partenza non terminale
• gli elementi di ${\displaystyle P}$ sono nella forma

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

Bibliografia

• Giorgio Ausiello, Fabrizio D'Amore, Giorgio Gambosi, Linguaggi modelli complessità, Milano, Franco Angeli Editore, 2003, ISBN 88-464-4470-1.

Voci correlate

• Grammatica formale
• Backus-Naur Form
• Forma normale di Greibach

Collegamenti esterni

• http://polygen.org
• (EN) Denis Howe, context-free grammar, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL

Teoria degli automi: linguaggi formali e grammatiche formali
Gerarchia di Chomsky	Grammatica formale	Linguaggio	Automa minimo
Tipo-0	(illimitato)	Ricorsivamente enumerabile	Macchina di Turing
	(illimitato)	Ricorsivo	Decider
Tipo-1	Dipendente dal contesto	Dipendente dal contesto	Automa lineare
Tipo-2	Libera dal contesto	Libero dal contesto	Automa a pila ND
Tipo-3	Regolare	Regolare	A stati finiti
Ciascuna categoria di linguaggio o grammatica è un sottoinsieme proprio della categoria immediatamente sovrastante.

Controllo di autorità	BNF (FR) cb180900709 (data)

Portale Linguistica: accedi alle voci di Wikipedia che trattano di linguistica