Tree walk without stack or recursion <https://stackoverflow.com/questions/3214312/traverse-tree-without-recursion-and-stack-in-c>
On Monday, December 27, 2021 at 9:44:09 AM UTC-5 Edward K. Ream wrote: > On Monday, December 27, 2021 at 6:30:04 AM UTC-6 Edward K. Ream wrote: > > *Summary* >> >> Any solution must execute arbitrary actions in some desired order. An >> elegant solution seems tantalizingly close, but my usual instincts lead me >> astray. >> > > The solution is starting to take shape: > > 1. Replace visitors with an *action dictionary.* Keys are > node.__class__.__name__; values are lists of actions. > > 2. Actions are like closures: a binding of functions to arguments. But the > actual args are not available in the table. Instead, each action is a > tuple (action_function, arg), where the arg will be a field name. > > For example, we can replace the ast.Module visitor with: > > [(visit_list, 'body')] > > As a more complex example, we could replace the TokenOrderGenerator.If > visitor with something like: > [ > (visit, 'value'), > (visit, 'test'), > (sync_op, ':'), > (visit, 'body'), > (visit_if, 'orelse', ( > (sync_name, 'else'), > (sync_op, ':'), > (visit, 'orelse'), > )), > ] > > Maybe you get the idea. The 'sync_op' and 'sync_name' actions are > particular to the TokenOrderGenerator class, but the *visit *and > *visit_if* actions are more general. > > The *visit* action is the key. The *present node* is an ast.If node. > Let's say the argument is 'value'. If node.value exists, the visit action > will: > > - Push the present node a *node_stack*. > - Make child = getattr(node, 'value') the present node. > - Push action_dictionary [child.__node__.__name__] on an *action_stack.* > > The main iterative loop looks at the next action, which is > action_stack[-1][0] > > When action_stack[-1] becomes the empty list, the main loop will pop the > action stack *and* the node stack, making the top of the node stack the > present node. The traversal is complete when the action stack becomes empty. > > *Summary* > > The *action_dictionary *will contain the *action list* for each kind of > ast node. Each action list will contain a list of actions. > > Each action is a tuple (function, arg), where "arg" must be a string. This > tuple is a kind of closure. More complex actions, like visit_if, may have > the form: (function, arg, inner tuple) > > The iterative main line must use at least a *node_stack* and an *action > stack*. The visit action moves to the next node, pushing entries on the > node_stack and action stacks. The main line pops both stacks when an action > list becomes empty. > > Probably other housekeeping details will be necessary. This whole scheme > is a prototype. > > Edward > -- You received this message because you are subscribed to the Google Groups "leo-editor" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/leo-editor/b081a521-e614-4ae2-9a8f-3417fd7a9da8n%40googlegroups.com.
