AST 평가 퍼즐 용 Java 솔루션

Question

this discussion about AST construction and evaluation in various languages에 관심이 있습니다. 나는이 문제에서 배울 수있는 것을보기 위해 Java의 솔루션을 개발 중이다.

아래 코드는 컴파일되지만 잘못된 결과 (즉, "oops"예외)가 발생합니다. 자바는 런타임 디스패치가 없기 때문에 작동하지 않습니다. 거기에 대한 간단한 해결 방법이 있습니까? 복잡한 해결 방법은 어떻습니까? 예 : 제네릭을 사용하여 컴파일러에 대한 힌트를 제공합니까? 나는 여기서 추측하고있다.

내가 배제한 몇 가지 아이디어는 다음과 같습니다. (1) instanceof를 사용하여 런타임에 인수 유형을 디스패치합니다. (2) 인자 타입을 적절한 핸들러에 매핑하는 룩업 테이블을 만듭니다. (3) 서브 클래스를 적절하게 평가하는 E의 각 서브 클래스에 평가 함수를 두십시오.

필자는 저를 위해 컴파일러 및/또는 런타임을 얻으려고하기 때문에 (1)과 (2)를 배제했습니다. 나는 표현식 표현과 평가 코드를 분리하기를 원하기 때문에 (3)을 배제했다. 표현에 대한 여러 작업 (재정렬, 단순화)이있을 수 있다는 생각입니다.

여기까지 제가 지금까지 가지고 있습니다. 위에서 언급 한 것처럼이 코드는 잘못된 결과를 생성합니다.

import java.util.*; 

public class EV 
{ 
    public static Integer ev (E e, Map <String, Integer> env) { throw new RuntimeException ("oops: " + e); } 
    public static Integer ev (V e, Map <String, Integer> env) { return env.get (e.name); } 
    public static Integer ev (C e, Map <String, Integer> env) { return e.value; } 
    public static Integer ev (P e, Map <String, Integer> env) { return ev (e.a1, env) + ev (e.a2, env); } 
    public static Integer ev (T e, Map <String, Integer> env) { return ev (e.a1, env) * ev (e.a2, env); } 

    public static void main (String [] a) 
    { 
     E e = new P (new T (new C (2), new V ("a")), new V ("b")); 
     Map <String, Integer> env = new Hashtable <String, Integer>(); 
     env.put ("a", 123); 
     env.put ("b", 456); 
     System.out.println ("ev (e, env) => " + ev (e, env)); 
    } 
} 

class E {} 

class V extends E 
{ 
    String name; 
    public V (String name) { this.name = name; } 
} 

class C extends E 
{ 
    Integer value; 
    public C (Integer value) { this.value = value; } 
} 

class P extends E 
{ 
    E a1, a2; 
    public P (E a1, E a2) { this.a1 = a1; this.a2 = a2; } 
} 

class T extends E 
{ 
    E a1, a2; 
    public T (E a1, E a2) { this.a1 = a1; this.a2 = a2; } 
} 

Answer 1

자바와 같은 단일 파견 OO 언어로이 일을 위해, 이것은 당신은 또한 귀하의 코멘트에 언급 된 꽤 인쇄 작업에 관심이 특히 경우 Visitor Pattern에 대한 고전적인 사용 사례입니다. 당신의 코멘트에 언급 된 다른 작업들 중 일부에 적용될 수도 있지만, 덜 자연스럽게 적용됩니다.