Skip to content

Latest commit

 

History

History
253 lines (190 loc) · 17.7 KB

Compiler.md

File metadata and controls

253 lines (190 loc) · 17.7 KB

Compiler

  • 컴파일러의 정의
  • 컴파일 과정
    • 구문 분석 단계
    • 최적화 단계
    • 코드 생성 단계
    • 링킹 단계
  • 결론

컴파일러의 정의


  • 컴파일러는 특정 프로그래밍 언어로 쓰여 있는 문서를 다른 프로그래밍 언어로 옮기는 언어 번역 프로그램을 의미한다.

  • 본래의 문서를 소스 코드 또는 원시 코드라고 부르고, 출력된 문서를 목적 코드라고 한다.

    목적 코드는 주로 다른 프로그램이나 하드웨어가 처리하기에 용이한 형태로 출력되지만, 문서 파일이나, 그림 파일 등으로 옮기는 경우도 있다.

  • 원시 코드에서 목적 코드로 옮기는 과정을 컴파일이라고 한다.

우리가 컴파일러를 이해하려면, 과거의 역사로 돌아가야한다. 초기 컴퓨터 프로그램들은 어셈블리어로 작성되었는데, CPU 아키텍처가 서로 달라, 똑같은 프로그램을 서로 다른 어셈블리어로 작성하는 비용이 커지면서, 고급 프로그래밍 언어의 필요성이 대두되었다.

intel과 AMD의 예시로 들어보면, 서로의 아키텍처가 다르기에 같은 프로그램이더라도, 다시 어셈블리어로 처리해야되는 불상사가 생기는 것이다.

 컴퓨터 구조에 따라, 사용하는 기계어가 달라진다. 즉 컴퓨터 CPU마다 지원하는 오퍼레이션 타입과 개수는 모두 다르며, 
 레스터의 크기와 개수, 저장된 데이터 형의 표현도 각기 다르다.
 모든  범용 컴퓨터는 기본적으로 동일한 기능을 수행하지만, 기능을 어떤 과정을 거쳐 수행할지는 다르다.

 왜 다를까?
 제조사가 설계한 특정 CPU 아키텍처의 명령 집합은 기계어로 작성된 명령어들의 집합을 의미한다.
 각 명령어는 특정 연산을 수행하도록 설계되어있다.
 어셈블리어는 기계어 명령어에 대응하는 니모닉 이라고하는 읽기 쉬운 문자열이 사용된다.
 (ADD 니모닉은 덧셈 연산을 의미하는 것과 같다.)

 하나의 기계어 명령어에 대해, 여러 가지 표현 방식이나 니모닉이 있을 수 있을 수 있으며, 
 어셈블리어 명령어의 구조나 문법을 의미하는 통사론이 제조사나 컴파일러에서 다른 문법을 사용할 수 있다.

이에 다양한 아키텍처에서 실행이 가능한 C언어가 생기게 되었고, 컴파일러를 통해 해당 CPU 아키텍처에 맞게 기계어로 번역을 할 수 있게 되었다.


컴파일 과정


하나의 프로그램을 완성하고나서, 일반적인 컴파일러는 다음과 같은 과정을 거친다.


구문 분석 단계

  • 구문 분석 (parsing) : 소스 코드 또는 원시 코드를 읽어, 개별 문법요소(연산자, 괄호, 식별자 등) 단위로 자른후 이 문법요소를 해석하여 추상 구문 트리를 생성한다. 이 과정에서, 문법에 맞지 않는 소스코드는 사용자에게 알려준다.
  • 목적 : 소스 코드를 읽고 문법적 구조를 파악하기 위함.
  • 결과 : 추상 구문 트리를 만들고, 문법 오류가 있을 때 사용자에게 알려주기위함
    • 어휘 분석 ( Lexical Analysis | Tokenizer ) : 소스 코드를 개별 문법요소(토큰)으로 분해하는 과정
      • 목적 : 소스 코드를 읽어 개별 문자들을 더 큰 의미 단위인 토큰으로 묶는다.
      • 토큰 : 연산자, 식별자, 리터럴, 특수 문자(구분자) 등을 의미한다.
     예시 : int main (){ int a; } 일 경우, 'int', 'main', '(', ')', '{', 'int', 'a', ';', '}' 로 구성이 되며
     각 토큰은 의미를 부여한다.
        int : 키워드
        main : 식별자
        (    : 특수 문자
        )    : 특수 문자
        {    : 특수 문자
        int  : 키워드
        a    : 식별자
        ;    : 특수 문자
        }    : 특수 문자

        어휘 분석은 입력 전처리, 토큰화, 토큰 분류, 토큰의 유효성 검증, 출력 생성 과정을 거친다.
        입력 전처리 : 입력 텍스트를 정리하고, 어휘 분석 준비를 한다. 이 과정에서 주석, 공백 등 중요하지 않은 문자를 제거한다.
        토큰화 : 입력 텍스트를 일련의 토큰으로 나누고, 다양한 유형의 토큰을 정의하는 패턴이나 정규 표현식 세트(Lexeme)에 대해 입력 텍스트의 문자를 일치시키며 수행된다.
        토큰 분류 : 키워드, 식별자, 연산자, 특수 문자 등으로 토큰의 유형을 분류한다.
        토큰 유효성 검사 : 프로그래밍 언어에 맞춰, 각 토큰이 유효한지 확인한다.
        출력 생성 : 어휘 분석을 끝 맞치고, 토큰의 목록을 다음 단계로 넘기 위한 단계이다.
  • 문법 요소들을 해석해, 추상 구문 트리를 생성한다.
    • 실제 구문에서 나타나는 모든 세세한 정보를 나타내지 않으며, 그룹핑을 위한 괄호의 경우, 트리 구조를 가지며, 분리된 노드로는 표현하지 않는다.
    • 컴파일러에서 사용되는 자료 구조로, 프로그램 코드의 구조를 표현할 수 있다. 일반적으로 구문 분석 단계의 결과물이다.
    • AST에서 소스 코드의 각 구성 요소의 위치를 저장하고, 컴파일러가 어떤 메시지를 출력할 때, 사용할 수 있다.
    • 일반적으로는 구문 분석 단계에서 파스 트리를 먼저 생성한 뒤, 추상 구문 트리로 벼환한다.
    • 파스 트리는 소스 코드의 구체적인 문법적 구조를 표현하며, 언어의 모든 문법 규칙과 세부 사항을 반영한다.
    • 추상 구문 트리는 파스 트리를 바탕으로 문법적인 세부 사항과 중복된 정보가 제거되고, 프로그램의 논리적 구조와 의미만을 가진 트리 구조를 만든다.

image

사진 출처 : 추상구문트리

  • 어휘 분석 참고
    • 어휘 분석에서 패턴들은 정규 문법에 의해 서술이 된다. C의 경우는 다음과 같은 패턴을 가진다. 일부만
      • ;
      • <return_type> <function_name>(<parameter_list>)
      • if () [else ]
      • for (; ; )
      • -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
      • -> a | b | c | ... | z | A | B | C | ... | Z
    • 토큰을 표현할 때에는 효율적으로 구문 분석을 위해, 토큰을 토큰 번호와 토큰 값의 순서 쌍으로 표현한다.
      • 토큰 번호 : 각각의 토큰들을 구분하기 위해서 각각의 토큰들에게 고유의 내부번호를 부여한 정수코드
      • 토큰 값 : 토큰 중에 식별자나 상수는 하나의 이름으로 여러 번 사용될 수 있으므로 다르게 표현하는게 아닌, 프로그래머가 사용한 값으로 구별하기 위한 값
        • 식별자나 상수의 토큰 값은 포인터의 값을 가진다.
    • 유한 오토마타
      • 유한한 수의 상태와 전이 규칙으로 구성되며, 입력 문자열을 처리하면서 상태를 전이한다.
        • 상태 : S0, S1, S2, S3, S4, S5
        • 입력 알파벳 : f, o, r, 나머지 문자
        • 시작 상태 : S0
        • 종료 상태 : S3
        • 상태 전이 규칙에 따라, 이동한다.
          • S0에서 i를 만나면, S1으로, f를 만나면, S3으로 이동
          • S3에서, o를 만나면 S4로 이동
          • S4에서 r을 만나면 S5로 이동
          • 이후 공백이나 구분자를 만나면 키워드를 인식한다.
      • 결정적 유한 오토마타 (DFA)
        • 각 상태에서 특정 입력에 대해 오직 하나의 전이가 가능하며, 현재 상태와 입력 문자가 주어지면 다음 상태가 정확히 하나로 결정되는 것이다.
        • 하나의 오토마타처럼 작동한다.
        • 규칙이 엄격하며, 구성하기가 어렵다.
        • 입력 문자열을 읽는 데 시간이 적게 소모된다.
      • 비결정적 유한 오토마타 (NFA)
        • 특정 상태에서 같은 입력에 대해 여러 개의 가능한 전이가 존재한다. 같은 입력에대해 다음 상태가 여러 개일 수 있어, 비결정적이다.
        • 동시에 작동하는 여러 개의 작은 오토마타처럼 작동한다.
        • 구성하기가 더 쉽다.
        • 입력 문자열을 읽을 때 필요한 시간이 DFA보다 더 오래걸린다.

      image 사진 출처 : t4tutorials

      • NFA와 DFA는 변환 알고리즘을 통해, 각각의 장점을 모두 사용한다.
        • NFA는 복잡한 패턴을 간결하게 표현하고, DFA는 실행 시간을 줄인다. 즉 NFA를 수행해서 전체 Area를 줄인 뒤 DFA를 통해 수행시간을 줄이는 것이 일반적인 처리한다.
        • NFA에서 DFA로 부분집합 구성 알고리즘을 통해, NFA의 각 상태를 DFA의 상태로 변환한다. NFA의 각 상태는 입력 심볼에 따라 여러 다음 상태를 가질 수 있고, 이런 상태의 집합을 하나의 DFA 상태로 취급한다.
        • 시작 상태를 찾고 상태를 탐색하며 새로운 상태를 생성하고 반복한 뒤 종료 상태를 설정한다.
        • 입실론 클로저를 계산하여, DFA 상태를 형성한다. (입실론 클로저로 만들어진 NFA 집합은 하나의 DFA의 상태이다.)
          • 입실론 클로저는 특정 상태에서 시작해, 람다 전이만을 사용해 도달할 수 있는 모든 상태의 집합을 나타낸다.

최적화 단계


  • 추상 구문 트리의 입력을 받아 의미 검사를 행한다. 컴파일러에 따라 독립된 의미 분석 단계를 가지며, 형검사, 변수의 선언 및 정의 확인 등을 진행한다.
  • 묵시적 타입에서 명시적 타입으로 변화한다.
  • 이후 생성된 중간 코드를 분석해, 효율을 높이는 변환(최적화)을 수행한다.
    • 핍홀 최적화 : 코드의 작은 부분을 대상으로 불필요한 명령어를 제거하거나, 더 효율적인 명령어로 바꾸는 최적화다. 연속된 산술 연산을 단일 연산으로 병합하거나 불필요한 레지스터 이동을 제거한다.
      • 중복 명령어 제거
      • 제어 흐름 최적화
      • 도달 불가능한 코드 제거
      • 비용 낮은 연산자로 변환
    • 지역 최적화 : 함수나 블록 내 코드를 대상으로 수행되는 최적화이다. 변수의 상수 전파, 공통 하위 표현식 제거가 해당된다.
      • 지역 공통 부분식 제거
      • 복사 전파
      • 상수 폴딩
    • 루프 최적화 : 반복문을 대상으로 수행되는 최적화로 루프 내 계산을 최소화하기 위한 변환을 수행한다. 루프 회전, 루프 병합 등이 있다.
    • 전역 최적화 : 전체 프로그램을 대상으로 수행되는 최적화로, 더 넓은 범위의 정보를 활용해 최적화를 수행한다. 사용하지 않는 함수를 제거하거나, 전역 변수의 할당을 최적화하거나, 프로시저 인라인화등이 존재한다.
      • 전역 공통 부분식 제거

코드 생성 단계


  • 매크로 처리기와 어셈블러의 결합 형태로 처리가 되며, 최적화된 중간 코드를 기계어로 변환하는 마지막 단계이다.

    • 매크로 처리기는 소스 코드 내의 매크로를 처리하고 확장한다.
    • 최적화된 중간 코드가 어셈블리어로 변환되며, 어셈블러는 이를 기계어로 변환한다.
    • 하드웨어 아키텍처에 맞는 기계어로 변환하는 마지막 단계이다.

  • 목적 코드 생성기

    • 명령어 선택, 명령어 스케줄링, 레지스터 할당과 배정이 가장 중요한 요소이다.
    • 명령어 선택 : 목적 기계에 따라 적절한 명령을 선택 (다양한 명령어가 존재)
    • 레지스터 할당과 배정 : 프로그램의 각 명령어가 어느 레지스터에 저장되어야 하는지 결정하는 것 (메모리보다 레지스터를 사용하면, 연산 속도가 빠르므로, 연산에 레지스터를 많이 사용해야함)
    • 명령어 스케줄링 : 명령어들의 실행을 어떤 순서로 나열할지 결정하는 것 (연산 순서에 따라 레지스터의 개수나, 메모리 요구량이 달라짐)

  • 목적 코드를 생성한다. 이후 실행파일을 만들기 위해 링킹 단계로 전달된다.

  • 목적 컴퓨터

    • 목적 컴퓨터는 n개의 범용 레지스터를 가진 바이트 주소 가능 기계로 컴파일러가 최종적으로 생성한 기계어 코드를 실행할 컴퓨터나 컴퓨터 계열이다.

링킹 단계


  • 링킹 : "목적 코드가 기계어일 경우, 여러 라이브러리 목적 코드를 묶어 하나의 실행 파일을 생성하게 된다. 이 과정은 링커에 의해 수행되며, 어떤 사람들은 링커를 컴파일러의 일부로 간주하지 않기도 한다."

  • 링커 : 컴파일러가 만들어낸 하나 이상의 목적 파일을 가져와 이를 단일 실행 프로그램으로 병합하는 프로그램이다.

    • 유닉스 계열 운영체제에서는 로더를 링커의 동의어로 사용한다.
    • 라이브러리 또는 럼타임 라이브러리라고 하는 모음에서 오브젝트들을 취할 수 있다.
    • 대부분의 링커들은 전체 라이브러리를 출력 파일에 포함시키지 않는다. 그대신 다른 오브젝트 파일 혹은 라이브러리가 참조하는 파일들만을 포함한다.
    • 프로그램의 주소 공간 안의 오브젝트들을 배열하는 일도 하며, 코드를 재배치한다.

  • 정적 링킹과 동적 링킹

    • 정적 링킹 : 실행 파일을 생성할 때, 라이브러리를 같이 포함시켜서 .exe파일을 생성하는 걸 의미한다.
      • 정적 라이브러리를 사용하여 컴파일을 하면, 링커가 프로그램이 필요로 하는 부분을 라이브러리에 찾아 실행파일에다가 바로 복사한다.
      • 실행파일에 다 들어가기 때문에, 라이브러리가 필요없고, 컴파일도 되어있어서 시간도 오래되지 않지만, 실행 파일 내에 라이브러리 코드가 저장도기 때문에 메모리를 많이 사용한다.
      • 이런 단점을 해결하고자 동적 링킹이 생성되었다. image
    • 동적 링킹 : 정적 링킹의 단점인 메모리를 줄이기 위해, 많이 사용하는 라이브러리는 메모리에 1개만을 올리는 것이다.
      • 동적 링크 라이브러리를 DLL이라 한다.
      • 메모리의 요구사항이 적어졌지만, 라이브러리가 저장되어있는 주소로 점프를 해야하기 때문에, 오버헤드가 발생한다.

결론


  • 컴파일러는 프로그래머가 작성한 고수준 언어의 소스 코드를 하드웨어가 이해할 수 있는 기계어로 변환하는 과정을 수행한다. 여러 단계로 구성되며, 각 단계는 특정한 목적과 역할을 가진다.
    • 구문 분석 단계: 소스 코드는 먼저 토큰화되어 각 기호와 단어를 의미 있는 요소로 분해한다. 그 후 구문 분석이 이루어져 추상 구문 트리(AST) 또는 중간 표현을 생성한다. 이 단계에서의 주요 과정은 다음과 같다:
      • 렉시컬 분석: 소스 코드를 토큰으로 분리하며, 공백, 주석 등을 제거한다.
      • 구문 분석: 토큰을 사용하여 문법에 따라 추상 구문 트리나 기타 중간 표현을 생성한다.
      • 의미 분석: 추상 구문 트리의 노드를 검사하여 변수의 선언 및 정의 검증과 형검사를 수행한다. 또한 타입 캐스팅, 상수 폴딩, 타입 호환성 검사 등도 수행된다.
      • 심볼 테이블 생성: 프로그램의 모든 심볼(변수, 함수, 클래스 등)에 대한 정보를 추출하여 저장한다. 이는 후속 단계에서 코드 생성과 최적화를 돕는다.
    • 최적화 단계: 중간 코드에 대해 다양한 최적화 기술을 적용하여 실행 효율을 높인다. 이 단계에는 핍홀 최적화, 지역 최적화, 루프 최적화, 전역 최적화 등이 포함된다.
    • 코드 생성 단계: 최적화된 중간 코드를 기계어로 변환한다. 매크로 처리, 명령어 선택, 레지스터 할당 및 배정, 명령어 스케줄링 등의 작업이 이루어진다.
    • 링킹 단계: 목적 파일과 라이브러리를 결합하여 실행 가능한 프로그램을 생성한다. 정적 링킹과 동적 링킹 중 선택하여 메모리 사용과 성능을 균형 있게 관리한다.
  • 마지막으로, 프로그램의 효율, 실행 속도, 메모리 사용량 등에 영향을 미치며, 최적화 기술과 링킹을 적절하게 선택하면 프로그램의 성능을 향상시킬 수 있다.

출처


parser, 파서에 대한 이해, 컴파일러, 유한 오토마타, DFA,NFA, 컴파일러 최적화, 어셈블리 프로그래밍, 최고