ceph/src/boost/libs/spirit/doc/x3/introduction.qbk

   1 [/==============================================================================
   2     Copyright (C) 2001-2015 Joel de Guzman
   3     Copyright (C) 2001-2011 Hartmut Kaiser
   4
   5     Distributed under the Boost Software License, Version 1.0. (See accompanying
   6     file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   7 ===============================================================================/]
   8
   9 [section Introduction]
  10
  11 Boost Spirit X3 is an object-oriented, recursive-descent parser for C++. It
  12 allows you to write grammars using a format similar to
  13 Extended Backus Naur Form (EBNF)[footnote
  14 [@http://www.cl.cam.ac.uk/%7Emgk25/iso-14977.pdf ISO-EBNF]] directly in C++.
  15 These inline grammar specifications can mix freely with other C++ code and,
  16 thanks to the generative power of C++ templates, are immediately executable.
  17 Conventional compiler-compilers or parser-generators have to perform an
  18 additional translation step from the source EBNF code to C or C++ code.
  19
  20 Since the target input grammars are written entirely in C++ we do not need any
  21 separate tools to compile, preprocess or integrate those into the build process.
  22 __spirit__ allows seamless integration of the parsing process with other C++
  23 code. This often allows for simpler and more efficient code.
  24
  25 The created parsers are fully attributed, which allows you to easily build and
  26 handle hierarchical data structures in memory. These data structures resemble
  27 the structure of the input data and can directly be used to generate
  28 arbitrarily-formatted output.
  29
  30 A simple EBNF grammar snippet:
  31
  32     group       ::= '(' expression ')'
  33     factor      ::= integer | group
  34     term        ::= factor (('*' factor) | ('/' factor))*
  35     expression  ::= term (('+' term) | ('-' term))*
  36
  37 is approximated using facilities of Spirit's /X3/ as seen in this code snippet:
  38
  39     group       = '(' >> expression >> ')';
  40     factor      = integer | group;
  41     term        = factor >> *(('*' >> factor) | ('/' >> factor));
  42     expression  = term >> *(('+' >> term) | ('-' >> term));
  43
  44 Through the magic of expression templates, this is perfectly valid and
  45 executable C++ code. The production rule `expression` is, in fact, an object
  46 that has a member function `parse` that does the work given a source code
  47 written in the grammar that we have just declared. Yes, it's a calculator. We
  48 shall simplify for now by skipping the type declarations and the definition of
  49 the rule `integer` invoked by `factor`. Now, the production rule `expression` in
  50 our grammar specification, traditionally called the `start` symbol, can
  51 recognize inputs such as:
  52
  53     12345
  54     -12345
  55     +12345
  56     1 + 2
  57     1 * 2
  58     1/2 + 3/4
  59     1 + 2 + 3 + 4
  60     1 * 2 * 3 * 4
  61     (1 + 2) * (3 + 4)
  62     (-1 + 2) * (3 + -4)
  63     1 + ((6 * 200) - 20) / 6
  64     (1 + (2 + (3 + (4 + 5))))
  65
  66 Certainly we have modified the original EBNF syntax. This is done to
  67 conform to C++ syntax rules. Most notably we see the abundance of shift >>
  68 operators. Since there are no juxtaposition operators in C++, it is simply not
  69 possible to write something like:
  70
  71     a b
  72
  73 as seen in math syntax, for example, to mean multiplication or, in our case,
  74 as seen in EBNF syntax to mean sequencing (b should follow a). __x3__
  75 uses the shift `>>` operator instead for this purpose. We take the `>>`
  76 operator, with arrows pointing to the right, to mean "is followed by". Thus we
  77 write:
  78
  79     a >> b
  80
  81 The alternative operator `|` and the parentheses `()` remain as is. The
  82 assignment operator `=` is used in place of EBNF's `::=`. Last but not least,
  83 the Kleene star `*`, which in this case is a postfix operator in EBNF becomes a
  84 prefix. Instead of:
  85
  86     a* //... in EBNF syntax,
  87
  88 we write:
  89
  90     *a //... in Spirit.
  91
  92 since there are no postfix stars, `*`, in C/C++. Finally, we terminate each
  93 rule with the ubiquitous semi-colon, `;`.
  94
  95 [endsect]