컴파일러는 일의 표현을 바꾼다.
작은 컴파일러는 표현식 트리를 나중에 별도 기계가 실행할 스택 명령으로 바꿀 수 있습니다.
표현식 트리는 어떻게 선형 명령열이 될까요?
- Emit constant and arithmetic instructions from syntax data
- Preserve operand order in stack code
- Separate compilation from machine execution
compile emits the left operand code, then the right operand code, and finally one arithmetic instruction. Recursion flattens the nested expression into a linear list.
execute pushes constants. An arithmetic instruction pops the right and left values, combines them, and pushes the result. When no code remains, the stack top is the program value.
(begin
(define (operator-instruction operator)
(cond ((eq? operator '+) 'add)
((eq? operator '-) 'sub)
((eq? operator '*) 'mul)))
(define (compile expression)
(if (number? expression)
(list (list 'const expression))
(append (compile (cadr expression))
(append (compile (caddr expression))
(list (operator-instruction (car expression)))))))
(define (execute code stack)
(if (null? code)
(car stack)
(let ((instruction (car code)))
(if (pair? instruction)
(execute (cdr code) (cons (cadr instruction) stack))
(let ((right (car stack)) (left (cadr stack)))
(execute
(cdr code)
(cons (cond ((eq? instruction 'add) (+ left right))
((eq? instruction 'sub) (- left right))
((eq? instruction 'mul) (* left right)))
(cddr stack))))))))
(let ((code (compile '(+ (* 3 4) 5))))
(list code (execute code '()))))- 출력
- —
- 값
- —
- 진단
- —
The first program returns the five emitted instructions and the executed value 17.
Separate the recursive compile calls from the later execute calls. During execution, each instruction consumes code while changing the stack.
힌트를 보기 전에 프로그램을 바꿔 보세요.
Compile (+ 1 (* 2 (+ 3 4))). Write the instruction list before you execute it.
힌트 하나 보기
Each number emits const. Each compound expression emits its operator after both operands.