Древовидное соответствие AST. Любой чистый путь в C ++?

Question

Контекст: мне нужно написать некоторые правила сопоставления деревьев для дерева абстрактного синтаксиса.

Я хотел бы, чтобы, например, был метод чистого совпадения, если числово-литеральный индекс (а недля доступа к массиву.

Учтите, что у меня есть абстрактный класс (т. е. имеет чисто виртуальную функцию), lvalue.lvalue подклассов только для 2 конкретных классов, variable и array_element.

Чтобы по-разному обрабатывать эти два случая, я мог бы применить применить шаблон посетителя (но я бы посчитал это излишним) или использоватьужасный беспорядок dynamic_cast.(Я уже использую шаблон посетителей для прохождения моего AST и CFG)

void main() {
    lvalue *lv = new variable("foo");
    // ... somehow do a tree-pattern matching on lv
}

Чтобы проверить, был ли lv доступ к массиву с литеральным (т.е. постоянным) индексом, я, безусловно, могу написать следующее:

if (array_element *ae = dynamic_cast<array_element*>(lv)) {
   if (dynamic_cast<constant*>(ae->index)) {
      cout << "Yes, lv is an array-access and indexed by a literal" << endl;
   }
}

... но это чертовски уродливо и недостижимо.Шаг в правильном направлении будет следующим (если только он сработает):

void func(variable *n) {
    cout << "got a variable" << endl;
}

void func(array_element *n) {
    cout << "got a array" << endl;
}

Есть ли способ избежать путаницы dynamic_cast?Пожалуйста, сообщите:)

Answer 1

Юрий Солодкий в настоящее время разрабатывает библиотеку C ++ 11 под названием Mach7 , которая предоставляет для этого оператор типа switch.Его слайды и статьи о переключении типов и сопоставлении с образцом (в соавторстве с Габриэлем Дос Рейсом и Бьярном Страуструпом) дают подробную информацию о производительности и реализации.

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

Match(lv)
{
    Case(array_element)
        cout << "array_element" << endl;
    ...
}

Впечатляюще, это также позволяет вам выполнять более сложное сопоставление шаблонов, подобное ML или Haskell:

Match(lv)
{
  Case(C<array_element>(C<constant>(index)))
      cout << "Yes, lv is an array-access and indexed by a literal" << endl;
  ...
}

См. Также ответ Томаса Пети на связанный с Скином вопрос о выполнении сопоставления с образцом в стиле ML в C ++.

Answer 2

Это может зависеть от вашего фактического контекста ... Я уверен, что ваш реальный код делает что-то более интересное, чем

cout << "Yes, lv is an array-access and indexed by a literal" << endl;

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

struct lvalue {
    virtual void policy() = 0;
};

struct variable : public lvalue {
    virtual void policy() { /* whatever */ }
};

struct array_element : public lvalue {
    virtual void policy() {
        cout << "Yes, lv is an array-access and indexed by a literal" << endl;
    }
};

Но я уверен, что это то, что вы уже поняли: P Вы также можете подумать о добавлении уровня косвенности:

// interface for a "policy" class.  this could look however you want it to.
struct lvalue_policy {
    virtual void operator()() = 0;
};

struct lvalue {
    virtual lvalue_policy policy() = 0;
};

// variables
struct variable_policy : public lvalue_policy {
    virtual void operator()() { /* whatever */ }
};

struct variable : public lvalue {
    virtual variable_policy policy() { return variable_policy; }
};

// array elements
struct array_element_policy : public lvalue_policy {
    virtual void operator()() {
        cout << "Yes, lv is an array-access and indexed by a literal" << endl;
    }
};

struct array_element : public lvalue {
    virtual array_element_policy policy() { return array_element_policy; }
};

... Но я не уверен, что вы действительно что-то покупаете по сравнению с более простым прямым подходом. Проблема, которую я думаю, что у них обоих есть, это негибкость с типом возврата policy() - они оба сводятся к void возвратам. Опять же, это может быть хорошо для вашей ситуации, но мой уклон всегда к полиморфизму во время компиляции, когда это возможно, потому что это дает вам значительно большую гибкость с типами. Так что решение, которое я бы попробовал на вашем месте, было бы что-то вроде этого:

template class lvalue<typename T, typename policyT> {
    policyT m_policy; // assume this has an operator() that returns T
public:
    T policy() { return m_policy(); }
};

Answer 3

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

Вы можете рассмотреть возможность использования инструмента, предназначенного для преобразований AST, например, источник-источник Program Transformation " tool. Большинство из них позволит вам написать какой-нибудь шаблон синтаксиса поверхности, используемый для включения перезаписи, правило вида" если вы видите этот синтаксис , заменитеэто этот синтаксис".

Теперь большинство таких инструментов требуют, чтобы вы каким-то образом определяли язык, которым вы хотите манипулировать для инструмента, поэтому он знает, что это за синтаксис.скажи, каким языком ты хочешь манипулировать, твой SO C ++ тэг, кажется, там, потому что ты хочешь сделать это в C ++. Я не могу помочь тебе с этой частью: - {Меня не удивит, если ты хочешь манипулировать C ++, так какэто то, что вы кодируете, но это только предположение. Но если вы собираетесь использовать инструмент трансформации программы, вам нужно надежное определение языка иЭто трудно получить.Хорошее определение C ++ для этой цели крайне сложно получить, особенно с выходом C ++ 11.

Наш набор инструментов для реинжиниринга программного обеспечения DMS с C ++ Front End сможет сделать это для C ++.DMS обеспечивает синтаксический анализ AST, процедурный доступ к AST (как вы делали в своей программе на C ++, но, что более важно, это понятие шаблонов исходного кода.

Для вашей конкретной задачи вы можете использовать следующий шаблон DMS.

 domain Cpp~gcc4;

 pattern numeric_literal_index(v: identifier, n: numeric_literal):lhs
    " \v[\n] ";

Язык и диалект указываются в объявлении domain . В этом случае язык C ++ (здесь, очевидно, Cpp), а диалект gcc4 (DMS может обрабатыватьРазнообразие диалектов C ++).

Назван шаблон (поскольку у нас часто бывает много шаблонов и правил) * numeric_literal_index *. Шаблон параметризован идентификатором (это токен грамматики C ++)) и numeric_literal (аналогично, но это нетерминал грамматики, который допускает любой из числовых литеральных типов zillion C ++), потому что мы хотим соответствовать 1, 3L и т. д. Шаблон ограничен для соответствия lhs (aC ++ грамматика нетерминальная), хотя на практике это не будет соответствовать чему-либо еще из-за его синтаксиса. Фактический образец заключен в metaquotes "..." , которые изолируют специфический синтаксис C ++ от окружающего моря синтаксиса языка шаблонов.

С этим шаблоном может быть выполнен вызов DMS для соответствияэтот шаблон против узла дерева.Совпадение вернет указатели на узел идентификатора AST и узел дерева numeric_literal.

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

Answer 4

Я даже не уверен, что это выполнимо в C или C ++, потому что сопоставление с шаблоном включает переменные шаблона, и нет простого способа получить их в C или C ++ (если вы не кодируете интерпретатор в C ++ для языка, имеющегошаблонов, в этом случае у вас есть некоторые представления окружений, и вам нужна стандартная процедура объединения для сопоставления).

Если вам нужны шаблоны внутри кода C ++, я бы предложил создать генератор кода C ++, который переводитваши шаблоны [выраженные на языке вашего домена] в код C ++.

Я сделал эквивалент для C (перевод шаблонов с переменными шаблонов из MELT в C) в GCC MELT специфичный для домена язык (с соответствием и шаблонами) для расширения компилятора GCC.