A project involves converting a relational expression map (rxm) to an XML/SQL statement. The map resembles:

root               > people,            # "root" keyword starts the document
person             > person,            # maps table context to a node
.first_name        > first,             # maps a column to a node
.last_name         > name/last,         # maps a column to an ancestor node
.age               > @age,              # @ maps a column to an attribute node
account.person_id +> person.person_id,  # +> performs an INNER JOIN
account            > account,           # context is now "account" node
.id                > @id,               # account id attribute
^,                                      # pop stack to previous context
address            > address,           # switch context to "address" node
.*,                                     # .* globs all columns
account.person_id -> company.person_id, # -> performs an OUTER JOIN
;                                       # Starts the optional WHERE clause

The rxm is converted into Java classes using ANTLR.

Walking through the AST uses a Visitor pattern that calls methods for entering and exiting various parts of the tree. For example:

  public void enterRoot( QueryParser.RootContext context ) {
    System.out.println( "Root: " + context.getChild(2).getText() );

  public void exitRoot( QueryParser.RootContext context ) {
    System.out.println( "<< root" );


The code needs to generate an XML/SQL statement along the lines of:

    NAME people,
      NAME person,
      XMLATTRIBUTE( ... )
  VERSION ’1.0’,

At the time that either enterRoot or exitRoot are called, it is not known whether there will be another line mapped using rxm. Ideally, I'd like to write:

  public void enterRoot( QueryParser.RootContext context ) {
    String root = context.getChild(2).getText();
    getStack().push( "SELECT XMLROOT( XMLELEMENT( NAME " + root );
    getStack().push( "VERSION '1.0', STANDALONE YES )" );


Using a stack seems to be a good way to generate the query based on the visitor pattern.

What data structure would you use to convert a linear map into a hierarchical query?

Would it be feasible, for example, to just pop the last element from the stack (i.e., the line containing the closing parenthesis), store it locally, then push it back on afterwards?

  • Are you asking how to stringify hierarchical data that require opening and closing tags? It seems like that is the problem you are trying to solve, but you are asking if your current idea for a solution is a good solution rather generalizing the problem statement. – mortalapeman Mar 3 '15 at 16:54
  • I am wondering whether a stack is a viable approach to stringify the data and whether there is another approach (data structure) to consider. – Dave Jarvis Mar 3 '15 at 17:24

Use a Tree data structure then convert it to a string using recursive polymorphic toString methods.

Let me reiterate your question in my own words to make sure I understand you correctly:

It appears that you are writing a Domain Specific Language (DSL) that you wish to convert directly your desired output via string manipulation without any intermediate representation. Your question is about your current solution and your choice of data structure required for building of the final string.

If your recursion calls get too deep, you can build a set of classes to walk the tree and build up the string as they visit each node using a depth first search. All this is assuming you have no circular references in your tree.

After re-reading the question, I think I have a better understanding of what you have implemented and what tools you are using. I had assumed you were skipping the whole process of AST generation because I missed that on my first few reads. Can you control how the visitors walk the tree? If start building your string with the deepest child and before you start walking back up the tree, you should just always be wrapping the previous string with opening and closing tags of the current node. Then there is no need to track whether or not you have to insert a closing tag or not, you just always do.

  • @Dave Jarvis I've edited my answer, let me know if that helps or hurts. – mortalapeman Mar 3 '15 at 21:33
  • Can you not build the tree structure in memory based off the AST and then at a later point convert that tree structure to a string of some kind after you have finished? DSL -> AST -> Data Tree -> Output Format. – mortalapeman Mar 3 '15 at 23:56
  • The AST is a data tree representing your code, but it still needs to be walked and interpreted to derive some meaning. As you visit each node of the AST, you should be constructing an in memory representation of your output (not in string form). You may need to walk the AST multiple times to do this, it just depends on how each node must be interpreted. Think of the AST as a source for information to assist in satisfying your requirements, not the main mechanism by which you solve your problem. – mortalapeman Mar 4 '15 at 16:46
  • 1
    I did not mean to sound condescending if that's how I came across, I just had trouble with the context of the question. Design discussions are always easier in person. Good luck with your implementation! – mortalapeman Mar 4 '15 at 18:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.