Symbols

Boost , ,

Symbols

Этот класс символов реализует таблицу символов. В таблице символов содержится словарь символов, где каждый символ представляет собой последовательность CharTs (achar,wchar_t,int, перечисление и т. д.). Класс шаблонов, параметризованный по типу символов (CharT), может эффективно работать с 8, 16, 32 и даже 64-битными символами. Изменяемые данные типа T связаны с каждым символом.

Традиционно управление таблицей символов поддерживается отдельно вне грамматики BNF посредством семантических действий. Вопреки стандартной практике, символ таблицы символов Духасимволовявляется парсером. Пример, который может быть использован в любом месте спецификации грамматики EBNF. Это пример динамического парсера. Динамический парсер характеризуется способностью изменять свое поведение во время выполнения. Изначально пустой символ ничего не соответствует. В любое время могут добавляться символы, тем самым динамически изменяя его поведение.

Каждая запись в таблице символов имеет связанный с ней изменяемый слот данных. В связи с этим можно рассматривать таблицу символов как ассоциативный контейнер (или карту) пар ключ-значение, где ключи являются струнами.

Класс символов ожидает двух параметров шаблона (на самом деле есть третий, см. детализацию). Первый параметрTопределяет тип данных, связанных с каждым символом (по умолчаниюint), и второй параметр.CharTопределяет тип символов символов (по умолчаниюChar).

    template
    <
        typename T = int,
        typename CharT = char,
        typename SetT = impl::tst<T, CharT>
    >
    class symbols;

Ternary State Trees The actual set implementation is supplied by the SetT template parameter (3rd template parameter of the symbols class) . By default, this uses the tst class which is an implementation of the Ternary Search Tree. Ternary Search Trees are faster than hashing for many typical search problems especially when the search interface is iterator based. Searching for a string of length k in a ternary search tree with n strings will require at most O(log n+k) character comparisons. 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. For details see http://www.cs.princeton.edu/~rs/strings/.

Вот некоторые примеры деклараций:

    symbols<> sym;
    symbols<short, wchar_t> sym2;
    struct my_info
    {
        int     id;
        double  value;
    };
    symbols<my_info> sym3;

После объявления таблиц символов символы могут быть добавлены статически с использованием конструкции:

    sym = a, b, c, d ...;

гдесим— таблица символов, аа.ди т.д. — строки.Обратите внимание, что оператор запятой разделяет элементы, добавленные в таблицу символов, посредством назначения. Из-за перегрузки оператора это возможно и правильно (хотя может потребоваться немного привыкнуть) и является лаконичным способом инициализации таблицы символов со многими символами. Кроме того, совершенно правильно делать несколько заданий в таблицу символов, чтобы итеративно добавлять символы (или группы символов) в разное время.

Простой пример:

    sym = "pineapple", "orange", "banana", "apple", "mango";

Обратите внимание, что неправильно добавлять один и тот же символ несколько раз в таблицу символов, хотя вы можете изменять значение, связанное с символом.

Теперь мы можем использовать сим в грамматике. Пример:

    fruits = sym >> *(',' >> sym);

Альтернативно, символы могут быть добавлены динамически через элемент функторадобавить(см.символ_вставканиже). Член функторадобавитьможет быть присоединен к парсеру в качестве семантического действия, принимающего в начале/конце пары:

    p[sym.add]

где p - парсер (а сим - таблица символов). При успехе соответствующая часть ввода добавляется в таблицу символов.

Добавитьтакже можно использовать для непосредственного инициализации данных. Примеры:

    sym.add("hello", 1)("crazy", 2)("world", 3);

Предположим, конечно, что слот данных, связанный ссимом, является целым числом.

Данные, связанные с каждым символом, могут быть изменены в любое время. Наиболее очевидный путь, конечно, черезсемантические действия. Функция или функтор, как обычно, могут быть прикреплены к таблице символов. В таблице символов предполагается функция или функтор, совместимый с подписью:

Подпись для функций:

    void func(T& data);

Подпись для функторов:

    struct ftor
    {
        void operator()(T& data) const;
    };

ГдеT— тип данных таблицы символов (42] Tв списке параметров шаблона). Когда таблица символов успешно соответствует чему-либо из входных данных, данные, связанные с соответствующей записью в таблице символов, сообщаются семантическому действию.

Symbol table utilities

Иногда можно захотеть иметь дело непосредственно со столом символов. Предоставляются некоторые символьные столовые утилиты.

Добавить

    template <typename T, typename CharT, typename SetT>
    T*  add(symbols<T, CharT, SetT>& table, CharT const* sym, T const& data = T());

Добавляет символсим(струна C) в таблицу символовтаблицуплюс дополнительные данныеданные, связанные с символом. Возвращает указатель к данным, связанным с символом илиNULL, если добавление не удалось (например, когда символ уже добавлен ранее).

Найти

    template <typename T, typename CharT, typename SetT>
    T*  find(symbols<T, CharT, SetT> const& table, CharT const* sym);

Найден символсим(струна C) из таблицы символовтаблицы. Возвращает указатель на данные, связанные с символом илиNULL, если не найдено

symbol_inserter

Класс символов содержит экземпляр этого класса, названного, добавить. Это можно назвать непосредственно так же, как функция участника, передавая в первом/последнем итераторе и необязательные данные:

    sym.add(first, last, data);

Или, передавая в строке C и необязательные данные:

    sym.add(c_string, data);

гдесим— таблица символов.данныеявляются необязательными. Самое приятное в этой схеме то, что она может быть каскадной. Мы видели, как это применялось выше. Вот фрагмент из парсера римских цифр

    //  Parse roman numerals (1..9) using the symbol table.
    struct ones : symbols<unsigned>
    {
    	ones()
    	{
            add
                ("I"    , 1)
                ("II"   , 2)
                ("III"  , 3)
                ("IV"   , 4)
                ("V"    , 5)
                ("VI"   , 6)
                ("VII"  , 7)
                ("VIII" , 8)
                ("IX"   , 9)
    		;
    	}
    } ones_p;

Обратите внимание, что определенная пользователем структураподклассирована изсимволов. Затем во время строительства мы добавили все символы, используядобавитьсимвол_inserter.

Полный исходный код можно посмотреть здесь. Это часть духовного распределения.

Опять же,добавитьможно также использовать в качестве семантического действия, поскольку оно соответствует интерфейсу действия (см. семантические действия):

    p[sym.add]

где p - парсер, конечно.

Copyright © 1998-2003 Joel de Guzman

Use, modification and distribution is subject to 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)

Статья Symbols раздела может быть полезна для разработчиков на c++ и boost.

:: Главная :: ::