Gli automi a stati finiti non sanno contare in modo illimitato, e quindi non riescono a descrivere strutture annidate come parentesi bilanciate, espressioni aritmetiche o blocchi di codice dentro altri blocchi. Per queste strutture serve un formalismo più espressivo: le grammatiche libere dal contesto (context-free grammars, CFG). Sono il fondamento della sintassi di quasi tutti i linguaggi di programmazione e di molti formati di dati.
La definizione
Una grammatica libera dal contesto è una quadrupla G = (V, Σ, R, S) dove:
- V è un insieme finito di variabili (o non terminali), che rappresentano categorie sintattiche;
- Σ è l'alfabeto dei terminali, i simboli che compaiono davvero nelle stringhe;
- R è un insieme finito di regole della forma A → α, dove A è una variabile e α è una stringa qualsiasi di variabili e terminali (anche vuota);
- S ∈ V è la variabile iniziale.
«Libera dal contesto» significa che a sinistra di ogni regola c'è una sola variabile, senza simboli intorno: la variabile A si può riscrivere con α ovunque compaia, indipendentemente da ciò che le sta accanto.
Derivazioni
Si parte dalla variabile iniziale e si applicano le regole, sostituendo una variabile alla volta, fino a ottenere una stringa di soli terminali. Questa sequenza è una derivazione. Il linguaggio della grammatica, L(G), è l'insieme di tutte le stringhe di terminali derivabili da S.
Un esempio minimo: la grammatica con la sola variabile S e le regole
S → a S b
S → ε
genera esattamente {aⁿbⁿ : n ≥ 0}. La derivazione di aabb è S ⇒ aSb ⇒ aaSbb ⇒ aabb. Il linguaggio che nessun DFA può riconoscere si descrive con due regole.
Parentesi bilanciate
Le stringhe di parentesi bilanciate sono generate da:
S → ( S ) S
S → ε
La prima regola dice: una sequenza bilanciata è vuota, oppure è una coppia di parentesi che racchiude una sequenza bilanciata, seguita da un'altra sequenza bilanciata. È una definizione ricorsiva tradotta direttamente in regole.
Alberi sintattici
Una derivazione si può rappresentare con un albero sintattico (parse tree): la radice è S, ogni nodo interno è una variabile e i suoi figli sono i simboli del lato destro della regola applicata, le foglie lette da sinistra a destra formano la stringa.
L'albero dimentica l'ordine in cui le variabili sono state sostituite e conserva solo la struttura. Per questo si distinguono la derivazione sinistra, in cui si sostituisce sempre la variabile più a sinistra, e la derivazione destra: a ogni albero corrisponde una e una sola derivazione sinistra.
Nei compilatori l'albero è ciò che conta davvero: è da lì che si ricava il significato del programma.
Ambiguità
Una grammatica è ambigua se esiste almeno una stringa con due alberi sintattici diversi. Il caso classico sono le espressioni aritmetiche:
E → E + E | E * E | ( E ) | n
La stringa n + n * n ha due alberi: uno in cui la somma viene prima, (n + n) * n, e uno in cui viene prima il prodotto, n + (n * n). Se l'albero determina il valore calcolato, l'ambiguità produce due risultati diversi.
Eliminare l'ambiguità con livelli di precedenza
La soluzione standard introduce una variabile per ogni livello di precedenza:
E → E + T | T
T → T * F | F
F → ( E ) | n
Ora un'espressione è una somma di termini, un termine è un prodotto di fattori, un fattore è un numero o un'espressione fra parentesi. La stringa n + n * n ha un solo albero, quello in cui il prodotto è raggruppato dentro il termine. La ricorsione a sinistra in E → E + T rende inoltre la somma associativa a sinistra: n + n + n si legge (n + n) + n.
Bisogna sapere un fatto importante: esistono linguaggi intrinsecamente ambigui, per i quali ogni grammatica possibile è ambigua. Inoltre stabilire se una CFG qualunque è ambigua è un problema indecidibile: non esiste un algoritmo generale che risponda sempre.
Forme normali
Per le dimostrazioni e per alcuni algoritmi conviene portare la grammatica in forma standard. La più usata è la forma normale di Chomsky, in cui ogni regola è del tipo A → BC oppure A → a (con un'eccezione per la stringa vuota). Ogni CFG si può convertire in questa forma senza cambiare il linguaggio. Il vantaggio è che ogni albero diventa binario, e questo rende possibili algoritmi come CYK, che decide in tempo cubico se una stringa appartiene al linguaggio.
Dove si incontrano nel lavoro reale
Nel mio lavoro le grammatiche emergono ogni volta che si scrive un parser per un formato di configurazione, un piccolo linguaggio di interrogazione o un validatore di espressioni inserite dagli utenti. Partire da una grammatica esplicita, invece che da una serie di condizioni scritte a mano, rende il codice più corto, più verificabile e molto meno fragile davanti ai casi limite.
In sintesi
- Una CFG ha regole con una sola variabile a sinistra e descrive strutture annidate che i DFA non gestiscono.
- Il linguaggio è l'insieme delle stringhe di terminali derivabili dalla variabile iniziale.
- L'albero sintattico rappresenta la struttura e corrisponde a una sola derivazione sinistra.
- Una grammatica è ambigua se una stringa ha due alberi; i livelli di precedenza risolvono il caso delle espressioni.
- Decidere se una CFG è ambigua è indecidibile, e alcuni linguaggi sono ambigui per natura.
