Analizzatore grafico - Chart parser
In informatica , un parser di grafici è un tipo di parser adatto per grammatiche ambigue (comprese le grammatiche dei linguaggi naturali ). Utilizza l' approccio della programmazione dinamica: i risultati ipotizzati parziali vengono memorizzati in una struttura chiamata grafico e possono essere riutilizzati. Ciò elimina il backtracking e previene un'esplosione combinatoria .
L'analisi dei grafici viene generalmente attribuita a Martin Kay .
Tipi di analizzatori di grafici
Un approccio comune consiste nell'utilizzare una variante dell'algoritmo di Viterbi . Il parser Earley è un tipo di parser grafico utilizzato principalmente per l'analisi nella linguistica computazionale , dal nome del suo inventore. Un altro algoritmo di analisi del grafico è l'algoritmo Cocke-Younger-Kasami (CYK).
I parser di grafici possono essere utilizzati anche per analizzare i linguaggi del computer. I parser Earley in particolare sono stati usati nei compilatori-compilatori dove la loro capacità di analizzare usando grammatiche libere dal contesto arbitrarie facilita il compito di scrivere la grammatica per una particolare lingua. Tuttavia la loro minore efficienza ha portato le persone a evitarli per la maggior parte del lavoro del compilatore.
Nell'analisi bidirezionale del grafico, i bordi del grafico sono contrassegnati con una direzione, avanti o indietro, e le regole vengono applicate sulla direzione in cui i bordi devono puntare per essere combinati in ulteriori bordi.
Nell'analisi incrementale del grafico, il grafico viene costruito in modo incrementale man mano che il testo viene modificato dall'utente, con ogni modifica al testo risultante nella minima modifica possibile corrispondente al grafico.
I parser di grafici si distinguono tra top-down e bottom-up , nonché attivi e passivi.
