Sintassi astratta dei linguaggi

Appunti rubati da @exiss

Definizione: Linguaggio

Definiamo come linguaggio un insieme di stringhe

Definizione: Grammatica

Definiamo come grammatica un insieme di regole, dette termini, che definiscono come poter manipolare le stringhe di un linguaggio.

La forma di Backus-Naur è una notazione utilizzata per descrivere grammatiche ed è definita come:

$$<\text{symbol}>::=\_\text{expression}\_$$

Dove:

• <symbol> è un simbolo non-terminale espresso dalla grammatica

• L’operatore ::= indica che ciò che si trova alla sua sinistra può essere sostituito con ciò che si trova alla sua destra

• <_expression_> consiste in una o più sequenze di simboli terminali o non-terminali, dove ogni sequenza è separata da una barra verticale (ossia |) indicante una scelta possibile per l’operatore ::=.

Esempio

Consideriamo il linguaggio $L$ espresso dalla grammatica:

$$M,N::=0\mid 1\mid \cdots \mid M+N\mid M\cdot N$$

Tale grammatica indica che i simboli non-terminali M e N possono essere sostituiti con:

• un numero naturale
• un’espressione $M+N$ o $M\cdot N$ dove M e N sono due ulteriori simboli terminali o non-terminali

Ad esempio, la stringa 5 + 7 è ben definita dalla grammatica, mentre la stringa 5 + + non lo è

Definizione: Sintassi Astratta

La sintassi astratta di un linguaggio è una definizione induttiva di un insieme T di termini, che permettendo di definire strutture algebriche senza dover necessariamente definire concretamente le sue operazioni.

Esempio

Consideriamo ancora il linguaggio $L$ definito dalla grammatica:

$$M,N::=0\mid 1\mid \cdots \mid M+N\mid M\cdot N$$

Definiamo quindi la funzione $eval:L\to \mathbb{N}$ in grado di valutare le espressioni del linguaggio:

$$\begin{array}{rl}& \text{eval}(x0\text{"})=0\\ & \text{eval}(\text{“}1\text{”})=1\\ & \dots \\ & \text{eval}(\text{"}M+N\text{"})=\text{eval}(\text{"}M\text{"})+\text{eval}(\text{"}N\text{"})\\ & \text{eval}(\text{"}M\cdot N\text{"})=\text{eval}(\text{"}M\text{"})\cdot \text{eval}(\text{"}N\text{"})\end{array}$$

Notiamo quindi che la grammatica definisce in modo astratto (ma concretamente tramite eval) le seguenti operazioni:

$$\begin{array}{rl}& 0:1\to \mathbb{N}:()\to 0\\ & 1:1\to \mathbb{N}:()\to 1\\ & \dots \\ & \text{plus:}\mathbb{N}\times \mathbb{N}\to \mathbb{N}:(m,n)\mapsto m+n\\ & \text{times:}\mathbb{N}\times \mathbb{N}\to \mathbb{N}:(m,n)\mapsto m\cdot n\end{array}$$

Nota: le operazioni plus e times non sono né iniettive né con immagini disgiunte. Di conseguenza, la funzione eval non ci permette di definire un’algebra induttiva.

Tuttavia, per tale linguaggio è comunque possibile definire (in qualche modo, ad esempio fissando una precedenza per le operazioni rompendo proprietà come l’associatività e la commutatività) una funzione che possa descrivere un’algebra induttiva.

Teorema: Algebra induttiva dei termini

Dato un linguaggio con una sintassi astratta con termini definiti in T, esiste sempre un’algebra induttiva $(T,\alpha )$. Di conseguenza, tutte le proprietà di un linguaggio sono dimostrabili tramite l’induzione strutturale sulla sua algebra dei termini.

(dimostrazione omessa)