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.
Parser
modificaPiù 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
modificaQuando 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
modificaData la seguente grammatica:
Possiamo costruire la relativa rete:
Bottom-up LR (k)
modificaTop-down LL (k)
modificaIn 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
modificaNote
modifica- ↑ LL è acronimo di Left-to-right e Leftmost.