Combinatori parser generalizzati dal basso in Haskell

Question

Mi chiedo perché non ci siano combinatori di parser generalizzati per l'analisi bottom-up in Haskell come un combinatore di parsec per l'analisi top-down.
(sono riuscito a trovare un po 'di lavoro di ricerca è andato nel corso del 2004, ma nulla dopo
https://haskell-functional-parsing.googlecode.com/files/Ljunglof-2002a.pdf http://www.di.ubi.pt/~jpf/Site/Publications_files/technicalReport.pdf)

C'è un motivo specifico per non realizzarlo?

Answer 1

Questo a causa della trasparenza referenziale. Così come nessuna funzione può dire la differenza tra

let x = 1:x 
let x = 1:1:1:x 
let x = 1:1:1:1:1:1:1:1:1:... -- if this were writeable 

nessuna funzione può dire la differenza tra una grammatica, che è un grafico finito e una grammatica, che è un albero infinito. Gli algoritmi di analisi bottom-up devono essere in grado di vedere la grammatica come un grafico, al fine di enumerare tutti i possibili stati di analisi.

Il fatto che i parser top-down vedano il loro input come alberi infiniti consente loro di essere più potenti, dal momento che l'albero potrebbe essere computazionalmente più complesso di qualsiasi grafico; per esempio,

numSequence n = string (show n) *> option() (numSequence (n+1)) 

accetta qualsiasi sequenza ascendente finito di numeri da n. Questo ha infiniti diversi stati di parsing. (Potrebbe essere possibile rappresentare in un modo context-free, ma sarebbe difficile e richiede una maggiore comprensione del codice di una libreria di analisi è in grado di, credo)

Un basso verso l'alto biblioteca combinatore poteva essere scritta, anche se è un po 'brutto, richiedendo tutti parser per essere "etichettato" in modo tale che

• la stessa etichetta si riferisce sempre alla stessa parser e
• c'è solo un insieme finito di etichette

a quel punto inizia ad assomigliare molto più ad una specifica tradizionale di una grammatica che ad una specifica combinatoria. Tuttavia, potrebbe essere ancora bello; dovresti solo etichettare produzioni ricorsive, che escluderebbero regole infinitamente grandi come numSequence.

Answer 2

Come la risposta di luqui indica un parser bottom-up combinator la libreria non è una realistica. Sulla possibilità che qualcuno arrivi a questa pagina cercando il parser bottom up di haskell generatore, quello che stai cercando si chiama the Happy parser generator. È come yacc per haskell.

Answer 3

Come detto sopra: il trattamento di Haskell delle definizioni del parser ricorsivo non consente la definizione di librerie di analisi bottom-up. Le librerie di analisi bottom-up sono possibili anche se si rappresentano le grammatiche ricorsive in modo diverso. Con le scuse per l'autopromozione, una libreria di ricerca (di ricerca) che utilizza tale approccio è grammar-combinators. Implementa una trasformazione grammatica denominata trasformazione Paull uniforme che può essere combinata con l'algoritmo del parser top-down per ottenere un parser bottom-up per la grammatica originale.