Jun 12

Here’s another cool Spirit talk. This time from Bryce Alexander Lelbach:


utree, a recent addition to the Boost.Spirit codebase, is a generic data structure designed to represent abstract syntax trees. Bindings to Qi and Karma make utree a powerful tool for parser and generator development with Boost.Spirit. This presentation would demonstrate the usage of utree and Spirit to build and manipulate an abstract syntax tree for four parsing/generating use cases: XML, symbolic expressions, JSON, and C-like source code. The details of utree’s integration with Spirit and their implications for writing utree-centric Spirit parsers and generators would be discussed. Additionally, design patterns for compiling a utree AST to other internal representations (DOM tree for XML, function tree for a Scheme-like language for symbolic expressions, associative arrays for JSON objects, a simple VM bytecode for mini-C source code) would be covered.

Here are the slides:



12 Responses to “AST Construction with the Universal Tree”

  1. Jarno says:

    Are the actual slides (i.e., not video) available as well?

  2. Richard says:

    While this talk was interesting, I found it didn’t really live up to the title. I got lost in all the details of implementing a LISP interpreter and didn’t come away with an understanding of how to build an AST with utree, other than “don’t use semantic actions”. Surely, there’s more to it than that?

  3. Greg Rubino says:

    I can’t seem to find the docs for utree here, can someone post a link?


    • adriaan says:

      Hi Greg,
      The documentation for utree is a bit limited, but I found a page for it in the current SVN source base:
      Also – there are some examples here:
      An advanced big project using utree: SVN\libs\spirit\example\scheme\
      and a smaller utree example: SVN\libs\spirit\example\support\utree\

  4. adriaan says:

    hi. I must agree that this presentation did not really help me too much in understanding how to effectively use the utree.
    Is there some commented examples or tuturial or article about how to use the utree? It looks like there are some examples in svn but they are not documented (that i could see).
    The utree is something that really interests me but seems to be hard to find good info about….

  5. adriaan says:

    I’ve been looking at the samples in SVN some more and there is quite a lot of code using utree (at least in the latest SVN):

    An advanced big project using utree: SVN\libs\spirit\example\scheme\
    and a smaller utree example: SVN\libs\spirit\example\support\utree\

    These both seem like good examples – the only problem is that there are no real explanations of why some things are done… if somebody could add good, extensive comments to maybe the basic utree example or just write an article with detailed comments it would help us all a lot I think! 🙂

    I also see that the string type that is supported by utree is a UTF8 type – does this have any performance impact if you only want to use ASCII? In the example there is a UTF-8 parser that does seem less efficient (using semantic actions). But if I were just to use normal string parser – that would still work fine while storing the resulting ascii strings in the UTF-8 type string, correct? Any would this have any performance impact on the resulting parser/AST?

    Thanks for any feedback!

    • Joel de Guzman says:

      The more complex examples there (scheme, utree and the compiler tutorial) started as material for boostcon presentation. Alas, the previous years presentations were not recorded (actually they were but the audio was very poor). The intent is to provide tutorials for them. Alas, unless someone else works on them (utree), the tutorials will have to wait. The best I could provide are the slides.

      I intend to focus more on the compiler tutorials which does not use the utree.

  6. adriaan says:

    I just skimmed over the following document:
    and found that it is one of the resources helping me most to understand the utree (and many other spirit features)
    I recommend reading it to everybody…

  7. Olaf says:

    What is the current status of utree? Bryce Lelbach doesn’t continue to develop the example use case prana (https://github.com/brycelelbach/prana) any more, isn’t? I like his idea to register callbacks (but imo he overused shared_ptr). On the compiler tutorial there isn’t progress with utree also. Shall I use utree for new parsers or use the old AST approach?

  8. Yiqing Yang says:

    Any new development on this topic? I am looking for something similar to the old spirit parse tree pt_parse() to work with the new spirit::Qi parser grammar. Would utree be it? Any good examples of utree?

Leave a Reply to adriaan

preload preload preload