Deforested tree construction possible?

[modulovalue]

Hello @ianh,

Here you wrote:

So the last thing to do is to incrementally update the tree itself based on the change to the sequence of construction actions. I'm not sure how to do this, but I'm sure someone has written about it somewhere.

This reminds me a lot of GLR parsing. One thing that has made GLR parsing much simpler for me is not to construct an explicit tree, but to maintain a postordered list of tree events (see "Post-Order Parser Output" for a brief explanation).

A postordered list of events is inherent to LR parsing. A preordered list of events is inherent to LL parsing. I was wondering, how feasible would it be to support generating such a list of events with the approach that owl takes? That is, would it be possible to compress your construction actions into just 2 categories of events: begin_subtree_of_type_x and end_subtree_of_type_x?

If so, do you think that your approach would support a preordered or a postordered list of events?

With such a list of events, updating subtrees could be made very simple with a Piece table, which I'm currently investigating in a different project.

[ianh]

Owl does use an event-based approach, though it's a little strange because (as I mentioned in the other issue), they're generated in a backward pass, with the "end" event before the "begin". I guess it would be preordered, but in reverse?

I'm curious what changes to owl you're looking to see here? Are you planning to use it for something where incremental parsing is important? Or do you want to understand how it works so you can build something like it (which to be clear I would be happy to help with however I can)?

[modulovalue]

Are you planning to use it for something where incremental parsing is important? Or do you want to understand how it works so you can build something like it

I'm currently researching if it would make sense to use visibly pushdown parsers for parsing the lexical structure of programming languages instead of immediately going to context free parsers if the lexical structure is not regular.

---

I guess it would be preordered, but in reverse?

Oh, that's interesting.

If my observations are correct, then the following parsing methods result in the following tree event orders:

LR (bottom up left to right): postorder
RR (bottom up right to left): postorder where the children are reversed (i.e., reversed preorder)
LL (top down left to right): preorder
RL (top down right to left): preorder where the children are reversed (i.e., reversed postorder)

I have an LR-style parser generator and I would like to maintain a single list of events for lexical and syntactical ASTs.

It seems that if owl supports RR-style events, that this wouldn't be compatible with LR-style events.

However, I might have to implement an RR-style mode of operation for my parser generator because this makes it much more efficient to traverse children from left to right. In which case it would become compatible with your approach.

I'm curious what changes to owl you're looking to see here?

Your RR-style approach might in fact be superior in practice, so, none, but I'm not entirely sure yet. I'll have to think some more.

Thank you for your help!