Skip to content
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

SPPF spanning tree iterator #100

Open
stevefan1999-personal opened this issue Oct 17, 2023 · 0 comments
Open

SPPF spanning tree iterator #100

stevefan1999-personal opened this issue Oct 17, 2023 · 0 comments

Comments

@stevefan1999-personal
Copy link
Contributor

This issue is spun-off from #96, where I was trying to "fork" the visitor so that we can implement a novel way to do clean semantic checking. 

However, it seems like there is some problem using traditional "AST walking" technique, which doesn't seem to generate the right derivation regarding multiple versions. 

My initial guess is that, for each version node, the next link to the next production is missing, and so the node walking terminated on the version node instead, causing information loss to the AST visitor. I could be wrong.

There are many solutions to this but one naive way is quite simple: when multiple versions are found, we simply clone the parent node, iterate each version, and glue the links back together after consuming the child version, then yield this node. This is also known as the spanning tree technique since each version should generate a complete walk from start to end of this SPPF over this path.

Alternative explaination

Given this example graph:

Here we have a spanning tree (the definition of spanning tree here is a valid path from start to end over the forest) of "A B C D G", "A B C E G" and "A B F G" respectively. What we should do is just yield them one by one, then the traditional AST walker can be reused on each of them easily.

The current behavior will only emit "A B F G" as one of the valid yields, but when it encounters "A B C D" or "A B C E" it terminates without going to G. Instead "A B C G" is mysteriously yielded. This is behavior observed over the PR mentioned.

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

No branches or pull requests

1 participant