ceph/src/boost/libs/spirit/doc/support/utree.qbk

   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