Linguaggi formali e grammatiche

Cos’è un linguaggio formale e perché ci serve

Un compilatore legge sequenze di simboli. Per stabilire se una sequenza ha la struttura di un’espressione o di un’istruzione, gli servono regole precise. Per esempio, 2 * (3 + 4) è un’espressione ben formata, mentre 2 * + 4 viola le regole delle espressioni aritmetiche che useremo in questa nota.

Prima di analizzare la sintassi di un sorgente C, l’analisi lessicale raggruppa i caratteri in token. In int totale = 42; riconosciamo una parola chiave, un identificatore, l’operatore di assegnamento, una costante intera e il punto e virgola. Le regole sintattiche stabiliscono poi come combinare questi token in una dichiarazione.

La stringa 01/03/2013 aiuta a distinguere tre domande sullo stesso enunciato.

LivelloDomandaEsempio
SintatticoLa sequenza rispetta le regole di formazione?La data contiene due cifre, una barra, due cifre, una barra e quattro cifre.
SemanticoChe cosa significa la sequenza secondo la convenzione adottata?Giorno/mese/anno indica il 1º marzo. Mese/giorno/anno indica il 3 gennaio.
PragmaticoA che cosa serve l’enunciato nel contesto?In un modulo la data può indicare la scadenza di una domanda oppure il giorno di un appuntamento.

Per descrivere la sintassi, partiamo da un insieme di simboli e selezioniamo le sequenze ammesse. Una grammatica formale permette di descrivere queste sequenze mediante un numero finito di regole anche quando sono infinite.


Alfabeti, stringhe e operazioni

Alfabeto e stringa

Alfabeto e stringa

Un alfabeto è un insieme finito e non vuoto di simboli. Una stringa (o parola) su è una sequenza finita di simboli di .

L’alfabeto binario è . Per descrivere parole possiamo scegliere come simboli le lettere minuscole, mentre per le espressioni aritmetiche possiamo scegliere cifre, operatori e parentesi. La lunghezza di una stringa è il numero di occorrenze dei suoi simboli e si indica con . Per esempio, . La stringa vuota (indicata anche con ) ha lunghezza zero.

Concatenazione e potenza

La concatenazione mette i simboli di dopo quelli di . Con e otteniamo . Vale e è l’elemento neutro, cioè .

La potenza concatena copie di . Per esempio, .

Chiusura di Kleene e chiusura positiva

è l’insieme delle stringhe su di lunghezza esattamente , con . La chiusura di Kleene contiene tutte le stringhe finite su . La chiusura positiva contiene quelle di lunghezza almeno uno.


Linguaggi formali e operazioni sui linguaggi

Linguaggio formale

Un linguaggio formale su è un insieme di stringhe su quell’alfabeto.

Un vocabolario fissato fornisce un linguaggio finito. Una regola come «esattamente zeri seguiti da uni per ogni » definisce il linguaggio infinito . I formati di data e le espressioni aritmetiche sono altri esempi. Una sequenza può usare soltanto simboli dell’alfabeto e violare comunque le regole del linguaggio.

Operazioni sui linguaggi

OperazioneRisultato
Unione Le parole di almeno uno dei due linguaggi.
Intersezione Le parole di entrambi i linguaggi.
Complemento Le stringhe su escluse da .
Concatenazione Tutte le concatenazioni di una parola di con una parola di .

Per le potenze, le copie sono del linguaggio e ogni fattore può fornire una parola diversa.

Numero di fattori e lunghezza della stringa

In concateniamo almeno una parola di . Se , possiamo scegliere quella parola e ottenere .

Il linguaggio vuoto ha zero elementi. ha un elemento e vale . Invece , perché manca una parola da scegliere nel secondo fattore.

Codici e decomposizione univoca

Codice

Un insieme di parole non vuote è un codice se ogni stringa di ha un’unica decomposizione in parole di .

  • Con ogni 0 impone che il precedente 1 faccia parte della parola 10. Gli altri 1 costituiscono parole singole. La decomposizione è quindi unica per qualsiasi stringa di . Per esempio, 101 si separa in 10 e 1.
  • Con la stessa stringa ababab si ottiene sia con aba · bab sia con ab · ab · ab. Queste due decomposizioni bastano a escludere che sia un codice.

In un codice a prefisso nessuna parola è prefisso di un’altra. Leggendo da sinistra, al primo riscontro di una parola possiamo tagliare lì. Questo basta a garantire l’univocità. mostra che la proprietà di prefisso è sufficiente ma non necessaria, dato che 1 è prefisso di 10.

Appartenenza, riconoscimento e generazione

Data una stringa , il problema dell’appartenenza chiede se . Possiamo descrivere tramite un modello che riconosce le parole ammesse oppure mediante regole che le generano.

  • Nell’approccio riconoscitivo il modello legge una parola e applica un criterio di accettazione. Gli automi a stati finiti decidono l’appartenenza ai linguaggi regolari. Terminano dopo aver letto l’input.
  • Nell’approccio generativo si parte da un simbolo iniziale e si applicano produzioni per ottenere le parole ammesse. Una derivazione completa di dimostra che appartiene al linguaggio.

Per i modelli di calcolo generali distinguiamo riconoscibilità e decidibilità. Un riconoscitore accetta tutte le parole del linguaggio e può rifiutare o proseguire indefinitamente sugli altri input. Un decisore termina sempre con un sì o un no. Riprenderemo la distinzione con la macchina di Turing.


Grammatiche formali

La quadrupla della grammatica

Una grammatica formale è una quadrupla .

  • è l’insieme finito dei non-terminali, cioè le categorie da sviluppare durante la derivazione.
  • è l’insieme finito dei terminali, cioè i simboli delle parole generate. Vale .
  • è l’insieme finito delle produzioni . contiene almeno un non-terminale, mentre può essere una sequenza qualsiasi di terminali e non-terminali, inclusa .
  • è il simbolo iniziale.

Scriviamo . Una produzione applicata alla sottostringa in dà , dove . Usiamo per un passo e per zero o più passi.

Il linguaggio generato raccoglie tutte le derivazioni che arrivano a una stringa di soli terminali.

Due grammatiche sono equivalenti se generano lo stesso linguaggio.


La gerarchia di Chomsky

I vincoli sulle produzioni individuano quattro classi di linguaggi. Ogni classe è strettamente inclusa nella precedente, dal tipo più restrittivo (3) al più generale (0).

TipoFamigliaForma delle produzioniModello di riconoscimento
0Illimitata contiene almeno un non-terminale.Macchina di Turing
1ContestualeNella caratterizzazione non contraente, .Automa linearmente limitato
2Libera dal contesto (CFG) con un solo non-terminale a sinistra.Automa a pila non deterministico
3RegolareLineare destra, o , oppure lineare sinistra, o .Automa a stati finiti

Per il tipo 1 usiamo la convenzione non contraente, equivalente per le classi di linguaggi alla formulazione mediante riscrittura in un contesto. Si può ammettere se è assente da tutti i lati destri. Per il tipo 3 usiamo la forma lineare che ammette anche , con e .

Nell’analisi lessicale, le grammatiche regolari e gli automi a stati finiti descrivono molte categorie di token, come numeri e identificatori. Nell’analisi sintattica, le grammatiche libere dal contesto descrivono strutture annidate come le espressioni tra parentesi.


Notazione BNF, alberi e ambiguità

La BNF (Backus–Naur Form) scrive le produzioni di una grammatica libera dal contesto. I non-terminali compaiono tra parentesi angolari, i terminali tra virgolette, ::= introduce la produzione e | separa le alternative. Per le nostre espressioni, <E> indica un’espressione, <T> un termine e <F> un fattore.

<E> ::= <E> "+" <T> | <T>
<T> ::= <T> "*" <F> | <F>
<F> ::= "(" <E> ")" | "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

Una somma è costruita a livello di <E> e i suoi addendi sono già raggruppati in termini. La moltiplicazione si costruisce dentro <T> e ha così precedenza sulla somma. Le parentesi permettono di inserire un’intera espressione in un fattore.

L’albero di derivazione (parse tree) ha come radice il simbolo iniziale. I figli di un nodo non-terminale, nell’ordine, sono i simboli del lato destro della produzione applicata. Leggendo le foglie da sinistra verso destra e omettendo otteniamo la stringa derivata. L’albero sintattico astratto (abstract syntax tree, AST) conserva la struttura che serve nelle fasi successive. Per un’espressione aritmetica, i nodi interni sono gli operatori e i figli ne rappresentano gli operandi in ordine.

Grammatica ambigua

Una grammatica libera dal contesto è ambigua se almeno una sua parola ammette due alberi di derivazione distinti. In modo equivalente, la parola ammette due derivazioni sinistre distinte, nelle quali si espande sempre il non-terminale più a sinistra.

Per esempio, con , la stringa 2 + 3 * 4 ammette due alberi di derivazione. Nel primo si applica alla radice e si ottiene 2 + (3 * 4). Nel secondo si applica alla radice e si ottiene (2 + 3) * 4. Nella BNF qui sopra, 2 + 3 * 4 si deriva solo raggruppando prima il prodotto. Le parentesi permettono di esprimere esplicitamente l’altro raggruppamento.


Esempi guidati

Esempio 1. Una grammatica per

Problema. Descrivere il linguaggio di e derivare aaabbb.

Svolgimento. Ogni applicazione della prima produzione aggiunge una a a sinistra e una b a destra. La seconda chiude la derivazione aggiungendo una coppia centrale. Per aaabbb usiamo due volte la prima produzione e una volta la seconda.

Ogni derivazione completa ha la forma e possiamo scegliere passi ricorsivi per ottenere ogni . Quindi . La grammatica è di tipo 2. La produzione ha terminali su entrambi i lati di .

Esempio 2. Stringhe binarie che iniziano con 1 e finiscono con 0

Problema. Costruire una grammatica regolare per .

Svolgimento. Da produciamo il primo 1 e passiamo ad . Da possiamo aggiungere un simbolo intermedio restando in , oppure chiudere con 0.

Per 1010 otteniamo . Tutte le produzioni sono lineari destre. La derivazione verifica anche il caso in cui .

Esempio 3. Dalla BNF all’AST di un’espressione

Problema. Usare la BNF per derivare 2 * (3 + 4) e ricavare le notazioni prefissa e postfissa.

Svolgimento. Partiamo da <E> e scegliamo <T>, poi scomponiamo il prodotto in <T> "*" <F>. Il termine a sinistra produce 2 e il fattore a destra apre una nuova espressione tra parentesi. Questa usa <E> "+" <T> per produrre la somma.

Albero di derivazione. I numeri sulle frecce indicano l’ordine dei figli quando una produzione ne ha più di uno.

flowchart TD
    Start["E"] --> Product["T"]
    Product -->|"1"| LeftTerm["T"]
    Product -->|"2"| Times["operatore *"]
    Product -->|"3"| RightFactor["F"]
    LeftTerm --> LeftFactor["F"]
    LeftFactor --> Two["2"]
    RightFactor -->|"1"| Open["("]
    RightFactor -->|"2"| Sum["E"]
    RightFactor -->|"3"| Close[")"]
    Sum -->|"1"| LeftExpr["E"]
    Sum -->|"2"| Plus["operatore +"]
    Sum -->|"3"| RightTerm["T"]
    LeftExpr --> InnerTerm["T"]
    InnerTerm --> InnerFactor["F"]
    InnerFactor --> Three["3"]
    RightTerm --> LastFactor["F"]
    LastFactor --> Four["4"]

Visitando le foglie nell’ordine dei figli otteniamo 2 * ( 3 + 4 ). Nell’AST il nodo + è il secondo operando di *. La struttura dell’albero mantiene il raggruppamento delle parentesi e possiamo valutare la somma a 7 prima del prodotto, che dà 14.

Albero sintattico astratto

flowchart TD
    Product["operatore *"] -->|"sinistro"| Two["2"]
    Product -->|"destro"| Sum["operatore +"]
    Sum -->|"sinistro"| Three["3"]
    Sum -->|"destro"| Four["4"]
NotazioneOrdine di visita dell’ASTRisultato
InfissaOperando sinistro, operatore, operando destro. Aggiungiamo le parentesi quando servono a conservare il raggruppamento.2 * (3 + 4)
PrefissaOperatore, operando sinistro, operando destro.* 2 + 3 4
PostfissaOperando sinistro, operando destro, operatore.2 3 4 + *

La nota sui compilatori riprende gli alberi nella fase di analisi sintattica.


Errori frequenti

Controlli da fare

Errore · Trattare , e come lo stesso oggetto.

Correzione · Il primo è una stringa di lunghezza zero. Gli altri sono linguaggi di cardinalità rispettivamente zero e uno. Solo è neutro per la concatenazione di linguaggi.

Errore · Supporre che escluda sempre .

Correzione · Il segno impone almeno un fattore. Se il fattore scelto è , anche il risultato è .

Errore · Classificare come regolare una grammatica perché ogni regola presa da sola è lineare destra oppure sinistra.

Correzione · La forma regolare usa un solo orientamento in tutta la grammatica. Con e , l’alternanza permette di generare per .

Errore · Contare come parola generata.

Correzione · È una forma di frase intermedia. Per ottenere una parola di , completiamo la derivazione fino a lasciare soltanto terminali.


Esercizi di prova

Esercizio 1. Operazioni su linguaggi e codici (Base)

Siano e .

  1. Calcola e . Indica la lunghezza di ogni parola di .
  2. Stabilisci se e se .
  3. Stabilisci se è un codice e se è a prefisso.

Esercizio 2. Classificazione delle produzioni (Base)

Determina il tipo più specifico (il numero più alto) di ciascuna grammatica secondo le convenzioni della nota. I simboli maiuscoli sono non-terminali e è il simbolo iniziale.

  1. e .
  2. .
  3. , e .
  4. , e .

Esercizio 3. Una grammatica per i palindromi (Intermedio)

Costruisci una grammatica libera dal contesto per le stringhe palindrome su , inclusa . Mostra una derivazione di abba.

Esercizio 4. Appartenenza a un linguaggio generato (Intermedio)

Data la grammatica con produzioni e , determina e stabilisci se aabccc vi appartiene.

Esercizio 5. Due derivazioni per le stesse parentesi (Avanzato)

Considera . Dimostra l’ambiguità con due derivazioni sinistre di (). Proponi una grammatica equivalente e motiva l’unicità della derivazione sinistra.

Esercizio 6. BNF per interi decimali con segno (Intermedio)

Scrivi una grammatica BNF per interi decimali rappresentati con almeno una cifra e un segno iniziale facoltativo. Verifica se -105, 0 e + appartengono al linguaggio.


Provenienza del materiale

  • Slide e dispensa ufficiale del corso, C1PROG1U1L1a_Linguaggi_Formali.pdf (Unità 1, Lezione 1a, linguaggi formali, grammatiche generative e gerarchia di Chomsky).
  • Marco Anisetti, Appunti di Programmazione e Algoritmi I. Fondamenti, Appunti_di_fine_Unita_1.pdf, §§ 1.1–1.10 e 2.1–2.7.
  • Guida unica di studio – Fondamenti, Guida_Unita_1_teoria_approfondimenti_per_argomento.pdf, §§ 1–5.
  • Appunti Avanzati di Programmazione e Algoritmi I, AppuntiInformatica-v3.pdf, §§ 1 e 3.
  • Dispensa del corso, C1PROG1B1L3_Semantica_grammatica_algoritmo.pdf (Lessico, sintassi, semantica e introduzione agli algoritmi).