Differenze tra le versioni di "Grammatica libera dal contesto"

nessun oggetto della modifica
m (Bot: virgola fuori dal aiuto:grassetto)
 
:V → ''w''
dove V è un [[grammatica formale|simbolo non terminale]] e ''w'' è una sequenza di [[grammatica formale|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 [[linguaggio di programmazione|linguaggi di programmazione]]; al tempo stesso, sono abbastanza semplici da consentire un [[parsing]] molto efficiente.
 
La [[Backus-Naur Form|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 <math> \{ a^n b^n c^n : n \ge 0 \} </math>. Questo particolare linguaggio può essere generato da una grammatica di parsing di espressione, un formalismo relativamente nuovo seguito particolarmente dai linguaggi di programmazione.
 
Non tutti i linguaggi formali sono liberi dal contesto — un conosciuto controesempio è il seguente <math> \{ a^n b^n c^n : n \ge 0 \} </math>.
 
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 <math>\mathcal{G}</math> può essere definita come una quadrupla:
 
Utente anonimo