IMG_6150.jpeg

# Automi e Linguaggi Formali ## Alberi ### Albero di Derivazione Un albero di derivazione (o parse tree) è un albero ordinato che rappresenta la derivazione di una stringa a partire da una grammatica. Ogni nodo interno è etichettato con un non-terminale, le foglie sono etichettate con terminali o...

# Automi e Linguaggi Formali ## Alberi ### Albero di Derivazione Un albero di derivazione (o parse tree) è un albero ordinato che rappresenta la derivazione di una stringa a partire da una grammatica. Ogni nodo interno è etichettato con un non-terminale, le foglie sono etichettate con terminali o $\epsilon$. **Esempio** Consideriamo la grammatica: $S \rightarrow aSb \mid \epsilon$ La stringa "aabb" ha il seguente albero di derivazione: ``` S / \ a S / \ a S / \ ε b \ / b ``` ### Definizioni Formale Dato una grammatica context-free $G = (V, \Sigma, R, S)$, per un albero di derivazione valgono le seguenti condizioni: * La radice è etichettata con il simbolo iniziale S. * Ogni foglia è etichettata con un terminale o con $\epsilon$. * Ogni nodo interno è etichettato con un non-terminale. * Se $A \rightarrow X_1X_2...X_n$ è una regola di produzione, allora il nodo interno etichettato con A ha n figli, etichettati da sinistra a destra con $X_1, X_2,..., X_n$. ### Costruzione di un Albero di Derivazione 1. Partire dal simbolo iniziale S come radice. 2. Per ogni nodo non-terminale A, scegliere una produzione $A \rightarrow X_1X_2...X_n$. 3. Aggiungere i nodi figli $X_1, X_2,..., X_n$ al nodo A. 4. Continuare fino a che tutte le foglie sono terminali o $\epsilon$. ### Ambiguità Una grammatica è ambigua se una stringa ha più di un albero di derivazione. **Esempio** Consideriamo la grammatica: $E \rightarrow E + E \mid E * E \mid id$ La stringa "id + id * id" ha due alberi di derivazione: ``` E E /|\ /|\ E + E E * E /|\ | | /|\ E * E id E + E id | | | | id id id id ``` Questo porta a diverse interpretazioni dell'espressione, a seconda dell'ordine in cui vengono eseguite le operazioni (precedenza). ### Grammatiche non ambigue Per evitare ambiguità, si possono riscrivere le grammatiche per forzare una specifica precedenza e associatività degli operatori. **Esempio** Una grammatica non ambigua per le espressioni aritmetiche: $E \rightarrow T + E \mid T$ $T \rightarrow F * T \mid F$ $F \rightarrow id \mid (E)$ Questa grammatica forza la precedenza della moltiplicazione sull'addizione e definisce l'associatività a sinistra per entrambi gli operatori.