Semplificazione grammatiche

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

  

1. No produzioni del tipo $A \to \varepsilon$ per bottom up (altrimenti va all’infinito!)
2. No produzioni unitarie, così evito cicli in cui da A derivo sé stesso.
3. No simboli inutili
4. No ricorsione sinistra (divergenza per top-down)
5. Fattorizzazione della grammatica

Eliminazione delel produzioni nulle

Vogliamo creare un algoritmo utile ad eliminare le produzioni che non ci piacciono.

• Formalizzazione algo obiettivo

!

Insieme dei simboli annullabili 🟩

Vogliamo con questa parte definire in modo formale l’insieme dei non terminali che portano a produzioni di quel genere

• Slide definizione simboli annullabili

!

Ossia una annullabilità in n passi, e andiamo ad indagare tutti i simboli che soddisfano queste cose.

NOTA: nello step induttivo, un simbolo è annulable solo se l’intera produzione è annullabile (quindi tutte le cose in output.

Una cosa del tipo $A \to BC$ è annullabile solo se lo sono entrambi (sia B che C).

Derivazione grammatica annullabilità 🟩

• Slide

  

• Slide esempio

  

Intuizione

In pratica vado ad eliminare i non terminali in tutti i modi possibili, e vado ad eliminare quelle che poi vanno ad eliminare. In pratica mi vado a tenere tutte le configurazioni che posso attenere, annullando quello che si può annullare.

Faccio questa cosa per tutti!

Nota sul vuoto

Se vogliamo che il nuovo linguaggio possa accettare il vuoto, allora basta aggiungere al non terminale iniziale la produzione dle tipo $S \to \varepsilon$, ma questo è presente solo al primo!.

Produzioni unitarie

Vorremmo evitare le produzioni unitarie che portano a cicli perché altrimenti avrei dei cicli infiniti che non sono molto buoni per il parsing.

• Definizioni utili

  

Coppie unitarie 🟩

• Slide

  

In pratica è come se definissi una operazion per le coppie unitarie, e la chiudo per riflessività e transitività.

Algoritmo di eliminazione 🟩

• Algoritmo per eliminare coppie unitarie

  

Per la creazione della nuova grammatica, quello che faccio non è altro che filtrare quelle che mi portano a coppie unitarie.

Oltre a questo faccio una copia… Se guardi l’esempio comunque lo vedi un pò meglio

• Esempio

  

Rimozione di simboli inutili

Def generatore e raggiungibilità (2) 🟩

In questa sezione andiamo a definire alcuni concetti utili a definire l’inutilità di alcuni simboli

• Slide

!

Così andiamo a definire come simbolo utile simbolo generatore e raggiungibile.

Così andiamo a racchiudere il concetto di simbolo che non genera nulla, come inutle

• Esempio in slide

!

Calcolo dei simboli generatori 🟩-

• Slide

!

Ossia se da un simbolo ricavo qualcosa che è un generatore, allora questo è un generatore!

E posso creare un algoritmo ricorsivo che genera questi simboli, partendo dai terminali che sono sempre dei generatori

Calcolo dei simboli raggiungibili 🟨++

• Slide

  

In pratica mi calcolo, ancora qui in modo ricorsivo, tutti i strumenti raggiungibili dal nodo di start, con qualcosa di simile a una dfs (aggiungo ai raggiungibili ogni non terminale figlio, e comincio ad esplorare questo non terminale).

Wrap-up (chiede) 🟨+

• Enunciato e dimostrazione

  

L’algoritmo è molto semplice, è costituito da due passi fondamentali:

1. Elimino tutti i simboli che non sono generatori
2. Rimuovo tutti i simboli non raggiungibili

Nota sull’ordine

È importante eseguire le operazioni in questo ordine, altrimenti capita come in slide

• Esempio importanza di ordine

  

• Esempio più tosto di applicazione di questo

  

Eliminazione rico sinistre

Rico sinistre immediate 🟨

• Slide

  

L’idea è spaccare la ricorsione sinistra in una altra produzione e un nuovo non terminale fittizzio che vado ad utilizzare come non terminale di supporto.

• Esempio di risoluzione

  

Posso considerare queste immediate, quando non ho dei cicli chiari nelle ricorsioni sinistre, sotto proviamo a creare un algoritmo per risolvere ricorsioni sinistre con cicli.

Rico sinistre non-immediate 🟥+

• Esempio di non-immediato

  

• Algoritmo di risoluzione O(n2)

  

In pratica provo a sostituire tutto quanto posso in modo greedy.

• Esempio di applicazione

  

• Esempio applicazione con tutto finora

  

Fattorizzazione 🟩

• Slide problema generale

  

L’intuizione per sta parte è raccogliere le cose in comune. L’algoritmo non va a far altro che guardare i prefissi, e prendere il più lungo per ogni non terminale.

• Algoritmo per fattorizzazione

  

• esempio di applicazione

  

Forme normali

Chomsky Normal Form

• Slide

  

Questa ci piace, perché le produzioni o sono di

1. SIngolo terminale
2. Doppio non terminale.

Si può notare che questa forma è sia libera da epsilon sia sia libera da coppie unitarie.

E si può sempre trovare una grammatica in questa forma, questa cosa ci piace.

Greibach Normal Form

• Slide

  

Anche questa si può sempre fare, ed è una forma che ci piace perché non abbiamo derivazione ricorsive sinistre brutte che ci distruggono tutto.