부트스트랩(컴파일러)

Bootstrapping (compilers)
이 문서는 부트스트랩 컴파일러에 관한 것입니다.일반적인 개념은 부트스트래핑을 참조하십시오.

컴퓨터 과학에서 부트스트랩은 컴파일러가 컴파일하려는 소스 프로그래밍 언어로 작성된 컴파일러(또는 어셈블리러)를 생성하는 기술입니다.컴파일러의 초기 코어 버전(부트스트랩 컴파일러)은 다른 언어(어셈블리 언어일 수 있음)로 생성됩니다.이 언어의 최소 서브셋을 사용하여 컴파일러의 연속 확장 버전이 개발됩니다.자기 컴파일 컴파일러의 컴파일 문제는 컴파일러 설계에서는 치킨 오어 에그 문제로 불리며 부트스트래핑은 이 [1][2]문제의 해결책입니다.

BASIC, ALGOL, C, C#, D, Pascal, PL/I, Factor, Haskell, Modula-2, Oberon, OCaml, Common Lisp, Scheme, Go, Java, Elixir, Rust, Nima, Scala용 컴파일러를 포함한 많은 프로그래밍 언어용 컴파일러가 부트스트랩되어 있습니다.

과정

일반적인 부트스트랩프로세스는 [3][4][5]3단계 또는 4단계로 동작합니다.

  • 스테이지 0: 부트스트랩 컴파일러가 동작하는 환경을 준비합니다.여기서 부트스트랩 컴파일러의 소스 언어가 선택되고 부트스트랩 컴파일러가 생성하는 출력 언어도 선택됩니다."베어 머신"의 경우(어느 언어용 컴파일러도 존재하지 않는 경우) 소스와 출력은 바이너리 머신 코드로 작성되거나 타깃 이외의 다른 머신에 크로스 컴파일을 통해 작성될 수 있습니다.그렇지 않으면 부트스트랩 컴파일러는 타깃 머신에 존재하는 프로그래밍 언어 중 하나로 작성되며, 그 컴파일러는 상위 레벨의 프로그래밍 언어, 어셈블리 언어, 오브젝트 파일 또는 심지어 머신 코드를 포함하여 타깃에서 실행할 수 있는 무언가를 생성합니다.
  • 스테이지 1: 부트스트랩 컴파일러가 생성됩니다.이 컴파일러는 자신의 소스를 대상 머신에서 실행할 수 있는 프로그램으로 변환하기에 충분합니다.이 시점에서 모든 추가 개발은 부트스트랩 컴파일러에 의해 정의된 언어를 사용하여 수행되며 2단계는 시작됩니다.
  • 스테이지 2: 완전한 컴파일러는 부트스트랩 컴파일러에 의해 생성됩니다.이것은 일반적으로 필요에 따라 단계적으로 이루어집니다.예를 들어 언어 버전 X의 컴파일러는 버전 X+1에서 기능을 컴파일할 수 있지만, 그 컴파일러는 실제로 이러한 기능을 사용하지 않습니다.이 컴파일러가 테스트되어 컴파일러 자체를 컴파일 할 수 있게 되면 이후 출시되는 컴파일러에서 버전 X+1 기능을 사용할 수 있게 됩니다.
  • 스테이지 3: 풀 컴파일러는 스테이지2 풀 컴파일러에 의해 생성됩니다.기능이 추가될 경우 2단계에서 작업이 재개되며 현재 3단계 풀 컴파일러가 부트스트랩 컴파일러를 대체합니다.

풀 컴파일러는 두 단계의 출력을 비교하기 위해 두 번 구축됩니다.다른 경우 부트스트랩 또는 풀 컴파일러 중 하나에 [3]버그가 포함되어 있습니다.

이점

컴파일러의 부트스트랩에는 다음과 같은 [6][7]이점이 있습니다.

  • 이것은 컴파일되고 있는 언어에 대한 간단한 테스트이며, 따라서 개밥의 한 형태입니다.
  • 컴파일러 개발자 및 버그 리포터는 컴파일 대상 언어만 알면 됩니다.
  • 컴파일러 개발은 컴파일 중인 상위 언어로 수행할 수 있습니다.
  • 컴파일러의 백엔드가 개선되면 범용 프로그램뿐만 아니라 컴파일러 자체도 개선됩니다.
  • 자체 객체 코드를 재현할 수 있어야 하므로 포괄적인 무결성 검사입니다.

이러한 포인트 중 일부는 언어 런타임도 같은 언어로 작성된다고 가정합니다.

방법들

언어 X로 작성된 언어 X용 컴파일러를 컴파일해야 하는 경우 첫 번째 컴파일러를 어떻게 컴파일할 수 있는지에 대한 문제가 있습니다.실제로 사용되는 방법은 다음과 같습니다.

  • 언어 Y의 언어 X용 인터프리터 또는 컴파일러 구현니클라우스 워스는 그가 [8]Fortran에서 최초의 파스칼 컴파일러를 썼다고 보고했다.
  • X용 다른 인터프리터 또는 컴파일러는 이미 다른 언어 Y로 작성되어 있습니다.이것은 Scheme가 부트스트랩되는 방법입니다.
  • 이전 버전의 컴파일러는 다른 컴파일러가 존재하는 X의 서브셋으로 작성되었습니다.이것이 Java, Haskell 및 초기 Free Pascal 컴파일러의 일부 슈퍼셋이 부트스트랩되는 방법입니다.
  • 비표준 언어 확장자 또는 옵션 언어 기능을 지원하는 컴파일러는 이러한 확장자 및 기능을 사용하지 않고 쓸 수 있으므로 동일한 기본 언어를 지원하지만 다른 확장자 및 기능 세트를 지원하는 다른 컴파일러와 컴파일할 수 있습니다.C++ 컴파일러의 주요 부분은 G++와 Microsoft Visual C++에서 컴파일할 수 있는 C++의 서브셋으로 작성되었습니다.고급 기능은 일부 GCC 확장으로 작성됩니다.
  • X용 컴파일러는 X용 컴파일러가 존재하는 다른 아키텍처에서 크로스 컴파일됩니다.이는 보통 C용 컴파일러를 다른 플랫폼으로 이식하는 방법입니다.또한 이것은 초기 부트스트랩 후에 Free Pascal에 사용되는 방법입니다.
  • 컴파일러를 X로 쓴 후 소스로부터 손으로 컴파일하여(대부분 최적화되지 않은 방법으로) 코드로 실행함으로써 최적화된 컴파일러를 얻을 수 있습니다.Donald Knuth는 그의 WEB 리터레이티 프로그래밍 시스템에 이것을 사용했습니다.

소스 코드로 컴파일러를 배포하는 방법에는 컴파일러 자체를 사용하여 컴파일러를 컴파일하는 프로세스를 부트스트랩하기 위해 컴파일러의 휴대용 바이트코드 버전을 제공하는 방법이 포함된다.T 다이어그램은 이러한 컴파일러 부트스트랩 기술을 설명하기 [7]위해 사용되는 표기법입니다.소프트웨어가 거의 또는 전혀 없는 시스템에서 복잡한 컴파일러를 실행하는 가장 편리한 방법은 일련의 더욱 정교한 어셈블러와 [9]컴파일러가 필요할 수 있습니다.

역사

주요 기사:컴파일러 구축의 역사

어셈블러는 스스로를 부트스트랩하는 최초의 언어 도구였습니다.

이러한 부트스트랩을 제공하는 최초의 고급 언어는 1958년 NELIAC이었습니다.이렇게 널리 사용된 최초의 언어는 1961년의 Burroughs B5000 Algol과 1962년의 LISP이다.

Hart와 Levin은 1962년 MIT의 LISP에서 LISP 컴파일러를 작성하여 기존의 LISP 인터프리터 안에서 테스트했습니다.일단 컴파일러가 자체 소스 코드를 컴파일할 수 있을 정도로 개선되면, 그것은 자기 [10]호스팅이 되었습니다.

표준 컴파일러 테이프에 존재하는 컴파일러는 인터프리터를 통해 컴파일러의 S-표현 정의를 스스로 작동시켜 얻은 기계어 프로그램입니다.

--

이 기술은 컴파일 대상과 동일한 언어를 지원하는 인터프리터가 이미 존재하는 경우에만 가능합니다.이것은 프로그램 자체를 입력으로 실행한다는 개념에서 직접 차용한 것이며, 이것은 또한 라이스의 정리를 사용하는 정지 문제가 결정 불가능하다는 증거의 변형과 같은 이론 컴퓨터 과학에서의 다양한 증명에도 사용됩니다.

현재의 노력

Trusting Trust 공격과 바이너리 신뢰성에 대한 다양한 공격으로 인해 소스로부터의 부트스트래핑뿐만 아니라 모든 사용자가 소스 및 실행 파일이 일치하는지 확인할 수 있도록 여러 프로젝트를 진행하고 있습니다.여기에는 부트스트래퍼블 빌드[11] 프로젝트와 재현 가능한 빌드 [12]프로젝트가 포함됩니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Reynolds, John H. (December 2003). "Bootstrapping a self-compiling compiler from machine X to machine Y". CCSC: Eastern Conference. Journal of Computing Sciences in Colleges. 19 (2): 175–181. The idea of a compiler written in the language it compiles stirs up the old 'chicken-or-the-egg' conundrum: Where does the first one come from?
  2. ^ Glück, Robert (2012). "Bootstrapping compiler generators from partial evaluators". In Clarke, Edmund; Virbitskaite, Irina; Voronkov, Andrei (eds.). Perspectives of Systems Informatics: 8th International Andrei Ershov Memorial Conference, PSI 2011, Novosibirsk, Russia, June 27 – July 1, 2011, Revised Selected Papers. Lecture Notes in Computer Science. Vol. 7162. Springer. pp. 125–141. doi:10.1007/978-3-642-29709-0_13. Getting started presents the chicken-and-egg problem familiar from compiler construction: one needs a compiler to bootstrap a compiler, and bootstrapping compiler generators is no exception.
  3. ^ a b "Installing GCC: Building". GNU Project - Free Software Foundation (FSF).
  4. ^ "rust-lang/rust: bootstrap". GitHub.
  5. ^ "Advanced Build Configurations — LLVM 10 documentation". llvm.org.
  6. ^ 컴파일러 및 컴파일러 생성기:C++의 개요패트릭 D.테리 1997.인터내셔널 톰슨 컴퓨터 프레스ISBN 1-85032-298-8
  7. ^ a b P.D.의 "컴파일러 구축과 부트스트랩"테리 2000.HTML Wayback Machine에서 2009-11-23 아카이브 완료.PDF 어카이브 2010년 12월 14일, Wayback Machine에 보관.
  8. ^ 니클라우스 워스 2021년파스칼의 50년.커뮤니케이션.ACM 64, 3(2021년 3월), 39~41.DOI: https://doi.org/10.1145/3447525
  9. ^ "무에서 단순한 컴파일러 부트스트랩" 2010년 3월 3일 Edmund Grimley EVANS 2001의 Wayback Machine에 아카이브
  10. ^ a b Tim Hart and Mike Levin. "AI Memo 39-The new compiler" (PDF). Archived from the original (PDF) on 2020-12-13. Retrieved 2008-05-23.
  11. ^ https://bootstrappable.org/
  12. ^ https://reproducible-builds.org/