Grammatica libera dal contesto: differenze tra le versioni
m Bot: Elimino interlinks vedi Wikidata |
m WPCleaner v1.30b - Fixed using Wikipedia:Check Wikipedia - Entità con codice nominale (automatico) |
||
Riga 1: | Riga 1: | ||
In informatica e in linguistica, una '''grammatica context-free''' ('''grammatica libera dal contesto''' 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): |
In informatica e in linguistica, una '''grammatica context-free''' ('''grammatica libera dal contesto''' 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'' |
||
:V |
:V → ''w'' |
||
dove V è un [[grammatica formale|simbolo non terminale]] e ''w'' è una sequenza di [[grammatica formale|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 (matematica)|linguaggio formale]] si dice ''context-free'' se esiste una grammatica context-free che lo genera. |
dove V è un [[grammatica formale|simbolo non terminale]] e ''w'' è una sequenza di [[grammatica formale|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 (matematica)|linguaggio formale]] si dice ''context-free'' se esiste una grammatica context-free che lo genera. |
||
Versione delle 02:31, 6 nov 2013
In informatica e in linguistica, una grammatica context-free (grammatica libera dal contesto 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. 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 .
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 può essere definita come una quadrupla:
dove
- è un insieme finito di simboli non terminali
- è un insieme finito di simboli terminali
- è un insieme finito di regole di produzione (o derivazione)
- è un elemento di , il quale determina il simbolo di partenza non terminale
- gli elementi di sono nella forma