[Compiler] 14. Language Processor (interperter, bootstrapping)

Language Processor

- 처리할 수 있는 프로그램 (translated or interpreted)

- 두 가지 종류의 언어 프로세서 : Translator, Interpereter

- translator는 한 언어로 표현된 텍스트를 받아들이고, 다른 언어로 표현된 semantically-equivalent 텍스트를 생성하는 프로그램

• assembler는 assembly 언어에서 기계 언어로 translate 한다.
• 컴파일러는 high-level의 언어를 low-level의 언어로 번역한다.
  High-level Language -> Compiler(Program) -> object code
• 컴파일러는 구현 언어로 작성된다.

- Interpreter는 소스 프로그램을 받아들이고, 소스프로그램을 즉시 실행하는 프로그램이다.

 

Terminology

 

Tombstone diagram (T-diagram)

프로그램, 언어 프로세서(translator, interpreter), 언어 프로세서에 의한 프로그램 조작을 나타낸다.

• L로 구현된 P
• L로 구현된 S -> T로 변환하는 Translator
• hardware M에서 작동한다.
  ex) X86, PPC, ARM 등
• L로 표현된 M interpreter

 

Tombstone diagram example

 

Tombstone diagrams : Combination rules

Program이 Machine 코드로 구현되어야한다.
Program이 Machine에서 실행되기 위해선 Program 코드를 Machine코드로 변환해야한다. 변환해주는 Transrator도 변환하려는 코드와 언어가 같아야 한다.

 

Compilation

C 코드로 작성된 Tetris라는 프로그램을 X86 machine에서 작동시키기

• C로 구현된 Tetris 프로그램을 x86에서 동작시키기 위해, transrator를 사용해 x86으로 구현된 프로그램으로 변환 

 

Cross compilation

하나의 컴퓨터(Host)에서 실행되지만, 다른 컴퓨터(Target)에 대한 코드를 내보내는 컴파일러

• PPC로 구현된 Tetris 프로그램을 PPC에서 다운받아서 실행시킨다.
• 서로 다른 machine이지만 코드 전달이 가능하다.

 

Two stage compilation

2개의 번역기로 구성된 컴파일러

• 첫 번째 transrator의 output은 두 번째 transrator의 input으로 제공된다.

 

Compiling a compiler

- compiler는 프로그램이다.

• C로 표현된 Java를 x86으로 transrate 하는 compiler가 있다면
• 이 compiler를 모든 머신에서 실행할 수 없다. machine 코드로 표현되지 않았기 때문이다.

- 컴파일러를 C를 X86으로 transrate 해줄 컴파일러에 의해 transrate될 일반적인 소스 프로그램으로 취급한다.

 

Interpreters

 

소프트웨어에 구현된 language processor로, 특정 언어로 표현된 소스 프로그램을 수용하고, 소스 프로그램을 즉시 실행한다.

 

 

 

 

 

Interpreters vs Compilers

- Compiler가 더 유용한 경우

• 프로그램이 production setting으로 돌아갈 때
  -> 복잡한 만큼 처리가 더 오래걸린다.

- Interpreter가 더 유용한 경우

• 디버깅시 line by line으로 실행
• 실행시간이 덜 중요한 경우

 

Interpreters

- Terminology : abstract (or virtual) machine vs real machine

- Example : Java Virtual Machine (JVM)

 

왼쪽 그림과 같이 만들면 Machine Independent

 

 

 

Interpreters : Why are abstract machines useful?

1. abstract machine은 더 나은 플랫폼 independence를 제공

2. abstract machine은 테스트 및 디버깅에 유용

ex) X86에 Ultima 에뮬레이터를 구현할 필요가 없다. high-level 언어를 사용해 컴파일 할 수 있다.

	속도 차이는 있지만, 기능적 차이는 없다. ex) Virtual box, VMware

 

Interpretive compilers

- interpretive compiler는 소스 프로그램을 intermediate(중간 단계) 언어로 번역하고,
결과 object 프로그램은 interpreter에 의해 실행된다.

- intermediate language 장점

• 빠른 컴파일과 합리적인 런타임 성능 사이의 균형
• 기계 코드보다 더 high-level -> 컴파일하기 쉬운
• 소스 언어보다 더 low-level -> 인터프리터로 구현이 용이

ex) Java Development Kit

• Java code -> byte code로 컴파일 -> JVM에서 interpreter
• C++ -> assemble code로 컴파일 -> machine code
• byte code와 assemble은 모두 중간 단계 코드
• assemble -> machine에 dependent
• byte code -> machine에 independent

Ex) Java Development Kit

Java program을 byte code로 translate하면, byte code를 machine에서 실행할 수 있는 interpreter를 통해 프로그램을 실행

---

Portable compilers

Partable 하다 -> 이식성이 좋다. 어느 머신에서든 동작할 수 있다.

---

Bootstrapping

transrator를 자기 자신의 language로 구현하는 것

- Simple 컴파일러를 만들어 계속해서 갱신해 점점 효율적인 컴파일러를 만드는 것

ex)

 

- 컴파일러를 자체 언어(컴파일 하려는 언어)로 구현함으로써, 우리는 대상 플랫폼에 덜 dependent하게 된다.
=> 더 많은 portable한 구현

- Chichen and egg problem 발생

• 위의 예시에서 Java를 compile하기위해서는 Java로 만든 컴파일러가 필요한데, 어떻게 첫 번째 컴파일러를 만들까?
• 크게 2가지 방법이 있다.
  1. Full Bootstrap
  2. Half Bootstrap

 

Full Bootstrap

ex) 우리는 M이라는 machine에서 동작하는 Ada compiler를 만들고 싶다. 하지만, 아직 Ada compiler가 없는 상황이다.

Step 1a : 처음에 C 언어로 Compiler(v1)를 구현한다.

Step 1b : machine M에서 동작하는 컴파일러를 만든다.

• 이 컴파일러는 bootstrapping에 사용할 수 있지만, C로 쓰여졌기 때문에, C 컴파일러에 의존하기를 원하지 않는다.

Step 2a : 자기 자신의 언어를 이용해 컴파일러를 만든다.

Step 2b : v1(앞에서 만든 컴파일러)로 v2 컴파일러를 컴파일 한다.

• 컴파일러가 자기 자신의 언어로 만들어졌다.
• v2는 C 언어에 대해 의존적이지 않다.
• C로 만들 경우 C -> M으로 바꿔주는 컴파일러까지 유지(관리)해야한다.

- 여기부턴 컴파일러 버전을 계속 up 시키는 것이다.

Step 3a : Ada-S를 이용해 컴파일러를 만든다.

Step 3b : v2를 이용해 v3를 컴파일한다.

• 이 시점부터 Ada에서 컴파일러를 유지할 수 있다.
• 후속 버전인 v4, v5, ... 컴파일러의 내용은 이전 버전의 Ada에서 작성된다.

 

Half bootstrap

HM(Host Machine)에서 M으로 cross compile을 사용해 M compiler를 bootstrap할 수 있다.

ex) Ada를 TM으로 바꾸는 컴파일러를 만들기

Step 1 : Ada로 Ada -> TM(Target Macine)으로 바꿔주는 컴파일러 작성한다.

Step 2 : 현재는 HM에서 동작하는 컴파일러만 가지고 있다. HM에서 컴파일한다.

Step 3 : v1을 이용해 step1에서 만든 컴파일러를 Cross Compile 한다.

• 이제부터 TM에서 동작하는 컴파일러의 후속 버전을 개발할 수 있다.

 

Bootstrapping to improve efficiency

- 프로그램의 효율성

• 메모리 사용
• runtime

- 컴파일러의 효율성

• 컴파일 자체의 효율성
• 배출된 code의 효율성

 

Go

Go 컴파일러는 처음에 C로 작성되었다.

현재는 Go로 작성되었다.

• C 보다 읽기 쉽다.
• 작성하기 쉽다.
• 디버깅이 쉽다.
• 앞의 bootstrapping 개념을 통해 점점 효율적인 컴파일러를 만들 수 있다.
• Go에 대해 더 이해할 수 있다.

 

Conclusion

- 좋은 컴파일러를 작성하기 위해서는 먼저 간단한 컴파일러를 몇 개 작성해야 한다.

- source language, target language 및 implementation language에 대해 생각해야 한다.

- 컴파일러 구현 전략

- 기계 코드로 써라.

- low-level 언어로 작성하고 기존 컴파일러를 사용해 컴파일 한다.

- 컴파일 및 bootstrap과 동일한 언어로 작성

- 컴파일러 writer의 작업은 결코 끝나지 않는다. 항상 버전업 한다.