trivial 의 lisp 컴 파일 러 개발 (1)

서언
나 는 lisp - like 언어의 해석 기 를 몇 개 썼 는 지, 그리고 바이트 코드 로 컴 파일 된 컴 파일 러 를 기억 하지 못 하지만, 이번 이 마지막 이 아 닐 것 이 라 고 생각한다.나 는 구덩이 에 들 어가 첫 번 째 해석 기 를 쓴 이 유 를 기억 하고 있다. 그 당시 에 Common Lisp 를 조금 배 웠 기 때문이다. 데이터 구조의 교과서 에서 광의 표 라 는 데이터 구 조 를 언급 했 는데 갑자기 '이 광의 표 는 CL 중의 아 톰 과 cons 를 표현 할 수 있 지 않 습 니까?' 라 고 생각 하여 프로그램 해석 입력 을 작성 하고 광의 표를 만 들 며 S 표현 식 으로 인쇄 하려 고 했다.이 를 바탕 으로 가감 승제 등 연산 기능 을 시도 해 해석 기 를 만 드 는 여정 을 한 걸음 한 걸음 시작 했다.나중에 저 는 Peter Norvig 가 쓴 《Paradigms of AI Programming》 을 보 았 습 니 다. 그 안에 두 장 이 해석 기와 컴 파일 러 를 어떻게 작성 하 는 지, 즉 자체 제작 가상 컴퓨터 의 바이트 코드 로 컴 파일 하 는 지 에 대해 이야기 해 주 었 습 니 다.거장 의 인도 아래 나 도 trivial 의 컴 파일 러 를 쓰기 시작 했다.
이번에 시 작 된 이 모델 은 다르다. lisp - like 코드 를 가공 가상 컴퓨터 의 바이트 코드 로 컴 파일 하지 않 고 macOS 의 x64 어 셈 블 리 코드 로 컴 파일 하 는 것 은 적지 않 은 도전 이다.알다 시 피 lisp - like 의 언어 (Scheme, Common Lisp, Clojure 등) 는 모두 고급 언어 로 높 은 차원 의 개념 을 가지 고 있다. cons, continia, lambda, symbol 등 이다.이런 언어 중의 개념 은 x64 어 셈 블 리 에 직접적 으로 대응 할 수 없 기 때문에 나 는 반드시 그들 간 의 장벽 을 메 워 야 한다.다른 한편, 저 는 x86 어 셈 블 리 에 대해 아무것도 모른다 고 할 수 있 습 니 다. 자 료 를 검색 하면 서 쓰 고 생 성 된 어 셈 블 리 코드 의 운행 효율 은 대부분 낮 습 니 다.그래도 재 미 있 으 면 충분해.
lisp - like 언어 에서 x64 어 셈 블 리 까지 의 trivial 컴 파일 러 를 실현 합 니 다.
컴 파일 덧셈 연산
만약 당신 이 활용 단어 참조 이나 다른 전형 적 인 컴 파일 원리 방면 의 책 을 보 았 다 면 컴 파일 러 가 매우 복잡 한 물건 이라는 것 을 알 것 입 니 다.그러나 나의 컴 파일 러 는 매우 간단 하 다. 그것 은 작은 이원 가산 기 에서 진화 하기 시작 할 것 이다.게 으 름 을 피 우 고 컴 파일 러 의 앞부분 을 쓰 지 않 기 위해 저 는 Common Lisp 를 사용 하여 이 컴 파일 러 의 코드 를 작성 할 것 입 니 다. 또한 제 가 가장 흥분 되 고 어 셈 블 리 코드 를 만 드 는 부분 에서 직접 시작 할 수 있 습 니 다.
우선 가장 간단 한 두 개의 작은 정수 의 덧셈 연산 부터 시작한다.lisp 가족의 언어, 예 를 들 어 Common Lisp 에서 덧셈 연산 코드 는 다음 과 같다.

(+ 1 2)

레지스터 가 수용 할 수 있 는 정수 에 대해 직접 출력 add 명령 을 내리 면 되 며, 두 조작 수 는 레지스터 에 잠시 임의로 저장 할 수 있다.이 사고방식 에 따 르 면 간단 하고 작은 정수 덧셈 연산 을 컴 파일 할 수 있 는 컴 파 일 러 가 나 왔 다

(defun jjcc2 (expr)
  "              "
  (cond ((eq (first expr) '+)
         `((movl ,(second expr) %eax)
           (movl ,(third expr) %ebx)
           (addl %eax %ebx)))))

(defun stringify (asm)
  "  jjcc2   S            "
  (format t "        .section __TEXT,__text,regular,pure_instructions~%")
  (format t "        .globl _main~%")
  (format t "_main:~%")
  (dolist (ins asm)
    (format t "        ~A ~A, ~A~%"
            (first ins)
            (if (numberp (second ins))
                (format nil "$~A" (second ins))
                (second ins))
            (if (numberp (third ins))
                (format nil "$~A" (third ins))
                (third ins))))
  (format t "        movl %ebx, %edi~%")
  (format t "        movl $0x2000001, %eax~%")
  (format t "        syscall~%"))

REPL 에서 다음 코드 를 실행 합 니 다.

(stringify (jjcc2 '(+ 1 2)))

다음 과 같은 어 셈 블 리 코드 를 얻 을 수 있 습 니 다.

        .section __TEXT,__text,regular,pure_instructions
        .globl _main
_main:
        MOVL $1, %EAX
        MOVL $2, %EBX
        ADDL %EAX, %EBX
        movl %ebx, %edi
        movl $0x2000001, %eax
        syscall

이 코드 를 jjcc.s 라 는 파일 에 저장 하고 다음 명령 을 실행 하면 실행 가능 한 a.out 실행 가능 한 파일 을 얻 을 수 있 습 니 다.

as -o jjcc.o jjcc.s
gcc jjcc.o
./a.out
echo $? #   3

후기
이 기본 적 인 프레임 워 크 가 있 으 면 많은 기능 을 확장 할 수 있다.예 를 들 어 덧셈 을 제외 하고 뺄셈, 곱셈, 나눗셈 도 지원 할 수 있다.여러 표현 식 의 효 과 를 순서대로 구 할 수 있 습 니 다 progn.지원 setq, 변수 와 할당 기능 등 을 실현 할 수 있 습 니 다.
이 작은 코드 에 도 문제 가 많다.예 를 들 어 호출 format 출력 .section 의 코드 는 gcc -S 의 결과 에서 나 왔 고 더 짧 은 .text 로 대체 할 수 있다.생 성 된 어 셈 블 리 코드 에 서 는 명령 보조 기호 와 레지스터 이름 의 대소 문자 가 일치 하지 않 습 니 다. 등등.그 후에 나 는 코드 를 더 잘 쓰 려 고 재 구성 을 시도 할 것 이다.
원문 을 읽다