Как эффективно реализовать неизменный граф разнородных неизменных объектов в C ++?

Question

Из любопытства пишу парсер текста на языке программирования. Скажем, я хочу определить неизменный (во время выполнения) граф токенов как вершины / узлы. Это, естественно, разные типы - некоторые токены являются ключевыми словами, некоторые - идентификаторами и т. Д. Однако все они имеют общую черту, где каждый токен в графе указывает на другой. Это свойство позволяет синтаксическому анализатору знать, что может следовать за конкретным токеном, и поэтому граф определяет формальную грамматику языка. Моя проблема в том, что я перестал использовать C ++ ежедневно несколько лет назад и с тех пор использовал много языков более высокого уровня, и моя голова полностью фрагментирована в отношении размещения кучи, размещения стека и тому подобного. Увы, мой C ++ ржавый.

Тем не менее, я хотел бы сразу подняться на крутой холм и поставить перед собой цель определить этот граф на этом императивном языке наиболее эффективным способом. Например, я хочу избежать выделения каждого объекта токена отдельно в куче, используя «new», потому что я думаю, что если я выделю весь график этих токенов, так сказать, в прямом (в линейном виде, как элементы в массиве), это как-то улучшит производительность, согласно принципу локальности ссылок - я имею в виду, когда весь граф сжимается, чтобы занять минимальное пространство вдоль «линии» в памяти, вместо того, чтобы все его объекты-токены располагались в случайных местах, это плюс? В любом случае, как вы видите, это немного открытый вопрос.

class token
{

}

class word: token
{
    const char* chars;

    word(const char* s): chars(s)
    {
    }
}

class ident: token
{
    /// haven't thought about these details yet
}

template<int N> class composite_token: token
{
    token tokens[N];
}

class graph
{
    token* p_root_token;
}

Непосредственный вопрос: какова будет процедура создания этого графического объекта? Он неизменен, и его структура мысли известна во время компиляции, поэтому я могу и хочу избегать копирования содержимого по значению и т. Д. - должна ли быть возможность составлять этот граф из литералов? Я надеюсь, что здесь есть смысл ... (это был бы не первый раз, когда я этого не делал). График будет использоваться синтаксическим анализатором во время выполнения как часть компилятора. И только потому, что это C ++, я был бы счастлив и решением на C. Заранее большое спасибо.

Answer 1

Я не понимаю, как вы определите «граф» токенов, который определяет синтаксис любого практического языка программирования, особенно если отношение между токенами «разрешено следовать».

Обычный способ представления грамматики языка программирования - это использование формы Бэкуса-Наура (BNF) или расширенных версий этого термина "EBNF".

Если вы хотите представить EBNF ("какнеизменный граф "), этот SO-ответ обсуждает, как это сделать в C #.Идеи имеют прямые аналоги в C ++.

Плохая новость заключается в том, что большинство синтаксических анализаторов не могут напрямую использовать EBNF, потому что на практике он слишком неэффективен.Трудно построить эффективный парсер, использующий прямое представление правил грамматики;Вот почему люди изобрели генераторы парсеров.Поэтому необходимость поместить эти правила в структуру памяти вообще, не говоря уже о «эффективном», неясна, если вы не собираетесь писать генератор синтаксического анализатора.

Наконец, даже если вы упаковываете грамматическую информациюкак-то оптимально, это, вероятно, не будет иметь никакого значения в реальной производительности.Большую часть времени синтаксического анализатора тратят на группировку символов в лексемах, иногда даже до того, что они просто делают пустое подавление.

Answer 2

Мой C ++ также ржавый, поэтому я, вероятно, не знаю лучшего решения для этого.Но поскольку никто больше не шагнул вперед ...

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

Чтобы выделить все узлы в одном блоке памяти, мне на ум придут две возможности: создать и заполнитьVector <> при запуске (с тем недостатком, что теперь у вас есть графическая информация дважды в памяти), или используйте инициализатор статического массива "Node [] graph = {...};".

Для обоих подходов самым большим препятствием является то, что вы хотите создать свой график разнородных объектов.Одним из очевидных решений является «Не»: вы можете сделать свой узел надмножеством всех возможных полей и различать типы с помощью явного члена типа.

Если вы хотите сохранить различные классы узлов,вам придется использовать несколько массивов / векторов: по одному для каждого типа.

В любом случае, соединения между узлами должны быть первоначально определены в терминах индексов массива (за Узлом [3] следует Узел [10]).Конечно, для повышения производительности разбора вы можете создавать прямые указатели объектов при запуске программы на основе этих индексов.

Я бы не вставлял буквальные строки ни в один узел («слово» в вашем случае): распознавание ключевых слов, идентификаторы и другие лексические элементы должны быть сделаны в модуле лексера отдельно от парсера.Я думаю, что это также помогло бы, если бы вы различали в терминальной логике токены, сгенерированные Lexer на основе входных данных программы, и узлы грамматического графа, используемые вашей программой для анализа входных данных.

Надеюсь, это поможет.

Answer 3

Я не думаю, что многие небольшие выделения токенов будут узким местом, если это так, вы всегда можете выбрать пул памяти.

На проблему; поскольку все токены имеют схожие данные (с указателем на следующий и, возможно, некоторым значением enum для того токена, с которым мы имеем дело), ​​вы можете поместить подобные данные в один std :: vector. Это будут непрерывные данные в памяти, и они очень эффективны для повторения.

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

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

Вектор может выглядеть так:

struct TokenData
{
    token *previous, *current, *next;
    token_id id; // some enum?
    ... // more data that is similar
}

std::vector<TokenData> token_data;

class token
{
    std::vector<TokenData> *token_data;
    size_t index;

    TokenData &data()
    {
        return (*token_data)[index];
    }

    const TokenData &data() const
    {
        return (*token_data)[index];
    }
}

// class plus_sign: token
// if (data().previous->data().id == NUMBER && data().next->data().id == NUMBER)

for (size_t i = 0; i < token_data.size(); i++)
{
    token_data[i].current->do_work();
}

Это идея.