Riassunto

Grammatica / Linguaggi liberi (context-free)


Pumping lemma per linguaggi liberi

Il negato di questo lemma ci permette di dimostrare che non esiste una determinata grammatica libera che genera un dato linguaggio.

Enunciato

Sia L un linguaggio libero. Allora:

โˆƒpโˆˆN+ย t.c.ย โˆ€zโˆˆL,|z|โ‰ฅp,โˆƒu,v,w,x,yย t.c.ย 
  1. z=uvwxy

  2. |vwx|โ‰คp

  3. |vx|>0

  4. โˆ€iโˆˆNย (anche nullo),ย uviwxiyโˆˆL


Proprietร 

I linguaggi liberi sono chiusi per UNIONE, CONCATENAZIONE ma NON per intersezione.


Espressioni regolari

Valgono:

Operazione Sintassi Linguaggio
ALTERNANZA rโˆฃs L(r)โˆชL(s)
CONCATENAZIONE rโ‹…s L(r)L(s)
MOLTEPLICITร€ rโˆ— {ฮต}โˆช{w1โ€ฆwkโ€ฆ}
PRECEDENZA (r)

Precedenze

โˆ—>โ‹…>โˆฃ

Esempio:

aโˆฃbโˆ—cโŸถ(aโˆฃ((bโˆ—)โ‹…c))

Conversioni

Da un'espressione regolare รจ possibile:


Simulazione di un NFA

Costo: O(|w|โ‹…(n+m))


Trasformazione di un NFA in DFA

La procedura segue questi passaggi:

  1. Inizio: Si parte da T0, che contiene lo stato iniziale piรน tutti quelli raggiungibili tramite ฮต-transizioni.

  2. Costruzione Tabella: Si crea una tabella dove:

    • Sulle righe si pongono i vari insiemi di stati Tn.

    • Sulle colonne si pongono tutti i terminali dell'alfabeto.

  3. Iterazione:

    • Partendo da T0, per ogni terminale nelle colonne si calcola la transizione, creando cosรฌ un nuovo stato del DFA.

    • Nota bene: Bisogna ricordarsi di calcolare la ฮต-chiusura (o ฮต-transizione) per ognuno degli stati cosรฌ ottenuti!


Minimizzare un DFA

Bisogna intanto essere sicuri che il DFA sia totale, ovvero che ogni stato abbia una transizione per tutti i terminali. Se non รจ cosรฌ, si aggiunge un SINK a cui si fanno arrivare tutte le transizioni mancanti.

A questo punto si inseriscono in un set tutti gli stati non finali ed in un altro set tutti gli stati finali. A questo punto si parte con le n-equivalenze.

Due stati appartengono allo stesso set se:

Se queste condizioni non valgono, i due stati non appartengono allo stesso set.


Linguaggi regolari

Un linguaggio L si dice regolare se e solo se:

Gerarchia delle Grammatiche

Ricordiamo che ogni grammatica regolare รจ anche una grammatica libera (context-free).

Proprietร  di Chiusura

I linguaggi regolari sono chiusi rispetto alle seguenti operazioni:

Pumping lemma per linguaggi regolari

Sia L un linguaggio regolare. Allora:

โˆƒpโˆˆN+ย t.c.ย โˆ€zโˆˆL:|z|โ‰ฅpโˆƒu,v,wย t.c.ย z=uvw&|uv|โ‰คp&|v|>0&โˆ€iโ‰ฅ0,uviwโˆˆL

FIRST

In linea generica, il FIRST di una stringa (di terminali / non-terminali) รจ il primo carattere che compare in ogni produzione di quella stringa.

Dunque:

  1. Per una produzione del tipo Xโ†’ฮต:

    First(X)={ฮต}
  2. Per ogni produzione con inizio di un terminale (Xโ†’aโ€ฆ):

    First(X)={a}
  3. Per ogni produzione del tipo Xโ†’Y1Y2โ€ฆYn con Yi terminali o non-terminali:

    • Se ฮตโˆ‰First(Y1)โŸนFirst(X)=First(Y1)

    • Se ฮตโˆˆFirst(Y1)โŸนFirst(X)={First(Y1)โˆ’ฮต}โˆชFirst(Y2โ€ฆYn)

Per calcolare First(Y2Y3โ€ฆYn) si rieseguono i passaggi del punto 3 ricorsivamente finchรฉ non si incontra un First che non contenga ฮต.

Se ฮตโˆˆFirst(Yn) (ovvero tutti i componenti della produzione possono annullarsi), allora:

First(X)=First(X)โˆช{ฮต}

FOLLOW

In linea generica il FOLLOW di una stringa (di non-terminali) รจ l'insieme dei terminali che seguono la stringa in qualche derivazione.

Procedura di calcolo

  1. Inizio: Come primo passo si aggiunge il simbolo $ (fine input) ai follow dello start symbol.

  2. Iterazione: Per ogni produzione del tipo Bโ†’Aฮฒ (dove A รจ un non-terminale e ฮฒ รจ la stringa che segue):

    • Se ฮฒโ‰ ฮต:

      Follow(A).addย (First(ฮฒ)โˆ–{ฮต})
    • Se ฮฒ=ฮตโˆจฮตโˆˆFirst(ฮฒ):

      Follow(A).addย (Follow(B))

Nello schema sopra, A rappresenta un non-terminale e ฮฒ รจ la stringa che lo segue all'interno di una produzione.


Parsing Top-Down: LL(1) parser

Sta per "Left-to-Right Leftmost" parser. Prende in input una parola e la parsing table e restituisce in output la derivazione leftmost per ottenere la parola (se โˆˆL(G)), altrimenti restituisce un errore.

Procedimento

  1. Calcolare First e Follow di ogni non-terminale.

  2. Costruire la tabella di parsing.

  3. Riconoscimento della parola usando uno stack e la parsing table.

Il punto 1 l'abbiamo giร  esplorato in precedenza.

(2) Costruzione della tabella di parsing

Innanzitutto si crea una tabella con:

Si prende poi ogni produzione della grammatica e si applica la seguente logica:

Algoritmo di riempimento:

foreach (Aโ†’ฮฑ):

โ€ƒ foreach (terminale bโˆˆFirst(ฮฑ)):

โ€ƒ โ€ƒ inserire Aโ†’ฮฑ nella entry [A,b] della tabella

โ€ƒ if ฮตโˆˆFirst(ฮฑ):

โ€ƒ โ€ƒ foreach (terminale xโˆˆFollow(A)):

โ€ƒ โ€ƒ โ€ƒ inserire Aโ†’ฮฑ nella entry [A,x]

(3) Grammatica LL(1)

Se la tabella di parsing non ha piรน di una produzione per una certa cella (non ha "multiple defined entries"), allora la grammatica รจ LL(1).

Riconoscimento della parola

In questa fase ci servono:

Procedimento

L'algoritmo legge la parola e utilizza lo stack per verificare la correttezza della derivazione:

stack s;
s.push($); 
s.push(S); // S รจ lo start symbol
x = s.top();

while (x != $) {
    b = read(); // legge un carattere dalla parola

    if (x == b) {
        s.pop();
    } 
    else if (x is terminal || M[x, b] is error) {
        error();
    } 
    else if (M[x, b] == A -> Y1 ... Yn) {
        s.pop();
        s.push(Y1 ... Yn); // Push dei simboli della produzione
    }
    
    x = s.top();
}

// Se il ciclo termina correttamente: w โˆˆ L
Nota sulla funzione read()

La funzione read() legge un carattere alla volta dalla parola in input.


Tips per riconoscere se una grammatica รจ LL(1)

Data una grammatica G con produzioni nel formato Aโ†’ฮฑโˆฃฮฒ, allora:

Casi di non-LL(1):

Rimuovere la ricorsione a sinistra

Generalmente, dato lo schema:

Aโ†’Aฮฑ1โˆฃโ‹ฏโˆฃAฮฑnโˆฃฮฒ1โˆฃโ‹ฏโˆฃฮฒk

con ฮฑjโ‰ ฮต e ฮฒiโ‰ Aฮณ

Si trasforma in:

Aโ†’ฮฒ1Aโ€ฒโˆฃโ‹ฏโˆฃฮฒkAโ€ฒAโ€ฒโ†’ฮฑ1Aโ€ฒโˆฃโ‹ฏโˆฃฮฑnAโ€ฒโˆฃฮต
In breve

Le produzioni non affette da ricorsione le tieni, ma ci attacchi Aโ€ฒ. Le altre le sposti in Aโ€ฒ ma senza la A ricorsiva iniziale.

Ricorsione sinistra non immediata

In caso di ricorsione sinistra non immediata, si sostituiscono le produzioni del 1ยฐ NON-terminale nel 2ยฐ NON-terminale.

Esempio:

Dati i seguenti passaggi:

Aโ†’BaโˆฃbBโ†’BcโˆฃAdโˆฃb

In questo caso, abbiamo una ricorsione sinistra su A (indiretta): Aโ‡’Baโ‡’AdA.

1. Procediamo per sostituzione

Sostituiamo le produzioni di A all'interno di B dove compare il simbolo non-terminale A.

La produzione Bโ†’Ad diventa quindi:

Bโ†’Badโˆฃbd

Otteniamo quindi la grammatica aggiornata:

Aโ†’BaโˆฃbBโ†’BcโˆฃBadโˆฃbdโˆฃb

2. Togliamo ora la ricorsione (immediata)

Applichiamo l'algoritmo standard per eliminare la ricorsione sinistra su B:

Aโ†’BaโˆฃbBโ†’bdBโ€ฒโˆฃbBโ€ฒBโ€ฒโ†’cBโ€ฒโˆฃadBโ€ฒโˆฃฮต

Fattorizzazione a sinistra

Data una grammatica del tipo:

Aโ†’ฮฑฮฒ1โˆฃโ‹ฏโˆฃฮฑฮฒnโˆฃฮณ1โˆฃโ‹ฏโˆฃฮณk

Questa si trasforma in:

Aโ†’ฮฑAโ€ฒโˆฃฮณ1โˆฃโ‹ฏโˆฃฮณkAโ€ฒโ†’ฮฒ1โˆฃโ‹ฏโˆฃฮฒn

E si continua iterativamente finchรฉ la grammatica non diventa LL(1).

Rimuovere le ambiguitร 

Non esiste un vero e proprio algoritmo universale, ma generalmente si segue questa regola logica:

Si cerca di tenere nelle prime derivazioni (quelle piรน vicine allo start symbol) i caratteri/operatori con minore prioritร , e nelle ultime derivazioni quelli con maggiore prioritร . In questo modo, nell'albero di derivazione, gli operatori con maggiore prioritร  si troveranno piรน in basso (e verranno quindi valutati per primi).

Esempio pratico

Data la grammatica ambigua:

Sโ†’SaSโˆฃSbSโˆฃScSโˆฃid

Con prioritร  degli operatori: c>b>a.

La grammatica trasformata diventa:

  1. Livello prioritร  bassa (a): Sโ†’SaEโˆฃE

  2. Livello prioritร  media (b): Eโ†’EbTโˆฃT

  3. Livello prioritร  alta (c): Tโ†’TcQโˆฃQ

  4. Qโ†’id

SLR(1)

Sta per Simple Left-to-right Rightmost parser. Siamo nel Bottom-Up parsing.

Procedimento

  1. Costruzione dell'automa

  2. Costruzione della tabella di parsing

  3. Riconoscimento della parola

1. Costruzione dell'automa

2. Costruzione della tabella di parsing

Ci sono essenzialmente 4 casi per il riempimento:

3. Riconoscimento della parola

L'algoritmo vero e proprio serve per ottenere il parsing di una parola w. Se wโˆˆL(G) l'algoritmo ha successo, altrimenti restituisce error().

Configurazione iniziale:

Algoritmo

b = first_symbol_in_the_input_buffer;
stSt.push(0); // Inizializza lo stack degli stati con lo stato 0

while (true) {
    S = stSt.top();

    if (M[S, b] == shift T) {
        symSt.push(b);      // Push del simbolo letto
        stSt.push(T);       // Push del nuovo stato
        b = next_symbol();  // Avanza nell'input
    }
    else if (M[S, b] == reduce A -> beta) {
        pop |beta| symbol off symSt; // Rimuove simboli pari alla lunghezza di beta
        symSt.push(A);               // Push del non-terminale driver
        pop |beta| state off stSt;   // Rimuove gli stati corrispondenti
        stSt.push(M[stSt.top(), symSt.top()]); // Esegue il GOTO
		print(A -> beta);
    }
    else if (M[S, b] == Accept) {
	    return; // Parsing completato con successo
	}
	else {
	    error(); // Errore di sintassi
	}
}

Generazione del codice intermedio

Questa fase si occupa di tradurre le istruzioni della grammatica in un linguaggio intermedio (solitamente simile all'assembly o a tre indirizzi) utilizzando degli attributi sintetizzati o ereditati.

Produzione Pโ†’S

Produzione Sโ†’if(B)S1

Produzione Sโ†’if(B)S1ย elseย S2

Produzione Sโ†’whileย (B)S1