123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899 |
- [/==============================================================================
- 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]
|