Elementi di un linguaggio

Un linguaggio può essere descritto completamente se affrontato in più livelli:

• Grammatica: La grammatica risponde alla domanda "quali frasi sono corrette?" ed è formata da due stadi fondamentali:
  • Lessico: ovvero l'insieme delle parole che posso usare, il dizionario;
  • Sintassi: ovvero le regole da seguire per costruire frasi corrette;
• Semantica: È la parte che prova a rispondere alla domanda "cosa significa una frase corretta?", quindi è la parte che dà un significato ad una frase. A tal proposito è importante conoscere la lingua di appartenenza della parola;
• Pragmatica: È quella parte del linguaggio che risponde alla domanda "come usare una frase corretta e sensata?", ovvero studia l'utilizzo delle frasi e il modo in cui vengono usate nel contesto;

Nel caso dei linguaggi di programmazione occorre poi aggiungere un quarto livello di analisi:

• Implementazione: Risponde alla domanda "come eseguire una frase corretta, in modo da rispettarne la semantica?".

Grammatica e sintassi

A differenza dei linguaggi naturali, i linguaggi di programmazione possono disporre di un lessico costituito da un numero infinito di parole. Per poter descrivere in maniera efficace un simile lessico si utilizzano le grammatiche generative (in parte già affrontate in logica).

Grammatica libera da contesto

Una grammatica libera da contesto è una quadrupla ($NT, T, R, S$) dove:

• $NT$: è l'insieme finito di simboli non terminali;
• $T$: è l'insieme finito di simboli terminali;
• $S\in NT$: è il simbolo iniziale;
• $R$: è l'insieme finito di produzioni (o regole), ciascuna delle quali nella forma: $v\rarr w$, dove $v\in NT$ e $w\in T\cup NT$.

Inoltre, data una grammatica libera da contesto, si dice che:

Da $v$ si deriva immediatamente $w$ (e lo denoto con $v\rarr w$) se:

$$ v = xAy \qquad (A\rarr z)\in R \qquad w= xzy \qquad x,y,z\in(T\cup NT) $$

Lo si può dire anche se la sostituzione $A\rarr z$ viene svolta in più passi.