인터프리터 백엔드, 추상 구문 트리를 어떻게 트래버스합니까?

Question

저는 통역사를 작업 중이며 의미 분석 후 트래버스 및 추상 구문 트리를 사용하는 방법에 대한 좋은 설명을 발견하지 못했습니다. 나는 그것을하는 올바른 방법이 무엇인지 궁금합니다. 나는 왼쪽에서 오른쪽으로 처리하는 부모에게 단말기를 병합하고 최대한 많이 반복하는 것을 이해합니다.

나는이 추상 구문 트리를 가지고 있습니다.이 추상 구문 트리는 올 바르거나 맞지 않을 수 있습니다.

ast http://theadesilva.com/so_1.jpg

어떻게해야합니까?

*에 34와 3을 병합 한 다음 4와 *를 +에 병합 한 다음 ident를 call과 + call에 병합 하시겠습니까? 그게 맞습니까? 트리를 거꾸로 통과하는 좋은 알고리즘은 무엇입니까?

Answer 1

내가했던 것처럼 AST를 작성하지 않았을 것입니다. print 인자를 인자로 보았습니다. 그래서 나는 나무를 만들 것입니다.

print 
    \ 
     + 
    / \ 
    4  * 
    / \ 
     3  34 

루트를 운영자/기능에 적용하기 전에 트리를 걸어 평가하십시오. 두 자녀 만있을 수 있다는 규정은 없습니다. 여러 명이 필요한 경우 여러 명의 자녀를 가질 수 있습니다.

즉 재미 (A, B, C, D)

fun 
// \ \ 
a b c d 

또는 자녀가없는

즉 currentTime을() 내 AST와 질문이 될 것이다 이처럼

currentTime 

visit            
print   need to evaluate right child 
+    left is 4, need to evaluate right 
*    left is 3, right is 34 
       evaluate 3 * 34 and return right = 102 
       evaluate 4 + 102 and return right = 106 
       evaluate print, so print 106