1.2. Motivation ¶
μ»΄νμΌλ¬κ° abstact syntax treeλ‘ νλ‘κ·Έλ¨μ νννλ€κ³ νμ. μ»΄νμΌλ¬λ λͺ¨λ λ³μλ€μ΄ μ μκ° λμ΄μλ μ§λ₯Ό κ²μ¬νλ κ²κ³Ό κ°μ 'μ μ μΈ μλ―Έ' λΆμμ μν΄ abstract syntax treeμ λν΄ operationμ μνν νμκ° μμ κ²μ΄λ€. μ»΄νμΌλ¬λ λν code λ³νμ ν νμκ° μλ€. λν μ»΄νμΌλ¬λ type-checking, code optimization, flow analysis μ ν΄λΉ λ³μκ° μ΄μ©λκΈ° μ μ μΈλμλμ§ λ±μ μ¬λΆλ₯Ό κ²μ¬νκΈ° μν΄μ ν΄λΉ operationsλ€μ μνν νμκ° μλ€. λ λμκ° μ°λ¦¬λ pretty-printing, program restructuring, code instrumentation, κ·Έλ¦¬κ³ νλ‘κ·Έλ¨μ λ€μν κΈ°μ€λ€μ λν κ³μ°μ νκΈ° μν΄ abstract syntax treeλ₯Ό μ΄μ©ν κ²μ΄λ€.
μ΄λ¬ν operationsλ€μ λλΆλΆλ€μ variableλ€μ΄λ arithmetic expressionλ€μ νννλ nodeλ€κ³Ό λ€λ₯΄κ² assignment statementλ€μ νννλ nodeλ₯Ό μ·¨κΈν νμκ° μλ€. λ°λΌμ, κ°κ° assignment statement λ₯Ό μν ν΄λμ€μ, variable μ μ κ·Ό νκΈ° μν ν΄λμ€, arithmetic expressionμ μν ν΄λμ€λ€μ΄ μμ΄μΌ ν κ²μ΄λ€. μ΄λ¬ν node classλ€μ μ»΄νμΌ λ μΈμ΄μ μμ‘΄μ μ΄λ©°, λν μ£Όμ΄μ§ μΈμ΄λ₯Ό μν΄ λ°λμ§ μλλ€.
μ΄ λ€μ΄μ΄κ·Έλ¨μ Node class κ³μΈ΅κ΅¬μ‘°μ μΌλΆλΆμ 보μ¬μ€λ€. μ¬κΈ°μμ λ¬Έμ λ λ€μν node classλ€μ μλ μ΄λ¬ν operationλ€μ λΆμ°μ μμ€ν
μΌλ‘ νμ¬κΈ μ΄ν΄νκΈ° μ΄λ ΅κ³ , μ μ§νκ±°λ μ½λλ₯Ό λ°κΎΈκΈ° νλ€κ² νλ€. Node μ type-checking μ½λκ° pretty-printing codeλ flow analysis codeλ€κ³Ό μμ¬ μλ κ²μ νΌλμ€λ½λ€. κ²λ€κ° μλ‘μ΄ operationμ μΆκ°νκΈ° μν΄μλ μΌλ°μ μΌλ‘ μ΄ ν΄λμ€λ€μ μ¬μ»΄νμΌν΄μΌ νλ€. λ§μΌ κ°κ°μ μ operationμ΄ λ
립μ μΌλ‘ μΆκ°λ μ μκ³ , μ΄ node classλ€μ΄ operationλ€μ λν΄ λ
립μ μ΄λΌλ©΄ λμ± μ’μ κ²μ΄λ€.
μ°λ¦¬λ κ°κ°μ ν΄λμ€λ€λ‘λΆν° κ΄λ ¨λ operationλ€μ ν¨ν€μ§ν νκ³ , traverse λ (tree μ κ° nodeλ€μ μ΄λ) abstract syntax treeμ elementλ€μκ² μΈμλ‘ λκ²¨μ€ μ μλ€. μ΄λ₯Ό visitorλΌκ³ νλ€. elementκ° visitorλ₯Ό 'accepts' ν λ elementλ elementμ ν΄λμ€λ₯Ό μΈμ½λ©ν visitorμκ² requestλ₯Ό 보λΈλ€. μ΄ request λν ν΄λΉ elementλ₯Ό μΈμλ‘ ν¬ν¨νκ³ μλ€. κ·Έλ¬λ©΄ visitorλ ν΄λΉ elementμ λν operationμ μνν κ²μ΄λ€.
μλ₯Όλ λ€λ©΄, visitorλ₯Ό μ΄μ©νμ§ μλ μ»΄νμΌλ¬λ μ»΄νμΌλ¬μ abstact syntax treeμ TypeCheck operationμ νΈμΆν¨μΌλ‘μ type-check μ μνν κ²μ΄λ€. κ°κ°μ nodeλ€μ nodeλ€μ΄ κ°μ§κ³ μλ TypeCheckλ₯Ό νΈμΆν¨μΌλ‘μ¨ TypeCheckλ₯Ό ꡬνν κ²μ΄λ€. (μμ class diagram μ°Έμ‘°). λ§μΌ visitorλ₯Ό μ΄μ©νλ€λ©΄, TypeCheckingVisior κ°μ²΄λ₯Ό λ§λ λ€, TypeCheckingVisitor κ°μ²΄λ₯Ό μΈμλ‘ λ겨주면μ abstract syntax treeμ Accept operationμ νΈμΆν κ²μ΄λ€. κ°κ°μ nodeλ€μ visitorλ₯Ό λλ‘ νΈμΆν¨μΌλ‘μ¨ Acceptλ₯Ό ꡬνν κ²μ΄λ€ (μλ₯Ό λ€μ΄, assignment nodeμ κ²½μ° visitorμ VisitAssignment operationμ νΈμΆν κ²μ΄κ³ , varible referenceλ VisitVaribleReferenceλ₯Ό νΈμΆν κ²μ΄λ€.) AssignmentNode ν΄λμ€μ TypeCheck operationμ μ΄μ TypeCheckingVisitorμ VisitAssignment operationμΌλ‘ λ체λ κ²μ΄λ€.
type-checking μ κΈ°λ₯μ λμ΄ μΌλ°μ μΈ visitorλ₯Ό λ§λ€κΈ° μν΄μλ abstract syntax treeμ λͺ¨λ visitorλ€μ μν abstract parent classμΈ NodeVisitorκ° νμνλ€. NodeVisitorλ κ° node classλ€μ μλ operationλ€μ μ μν΄μΌ νλ€. ν΄λΉ νλ‘κ·Έλ¨μ κΈ°μ€ λ±μ κ³μ°νκΈ° μνλ applicationμ node class μ application-specificν μ½λλ₯Ό μΆκ°ν νμ μμ΄, κ·Έλ₯ NodeVisitorμ λν μλ‘μ΄ subclassλ₯Ό μ μνλ©΄ λλ€. VisitorPatternμ ν΄λΉ Visitor μ μ°κ΄λ λΆλΆμμ μ»΄νμΌλ ꡬ문λ€μ μν operationλ€μ μΊ‘μννλ€.
VisitorPatternμΌλ‘, κ°λ°μλ λκ°μ ν΄λμ€ κ³μΈ΅μ μ μνλ€. νλλ operationμ΄ μνλ elementμ λν κ³μΈ΅μ΄κ³ (Node hierarchy), νλλ elementμ λν operationλ€μ μ μνλ visitorλ€μ΄λ€. (NodeVisitor hierarchy). κ°λ°μλ visitor hierarchy μ μλ‘μ΄ subclassλ₯Ό μΆκ°ν¨μΌλ‘μ μ operationμ λ§λ€ μ μλ€.
1.5. Participants ¶
- Visitor (NodeVisitor)
- declares a Visit operations for each class of ConcreteElement in the object structure. The operation's name and signature identifies the class that sends the Visit request to the visitor. That lets the visitor determine the concrete class of the element being visited. Then the visitor can access the element directly through its particular interface.
- ConcreteVisitor (TypeCheckingVisitor)
- implements each operation declared by Visitor. Each operation implements a fragment of the algorithm defined for the corresponding class of object in the structure. ConcreteVisitor provides the context for the algorithm and stores its local state. This state often accumulates result during the traversal of the structure.
- Element (Node)
- defines an Accept operation that takes a visitor as an argument.
- ConcreteElement (AssignmentNode, VariableRefNode)
- implements an Accept operation that takes a visitor as an argument.
- ObjectStructure (Program)
- can enumerate its elements.
- may provide a high-level interface to allow the visitor to visit its elements.
- may either be a composite (See CompositePattern) or a collection such as a list or a set.
1.7. Consequences ¶
template <class Item> class Iterator { // ... Item CurrentItem () const; };
class Visitor { public: // ... void VisitMyType (MyType*); void VisitYourType (YourType*); };
1.8. Implementation ¶
class Visitor { public: virtual void VisitElementA (ElementA*); virtual void VisitElementB (ElementB*); // and so on for other concrete elements protected: Visitor (); };
class Element { public: virtual ~Element (); virtual void Accept (Visitor&) = 0; protected: Element (); }; class ElementA : public Element { public: ElementA (); virtual void Accept (Visitor& v) { v.VisitElementA (this); } }; class ElementB : public Element { public: ElementB (); virtual void Accept (Visitor& v) { v.VisitElementB (this); } };
class CompositeElement : public Element { public: virtual void Accept (Visitor&); private: List<Element*>* _children; }; void CompositeElement::Accept (Visitor& v) { ListIterator<Element*> i (_children); for (i.First (); !i.IsDone(); i.Next ()) { i.CurrentItem ()->Accept (v); } v.VisitCompositeElement (this); }
1.9. Sample Code ¶
class Equipment { public: virtual ~Equipment (); const char* Name () { return _name; } virtual Watt Power (); virtual Currency NetPrice (); virtual Currency DiscountPrice (); virtual void Accept (EquipmentVisitor&); protected: Equipment (const char*); private: const char* _name; };
class EquipmentVisitor { public: virtual ~EquipmentVisitor (); virtual void VisitFloppyDisk (FloppyDisk*); virtual void VisitCard (Card*); virtual void VisitrChassis (Chassis*); virtual void VisitBus (Bus*); // and so on for other concrete subclasses of Equipment protected: EquipmentVisitor (); };
void FloppyDisk::Accept (EquipmentVisitor& visitor) { visitor.VisitFloppyDisk (this); }
void Chassis::Accept (EquipmentVisitor& visitor) { for (ListIterator<Equipment*> i(_parts); !i.IsDone (); i.Next ()) { i.CurrentItem ()->Accept (visitor); } visitor.VisitChassis (this); }
class PricingVisitor : public EquipmentVisitor { public: PricingVisitor (); Currency& GetTotalPrice (); virtual void VisitFloppyDisk (FloppyDisk*); virtual void VisitCard (Card*); virtual void VisitChassis (Chassis*); virtual void VisitBus (Bus*); // ... private: Currency _total; }; void PricingVisitor::VisitFloppyDisk (FloppyDisk* e) { _total += e->NextPrice (); } void PricingVisitor::VisitChassis (Chassis* e) { _total += e->DiscountPrice (); }
class InventoryVisitoy : public EquipmentVisitor { public: InventoryVisitor (); Inventory& GetInventory (); virtual void VisitFloppyDisk (FloppyDisk*); virtual void VisitCard (Card*); virtual void VisitChassis (Chassis*); virtual void VisitBus (Bus*); // ... private: Inventory _inventory; };
void InventoryVisitor::VisitFloppyDisk (FloppyDisk* e) { _inventory.Accumulate (e); } void InventoryVisitor::VisitChassis (Chassis* e) { _inventory.Accumulate (e); }
Equipment* component; InventoryVisitor visitor; component->Accept (visitor); cout << "Inventory " << componet->Name () << visitor.GetInventory ();
accept: aVisitor ^ aVisitor visitSequence : self
visitSequence: sequenceExp inputState := sequenceExp expression1 accept: self. ^ sequenceExp expression2 accept: self. visitRepeat : repeatExp | finalState | finalState := inputState copy. [inputState isEmpty] whileFalse: [inputState := repeatExp repetition accept: self. finalState addAll: inputState]. ^ finalState visitAlternation: alternateExp | finalState originalState | originalState := inputState. finalState := alternateExp alternative1 accept: self. inputState := originalState. finalState addAll: (alternateExp alternative2 accept: self). ^ finalState visitLiteral: literalExp | finalState tStream | finalState := Set new. inputState do: [:stream | tStream := stream copy. (tStream nextAvailable: literalExp components size ) = literalExp components ifTrue: [finalState add: tStream] ]. ^ finalState