매우 기본적인 컴파일러 작성 방법

Intro

일반 컴파일러는 다음 단계를 수행합니다.

• 파싱 : 소스 텍스트는 추상 구문 트리 (AST)로 변환됩니다.
• 다른 모듈에 대한 참조 해결 (C는 연결될 때까지이 단계를 연기합니다.)
• 의미 적 유효성 검사 : 구문 적으로 올바른 명령문 제거 말이 안되는 것, 예를 들어 도달 할 수없는 코드 또는 중복 선언.
• 동등한 변환 및 높은 수준의 최적화 : AST는 동일한 의미로 더 효율적인 계산을 나타내도록 변환됩니다. 여기에는 예가 포함됩니다. 일반적인 하위 표현식 및 상수 표현식의 조기 계산, 과도한 로컬 할당 제거 ( SSA 참조) 등
• 코드 생성 : AST는 점프, 레지스터 할당 등을 통해 선형 저수준 코드로 변환됩니다. 일부 함수 호출은이 단계에서 인라인 될 수 있고, 일부 루프는 풀릴 수 있습니다.
• 구멍 최적화 : 제거되는 단순한 로컬 비 효율성을 위해 저수준 코드를 스캔합니다.

대부분의 최신 컴파일러 (예 : gcc 및 clang)는 마지막 두 단계를 한 번 더 반복합니다. 초기 코드 생성을 위해 중급 저수준이지만 플랫폼 독립적 인 언어를 사용합니다. 그런 다음 해당 언어는 플랫폼에 최적화 된 방식으로 거의 동일한 작업을 수행하는 플랫폼 별 코드 (x86, ARM 등)로 변환됩니다. 여기에는 예가 포함됩니다. 가능한 경우 벡터 명령어 사용, 분기 예측 효율성을 높이기위한 명령어 재정렬 등입니다.

그 후 개체 코드를 연결할 준비가되었습니다. 대부분의 네이티브 코드 컴파일러는 실행 파일을 생성하기 위해 링커를 호출하는 방법을 알고 있지만 그 자체로는 컴파일 단계가 아닙니다. Java 및 C #과 같은 언어에서는로드시 VM에 의해 연결이 완전히 동적 일 수 있습니다.

기본 사항 기억

• 효과적으로 만들기
• 멋지게 만들기
• 효율적으로 만들기

이 고전적인 시퀀스는 모든 소프트웨어 개발에 적용되지만 반복이 필요합니다.

시퀀스의 첫 번째 단계에 집중하고 작동 할 수있는 가장 간단한 것을 만듭니다.

책을 읽으십시오!

Aho와 Ullman의 Dragon Book 을 읽어보세요. 이것은 고전적이며 오늘날에도 여전히 적용 가능합니다.

최신 컴파일러 설계 도 칭찬합니다.

지금이 작업이 너무 힘들다면 먼저 파싱에 대한 소개를 읽어보세요. 일반적으로 라이브러리 파싱 소개와 예를 포함합니다.

그래프, 특히 나무 작업에 익숙한 지 확인하세요. 이러한 것들은 프로그램이 논리적 수준에서 만들어지는 것들입니다.

언어를 잘 정의하세요

원하는 표기법을 사용하되, 당신의 언어에 대한 완전하고 일관된 설명이 있는지 확인하세요. 언어. 여기에는 구문과 의미가 모두 포함됩니다.

향후 컴파일러를위한 테스트 케이스로 새 언어로 코드 스 니펫을 작성할 때입니다.

원하는 언어 사용

파이썬이나 루비 또는 여러분에게 쉬운 어떤 언어로든 컴파일러를 작성해도 괜찮습니다.잘 이해하는 간단한 알고리즘을 사용하십시오. 첫 번째 버전은 빠르거나 효율적이거나 기능이 완벽 할 필요가 없습니다. 충분히 정확하고 쉽게 수정할 수 있으면됩니다.

필요한 경우 다른 언어로 컴파일러의 여러 단계를 작성하는 것도 괜찮습니다.

많은 작성 준비 테스트 수

전체 언어는 테스트 케이스로 다루어야합니다. 실제로는 테스트 케이스에 의해 정의 됩니다. 선호하는 테스트 프레임 워크에 익숙해 지세요. 첫날부터 테스트를 작성하세요. 잘못된 코드를 감지하는 대신 올바른 코드를 허용하는 “양성”테스트에 집중하십시오.

모든 테스트를 정기적으로 실행하십시오. 계속하기 전에 손상된 테스트를 수정하십시오. 병으로 끝나는 것은 부끄러운 일입니다. 유효한 코드를 허용 할 수없는 정의 된 언어입니다.

좋은 파서 만들기

파서 생성기는 많습니다 . 원하는 것을 선택하세요. 자신 만의 파서를 처음부터 작성할 수도 있지만, 언어 구문이 죽은 단순한 경우에만 그만한 가치가 있습니다.

파서는 구문 오류를 감지하고보고해야합니다. 많은 테스트 케이스 (양성 및 부정) ve; 언어를 정의 할 때 작성한 코드를 재사용하십시오.

파서의 출력은 추상 구문 트리입니다.

언어에 모듈이있는 경우 파서의 출력은 가장 간단한 표현 일 수 있습니다. 생성하는 “개체 코드”의. 트리를 파일에 덤프하고 신속하게 다시로드하는 간단한 방법이 많이 있습니다.

의미 론적 유효성 검사기 만들기

대부분의 언어는 구문 적으로 올바른 구성을 허용합니다. 특정 상황에서는 의미가 없습니다. 예를 들어 동일한 변수의 중복 선언 또는 잘못된 유형의 매개 변수 전달이 있습니다. 유효성 검사기는 트리를보고 이러한 오류를 감지합니다.

검사기는 또한 사용자 언어로 작성된 다른 모듈에 대한 참조를 확인하고 이러한 다른 모듈을로드하고 유효성 검사 프로세스에 사용합니다. 예를 들어,이 단계는 다른 모듈에서 함수로 전달 된 매개 변수의 수가 올바른지 확인합니다.

다시 많은 테스트 케이스를 작성하고 실행합니다. 사소한 경우는 현명하고 복잡한 문제 해결에 없어서는 안될 필수 요소입니다.

코드 생성

알고있는 가장 간단한 기술을 사용하십시오. 종종 언어 구조 (예 : if 문)를 HTML 템플릿과 달리 매개 변수가 적은 코드 템플릿으로 직접 번역하는 것이 좋습니다.

다시 , 효율성을 무시하고 정확성에 집중하십시오.

플랫폼 독립적 인 하위 수준 VM을 대상으로 지정

하드웨어 별에 관심이없는 경우 하위 수준의 항목을 무시한다고 가정합니다. 세부. 이러한 세부 사항은 복잡하고 복잡합니다.

옵션 :

• LLVM : 일반적으로 x86 및 ARM에 대해 효율적인 기계어 코드 생성을 허용합니다.
• CLR : .NET, 다중 플랫폼을 대상으로합니다. 좋은 JIT가 있습니다.
• JVM : Java 세계를 대상으로하고, 상당히 다중 플랫폼이며, 좋은 JIT가 있습니다.

최적화 무시

최적화는 어렵습니다. 거의 항상 최적화는 시기상조입니다. 비효율적이지만 올바른 코드를 생성합니다. 결과 코드를 최적화하기 전에 전체 언어를 구현하십시오.

물론 사소한 최적화를 도입해도 좋습니다. 그러나 컴파일러가 안정되기 전에 교활하고 털이 많은 것들을 피하십시오.

그래서 무엇입니까?

이 모든 것이 당신에게 너무 위협적이지 않다면 계속 진행하십시오! 간단한 언어의 경우 각 단계가 생각보다 간단 할 수 있습니다.

컴파일러가 만든 프로그램에서 “Hello world”를 보는 것은 그만한 가치가 있습니다.

댓글

• 이것은 제가 ‘ 아직 본 최고의 답변 중 하나입니다.
• 당신이 생각합니다. 질문의 일부를 놓쳤습니다 … OP는 매우 기본적인 컴파일러를 작성하고 싶었습니다. 여기서는 아주 기본적인 것 이상으로 생각합니다.
• @ marco-fiset , 반대로 저는 그렇게 생각합니다. ‘는 OP에 매우 기본적인 컴파일러를 수행하는 방법을 알려주는 동시에 더 고급 단계를 피하고 정의하는 함정을 지적하는 뛰어난 답변입니다.
• 이것은 최고의 답변 중 하나입니다. 나는 전체 Stack Exchange 세계에서 본 적이 있습니다. 감사합니다!
• 컴파일러가 만든 프로그램에서 ‘ Hello world ‘를 보는 것은 그만한 가치가 있습니다. -INDEED

Jack Crenshaw의 Let “s Build a Compiler 는 아직 완성되지 않았지만 매우 읽기 쉬운 소개 및 자습서입니다.

Nicklaus Wirth의 컴파일러 구성 는 단순한 컴파일러 구성의 기초에 관한 매우 훌륭한 교과서입니다. 그는 하향식 재귀 하강에 초점을 맞추고 있습니다. lex / yacc 또는 flex / bison보다 훨씬 쉽습니다. 그의 그룹이 작성한 원래 PASCAL 컴파일러는 이러한 방식으로 수행되었습니다.

다른 사람들은 다양한 Dragon 책을 언급했습니다.

코멘트

• 파스칼의 좋은 점 중 하나는 사용하기 전에 모든 것을 정의하거나 선언해야한다는 것입니다. 따라서 한 번에 컴파일 할 수 있습니다. Turbo Pascal 3.0이 그러한 예 중 하나이며 내부에 대한 많은 문서가 여기 에 있습니다.
• PASCAL은 특별히 one- 염두에두고 컴파일 및 링크를 전달하십시오. Wirth ‘의 컴파일러 책은 멀티 패스 컴파일러에 대해 언급하고, 그가 70 번 (예, 70 번) 패스를받은 PL / I 컴파일러를 알고 있다고 덧붙였습니다.
• 필수 선언 사용하기 전에 ALGOL로 거슬러 올라갑니다. Tony Hoare는 ALGOL위원회에서 FORTRAN과 유사한 기본 유형 규칙을 추가 할 것을 제안하려고 할 때 귀를 고정했습니다. 그들은 이로 인해 발생할 수있는 문제에 대해 이미 알고있었습니다. 이름의 오타와 흥미로운 버그를 만드는 기본 규칙은 다음과 같습니다.
• 다음은 원저자가 직접 작성한 책의 더 업데이트되고 완성 된 버전입니다. stack.nl/~marcov/compiler.pdf 답을 수정하고 다음을 추가하세요. 🙂

가상 컴퓨터를 대상으로하지 않고 컴퓨터에서 읽을 수있는 코드 만 작성하려면 Intel 설명서를 읽고 이해해야합니다.

• a. 실행 코드 연결 및로드

• b. COFF 및 PE 형식 (Windows 용), 또는 ELF 형식 (Linux 용) 이해

• c. .COM 파일 형식 이해 (PE보다 쉬움)
• d. 어셈블러 이해
• e. 컴파일러의 컴파일러와 코드 생성 엔진을 이해합니다.

말한 것보다 훨씬 더 어렵습니다. C ++의 컴파일러와 인터프리터를 시작점으로 읽는 것이 좋습니다 (By Ronald Mak). 또는 Crenshaw의 “let build a compiler”도 괜찮습니다.

그렇게하고 싶지 않다면 자신의 VM을 작성하고 해당 VM을 대상으로하는 코드 생성기를 작성할 수도 있습니다.

• 다른 출발점 : http://gnuu.org/2009/09/18/writing-your-own-toy-compiler/
• 훌륭한 예약 Kenneth Louden : http://www.amazon.com/Compiler-Construction-Principles-Kenneth-Louden/dp/0534939724

팁 : Flex와 Bison을 먼저 배우십시오. 그런 다음 자체 컴파일러 / VM을 빌드하십시오.

행운!

댓글

• 나는 LLVM을 대상으로하는 것이 아니라 실제 기계어 코드는 오늘날 사용 가능한 가장 좋은 방법에 관한 것입니다.
• 동의합니다. 저는 LLVM을 지금까지 따라 왔으며 프로그래머의 노력 측면에서 수년 동안 보았던 최고의 것 중 하나라고 말해야합니다. 타게팅하는 데 필요했습니다!
• MIPS는 어떻습니까? spim 을 사용하여 실행 하시겠습니까? 또는 MIX ?
• @MichaelT MIPS를 사용하지 않았지만 좋을 것이라고 확신합니다.
• @PrototypeStark RISC 명령어 세트, 오늘날 여전히 사용중인 실제 프로세서입니다 (임베디드 시스템으로 번역 될 수 있음을 이해). 전체 지침 세트는 wikipedia 에 있습니다. 인터넷을 보면 많은 예제가 있으며 많은 학업 수업에서 기계 언어 프로그래밍의 대상으로 사용됩니다. SO 에 약간의 활동이 있습니다.

실제로 Brainfuck 용 컴파일러를 작성하는 것으로 시작했습니다. 프로그래밍하기에는 상당히 둔한 언어이지만 구현할 8 가지 지침. 가능한 한 간단하고 구문이 잘못된 경우 관련 명령에 대해 동등한 C 명령어가 있습니다.

코멘트

• 하지만 BF 컴파일러가 준비되면 그 안에 코드를 작성해야합니다. (
• @ 500-InternalServerError C 하위 집합 메서드 사용

간단한 컴파일러에 대한 DIY 접근 방식은 다음과 같을 수 있습니다 (적어도 내 uni 프로젝트의 모습).

1. 언어의 문법을 정의합니다. 문맥에 구애받지 않습니다.
2. 문법이 아직 LL (1)이 아니라면 지금하십시오. 일반 CF에서 괜찮아 보이는 일부 규칙에 유의하십시오. 문법이 이상 할 수 있습니다. 언어가 너무 복잡 할 수 있습니다 …
3. 텍스트 스트림을 토큰 (단어, 숫자, 리터럴)으로 잘라내는 Lexer를 작성하십시오.
4. 하향식으로 작성 입력을 수락하거나 거부하는 문법에 대한 재귀 하강 파서
5. 파서에 구문 트리 생성을 추가하십시오.
6. ma 쓰기 구문 트리에서 차인 코드 생성기.
7. 이익 & Beer, 또는 더 똑똑한 파서를 수행하거나 더 나은 코드를 생성하는 방법을 생각할 수 있습니다.

각 단계를 자세히 설명하는 많은 문헌이 있어야합니다.

댓글

• 7 번째 요점은 OP가 요구하는 사항입니다.
• 1-5는 무관하며 그럴 자격이 없습니다. 세심한주의. 6이 가장 흥미로운 부분입니다.안타깝게도 대부분의 책은 악명 높은 드래곤 책 이후에 동일한 패턴을 따르며 구문 분석에 너무 많은주의를 기울이고 코드 변환을 범위를 벗어나게합니다.