Analisi sintattica (linguaggi formali)

Da Wikiversità, l'apprendimento libero.
Jump to navigation Jump to search
lezione
Analisi sintattica (linguaggi formali)
Tipo di risorsa Tipo: lezione
Materia di appartenenza Materia: Linguaggi formali e automi
Avanzamento Avanzamento: lezione completa al 00%.

In questa lezione introdurremo gli analizzatori di sintassi o parser, cioè gli algoritmi che analizzano una stringa e generano il suo albero di sintassi secondo un dato linguaggio. Se la stringa non appartiene al linguaggio il parser deve accorgersene e segnalare l'evento.

Parser[modifica]

Più formalmente, data una grammatica un analizzatore di sintassi o parser deve leggere una stringa sorgente e:

  • se : accettare la stringa e produrre un albero di sintassi o una derivazione;
  • se : rifiutare la stringa e segnalare l'errore.
  • se è una proposizione ambigua della grammatica , il parser deve segnalare il problema (alcuni parser generano tutti i possibili alberi di sintassi, altri segnalano solo un errore)

Questo componente è solitamente il primo step dell'esecuzione di un compilatore dopo lo scanner.

Distinguiamo principalmente due approcci alla scrittura di un algoritmo di parsing:

  • Bottom-Up: costruisce l'albero per riduzioni a partire dalle foglie fino alla radice (derivazioni a sinistra);
  • Top-Down: costruisce l'albero per espansioni a partire dalla radice fino alle foglie (derivazioni a destra);

Grammatiche come reti di automi a stati finiti[modifica]

Quando le grammatiche libere dal contesto rappresentano algoritmi di parsing, risulta molto utile trasformarle in reti di automi a stati finiti o rete di macchine a stati finiti(termine generalmente usato in inglese net of finite machines); questo porta a numerosi vantaggi che verranno presentati più avanti nella lezione.

Definiamo ora in maniera sufficientemente formale le reti di automi a stati finiti, aggiungendo anche altre definizioni necessarie:

  • come solito, sia l'alfabeto terminale, il non-terminale e l'assioma della grammatica ;
  • per ogni terminale esiste una regola e è una RE sull'alfabeto ; indichiamo il linguaggio generato da queste RE con i simboli rispettivamente dalla RE della regola di , di e così via...
  • i simboli rappresentano le macchine a stati finiti che accettano i linguaggi rispettivamente
  • per evitare confusione, ogni macchina possiede stati con nomi diversi. In particolare alla macchina saranno assegnati gli stati , alla macchina gli stati e così via, in modo da mantenere gli stati tra le macchine ben disgiunti;
  • definiamo inoltre il linguaggio generato dalla macchina se lo stato iniziale è imposto essere un certo stato ; ovviamente se lo stato è il consueto stato iniziale risulta ;
  • l'insieme di tutte le macchine è detto rete di macchine a stati finiti e si indica con .

Viste le regole qui sopra deifnite, il linguaggio generato dalla rete di macchine a stati finiti è lo stesso della grammatica .

Visto che i linguaggi (e anche ) potrebbe contenere simboli non terminali, definiamo il linguaggio terminale generato da una macchina della rete a partire da un certo stato:

Si noti che essendo l'assioma:

Esempio[modifica]

Data la seguente grammatica:

Possiamo costruire la relativa rete:

Syntax Parser Net Finite States Machine.png

Bottom-up LR (k)[modifica]

Top-down LL (k)[modifica]

In questa sezione presentiamo l'algoritmo di parsing top-down LL (K)[1]. Il "parametro" k indica la lunghezza in caratteri di quanto l'algoritmo può "guardare avanti" (questo concetto sarà ripreso più avanti).

Analisi sintattica di grammatiche non deterministiche - Metodo Early[modifica]

Note[modifica]

  1. LL è acronimo di Left-to-right e Leftmost.