Say I want to parse a file in language X. Really, I'm only interested in a small part of the information within. It's easy enough to write a parser in one of Haskell's many eDSLs for that purpose (e.g. Megaparsec).
data Foo = Foo Int -- the information I'm after.
parseFoo :: Parsec Text Foo
parseFoo = ...
That readily gives rise to a function getFoo :: Text -> Maybe Foo
.
But now I would also like to modify the source of the Foo
information, i.e. basically I want to implement
changeFoo :: (Foo -> Foo) -> Text -> Text
with the properties
changeFoo id ≡ id
getFoo . changeFoo f ≡ fmap f . getFoo
It's possible to do that by changing the result of the parser to something like a lens
parseFoo :: Parsec Text (Foo, Foo -> Text)
parseFoo = ...
but that makes the definition a lot more cumbersome – I can't just gloss over irrelevant information anymore, but need to store the match of every string
subparse and manually reassemble it.
This could be somewhat automated by keeping the string-reassembage in a StateT
layer around the parser monad, but I couldn't just use the existing primitive parsers.
Is there an existing solution for this problem?
A parser generator takes a grammar as input and automatically generates source code that can parse streams of characters using the grammar. The generated code is a parser, which takes a sequence of characters and tries to match the sequence against the grammar.
A lexer is a software program that performs lexical analysis. ... A parser goes one level further than thelexer and takes the tokens produced by the lexer and tries to determine if proper sentences have been formed. Parsers work at the grammatical level, lexerswork at the word level.
Is this a case of "bidirectional transformation"? E.g., http://ceur-ws.org/Vol-1571/
In particular, "Invertible Syntax Descriptions: Unifying Parsing and Pretty Printing" by Rendel and Osterman http://dblp.org/rec/conf/haskell/RendelO10 , Haskell Symposium 2010 (cf. http://lambda-the-ultimate.org/node/4191 )
A solution implemented in Haskell? I don't know of one; they may exist.
In general, though, one can store enough information to regenerate a legal version of the program that resembles the original to an arbitrary degree, by storing "formatting" information with collected tokens. In the limit, the format information is the original string for the token; any approximation of that will give successively less accurate answers.
If you keep whitespace as explicit tokens in the parse tree, in the limit you can even regenerate that. Whether that is useful likely depends on the application. In general, I think this is overkill.
Details on what/how to capture and how to regenerate can be found in my SO answer: Compiling an AST back to source code
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With