자체 언어로 컴파일러를 작성합니다

StackOverflow https://stackoverflow.com/questions/193560

문제

직관적으로 언어를위한 컴파일러가 Foo 그 자체는 foo로 작성 될 수 없습니다. 보다 구체적으로, 첫 번째 언어 컴파일러 Foo Foo로 작성할 수는 없지만 후속 컴파일러는 Foo.

그러나 이것이 사실입니까? 나는 첫 번째 컴파일러가 "자체"로 작성된 언어에 대한 독서를 매우 모호하게 기억하고 있습니다. 이것이 가능합니까? 그렇다면 어떻게?

도움이 되었습니까?

해결책

이것을 "부트 스트랩"이라고합니다. 먼저 다른 언어 (보통 Java 또는 C)로 언어에 대한 컴파일러 (또는 통역사)를 구축해야합니다. 일단 완료되면 언어 foo에 새 버전의 컴파일러를 쓸 수 있습니다. 첫 번째 부트 스트랩 컴파일러를 사용하여 컴파일러를 컴파일 한 다음이 컴파일러 컴파일러를 사용하여 다른 모든 버전 (미래 버전 자체 포함)을 컴파일합니다.

대부분의 언어는 실제로 이러한 방식으로 만들어졌으며, 언어 디자이너는 자신이 만든 언어를 사용하는 것을 좋아하고, 사소한 컴파일러가 종종 언어가 "완전한"언어가 어떻게 "완료 될 수 있는지에 대한 유용한 벤치 마크 역할을하기 때문에 부분적으로 만들어집니다.

이것의 예는 스칼라입니다. 첫 번째 컴파일러는 Martin Odersky의 실험 언어 인 피자로 만들어졌습니다. 버전 2.0 현재, 컴파일러는 스칼라에서 완전히 다시 작성되었습니다. 그 시점부터 새로운 스칼라 컴파일러가 향후 반복을 위해 자체 컴파일하는 데 사용될 수 있기 때문에 이전 피자 컴파일러는 완전히 폐기 될 수 있습니다.

다른 팁

나는 a를 듣는 것을 기억합니다 소프트웨어 엔지니어링 라디오 팟 캐스트 Dick Gabriel은 LISP에서 베어 본 버전을 작성하여 원래 LISP 통역사를 부트 스트랩하는 것에 대해 이야기했습니다. 종이에 그리고 손으로 그것을 기계 코드로 조립합니다. 그때부터 나머지 LISP 기능은 LISP로 작성되어 해석되었습니다.

이전 답변에 호기심을 추가합니다.

다음은 다음과 같습니다 처음부터 리눅스 매뉴얼, 소스에서 GCC 컴파일러를 구축하기 시작하는 단계에서. (스 처음부터 Linux는 분배 설치와는 다른 Linux를 설치하는 방법입니다. 모든 대상 시스템의 단일 바이너리.)

make bootstrap

'부트 스트랩'대상은 GCC를 컴파일 할뿐만 아니라 여러 번 컴파일합니다. 첫 번째 라운드에서 컴파일 된 프로그램을 사용하여 두 번째로 컴파일 한 다음 다시 세 번째로 컴파일합니다. 그런 다음이 두 번째 및 세 번째 컴파일을 비교하여 완벽하게 재현 할 수 있습니다. 이것은 또한 올바르게 컴파일되었음을 의미합니다.

'부트 스트랩'대상의 사용은 대상 시스템의 툴체인을 빌드하는 데 사용하는 컴파일러가 대상 컴파일러와 동일한 버전의 대상 컴파일러를 가질 수 없다는 사실에 의해 동기가 부여됩니다. 그런 식으로 진행하는 것은 대상 시스템에서 자체 컴파일 할 수있는 컴파일러를 얻을 수 있습니다.

C에 대한 첫 번째 컴파일러를 작성하면 다른 언어로 작성합니다. 이제 COSTILER를위한 컴파일러가 있습니다. 결국, 당신은 끈, 특히 탈출 시퀀스를 구문 분석 해야하는 곳으로 올 것입니다. 변환 할 코드를 작성합니다 \n 십진 코드 10을 가진 캐릭터에게 (그리고 \r 13 등).

그 컴파일러가 준비된 후에는 C에서 그것을 상환하기 시작합니다.이 프로세스는 "입니다."부트 스트랩".

문자열 구문 분석 코드는 다음과 같습니다.

...
if (c == 92) { // backslash
    c = getc();
    if (c == 110) { // n
        return 10;
    } else if (c == 92) { // another backslash
        return 92;
    } else {
        ...
    }
}
...

이 컴파일하면 ' n'을 이해하는 바이너리가 있습니다. 이것은 소스 코드를 변경할 수 있음을 의미합니다.

...
if (c == '\\') {
    c = getc();
    if (c == 'n') {
        return '\n';
    } else if (c == '\\') {
        return '\\';
    } else {
        ...
    }
}
...

그렇다면 ' n'이 13의 코드는 어디에 있습니까? 이진에 있습니다! DNA와 같습니다.이 바이너리를 사용하여 C 소스 코드를 컴파일하면이 정보가 상속됩니다. 컴파일러가 자체를 컴파일하면이 지식을 자손에게 전달합니다. 이 시점부터 소스만으로 컴파일러가 할 일을 볼 수있는 방법이 없습니다.

일부 프로그램 소스에서 바이러스를 숨기려면 다음과 같이 할 수 있습니다. 컴파일러의 소스를 가져 와서 함수를 컴파일하는 함수를 찾아서 다음과 같이 대체하십시오.

void compileFunction(char * name, char * filename, char * code) {
    if (strcmp("compileFunction", name) == 0 && strcmp("compile.c", filename) == 0) {
        code = A;
    } else if (strcmp("xxx", name) == 0 && strcmp("yyy.c", filename) == 0) {
        code = B;
    }

    ... code to compile the function body from the string in "code" ...
}

흥미로운 부분은 A와 B입니다. A는 소스 코드입니다. compileFunction 바이러스를 포함하여 아마도 어떤 식 으로든 암호화 될 수 있으므로 결과 바이너리를 검색하는 것은 분명하지 않습니다. 이를 통해 컴파일러 자체로 컴파일하면 바이러스 주입 코드가 보존됩니다.

B는 바이러스로 교체하려는 기능과 동일합니다. 예를 들어 Linux 커널에서 온 소스 파일 "login.c"에서 "로그인"함수 일 수 있습니다. 일반 암호 외에 루트 계정의 비밀번호 "Joshua"를 허용하는 버전으로 대체 할 수 있습니다.

당신이 그것을 편집하고 바이너리로 뿌리면, 소스를 보면 바이러스를 찾을 수있는 방법이 없을 것입니다.

아이디어의 원래 출처 : http://cm.bell-labs.com/who/ken/trust.html

시작 소스 코드를 컴파일 할 것이 없기 때문에 컴파일러를 자체적으로 작성할 수 없습니다. 이것을 해결하기위한 두 가지 접근법이 있습니다.

가장 선호하는 것은 다음과 같습니다. 최소한의 언어 세트를 위해 Assembler (Yuck)에 최소 컴파일러를 작성한 다음 해당 컴파일러를 사용하여 언어의 추가 기능을 구현합니다. 모든 언어 기능이있는 컴파일러가있을 때까지 길을 구축하십시오. 일반적으로 다른 선택이 없을 때만 수행되는 고통스러운 과정.

선호되는 접근법은 크로스 컴파일러를 사용하는 것입니다. 다른 컴퓨터에서 기존 컴파일러의 백엔드를 변경하여 대상 시스템에서 실행되는 출력을 만듭니다. 그런 다음 멋진 전체 컴파일러를 사용하여 대상 기계에서 작업합니다. 가장 인기있는 것은 C 언어입니다. 교체 할 수있는 뒷쪽 끝이있는 기존 컴파일러가 많이 있기 때문입니다.

알려진 사실은 GNU C ++ 컴파일러에는 C 서브 세트 만 사용하는 구현이 있다는 것입니다. 그 이유는 일반적으로 새 대상 기계를위한 C 컴파일러를 찾기가 쉽습니다. 그러면 전체 GNU C ++ 컴파일러를 빌드 할 수 있습니다. 이제 부팅을 대상 시스템에 C ++ 컴파일러를 갖도록 묶었습니다.

일반적으로 컴파일러가 먼저 작동하는 (원시적 인 경우) 컷이 필요합니다. 그러면 자체 호스팅에 대해 생각할 수 있습니다. 이것은 실제로 일부 langauges에서 중요한 이정표로 간주됩니다.

내가 "모노"에서 기억하는 것에서, 그들은 그것을 작동시키기 위해 반사에 몇 가지 사항을 추가해야 할 것입니다. 모노 팀은 단순히 어떤 것들이 불가능하다는 것을 계속 지적합니다. Reflection.Emit; 물론 MS 팀은 그들이 틀렸다는 것을 증명할 수 있습니다.

이것은 몇 가지가 있습니다 진짜 장점 : 초보자에게는 상당히 좋은 단위 테스트입니다! 그리고 당신은 걱정할 언어가 하나뿐입니다 (예 : C# 전문가가 C ++를 많이 알지 못할 수도 있지만 이제 C# 컴파일러를 수정할 수 있음). 하지만 여기서 직장에서 전문적인 자부심이 없는지 궁금합니다. 원하다 그것은 자조입니다.

컴파일러는 아니지만 최근에 자체 호스팅 인 시스템을 연구하고 있습니다. 코드 생성기는 코드 생성기를 생성하는 데 사용됩니다 ... 스키마가 변경되면 단순히 자체적으로 실행됩니다 : 새 버전. 버그가 있으면 이전 버전으로 돌아가서 다시 시도합니다. 매우 편리하고 유지하기가 매우 쉽습니다.

업데이트 1

방금 봤어요 이 비디오 PDC의 Anders와 (약 1 시간) 그는 서비스로 컴파일러에 관한 훨씬 더 유효한 이유를 제시합니다. 기록만을 위해서.

다음은 덤프입니다 (실제로 검색하기 어려운 주제) :

이것은 또한 아이디어입니다 pypy 그리고 루비니우스:

(나는 이것이 또한 적용될 수 있다고 생각합니다 앞으로, 그러나 나는 Forth에 대해 아무것도 모른다.)

GNU ADA 컴파일러 인 GNAT는 ADA 컴파일러를 완전히 빌드해야합니다. 이것은 쉽게 구할 수있는 GNAT 바이너리가없는 플랫폼으로 포팅 할 때 통증이 될 수 있습니다.

실제로 대부분의 컴파일러는 위에서 언급 한 이유로 컴파일 된 언어로 작성됩니다.

첫 번째 부트 스트랩 컴파일러는 일반적으로 C, C ++ 또는 어셈블리로 작성됩니다.

Mono Project C# 컴파일러는 오랫동안 "자체 호스팅"되어 왔으며, 그 의미는 C# 자체로 작성되었다는 것입니다.

내가 아는 것은 컴파일러가 순수한 C 코드로 시작되었지만 ECMA의 "기본"기능이 구현되면 C#에서 컴파일러를 다시 작성하기 시작했습니다.

나는 같은 언어로 컴파일러를 작성하는 이점을 알지 못하지만, 언어 자체가 제공 할 수있는 기능과 적어도 수행해야한다고 확신합니다 (예 : C는 객체 지향 프로그래밍을 지원하지 않습니다). .

더 많은 정보를 찾을 수 있습니다 여기.

어쩌면 당신은 쓸 수 있습니다 BNF BNF 설명.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top