Rappresentazione e terminologia # Operazioni importanti Definizione di grafo # È un insieme di nodi e di archi. (prendili da insiemi corretti) Metodi di rappresentazione # Liste di incidenza # In pratica numero tutti gli archi e storo il valore dell'arco incidente per ogni nodo.…
In questa nota andiamo a parlare in modo sommario (si impara probabilmente molto meglio con la pratica) di generali tipologie di approcci che esistono per affrontare problemi di tipo algoritmico. Divide et impera # Introduzione # Abbiamo già visto L'utilizzo di questa tecnica…
Questo documento è totalmente concentrato sull'analisi del problema della selezione del k-esimo elemento. 7.1 Introduzione al problema # Dato un array di elementi vogliamo cercare di trovare un modo efficiente per selezionare il k-esimo elemento, ossia un elemento che sia…
LR(k) # Grammatiche LR(k) # Anche in questo caso proviamo a generalizzare il concetto dei pirmi k caratteri, in modo da generalizzare in qualche senso il concetto di LR(k), quindi andiamo a modificare la closure considerando ora first k Per ricordarti come si calcolava first k,…
DPDA # Definizione (2) # La definizione di DPDA è molto simile a quella trattata in Linguaggi liberi e PDA , con solo costraints sulla deterministicità, che si traducono in due condizioni: Al massimo posso avere un risultato per ogni coppia di lettura e simbolo su stack Se ho…
In questa parte del nostro percorso nei linguaggi di programmazione proviamo ad espandere NFA e DFA in modo che possano riconoscere linguaggi come w w r ∣ w ∈ { a , b } ∗ , con r maggiore o uguale a zero (r per dire che è il contrario di w) (questo linguaggio per il pumping…
Definizione ed esempi per macchine astratte # Una macchina astratta è un qualunque insieme di algoritmi e strutture di dati che permettono di memorizzare ed eseguire il linguaggio L , quindi una macchina astratta esiste per esguire il proprio linguaggio (inteso come insieme…
I Nomi e oggetti # Oggetti denotati e identificatori # I nomi sono sequenze di caratteri o numeri aka: token alfanumerico (anche IDENTIFICATORE (per token guardare Grammatiche Regolari ) utilizzate principalmente come Astrazione sul controllo e sui dati (quindi sono cose molto…
Vincoli sintattici contestuali # Intro: dipendenze da contesto # I vincoli sintattici non sono esprimibili tramite BNF perché dipendono dal contesto, mentre le grammatiche libere sono per definizione libere da contesto, vogliamo quindi trovare una soluzione a questo problema.…
Gestione del non determinismo # Il modo più facile per gestire il non determinsmo è semplificare le grammatiche quindi andiamo a vedere metodi per fare ciò. Semplificazione grammatiche (5) # Slide No produzioni del tipo A → ε per bottom up (altrimenti va all'infinito!) No…