Skip to content

isNullable is exponential in certain degenerate cases #25

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

Open
djspiewak opened this issue Feb 3, 2017 · 0 comments
Open

isNullable is exponential in certain degenerate cases #25

djspiewak opened this issue Feb 3, 2017 · 0 comments

Comments

@djspiewak
Copy link
Owner

lazy val a = b | b
lazy val b = c | c
lazy val c = d | d
// ...
lazy val z = a | a

Example courtesy of Michael Adams. I'm pretty sure this requires 2^26 operations to compute, since tracked is unshared between branches. Unfortunately, the fix is not as simple as extracting tracked to be shared by both branches, since doing so will cause nodes to not be revisited when their values have been subsequently determined. An example of where naive extraction will fail:

lazy val a: Parser[Any] = b ~ c
lazy val b: Parser[Any] = c | () ^^^ ""
lazy val c: Parser[Any] = b | "x"

a.isNullable must beTrue
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant