C#에서 추상 구문 트리의 방문자 패턴을 작성하는 방법은 무엇입니까?

Question

AST를 탐색하기 위해 방문자 패턴을 작성해야합니다. 아무도 내가 어떻게 그것을 쓰기 시작할 것이라고 더 말할 수 있습니까? 내가 이해하는 한, AST의 각 노드에는 어떻게 든 호출되는 visit() 메서드 (?)가 있어야합니다 (어디에서?). 그건 내 이해를 끝내. 모든 것을 단순화하기 위해 , 내가 노드 루트는 표현은, 번호, 영업 이익과 나무는 다음과 같습니다 있다고 가정

 Root 
     | 
     Op(+) 
    / \ 
    / \ 
Number(5) \ 
      Op(*) 
      / \ 
      / \ 
     /  \ 
     Number(2) Number(444) 

Answer 1

패턴 방문자 (방문자로 구현)은 임의의 동작을 구현할 수있는 디자인 패턴에 구문 분석 트리의 노드 구현을 수정할 필요없이 구문 분석 트리 (예 : 유형 확인).

그것은 다음과 같은 방법으로 (내가 의사 코드를 사용하고 있습니다)에서 구현 될 수있다 :

먼저 당신은 모든 노드가 구현해야 트리의 노드의 기본 클래스를 정의 할 필요가있다.

abstract class VisitableNode { 
    abstract void accept(Visitor v); 
} 

노드 클래스가 구현해야하는 유일한 방법은 accept 메소드입니다.

그런 다음 구문 분석 트리의 방문자 노드의 기본 클래스를 정의해야합니다. 방문자의베이스 클래스 만 파스 트리 위해 만들어, 당신이 당신의 파스 트리에서 정의하는 모든 노드 유형에 대한 하나 개의 방문 방법이 있어야합니다

abstract class Visitor { 
    abstract void visit(Root rootNode); 
    abstract void visit(Op opNode); 
    abstract void visit(Number number); 
} 

참고.

그런 다음 노드 클래스의 구현은 다음과 같은 방법으로 VisitableNode 클래스를 확장 할 수 있어야합니다

class Root : VisitableNode { 
    [...] 
    void accept(Visitor v) { 
     v.visit(this); 
    } 
} 

class Op : VisitableNode { 
    [...] 
    void accept(Visitor v) { 
     v.visit(this); 
    } 
} 

class Number : VisitableNode { 
    [...] 
    void accept(Visitor v) { 
     v.visit(this); 
    } 
} 

지금 당신은 당신의 구문 분석 트리 구조를 변경하지 마십시오, 당신은 많은 사람을 자유롭게 구현할 수 있습니다 방문자 (작업)가 원하는대로. NumberFloat, NumberInteger, NumberDouble 등

:

유형 검사를 수행하기 위해, 당신은 당신의 가치와 함께 Number 클래스의 내부 유형을 저장하거나, 그렇지 않으면 당신은 지원의 모든 유형에 대한 Number 클래스를해야합니다

예를 들어, Number 클래스의 값의 정적 유형을 추론 할 수있는 방법이 있다고 가정 해 보겠습니다.

getChild (int childIndex) 메서드를 사용하여 노드의 자식에 액세스 할 수 있다고 가정합니다.

마지막으로, 지원할 정적 유형 (예 : Float, Integer, 등 ...)을 간단히 나타내는 class Type을 사용합니다.

enum Type { 
    Double, 
    Float, 
    Integer; 

    boolean isCompatible(Type type1, Type type2){ 
     // Lookup some type table to determine types compatibility 
    } 
} 

을 그리고 마지막으로 당신은 단지 당신의 유형 테이블과 연산자 테이블을 구현해야합니다

class TypeCheckVisitor : Visitor { 

    // Field used to save resulting type of a visit 
    Type resultType; 


    void visit(Root rootNode) 
    { 
     rootNode.getChild(0).accept(this); 
    } 

    void visit(Op opNode) 
    { 
     opNode.getChild(0).accept(this); 
     Type type1 = resultType; 

     opNode.getChild(1).accept(this); 
     Type type2 = resultType; 

     // Type check 
     if(!type1.isCompatible(type2)){ 
     // Produce type error 
     } 

     // Saves the return type of this OP (ex. Int + Int would return Int) 
     resultType = typeTableLookup(opNode.getOperator(), type1, type2); 
    } 

    void visit(Number number) 
    { 
     // Saves the type of this number as result 
     resultType = number.getType(); 
    } 
} 

그렇다면, 당신은 유사한 방식으로 열거로 아마 Type 클래스를 구현하는 것입니다.

EDIT : 방문 재귀에서 재귀하려는 노드의 accept 메소드를 사용하여 실제로 재귀하는 것이 맞습니다.

TypeCheckVisitor v = new TypeCheckVisitor(); 
rootNode.accept(v); 
print("Root type is: " + v.resultType); 

당신은 또한 임의의 노드를 입력-확인할 수 있습니다

은 사용에 관해서는, 당신은에 의해 구문 분석 트리의 루트 노드에 유형 검사를 수행 (동시에 표현의 유형을 결정) 할 수 동일한 방식으로 루트와 다른 트리를 파싱합니다.