Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is there an established way to write parsers that can reconstruct their exact input?

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?

like image 964
leftaroundabout Avatar asked May 30 '16 15:05

leftaroundabout


People also ask

How do parser generators work?

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.

What is a Lexer vs parser?

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.


2 Answers

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 )

like image 140
d8d0d65b3f7cf42 Avatar answered Sep 28 '22 15:09

d8d0d65b3f7cf42


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

like image 45
Ira Baxter Avatar answered Sep 28 '22 14:09

Ira Baxter