]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | |
16 | abstract syntax trees. It's well integrated with __qi__ and __karma__. `utree` | |
17 | can be passed as an attribute to almost any grammar. `utree`'s type system is | |
18 | implemented 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 | |
21 | 32-bit platform, and 32 bytes on 64-bit a platform (`4*sizeof(void*)`). Being a | |
22 | container of itself, it can represent tree structures. | |
23 | ||
24 | [utree_types] | |
25 | ||
26 | The UTF-8 string, UTF-8 symbol, and binary data types are internally stored | |
27 | either directly as the node data (small string optimization applied), or they | |
28 | are 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 | |
30 | depends on the platform the `utree` is compiled for. It is 14 bytes for a | |
31 | 32-bit platform and 30 bytes for a 64-bit platform. | |
32 | ||
33 | [heading Class Reference] | |
34 | ||
35 | The `utree` data structure is very versatile and can be used as an attribute | |
36 | for all possible __qi__ parsers and __karma__ generators. For this reason, it | |
37 | exposes a set of typedef's making it compatible with STL containers: | |
38 | ||
39 | [utree_container_types] | |
40 | ||
41 | The `utree` data type exposes the functional interface of a bidirectional STL | |
42 | container. The iterators returned from `begin()` et.al. conform to the Standard | |
43 | requirements of a bidirectional iterator. | |
44 | ||
45 | [utree_container_functions] | |
46 | ||
47 | The exposed container interface makes the `utree` usable with all __qi__ | |
48 | parser and __karma__ generator components, which are compatible with an | |
49 | STL container attribute type. | |
50 | ||
51 | [utree_initialization] | |
52 | ||
53 | The `utree` data type exposes the functional interface compatible to | |
54 | __boost_variant__ as well. Its very nature is to hold different data types, one | |
55 | at each point in time, making it functionally very similar to __boost_variant__. | |
56 | ||
57 | [utree_variant_functions] | |
58 | ||
59 | The exposed variant-like interface makes the `utree` usable with all __qi__ | |
60 | parser 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 | ||
69 | The stored_function template class can to store a unary function objects with | |
70 | a 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 | ||
86 | Our first example demonstrates how to use `utree` to write a parser for | |
87 | [@http://en.wikipedia.org/wiki/S-expression symbolic expressions]. | |
88 | While `utree` is capable of representing just about any AST, `utree`'s design | |
89 | is based on the simple yet powerful nature of symbolic expressions. This | |
90 | example introduces a number of basic and intermediate `utree` development | |
91 | techniques: using __qi__ and __karma__ integration, tracking source code | |
92 | locations and taking advantage of UTF8 support. | |
93 | ||
94 | The source for this example can be found here: [@../../example/support/utree]. | |
95 | ||
96 | [utree_sexpr_parser] | |
97 | ||
98 | [endsect] | |
99 |