BOOST SPIRIT parsing - create correct AST tree

Question

I have to parse using Boost Spirit a sequence like

t1 JOIN t2 JOIN t3 JOIN ... JOIN tn

and the result should be AST tree with the semantics

((...((t1 JOIN t2) JOIN t3) JOIN ...) JOIN tn)

I tried to use a rule like:

source = singleTable | (source >> JOIN >> singleTable);

but, per Boost Spirit design, the parsing process uses just the first part of the rule and parses only the first item ("t1") from expression and lefts the rest of the sequence not parsed ("JOIN t2 JOIN t3 JOIN ... JOIN tn").

Which is the best way to solve this problem?

I can rewrite the rule like

source = (singleTable >> JOIN >> source) | singleTable;

but in this case the created AST will look like

(t1 JOIN (t2 JOIN (t3 JOIN (... JOIN tn)...))).

So I will need a supplementary processing step to get the AST to the desired form.

Is there any other method that provides the correct AST after parsing?

Answer 1

*Aside Database engines don't blindly create their ASTs like that. More likely, they probably create an unordered list of row sources ((joins to) tables/views) and let the query optimizer work out how to optimally plan the execution.

Barring a better example of your actual AST, here's a rule that comes closer:

 singleTable >> - ("JOIN" >> source)