Esiste un modo stabilito per scrivere parser in grado di ricostruire il loro input esatto?

Question

Dire che voglio analizzare un file in lingua X. Davvero, mi interessa solo una piccola parte delle informazioni all'interno. È abbastanza facile scrivere un parser in uno dei numerosi eDSL di Haskell a tale scopo (ad esempio Megaparsec).

data Foo = Foo Int -- the information I'm after. 

parseFoo :: Parsec Text Foo 
parseFoo = ... 

Che prontamente dà origine a una funzione getFoo :: Text -> Maybe Foo.

Ma ora mi piace anche per modificare la fonte delle informazioni Foo, cioè fondamentalmente voglio implementare

changeFoo :: (Foo -> Foo) -> Text -> Text 

con le proprietà

changeFoo id ≡ id 
getFoo . changeFoo f ≡ fmap f . getFoo 

E 'possibile farlo con cambiare il risultato del parser in qualcosa come un obiettivo

parseFoo :: Parsec Text (Foo, Foo -> Text) 
parseFoo = ... 

ma ciò rende la definizione molto più ingombrante – Non riesco a ignorare più informazioni irrilevanti, ma è necessario memorizzare la corrispondenza di ogni string subparse e rimontarla manualmente.

Questo potrebbe essere un po 'automatizzato mantenendo la stringa-riassemblare in un livello StateT attorno alla monade del parser, ma non potrei semplicemente usare i parser primitivi esistenti.

Esiste una soluzione esistente per questo problema?

Answer 1

Una soluzione implementata in Haskell? Non ne conosco uno; possono esistere.

In generale, tuttavia, è possibile memorizzare un numero sufficiente di informazioni per rigenerare una versione legale del programma che assomiglia all'originale a un livello arbitrario, memorizzando le informazioni di "formattazione" con i token raccolti. Nel limite, le informazioni sul formato sono la stringa originale per il token; qualsiasi approssimazione di ciò darà risposte meno accurate.

Se si mantengono spazi bianchi come token espliciti nell'albero di analisi, nel limite è possibile anche rigenerarlo. Se ciò è utile probabilmente dipende dall'applicazione. In generale, penso che questo sia eccessivo.

dettagli su cosa/come catturare e come rigenerare possono essere trovati nel mio SO rispondere: Compiling an AST back to source code

Answer 2

Si tratta di un caso di "trasformazione bidirezionale"? Ad esempio, http://ceur-ws.org/Vol-1571/

In particolare, "Descrizione invertibile Sintassi: Unifying analisi e la stampa piuttosto" di Rendel e Osterman http://dblp.org/rec/conf/haskell/RendelO10, Haskell Symposium 2010 (cfr http://lambda-the-ultimate.org/node/4191)