integrato ;)
Il metalinguaggio B.N.F
Introduzione e accenni alla grammatica formale

 
Introduzione
 
Qualsiasi linguaggio di programmazione utilizzato in informatica, come sappiamo, è definito da una sintassi ben nota e inflessibile che il programmatore deve conoscere a fondo per poter stendere un programma compilabile/interpretabile dalla macchina. Potendo definire un qualsiasi linguaggio generico come un insieme di parole e di metodi di combinazione di parole è facile capire, come lo è anche nel parlato, l'importanza della sintassi per una corretta comunicazione. Trattando in informatica più specificatamente linguaggi di programmazione (quindi letti e eseugiti da "macchine stupide" che seguono rigorosamente alla lettera quello che trovano) diventa quindi fondamentale l'importanza della sintassi per permettere una corretta interpratazione del codice da parte del calcolatore. A tale scopo nascono i metalinguaggi cioè dei "linguaggi" al dì sopra del linguaggio di programmazione stesso che definiscono in modo formale e non ambiguo l'insieme di regole sintattiche di quel specifico linguaggio di programmazione. (scusate le ripetizioni)
Tramite l'interpretazione di queste rigide grammatiche è quindi possibile stabilire con assoluta certezza la correttezza sintattica o meno di una frase letta.
I parser dei compilatori utilizzano questo sistema per segnalare in principio gli errori di sintassi di un codice sorgente.

 
Backus-Naur-Form
 
I metalinguaggi per la definizione maggiormente utilizzati sono il BNF e l'EBNF (Extended BNF); essi si avvalgono di 5 simboli:
Simbolo
Significato
<nome_label>
Definisce un simbolo non-terminale
::=
Assegnazione
|
OR logica
{}
0 o più elementi
[]
0 o 1 elementi

Tramite l'utilizzo di questi simboli (insieme a delle regole generali di grammatica formale) è possibile definire infinite regole sintattiche per qualsiasi linguaggio di programmazione in modo univoco.

 
Regole di grammatica formale
 
La grammatica formale è una notazione matematica che consente appunto di esprimere in modo rigoroso la sintassi di un linguaggio; la grammatica formale può essere espressa tramite una quadrupla <VT,VN,P,S> dove:
VT:
è un insieme finito di simboli terminali (alfabeto ammissibile)
VN:
è un insieme finit di simboli non terminali
P:
è un insieme finito di produzioni, ossia di regole di riscrittura
S:
è un particolare simbolo non-terminale detto simbolo iniziale o scopo della grammatica.

Utilizzando quindi la grammatica formale B.N.F si definisce un linguaggio sull'alfabeto terminale VT che utilizzato con meccanismi di derivazione (o riscrittura) permette la verifica della correttezza di frasi del linguaggio per il quale si è scritta la grammatica.

 
EBNF: Esempio di sintassi di un numero naturale
 
Prendiamo una grammatica G =<VT,VN,P,S> dove:
  1. VT = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
  2. VN = { <numero-naturale>, <cifra>, <cifra-non-nulla> }
  3. S = <numero-naturale>
  4. P = {
  5. <numero-naturale> ::= 0 | <cifra-non-nulla> { <cifra> }
  6. <cifra> :: = 0 | <cifra-non-nulla>
  7. <cifra-non-nulla> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
  8. }
Questo codice, che può essere letto ed interpretato univocamente (senza ambigiutà) dalla macchina, permette quindi di riconocere, secondo le regole formalizzate, la correttezza o meno di un numero naturale; analizziamo ora questo codice:
Nell'insieme VT dei simboli terminali sono definiti tutti i valori che possono comporre (secondo le regole di produzione) un numero naturale. Ciò significa che l'alfabeto ammissibile in questa grammatica è composto dai numeri da 0 a 9. (se ad esempio volessi definire le regole di notazione esadecimale tra i simboli terminali avrei dovuto inserire anche le lettere A-F tra questi simboli).
L'insieme VN dei simboli non terminali invece raggruppa degli oggetti "astratti" utilizzati per costruire la nostra grammatica; ogni simbolo non terminale, durante il controllo della correttezza della frase, deve essere ricondotto a un simbolo terminale.
Lo scopo S è invece l'oggetto che stiamo analizzando, in questo caso il numero naturale, ed è il simbolo non-terminale dal quale si parte per il controllo di correttezza.
Le produzioni P infine sono l'insieme più importante della grammatica e definiscono secondo quali metodi è possibile utilizzare gli "oggetti" non terminali per rappresentare il numero naturale utilizzando i simboli prima visti; in questo caso:
  1. <numero-naturale> ::= 0 | <cifra-non-nulla> { <cifra> }
Significa che il numero naturale si può scrivere come 0 oppure (|) come una cifra non nulla seguita da zero o più ({}) cifre.
  1. <cifra> :: = 0 | <cifra-non-nulla>
Una cifra si può scrivere come 0 oppure come una cifra non nulla.
  1. <cifra-non-nulla> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Ed infine una cifra non nulla si può riscrivere come 1 oppure 2 oppure 3...

 
Controllo della correttezza di una frase
 
I metodi più semplici per procedere con il controllo di una frase del linguaggio sono essenzialmente due:
- La derivazione left-most
- L'albero sintattico
Entrambi questi metodi procedono all'analisi della frase partendo dallo della grammatica. Analizziamoli uno alla volta con esempi pratici

 
Derivazione LEFT-MOST
 
Questo tipo di controllo riscrive ogni simbolo non-terminale più a sinistra della frase (analogamente la derivazione right-most fa la stessa cosa partendo da destra) e alla fine della sostituzione deve essere possibile riscrivere esattamente la frase analizzata utilizzando i simboli terminali della grammatica. Se la frase non è uguale a quella di partenza o non esistono produzioni che riescano a riscrivere un qualsiasi simbolo terminale della frase la verifica fallisce. Ad esempio:
  1. G = <VT,VN,P,S>
  2. VT = { il, la, gatto, mattina, topo, sasso, mangia, beve }
  3. VN = {
  4. <frase>, <soggetto>, <verbo>,
  5. <compl-ogg>, <articolo>, <nome>
  6. }
  7. F = <frase>
  8. P = {
  9. <frase> ::= <soggetto> <verbo> <compl-oggetto>
  10. <soggetto> ::= <articolo> <nome>
  11. <compl-ogg> ::= <articolo> <nome>
  12. <articolo> ::= il | la
  13. <nome> ::= gatto | topo | sasso | mattina
  14. <verbo> ::= mangia | beve
  15. }
Analizziamo la frase "Il gatto mangia il topo"
Partendo la sostituzione dallo scopo abbiamo in sequenza:
  1. <frase>
  2. <soggetto> <verbo> <compl-ogg>
  3. <articolo> <nome> <verbo> <compl-ogg>
  4. il <nome> <verbo> <compl-ogg>
  5. il gatto <verbo> <compl-ogg>
  6. il gatto mangia <compl-ogg>
  7. il gatto mangia <articolo> <nome>
  8. il gatto mangia il <nome>
Fino ad arrivare alla soluzione esatta
il gatto mangia il topo

Proviamo adesso con un'altra frase: "La mattina il gatto mangia il topo":
  1. <frase>
  2. <soggetto> <verbo> <compl-ogg>
  3. <articolo> <nome> <verbo> <compl-ogg>
  4. la <nome> <verbo> <compl-ogg>
  5. il mattina <verbo> <compl-ogg>
E qui come si nota la verifica si interrompe in quanto secondo l'insieme delle produzioni nella frase occorrerebbe inserire al posto di <verbo> il simbolo terminale "il" che è presente nella frase iniziale ma cià non è possibile.
Secondo la nostra grammatica quindi questa frase non è corretta.

 
Albero sintattico
 
Un'altro metodo di controllo grammaticale è l'albero sintattico. Partendo sempre dallo scopo come radice, si costruisce un albero i cui nodi sono composti dai simboli non-terminali e si procede con la derivazione fino ad ottenere nelle foglie solo simboli terminali. Anche in questo caso la verifica fallisce se non è possibile sostituire il simbolo terminale corretto della frase o se la frase generata differisce da quella inziale.
Facciamo un esempio con la frase vista in precedenza "Il gatto mangia il topo" avvalendoci della stessa grammatica e osserviamo l'albero sintattico:


E anche in questo caso come si nota la è verificata la correttezza della frase.

 
Fonti
 
Lucidi "Introduzione a linguaggi e grammatiche" del corso di Fondamenti di informatica L-A, facoltà di ingegneria informatica università di Bologna docente Prof. Paola Mello.
Script Execution Time: 0.026636 seconds - Visite: 641938
Copyright © 2007-2017 Suondmao v0.1.5-1