On 7 June 2015 at 16:32, Jonathan S. Shapiro <s...@eros-os.org> wrote:
> On Sat, Jun 6, 2015 at 12:11 PM, Keean Schupke <ke...@fry-it.com> wrote: > > What I do in the C++ combinators, because backtracking is controlled by >> the 'attempt' parser (its the only place backtracking happens) is save the >> current state and restore it on backtracking. The current state is threaded >> like the inherited attributes of an attribute grammar, so if you want >> backtracking it has to be copyable and assignable. >> > > So the "copyable and assignable" part makes sense, but I don't know that > this answers the question I was trying to ask. > > Assume the parse result is some form of graph structure. Perhaps an AST. > How do we get unreachable subtrees collected? It's a problem for LR parsers > as well. I'm just curious what your mental model is for how to do that. > Offhand, I think refcounted pointers. > > Backtracking seems to be one of those things that's harder to do without > GC. > The way to implement backtracking is with a vector of unique pointers, so that popping the vector de-constructs the heap objects. You then build an undo list where you record every link you make in the tree, recording the previous destination in the tree indexed by the object linked from. When you come to a choice point you record the index of the last heap item in the vector, and the last link in the undo-stack. To backtrack you 'undo' each link made in reverse order using the undo stack, and after all links safely removed, you resize the vector containing the unique pointers which frees the heap objects. You do this to both stacks until you get back to the choice-point. This is much more efficient than ref-counting. However the simple way is to include all the data in the state object, so for example linearise the tree into a vector, and use the copy assignment. Complex graph structures can be represented in managed memory objects in C++ that support copy and assignment by, for example having a separate vector for each node type (so no pointers) and a vector for edges. This can simply be copied at choice-points, and restored by assignment. In general it is better to code objects that behave as values, and support copy and assignment, even if they are complex tree structures. In C++ you would provide a copy operator and assignment operator for your AST however you implement it. Keean.
_______________________________________________ bitc-dev mailing list bitc-dev@coyotos.org http://www.coyotos.org/mailman/listinfo/bitc-dev
