LFC riassunto appunti

Il corso di Linguaggi Formali e Compilatori copre i seguenti argomenti essenziali:

• Compilatori e Interpreti: I compilatori traducono un programma completo in linguaggio macchina, mentre gli interpreti eseguono la traduzione riga per riga. L'Albero Sintattico Astratto (AST) è una rappresentazione intermedia.
• Fasi di Compilazione:
  • Analitica: Include l'analisi lessicale (scanner, lessemi, token), sintattica (parser, AST) e semantica statica (type checking).
  • Sintetica: Generazione del codice intermedio (indipendente dall'architettura) e del codice oggetto (specifico dell'architettura), con ottimizzazione.
• Linguaggi Formali: Definiti da un alfabeto (insieme finito di simboli) e parole (sequenze finite di simboli). Il Teorema di Cantor sottolinea l'impossibilità di una caratterizzazione univoca dei linguaggi tramite una singola parola.
• Grammatiche: Una grammatica a struttura di frase è una quadrupla (V, Σ, P, S). Vengono definite le conseguenze dirette e le derivazioni.
• Gerarchia di Chomsky: Classifica le grammatiche in Tipo 0 (struttura di frase), Tipo 1 (sensibili al contesto), Tipo 2 (non contestuali) e Tipo 3 (regolari), in base alle restrizioni sulle produzioni.
• Automi a Stati Finiti (FSA): Modelli per riconoscere i linguaggi.
• Automi Deterministici (DFA): Ogni coppia stato-simbolo ha una singola transizione definita. Il linguaggio accettato è l'insieme delle parole che portano a uno stato finale.
• Automi Non Deterministici (NFA) e con Epsilon-transizioni (ε-NFA): Possono avere più transizioni o transizioni "vuote" per una data coppia stato-simbolo.
• Determinizzazione: Ogni NFA o ε-NFA può essere convertito in un DFA equivalente.
• Espressioni Regolari: Costruite con operazioni di unione, concatenazione e chiusura di Kleene. Il Teorema di Kleene stabilisce l'equivalenza tra linguaggi regolari e linguaggi riconoscibili da FSA.
• Minimizzazione degli Automi: L'algoritmo di minimizzazione e il Teorema di Nerode permettono di costruire il DFA con il minor numero di stati.
• Analisi Lessicale: Identifica lessemi e li raggruppa in token (es. identificatori, parole chiave) usando pattern (espressioni regolari). Gestisce priorità e il prefisso più lungo.
• Semplificazione delle Grammatiche: Processi per eliminare produzioni "inutili" come ε-produzioni, produzioni 1-arie, variabili improduttive e inaccessibili.
• Forme Normali: La Forma Normale di Chomsky (CNF) e la Forma Normale di Greibach (GNF) sono standardizzate per le grammatiche non contestuali.
• Parsing:
  • Algoritmo CYK: Soluzione per parsing e ricognizione per grammatiche in CNF (complessità O(n³)).
  • Parsing Top-Down (Predittivo): Utilizza le funzioni FIRST e FOLLOW per fare scelte deterministiche nella derivazione.
  • Grammatiche LL(1): Permettono un parsing top-down deterministico senza backtracking.
• Automi a Pila (PDA): Estensioni degli FSA con una pila, utilizzati per riconoscere i linguaggi non contestuali. Il Teorema di Caratterizzazione collega PDA e grammatiche non contestuali.
• Pumping Lemmas: Dimostrano che certi linguaggi non sono regolari o non contestuali, verificando l'iterabilità di sottostringhe.
• Proprietà di Chiusura: I linguaggi regolari sono chiusi rispetto alle operazioni booleane. I linguaggi non contestuali sono chiusi per unione, concatenazione, chiusura di Kleene e intersezione con linguaggi regolari.