자체 언어로 컴파일러 작성

자체 언어로 컴파일러 작성

---

직관적으로, 언어의 컴파일러 Foo자체는 Foo로 작성할 수 없습니다. 보다 구체적으로, 언어 의 첫 번째 컴파일러 Foo는 Foo로 작성할 수 없지만 이후의 컴파일러는에 대해 작성할 수 있습니다 Foo.

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

---

이것을 "부트 스트래핑"이라고합니다. 먼저 다른 언어 (보통 Java 또는 C)로 언어에 대한 컴파일러 (또는 인터프리터)를 빌드해야합니다. 이 작업이 끝나면 Foo 언어로 새로운 버전의 컴파일러를 작성할 수 있습니다. 첫 번째 부트 스트랩 컴파일러를 사용하여 컴파일러를 컴파일 한 다음이 컴파일 된 컴파일러를 사용하여 다른 모든 버전 (향후 버전 자체 포함)을 컴파일합니다.

대부분의 언어는 실제로 이런 방식으로 만들어집니다. 부분적으로 언어 디자이너는 자신이 만들고있는 언어를 사용하기를 원하며, 사소하지 않은 컴파일러는 종종 언어의 "완전한"정도에 대한 유용한 벤치 마크 역할을하기 때문입니다.

이에 대한 예는 스칼라입니다. 최초의 컴파일러는 Martin Odersky의 실험 언어 인 Pizza에서 만들어졌습니다. 버전 2.0부터는 컴파일러가 Scala로 완전히 다시 작성되었습니다. 그 시점부터는 새로운 Scala 컴파일러가 향후 반복을 위해 자체 컴파일하는 데 사용될 수 있기 때문에 오래된 피자 컴파일러는 완전히 버릴 수 있습니다.

---

나는 듣고 기억합니다 소프트웨어 공학 라디오 팟 캐스트 딕 가브리엘은 LISP의 베어 본 버전을 작성하여 원래의 LISP 인터프리터를 부트 스트랩에 대해 언급 항에있어서, 종이에 손이 기계 코드로 조합. 그때부터 나머지 LISP 기능은 LISP로 작성되고 해석되었습니다.

---

이전 답변에 호기심 추가.

다음은 Linux From Scratch 매뉴얼 에서 인용 한 것입니다. 소스에서 GCC 컴파일러 빌드를 시작하는 단계입니다. (Linux From Scratch는 대상 시스템의 모든 단일 바이너리 를 컴파일해야한다는 점에서 배포판 설치와 근본적으로 다른 Linux를 설치하는 방법 입니다.)

make bootstrap

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

'bootstrap'대상의 사용은 대상 시스템의 툴체인을 빌드하는 데 사용하는 컴파일러가 대상 컴파일러의 버전과 동일하지 않을 수 있다는 사실에 의해 동기가 부여됩니다. 이런 식으로 진행하면 대상 시스템에서 자체 컴파일 할 수있는 컴파일러를 얻을 수 있습니다.

---

C에 대한 첫 번째 컴파일러를 작성할 때 다른 언어로 작성합니다. 이제 C 어셈블러에 대한 컴파일러가 있습니다. 결국, 문자열을 구문 분석 해야하는 곳, 특히 이스케이프 시퀀스를 찾아야합니다. \n10 진수 코드 10 (및 \r13 등)으로 문자 로 변환 하는 코드를 작성합니다 .

해당 컴파일러가 준비되면 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" ...
}

The interesting parts are A and B. A is the source code for compileFunction including the virus, probably encrypted in some way so it's not obvious from searching the resulting binary. This makes sure that compiling to compiler with itself will preserve the virus injection code.

B is the same for the function we want to replace with our virus. For example, it could be the function "login" in the source file "login.c" which is probably from the Linux kernel. We could replace it with a version that will accept the password "joshua" for the root account in addition to the normal password.

If you compile that and spread it as a binary, there will be no way to find the virus by looking at the source.

The original source of the idea: https://web.archive.org/web/20070714062657/http://www.acm.org/classics/sep95/

---

You cannot write a compiler in itself because you have nothing to compile your starting source code with. There are two approaches to solving this.

The least favored is the following. You write a minimal compiler in assembler (yuck) for a minimal set of the language and then use that compiler to implement extra features of the language. Building your way up until you have a compiler with all the language features for itself. A painful process that is usually only done when you have no other choice.

The preferred approach is to use a cross compiler. You change the back end of an existing compiler on a different machine to create output that runs on the target machine. Then you have a nice full compiler up and working on the target machine. Most popular for this is the C language, as there are plenty of existing compilers that have pluggable back ends that can be swapped out.

A little known fact is that the GNU C++ compiler has an implementation that uses only the C subset. The reason being it is usually easy to find a C compiler for a new target machine that allows you to then build the full GNU C++ compiler from it. You have now boot strapped yourself to having a C++ compiler on the target machine.

---

Generally, you need to have a working (if primative) cut of the compiler working first - then you can start thinking about making it self-hosting. This is actually considered an important milestone in some langauges.

From what I remember from "mono", it is likely they will need to add a few things to reflection to get it working: the mono team keep pointing out that some things simply aren't possible with Reflection.Emit; of course, the MS team might prove them wrong.

This has a few real advantages: it is a fairly good unit test, for starters! And you only have one language to worry about (i.e. it is possible a C# expert might not know much C++; but now thy can fix the C# compiler). But I wonder if there isn't an amount of professional pride at work here: they simply want it to be self-hosting.

Not quite a compiler, but I've recently been working on a system that is self hosting; the code generator is used to generate the code generator... so if the schema changes I simply run it on itself : new version. If there is a bug, I just go back to an earlier version and try again. Very convenient, and very easy to maintain.

---

Update 1

I've just watched this video of Anders at PDC, and (about an hour in) he does give some much more valid reasons - all about the compiler as a service. Just for the record.

---

Here's a dump (difficult topic to search on, actually):

• Smalltalk

• C

This is also the idea of PyPy and Rubinius:

(I think this might also apply to Forth, but I don't know anything about Forth.)

---

GNAT, the GNU Ada compiler, requires an Ada compiler to be fully built. This can be a pain when porting it to a platform where there is no GNAT binary readily available.

---

Actually, most compilers are written in the language they compile, for the reasons stated above.

The first bootstrap compiler is usually written in C, C++ or Assembly.

---

The Mono project C# compiler has been "self-hosted" for a long time now, what it means is that it has been written in C# itself.

What I know is that the compiler was started as pure C code, but once the "basic" features of ECMA were implemented they started to rewrite the compiler in C#.

I'm not aware of the advantages of writing the compiler in the same language, but I'm sure it has to do at least with the features that the language itself can offer (C, for example, does not support object oriented programming).

You can find more information here.

---

Maybe you can write a BNF describing BNF.

참고URL : https://stackoverflow.com/questions/193560/writing-a-compiler-in-its-own-language