Un parser per linguaggi liberi dal contesto basato sull’algoritmo di Earley

Il presente elaborato si rivolge al proseguimento dello sviluppo di uno strumento per la generazione automatica di esercizi con rispettive soluzioni, da proporre agli esami del corso di Linguaggi Formali e Traduttori. La tipologia di esercizi da generare riguarda la parte dei linguaggi liberi dal contesto ponendo il seguente problema: “data una stringa x e una grammatica G libera dal contesto, x è riconosciuta da G? In caso positivo qual è o quali sono gli alberi di derivazione della stringa x rispetto G?”. La generazione automatica di questa tipologia di esercizi richiede l’implementazione di due parti: • la formulazione del problema, cioè la generazione di una grammatica libera dal contesto e una stringa; • la generazione della rispettiva soluzione, ovvero la costruzione degli alberi di derivazione della stringa rispetto alla grammatica, nel caso in cui la stringa appartiene al linguaggio generato dalla grammatica. Dato lo sviluppo già completato della prima parte, nell’elaborato si discute di come sia possibile determinare se una stringa viene riconosciuta da una gram- matica libera dal contesto e, in caso positivo, fornire le derivazioni della stringa nella grammatica. Vengono affrontati quindi i problemi del riconoscimento e del parsing per i linguaggi liberi dal contesto proponendo una soluzione basata sul- l’algoritmo di Earley, discutendo di come l’algoritmo sia in grado di risolvere il problema del riconoscimento per qualsiasi grammatica libera dal contesto e di come sia possibile ottenere un parser raffinando lo stesso algoritmo, conservan- done lo stesso potere riconoscitivo. Inoltre la stesura della soluzione è presentata in ottica di una possibile implementazione in un linguaggio puramente funzionale come Haskell.