Boost :: Spirit :: Qi autorules - предотвращение повторного копирования структур данных AST - PullRequest
Новая
       16

Boost :: Spirit :: Qi autorules - предотвращение повторного копирования структур данных AST

4 голосов
/ 10 января 2011

Я использую Ци и Карму для обработки некоторых небольших языков.Большинство грамматик довольно маленькие (20-40 правил).Я был в состоянии использовать autorules почти исключительно, поэтому мои деревья разбора полностью состоят из вариантов, структур и std :: vectors.

Эта установка прекрасно работает для общего случая:
1) анализирует что-то (Qi),
2) делает незначительные манипуляции с деревом анализа (посетителем) и
3) выводит что-то(Карма).

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

Грамматика для логических выражений в стиле 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-выражения и варианты) * )

1 Ответ

3 голосов
/ 11 января 2011

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

...