Я использовал Qi и Karma для обработки нескольких небольших языков. Большинство грамматик довольно маленькие (20-40 правил). Я мог использовать автоправила почти исключительно, поэтому мои деревья синтаксического анализа полностью состоят из вариантов, структур и std :: vectors.
Эта настройка отлично работает в общем случае:
1) что-то анализирует (Qi),
2) производит незначительные манипуляции с деревом синтаксического анализа (посетитель) и
3) выводит что-то (Karma).
Однако меня беспокоит, что произойдет, если я захочу внести сложные структурные изменения в синтаксическое дерево, например, переместить большие поддеревья. Рассмотрим следующий пример игрушки:
Грамматика для логических выражений в стиле s-expr, использующая автоправила ...
// Inside grammar class; rule names match struct names...
pexpr %= pand | por | var | bconst;
pand %= lit("(and ") >> (pexpr % lit(" ")) >> ")";
por %= lit("(or ") >> (pexpr % lit(" ")) >> ")";
pnot %= lit("(not ") >> pexpr >> ")";
... что приводит к представлению дерева синтаксического анализа, которое выглядит так ...
struct var {
std::string name;
};
struct bconst {
bool val;
};
struct pand;
struct por;
struct pnot;
typedef boost::variant<bconst,
var,
boost::recursive_wrapper<pand>,
boost::recursive_wrapper<por>,
boost::recursive_wrapper<pnot> > pexpr;
struct pand {
std::vector<pexpr> operands;
};
struct por {
std::vector<pexpr> operands;
};
struct pnot {
pexpr victim;
};
// Many Fusion Macros here
Предположим, у меня есть дерево синтаксического анализа, которое выглядит примерно так:
pand
/ ... \
por por
/ \ / \
var var var var
(Многоточие означает «намного больше детей аналогичной формы для pand.»)
Теперь предположим, что я хочу инвертировать каждый из por узлов, чтобы конечный результат был таким:
pand
/ ... \
pnot pnot
| |
por por
/ \ / \
var var var var
Прямой подход для каждого por поддерева:
- создать pnot узел
(копирует por в процессе создания);
- переназначить соответствующий векторный слот в pand узле
(копирует pnot узел и его por поддерево).
В качестве альтернативы я мог бы построить отдельный вектор, а затем заменить (поменять местами) вектор pand оптом, исключив второй раунд копирования.
Все это кажется громоздким по сравнению с древовидным представлением на основе указателей, которое позволяет вставлять pnot узлы без какого-либо копирования существующих узлов. Мой вопрос:
Есть ли способ избежать манипуляций с деревьями, требующими большого количества копий, с помощью структур данных, совместимых с автоправилами? Должен ли я укусить пулю и просто использовать неавторизованные правила для создания AST на основе указателей (например, http://boost-spirit.com/home/2010/03/11/s-expressions-and-варианты/)?
