Grammatica libera dal contesto

Da Wikipedia, l'enciclopedia libera.

In informatica e in linguistica, una grammatica context-free (o libera dal contesto, CFG o non contestuale) è 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. Il termine "context-free" (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 context-free se esiste una grammatica context-free che lo genera.

Le grammatiche context-free 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 context-free — un conosciuto controesempio è il seguente  \{ a^n b^n c^n : n \ge 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[modifica | modifica sorgente]

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

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

dove

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

Bibliografia[modifica | modifica sorgente]

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

Voci correlate[modifica | modifica sorgente]

Collegamenti esterni[modifica | modifica sorgente]

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 sottostante.
linguistica Portale Linguistica: accedi alle voci di Wikipedia che trattano di linguistica