...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
The class symbols
implements
a symbol table: an associative container (or map) of key-value pairs
where the keys are strings. The symbols
class can work efficiently with 8, 16, 32 and even 64 bit characters.
Traditionally, symbol table management is maintained separately outside
the grammar through semantic actions. Contrary to standard practice,
the Spirit symbol table class symbols
is-a parser, an instance of which may be used anywhere in the grammar
specification. It is an example of a dynamic parser. A dynamic parser
is characterized by its ability to modify its behavior at run time. Initially,
an empty symbols object matches nothing. At any time, symbols may be
added, thus, dynamically altering its behavior.
// forwards to <boost/spirit/home/qi/string/symbols.hpp> #include <boost/spirit/include/qi_symbols.hpp>
Also, see Include Structure.
Name |
---|
|
|
|
template <typename Char, typename T, typename Lookup> struct symbols;
Parameter |
Description |
Default |
---|---|---|
|
The character type of the symbol strings. |
|
|
The data type associated with each symbol. |
|
|
The symbol search implementation |
|
Notation
Semantics of an expression is defined only where it differs from, or
is not defined in PrimitiveParser
.
Expression |
Semantics |
---|---|
|
Construct an empty symbols names |
|
Construct an empty symbols named |
|
Copy construct a symbols from |
|
Construct symbols from |
|
Construct symbols from |
|
Construct symbols from |
|
Construct symbols from |
|
Assign |
|
Assign one or more symbols ( |
|
Add one or more symbols ( |
|
Add one or more symbols ( |
|
Add one or more symbols ( |
|
Remove one or more symbols ( |
|
Remove one or more symbols ( |
|
Erase all of the symbols in |
|
Return a reference to the object associated with symbol, |
|
Return a pointer to the object associated with symbol, |
|
Return a pointer to the object associated with longest symbol
that matches the beginning of the range |
|
For each symbol in |
|
Retrieve the current name of the symbols object. |
|
Set the current name of the symbols object to be |
The attribute of symbol<Char, T>
is T
.
The default implementation uses a Ternary Search Tree (TST) with complexity:
O(log n+k)
Where k is the length of the string to be searched in a TST with n strings.
TSTs are faster than hashing for many typical search problems especially when the search interface is iterator based. TSTs are many times faster than hash tables for unsuccessful searches since mismatches are discovered earlier after examining only a few characters. Hash tables always examine an entire key when searching.
An alternative implementation uses a hybrid hash-map front end (for the
first character) plus a TST: tst_map
.
This gives us a complexity of
O(1 + log n+k-1)
This is found to be significantly faster than plain TST, albeit with
a bit more memory usage requirements (each slot in the hash-map is a
TST node). If you require a lot of symbols to be searched, use the tst_map
implementation. This can be
done by using tst_map
as the third template parameter to the symbols class:
symbols<Char, T, tst_map<Char, T> > sym;
Note | |
---|---|
The test harness for the example(s) below is presented in the Basics Examples section. |
Some using declarations:
using boost::spirit::qi::symbols;
Symbols with data:
symbols<char, int> sym; sym.add ("Apple", 1) ("Banana", 2) ("Orange", 3) ; int i; test_parser_attr("Banana", sym, i); std::cout << i << std::endl;
When symbols
is used
for case-insensitive parsing (in a no_case
directive), added symbol
strings should be in lowercase. Symbol strings containing one or more
uppercase characters will not match any input when symbols is used in
a no_case
directive.
symbols<char, int> sym; sym.add ("apple", 1) // symbol strings are added in lowercase... ("banana", 2) ("orange", 3) ; int i; // ...because sym is used for case-insensitive parsing test_parser_attr("Apple", no_case[ sym ], i); std::cout << i << std::endl; test_parser_attr("ORANGE", no_case[ sym ], i); std::cout << i << std::endl;