hime icon indicating copy to clipboard operation
hime copied to clipboard

SPPF spanning tree iterator

Open stevefan1999-personal opened this issue 8 months ago • 0 comments

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.

stevefan1999-personal avatar Oct 17 '23 07:10 stevefan1999-personal