100 lines
3.6 KiB
Plaintext
100 lines
3.6 KiB
Plaintext
[/==============================================================================
|
|
Copyright (C) 2001-2011 Hartmut Kaiser
|
|
Copyright (C) 2001-2011 Joel de Guzman
|
|
Copyright (C) 2011 Bryce Lelbach
|
|
|
|
Distributed under the Boost Software License, Version 1.0. (See accompanying
|
|
file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
|
|
==============================================================================/]
|
|
|
|
[import ../../../../boost/spirit/home/support/utree/utree.hpp]
|
|
[import ../../example/support/utree/sexpr_parser.hpp]
|
|
|
|
[section:utree The utree data structure]
|
|
|
|
`utree` is a dynamically-typed hierarchical data structure that can represent
|
|
abstract syntax trees. It's well integrated with __qi__ and __karma__. `utree`
|
|
can be passed as an attribute to almost any grammar. `utree`'s type system is
|
|
implemented through the use of a discriminated union and type punning.
|
|
|
|
`utree` has a minimal memory footprint. The data structure size is 16 bytes on a
|
|
32-bit platform, and 32 bytes on 64-bit a platform (`4*sizeof(void*)`). Being a
|
|
container of itself, it can represent tree structures.
|
|
|
|
[utree_types]
|
|
|
|
The UTF-8 string, UTF-8 symbol, and binary data types are internally stored
|
|
either directly as the node data (small string optimization applied), or they
|
|
are allocated from the heap, storing the pointer to the allocated data in the
|
|
`utree`. The maximum possible length of the data to be stored in the node data
|
|
depends on the platform the `utree` is compiled for. It is 14 bytes for a
|
|
32-bit platform and 30 bytes for a 64-bit platform.
|
|
|
|
[heading Class Reference]
|
|
|
|
The `utree` data structure is very versatile and can be used as an attribute
|
|
for all possible __qi__ parsers and __karma__ generators. For this reason, it
|
|
exposes a set of typedef's making it compatible with STL containers:
|
|
|
|
[utree_container_types]
|
|
|
|
The `utree` data type exposes the functional interface of a bidirectional STL
|
|
container. The iterators returned from `begin()` et.al. conform to the Standard
|
|
requirements of a bidirectional iterator.
|
|
|
|
[utree_container_functions]
|
|
|
|
The exposed container interface makes the `utree` usable with all __qi__
|
|
parser and __karma__ generator components, which are compatible with an
|
|
STL container attribute type.
|
|
|
|
[utree_initialization]
|
|
|
|
The `utree` data type exposes the functional interface compatible to
|
|
__boost_variant__ as well. Its very nature is to hold different data types, one
|
|
at each point in time, making it functionally very similar to __boost_variant__.
|
|
|
|
[utree_variant_functions]
|
|
|
|
The exposed variant-like interface makes the `utree` usable with all __qi__
|
|
parser and __karma__ generator components, which are compatible with an
|
|
__boost_variant__ attribute type.
|
|
|
|
[heading String Types]
|
|
|
|
[utree_strings]
|
|
|
|
[heading Function Object Interface]
|
|
|
|
The stored_function template class can to store a unary function objects with
|
|
a signature of utree(scope const&) as a utree node.
|
|
|
|
[utree_function_object_interface]
|
|
|
|
[heading Exceptions]
|
|
|
|
[utree_exceptions]
|
|
|
|
[/
|
|
[heading Scope]
|
|
|
|
[utree_scope]
|
|
]
|
|
|
|
[heading Example: Sexpr Parser]
|
|
|
|
Our first example demonstrates how to use `utree` to write a parser for
|
|
[@http://en.wikipedia.org/wiki/S-expression symbolic expressions].
|
|
While `utree` is capable of representing just about any AST, `utree`'s design
|
|
is based on the simple yet powerful nature of symbolic expressions. This
|
|
example introduces a number of basic and intermediate `utree` development
|
|
techniques: using __qi__ and __karma__ integration, tracking source code
|
|
locations and taking advantage of UTF8 support.
|
|
|
|
The source for this example can be found here: [@../../example/support/utree].
|
|
|
|
[utree_sexpr_parser]
|
|
|
|
[endsect]
|
|
|