방문자 패턴을 사용한 트리 변환

StackOverflow https://stackoverflow.com/questions/1898967

문제

(면책 조항 :이 예제는 컴파일러 구축의 맥락에서 제공되지만이 질문은 방문자 패턴에 관한 것이며 컴파일러 이론에 대한 지식이 필요하지 않습니다.) Java에서 Andrew Appel의 최신 컴파일러 구현을 통해 노력하고 있습니다. 나 자신에게 컴파일러 이론을 가르치십시오 (아니, 이것은 숙제가 아닙니다) 그리고 나는 그가 방문자 패턴을 사용하여 AST를 IR 트리로 변환하는 방법을 이해하는 데 어려움을 겪고 있습니다. (참고 : Python 에서이 작업을 수행하므로 Python도 배울 수 있습니다. 따라서 다가오는 예제가 Java에 있지 않은 이유입니다.) 내가 이해하는 것처럼, 방문자 패턴의 방문 및 수락 방법은 디자인에 의해 무효가됩니다. 그래서 내가 같은 것이 있다면

class PlusExp(Exp):
    def __init__(self, exp_left, exp_right):
        self.exp_left = exp_left
        self.exp_right = exp_right

    def accept(self, v):
        v.visit_plus_exp(self)

그런 다음 같은 방문자 방법을 작성하고 싶습니다.

def visit_plus_exp(self, plus_exp):
    return BINOP(BinOp.PLUS, 
                 plus_exp.exp_left.accept(self), 
                 plus_exp.exp_right.accept(self))

두 개의 자식 표현을 IR로 번역 한 다음 플러스 표현을 나타내는 Binop과 연결합니다. 물론, 추가 정보를 반환하기 위해 모든 수락 함수를 수정하지 않으면 불가능합니다. 때로는 아무것도 반환하지 않는 인쇄 방문자 만 원하기 때문에 지저분합니다. 그러나이 본문은 방문자가 올바른 방법이며 Java에서는 Python의 유연성없이 수행 할 수 있음을 의미합니다. 나는 엄청나게 해킹되지 않는 솔루션을 생각할 수 없습니다. 누구든지 의도 한 디자인에 대해 나를 깨달을 수 있습니까?

도움이 되었습니까?

해결책

색소폰 파서는 일종의 방문자입니다. 메소드에 리턴 값을 추가하지 않으려면 스택을 사용할 수 있습니다.

class Visitor {
    Stack<Node> stack = new Stack<Node>();

//    . . .

    void visitPlus(PlusExp pe) {
        pe.left.accept(this);
        pe.right.accept(this);
        Node b = stack.pop();
        Node a = stack.pop();
        stack.push(new BinOp(BinOp.PLUS, a, b));
    }

다른 팁

소스 코드를보십시오 이것 컴파일러. 나는 그 사람이 방문자 패턴을 사용했다고 생각합니다.

경고 : 나는 그 책을 읽지 않았다.

이 방법은 무효가 될 수 있지만 Java (책이 쓰여진)에서는 객체의 일부이기도합니다. 따라서 방문자 방법은 로컬 멤버 변수에서 구조를 구축하여 통화간에 필요한 컨텍스트를 유지할 수 있습니다.

예를 들어, 인쇄 방문자는 회원 변수 (또는 방문자 객체를 생성 한 메소드의 최종 로컬 변수로 보유 된 StringBuilder에 추가됩니다. 이것은 작은 익명을 생성하는 Java에서 상당히 일반적입니다. 내면의 대상은 일반적인 습관입니다).

Python에서는 방문자 방법이 컨텍스트를 유지하고 구조를 구축하기 위해 비 초점 변수에 액세스 할 수 있습니다. 예를 들어, 폐쇄 또는 작은 물체.

업데이트 - 아래 주석에서 예제로 추가 된 작은 코드가 추가되었습니다.

result = new Node();
result.left.add(n1.accept(this)); 
result.right.add(n2.accept(this)); 
return result;

또는 

result = new Node(); 
this.nextLoc.add(result); 
this.nextLoc = result.left; 
n1.accept(this); 
this.nextLoc = result.right; 
n2.accept(this);

첫 번째는 더 예쁘지 만 (여전히 엉뚱한 주석 예제 코드), 두 번째는 실제로 필요한 경우 빈 공간 반환 유형을 유지할 수 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top