Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

Click here to view the latest version of this page.
PrevUpHomeNext
Symbols (symbols)
Description

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 seperately 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.

Header
// forwards to <boost/spirit/home/qi/string/symbols.hpp>
#include <boost/spirit/include/qi_symbols.hpp>

Also, see Include Structure.

Namespace

Name

boost::spirit::qi::symbols

boost::spirit::qi::tst

boost::spirit::qi::tst_map

Synopsis
template <typename Char, typename T, typename Lookup>
struct symbols;
Template parameters

Parameter

Description

Default

Char

The character type of the symbol strings.

char

T

The data type associated with each symbol.

unused_type

Lookup

The symbol search implementation

tst<Char, T>

Model of

PrimitiveParser

Notation

Sym

A symbols type.

Char

A character type.

T

A data type.

sym, sym2

symbols objects.

sseq

An STL container of strings.

dseq

An STL container of data with value_type T.

s1...sN

A String.

d1...dN

Objects of type T.

f

A callable function or function object.

f, l

ForwardIterator first/last pair.

Expression Semantics

Semantics of an expression is defined only where it differs from, or is not defined in PrimitiveParser.

Expression

Semantics

Sym()

Construct an empty symbols.

Sym(sym2)

Copy construct a symbols from sym2 (Another symbols object).

Sym(sseq)

Construct symbols from sseq (An STL container of strings).

Sym(sseq, dseq)

Construct symbols from sseq and dseq (An STL container of strings and an STL container of data with value_type T).

sym = sym2

Assign sym2 to sym.

sym = s1, s2, ..., sN

Assign one or more symbols (s1...sN) to sym.

sym += s1, s2, ..., sN

Add one or more symbols (s1...sN) to sym.

sym.add(s1)(s2)...(sN)

Add one or more symbols (s1...sN) to sym.

sym.add(s1, d1)(s2, d2)...(sN, dN)

Add one or more symbols (s1...sN) with associated data (d1...dN) to sym.

sym -= s1, s2, ..., sN

Remove one or more symbols (s1...sN) from sym.

sym.remove(s1)(s2)...(sN)

Remove one or more symbols (s1...sN) from sym.

sym.clear()

Erase all of the symbols in sym.

sym.at(s)

Return a reference to the object associated with symbol, s. If sym does not already contain such an object, at inserts the default object T().

sym.find(s)

Return a pointer to the object associated with symbol, s. If sym does not already contain such an object, find returns a null pointer.

sym.prefix_find(f, l)

Return a pointer to the object associated with longest symbol that matches the beginning of the range [f, l), and updates f to point to one past the end of that match. If no symbol matches, then return a null pointer, and f is unchanged.

sym.for_each(f)

For each symbol in sym, s, a std::basic_string<Char> with associated data, d, an object of type T, invoke f(s, d).

Attributes

The attribute of symbol<Char, T> is T.

Complexity

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;
Example
[Note] 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;


PrevUpHomeNext