1[/============================================================================== 2 Copyright (C) 2001-2011 Hartmut Kaiser 3 Copyright (C) 2001-2011 Joel de Guzman 4 Copyright (C) 2011 Bryce Lelbach 5 6 Distributed under the Boost Software License, Version 1.0. (See accompanying 7 file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 8==============================================================================/] 9 10[import ../../../../boost/spirit/home/support/utree/utree.hpp] 11[import ../../example/support/utree/sexpr_parser.hpp] 12 13[section:utree The utree data structure] 14 15`utree` is a dynamically-typed hierarchical data structure that can represent 16abstract syntax trees. It's well integrated with __qi__ and __karma__. `utree` 17can be passed as an attribute to almost any grammar. `utree`'s type system is 18implemented through the use of a discriminated union and type punning. 19 20`utree` has a minimal memory footprint. The data structure size is 16 bytes on a 2132-bit platform, and 32 bytes on 64-bit a platform (`4*sizeof(void*)`). Being a 22container of itself, it can represent tree structures. 23 24[utree_types] 25 26The UTF-8 string, UTF-8 symbol, and binary data types are internally stored 27either directly as the node data (small string optimization applied), or they 28are allocated from the heap, storing the pointer to the allocated data in the 29`utree`. The maximum possible length of the data to be stored in the node data 30depends on the platform the `utree` is compiled for. It is 14 bytes for a 3132-bit platform and 30 bytes for a 64-bit platform. 32 33[heading Class Reference] 34 35The `utree` data structure is very versatile and can be used as an attribute 36for all possible __qi__ parsers and __karma__ generators. For this reason, it 37exposes a set of typedef's making it compatible with STL containers: 38 39[utree_container_types] 40 41The `utree` data type exposes the functional interface of a bidirectional STL 42container. The iterators returned from `begin()` et.al. conform to the Standard 43requirements of a bidirectional iterator. 44 45[utree_container_functions] 46 47The exposed container interface makes the `utree` usable with all __qi__ 48parser and __karma__ generator components, which are compatible with an 49STL container attribute type. 50 51[utree_initialization] 52 53The `utree` data type exposes the functional interface compatible to 54__boost_variant__ as well. Its very nature is to hold different data types, one 55at each point in time, making it functionally very similar to __boost_variant__. 56 57[utree_variant_functions] 58 59The exposed variant-like interface makes the `utree` usable with all __qi__ 60parser and __karma__ generator components, which are compatible with an 61__boost_variant__ attribute type. 62 63[heading String Types] 64 65[utree_strings] 66 67[heading Function Object Interface] 68 69The stored_function template class can to store a unary function objects with 70a signature of utree(scope const&) as a utree node. 71 72[utree_function_object_interface] 73 74[heading Exceptions] 75 76[utree_exceptions] 77 78[/ 79 [heading Scope] 80 81 [utree_scope] 82] 83 84[heading Example: Sexpr Parser] 85 86Our first example demonstrates how to use `utree` to write a parser for 87[@http://en.wikipedia.org/wiki/S-expression symbolic expressions]. 88While `utree` is capable of representing just about any AST, `utree`'s design 89is based on the simple yet powerful nature of symbolic expressions. This 90example introduces a number of basic and intermediate `utree` development 91techniques: using __qi__ and __karma__ integration, tracking source code 92locations and taking advantage of UTF8 support. 93 94The source for this example can be found here: [@../../example/support/utree]. 95 96[utree_sexpr_parser] 97 98[endsect] 99 100