Analisi sintattica (linguaggi formali)

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.

lezione
lezione
Analisi sintattica (linguaggi formali)
Tipo di risorsa Tipo: lezione
Materia di appartenenza Materia: Linguaggi formali e automi
Avanzamento Avanzamento: lezione completa al 00%

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:

 

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
  1. LL è acronimo di Left-to-right e Leftmost.