Grammatica libera dal contesto: differenze tra le versioni
m link rossi |
m robot Aggiungo: bn:প্রসঙ্গমুক্ত ব্যাকরণ |
||
Riga 79: | Riga 79: | ||
{{linguistica}} |
{{linguistica}} |
||
[[bn:প্রসঙ্গমুক্ত ব্যাকরণ]] |
|||
[[cs:Bezkontextová gramatika]] |
[[cs:Bezkontextová gramatika]] |
||
[[de:Kontextfreie Grammatik]] |
[[de:Kontextfreie Grammatik]] |
Versione delle 12:41, 2 mag 2007
In informatica e in linguistica, una grammatica context-free (grammatica libera dal contesto o CFG) è una grammatica formale in cui ogni regola di derivazione è della forma
- 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 contex-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 G può essere definita come una quadrupla:
dove
- è un insieme finito di simboli terminali
- è un insieme finito di simboli non terminali
- è un insieme finito di regole di produzione (o derivazione)
- è un elemento , il quale determina il simbolo di partenza non terminale.
- gli elementi di sono nella forma
Esempi
Esempio 1
Una semplice grammatica context-free:
- S → aSb | ε
dove il metasimbolo | è una disgiunzione logica, usata per separare multiple opzioni. Questa grammatica genera il linguaggio , il quale è un linguaggio non regolare.
Esempio 2
Ecco una grammatica context-free per espressioni algebriche con infissi sintatticamente corretti nelle variabili x, y e z:
- S → x | y | z | S + S | S - S | S * S | S/S | (S)
Questa grammatica può, ad esempio, generare la stringa "( x + y ) * x - z * y / ( x + x )".
Esempio 3
Una grammatica context-free per il linguaggio consiste in tutte le stringhe nell'insieme {a,b} contengono un numero diverso di a e di b è
- S → U | V
- U → TaU | TaT
- V → TbV | TbT
- T → aTbT | bTaT | ε
T può generare tutte le strighe con lo stesso numero di a e b, U genera tutte le stringhe con più a che b e V genera tutte le stringhe con meno a di b.
Esempio 4
Un altro esempio di linguaggio context-free è . Non è un linguaggio regolare, ma è context free dal momento che può essere generato dalla seguente CFG (Context Free Grammar):
- S → aSc | B
- B → bBc | ε
Altri esempi
Le grammatiche Context-free non sono limitate alle applicazioni matematiche (linguaggi "formali"). La grammatica del Lojban, è un linguaggio artificiale con un immenso potere espressivo, è context-free, e non ambiguo. Recentemente si è pensato che una classe poetica chiamata Venpa del Tamil è guidata da una grammatica context-free.