LLVM - 코드 생성 흐름

Question

LLVM 문서를 살펴본 결과

일부 용어는 의미가 있습니다.

알고 계시면 의견을 보내주세요.

1. [프론트 엔드] 소스 코드 -> Tokeniser (토큰 스트림) -> 파서 (파서 액션)

   사람이 Tokeniser가 정확히 무엇을합니까 설명 할 수 있습니까? 파서가하는 일은 무엇입니까? 아마도이 사실을 명확하게 할 수있는 예제를 제공 할 수 있습니다.

2. [백엔드] IR -> 최적화 (IR) -> 코드 생성

   나는이 단계에서, 어떤 최적화를 수행해야 해달라고 이해.

다양한 프론트 엔드와 백엔드간에 약간의 차이점이 있습니다. 하지만 내가 묻는 것은 일반적인 경우입니다.

의견을 보내 주셔서 감사합니다.

Answer 1

모든 것은 표준 컴파일러 용어입니다 (Aho, Lam, Sethi, Ullmann : Compilers 참조).

컴파일러에 대한 입력은 일련의 문자를 포함하는 파일입니다. IN

: 토크 나이의 출력은 토큰이 공백을 포함하지 않는 문자의 문자열로 정의 된 토큰의 시퀀스입니다

int main(int argc, char* argv[]) 
{ 

    printf("blimey\n"); 
    // this is a comment 
    return 0; 
} 

(당신은 또한 경우를 추적 할 더 나은 토큰 유형을 디자인 할 수 있습니다 숫자는 실제 또는 정수처럼 보이고, 문자의 시퀀스는 예약어이거나 아닌지 ...). 때로는 언어의 예약어가 고유 식별자 (보통 정수)로 대체됩니다, 숫자를 표현 문자의 순서는 실제 숫자로 변환하는, 그래서 당신은 얻을 수 있습니다 :

OUT :

"int" "main" "(" "int" "argc" "," "char", "*", "argv" "[" "]" "{" 
"printf" "(" "blimey\n" ")" ";" "return" "0" ";" "}" 

공지 사항이 "{"뒤에 나오는 빈 줄은 주석입니다. 구문 분석 트리를 작성하는 데 주석이 필요하지 않습니다. 나는 또한 문자열 "blimey \ n"으로 속이고, 상수 (따옴표) 문자열로 주석을 달 필요가있다. 그건 토크 나이저 였어. 토큰 화/파싱을 분리하는 것은 토큰 화가 파서보다 더 빠른 유한 상태 오토 마톤으로 수행 될 수 있다는 것입니다.

파서는 위의 시퀀스에서 트리를 만듭니다. 구문 분석 할 언어에 대한 문법이 없기 때문에 파서의 출력을 표시하는 것은 어렵습니다.'foo는 + 3 * 바'에 대한

토큰 화 출력 : 그래서 단순한 언어를 가지고

"foo" "+" "3" "*" "bar" 

파서가이를 구축 할 대부분의 산술 식의 언어에 대한 문법은 여러 가지가있을 수 있습니다 나무 :

 + 
    / \ 
"foo" * 
     /\ 
     3 "bar" 

AST : "추상 구문 트리 다를 ... 구문 트리에 표시되지 않습니다, 번역 중요하기 때문에 피상적 구분 형태의 구문 분석 나무에서"(컴파일러, 초 2.5)

"foo + (3 * bar)"표현식을 작성했다고 가정 해보십시오. 괄호가 필요하지 않기 때문에 파서는 여전히 위의 트리를 작성합니다. 그러나 "(foo + 3) * bar"라고 쓰면 다른 나무가 생깁니다 :

 * 
    /\ 
    + "bar" 
/\ 
"foo" 3 

괄호 안 함! 추상 트리 구조는 모든 것을 인코딩합니다. 구현 방식 : 최신 객체 지향 언어로 컴파일러를 작성하는 경우 추상 구문 트리는 클래스 계층 구조로 표시됩니다. C 언어에서는 태그가 붙은 각 노드 유형 (정수형)에 대해 '구조체'가 있습니다.

트리에서 실행 코드 (또는 원하는 코드)를 생성 할 수는 있지만 지루합니다. 따라서 많은 경우 (Pascal의 경우 P 코드, C는 다른 세 개의 주소 코드 중간 표현 ...) 트리가 중간 표현 (IR)으로 변환 (병합)됩니다. 목적은 잘 설계된 IR에서 최적화하는 것이 더 쉽다는 것입니다. 당신이 할 수 있습니다 최적화 수백만이 있습니다

가

use algebraic identities x+0 => x, x*1 => x etc 
drop unused variables 
simplify control flow 
reorder assignments 
... 

시대의 대부분은 IR을 유지 옵티마이 ... 즉, 함수 IR입니다 -> IR,하지만 IR1 번역 영리한 최적화의 몇 가지 있습니다 -> IR2 (표현을 변경), 특정 속성을 명시 적으로 만듭니다 ('benton' 'moggi' 'monad'를 사용하면 검색을 시작할 수 있습니다).