Scala Parser Combinator, Ambiguous Grammar e Parse Forest

Question

Sto cercando di ottenere il parser per restituire tutti i possibili risultati di analisi (foresta di analisi) da una grammatica ambigua e scegliere dalla foresta di analisi valutandoli rispetto al contesto/cronologia utente e una conoscenza base. Per ragioni di prestazioni, questo dovrebbe probabilmente essere fatto con il parser packrat e un limite di ricerca/limite superiore per limitare il numero di chiamate ricorsive nell'applicare le regole di produzione per evitare loop infiniti.

Essendo nuovo sia per Scala che per i suoi Combinatori di parser, non riesco a capire come farlo o se sia possibile farlo. Qualcuno potrebbe aiutarmi? Molto apprezzato.

Cordiali saluti, Thomas Juan

Answer 1

Non si può fare questo con Scala di built-in combinatori parser. I combinatori Packrat sono limitati alle sole grammatiche non ambigue. Se si tenta di gestire l'ambiguità, si perde la capacità di memoizzare e la complessità dell'analisi diventa O (k^n) anche per scie non ambigue. Quindi, non farlo.

Quello che vuoi è un framework di combinatore di parser che gestisca correttamente l'ambiguità. Per quanto ne so, l'unico framework di questo tipo per Scala è il mio GLL combinators. La sintassi è quasi identica ai combinatori di parser di Scala (la differenza principale è che le funzioni di livello superiore funzionano correttamente), ma l'output è Stream[A], dove A è il tipo di risultato. Quindi, ottieni una foresta di analisi. Si noti che il risultato non è in realtà un SPPF (foresta di analisi compresso condivisa), quindi se si produce un numero esponenziale di risultati, lo stream avrà dimensioni proporzionali. Questo è stato fatto per mantenere la massima flessibilità nel tipo di risultato.

I combinatori GLL sono O (n^3) nel caso peggiore, anche per grammatiche patologicamente ambigue. Nel caso medio, dove il percorso di analisi è univoco, i combinatori GLL sono O (n). L'overhead del tempo costante è attualmente un po 'eccessivo, ma l'ottimizzazione è un progetto in corso. Utilizziamo i combinatori GLL in produzione allo Precog, quindi ci si può aspettare che la libreria sia ben mantenuta in futuro.