Обход AST в посетителе или в узлах?

Обновление приняло ответ Иры Бакстера, поскольку он указал мне в правильном направлении: сначала я понял, что мне действительно нужно, начав реализацию этапа компиляции, и довольно скоро стало очевидно, что обход узлов делает невозможным подход. Не все узлы следует посещать, а некоторые из них в обратном порядке (например, сначала правая часть присваивания, чтобы компилятор мог проверить, совпадает ли тип с оператором rhs /). Помещение обхода в посетителя делает все это очень легко.

I ' Я создал Lexer / Parser и могу нормально получить AST. Также есть Visitor, и в качестве конкретной реализации я создал ASTToOriginal, который просто воссоздает исходный исходный файл. В конце концов, будет какой-то компилятор, который также реализует Vsisitor и создает реальный код C ++ во время выполнения, поэтому я хочу убедиться, что все в порядке с самого начала. Хотя сейчас все работает нормально, есть некоторый похожий / повторяющийся код, поскольку порядок обхода реализован в самом посетителе.

При поиске дополнительной информации кажется, что некоторые реализации вместо этого предпочитают сохранять порядок обхода в самих посещенных объектах, чтобы это не повторялось у каждого конкретного посетителя. Даже GoF лишь вкратце говорит об этом, точно так же. Так что я хотел попробовать и этот подход, но довольно скоро застрял ... Позвольте мне объяснить.

Пример исходной строки и соответствующие узлы AST:

if(t>100?x=1;sety(20,true):x=2)
Conditional
  BinaryOp
    left=Variable [name=t], operator=[>], right=Integer [value=100]
  IfTrue
    Assignment
      left=Variable [name=x], operator=[=], right=Integer [value=1] 
    Method
      MethodName [name=sety], Arguments( Integer [value=20], Boolean [value=true] )
  IfFalse
    Assignment
      left=Variable [name=x], operator=[=], right=Integer [value=1]

Некоторый код:

class BinaryOp {
  void Accept( Visitor* v ){ v->Visit( this ); }
  Expr* left;
  Op* op;
  Expr* right;
};    
class Variable {
  void Accept( Visitor* v ){ v->Visit( this ); }
  Name* name;
};
class Visitor { //provide basic traversal, terminal visitors are abstract
  void Visit( Variable* ) = 0;
  void Visit( BinaryOp* p ) {
    p->left->Accept( this );
    p->op->Accept( this );
    p->right->Accept( this );        
  }
  void Visit( Conditional* p ) {
    p->cond->Accept( this );
    VisitList( p->ifTrue ); //VisitList just iterates over the array, calling Accept on each element
    VisitList( p->ifFalse );
  }
};

Реализация ASTToOriginal довольно проста: все абстрактно Методы посетителя просто распечатывают имя или член значения терминала. Для нетерминалов это зависит; печать присвоения работает нормально с обходом посетителей по умолчанию, для условного требуется дополнительный код:

class ASTToOriginal {
  void Visit( Conditional* p ) {
    str << "if(";
    p->cond->Accept( this );
    str << "?";
      //VisitListWithPostOp is like VisitList but calls op for each *except the last* iteration
    VisitListWithPostOp( p->ifTrue, AppendText( str, ";" ) );
    VisitListWithPostOp( p->ifFalse, AppendText( str, ";" ) );
    str << ")";
  }
};

Итак, как можно видеть, оба метода посещения для условного в посетителе и ASTToOriginal действительно очень похожи. Однако попытка решить эту проблему путем обхода узлов не только ухудшила ситуацию, но и создала полный беспорядок. Я пробовал подход с методами PreVisit и PostVisit, которые решили некоторые проблемы, но просто вводили все больше и больше кода в узлы. Также стало казаться, что мне нужно отслеживать ряд состояний внутри посетителя, чтобы знать, когда добавлять закрывающие скобки и т. Д.

class BinaryOp {
  void Accept( Conditional* v ) { 
    v->Visit( this );
    op->Accept( v )
    VisitList( ifTrue, v );
    VisitList( ifFalse, v );
};
class Vistor {
  //now all methods are pure virtual
};
class ASTToOriginal {
  void Visit( Conditional* p ) {
    str << "if(";
    //now what??? after returning here, BinaryOp will visit the op automatically so I can't insert the "?"
    //If I make a PostVisit( BinaryOp* ), and call it it BinaryOp::Accept, I get the chance to insert the "?",
    //but now I have to keep a state: my PostVisit method needs to know it's currently being called as part of a Conditional
    //Things are even worse for the ifTrue/ifFalse statement arrays: each element needs a ";" appended, but not the last one,
    //how am I ever going to do that in a clean way?
  }
};

Вопрос : не подходит ли этот подход для моего случая? или я упускаю из виду что-то важное? Есть ли общий дизайн, позволяющий справиться с этими проблемами? Что, если мне также нужен обход в другом направлении?