I used Flex & Bison to generate a parser. The parser works great. It generates an XML document. It has rules like this:

monthdatetime: TWODIGITS TWODIGITS TWODIGITS TWODIGITS timezone { $$ = concat(10, "<MonthNumeric>", $1, "</MonthNumeric><Day>", $2, "</Day><HourTime>", $3, "</HourTime><MinuteTime>", $4, "</MinuteTime>", $5); }

Now I want to replace the actions with actions that build an abstract syntax tree (AST). The action for the start rule will be to call a "serialize" function that walks the AST to generate the XML in one fell swoop.

That's my plan.

In the rule that I show above, the right-hand side has 5 items. Some rules have even more items. Eeek! Should I design the AST to support nodes with an arbitrary number of branches (N-ary nodes)? In the rule above I would need to replace the action with an action like this:

{ $$ = new_ast("field", $1, $2, $3, $4, $5); } 

Is that a good way to go? Or, should I redesign my rules so that the right-hand side of each rule contains, at most, two items? That way, I can create an AST that is a binary tree.

What do you recommend? Is there a best practice for designing parser rules, with respect to the number of items on the right-hand side of rules? Is it better to create an AST that is a binary tree or an AST that is an N-ary tree?

CodePudding user response：

This is about Computer Science. Any tree structure (with n-way branches) can be used to represent all other trees with m-branches.

If m is smaller than n it is trivial as null is used to fill in the n-m child entries. When n is equal to m then there is also no issue.

You are asking about what to do when m is greater than n. Simple; make them subtrees, which can easily be done. Let us say you wanted to have 9 items in your tree node when there was only space for 5 (like your example), you code it like this:

{$$ = new_ast("field",$1,$2,$3,$4, new_ast("child",$5,$6,$7,$8,$9)); }

Now your tree-walk in the future will know that this is a longer node.