New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Parser Traversal? #158

Closed
carueda opened this Issue Jul 7, 2017 · 2 comments

Comments

Projects
None yet
2 participants
@carueda
Contributor

carueda commented Jul 7, 2017

(from gitter)

The fastparse DSL is just fantastic to the developer!

Here I'm wondering about some mechanism to traverse the parser instance to construct a representation (say, some simplified pseudo EBNF), mainly targeted at the less-expert user, and for not-necessarily-formal documentation.

Say, operating on the expr parser in this example:

val number: P[Int] = P( CharIn('0'to'9').rep(1).!.map(_.toInt) )
val parens: P[Int] = P( "(" ~/ addSub ~ ")" )
val factor: P[Int] = P( number | parens )

val divMul: P[Int] = P( factor ~ (CharIn("*/").! ~/ factor).rep ).map(eval)
val addSub: P[Int] = P( divMul ~ (CharIn("+-").! ~/ divMul).rep ).map(eval)
val expr: P[Int]   = P( addSub ~ End )

generate something like:

expr   = addSub End 
addSub = divMul ( CharIn("+-") divMul )*
divMul = factor ( CharIn("*/") factor )*
factor = number | parens
parens = "(" addSub  ")"
number = CharIn('0' to '9')+

Anybody have any hints on how to accomplish this? Perhaps worth considering adding support for this in the library itself? Thx.

Jun 29 23:59
there is no way right now

each parser is a totally opaque Parser[T] with a totally opaque .parse method

i've had some ideas of how to make it work, but it's a hard problem that goes against the grain of how the library works right now

basically we need to make Parser[T]s less opaque so we can inspect them without executing .parse, and from there we can then do this kind of transformation/rendering

@lihaoyi lihaoyi changed the title from parser traversal? to Parser Traversal? Jul 7, 2017

@lihaoyi

This comment has been minimized.

Show comment
Hide comment
@lihaoyi

lihaoyi Jul 7, 2017

Owner

Basically, we need to let people recurse over the Parser[T] objects without executing them.

Apart from letting us pretty-print it, we could use that info to perform transformations/optimizations of the parser tree (parser tree, not the parse tree), and probably other things.

This isn't hard in niche cases: most parsers are made of typical |s, ~s, and intrinsics which can be enumerated. However, in the general case a Parser[T] can be almost anything, so we'd want a way to recurse over "unknown" parsers even if we end up ignoring them or handling them with some default handler.

I imagine a good approach may be to

  • Force parsers to define a def children: Iterator[Parser] attribute. This can default to empty for "leaf" parsers, and non-empty for parsers like ~ or | or .rep

  • Define a general def traversal[T, V](p: Parser[T]): V method that works on Parser[T]s and recurses over children, with a callback/transformation on each child

  • Write a callback/transformation for use with traversal[_, String] that can then be used to convert the parsers into a String. Additional transformations could be used with e.g. traversal[T, Parser[T]] to convert a parser into a more-optimized parser, etc.

This is rough and not nearly sufficiently fleshed out, but I think it could work if anyone wants to take a crack at it

Owner

lihaoyi commented Jul 7, 2017

Basically, we need to let people recurse over the Parser[T] objects without executing them.

Apart from letting us pretty-print it, we could use that info to perform transformations/optimizations of the parser tree (parser tree, not the parse tree), and probably other things.

This isn't hard in niche cases: most parsers are made of typical |s, ~s, and intrinsics which can be enumerated. However, in the general case a Parser[T] can be almost anything, so we'd want a way to recurse over "unknown" parsers even if we end up ignoring them or handling them with some default handler.

I imagine a good approach may be to

  • Force parsers to define a def children: Iterator[Parser] attribute. This can default to empty for "leaf" parsers, and non-empty for parsers like ~ or | or .rep

  • Define a general def traversal[T, V](p: Parser[T]): V method that works on Parser[T]s and recurses over children, with a callback/transformation on each child

  • Write a callback/transformation for use with traversal[_, String] that can then be used to convert the parsers into a String. Additional transformations could be used with e.g. traversal[T, Parser[T]] to convert a parser into a more-optimized parser, etc.

This is rough and not nearly sufficiently fleshed out, but I think it could work if anyone wants to take a crack at it

@lihaoyi

This comment has been minimized.

Show comment
Hide comment
@lihaoyi

lihaoyi Oct 18, 2018

Owner

Closing due to inactivity

Owner

lihaoyi commented Oct 18, 2018

Closing due to inactivity

@lihaoyi lihaoyi closed this Oct 18, 2018

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment