본문 바로가기
Compiler Study

컴파일러 개요

by 별준 2023. 10. 14.

References

  • Engineering a Compiler, 2nd
  • 컴파일러의 이해

Contents

  • Compiler Structure
  • Overview of Translations
    • Front End - Scanner, Parser, IR
    • Optimizers
    • Back End - Instruction Selection, Register Allocation, Instruction Scheduling

Introduction

모든 컴퓨터 응용프로그램(applications)은 기본 하드웨어에서 제공되는 저수준의 추상화 위에 가상 도구(virtual tools)를 빌드하는 소프트웨어 컴퓨터 프로그램에 의존한다. 거의 모든 소프트웨어는 컴파일러(compiler)라고 부르는 도구를 통해서 번역된다. 컴파일러는 단순히 다른 컴퓨터 프로그램을 번역하여 실행을 준비하는 프로그램이다.

 

컴파일러는 한 언어로 작성된 소프트웨어를 다른 언어로 번역하는 도구이다. 한 언어에 대한 텍스트를 다른 언어로 번역하려면 도구가 입력 언어의 형식(form)이나 구문(syntax), 내용(content) 또는 의미(meaning)을 모두 이해해야 한다. 그리고, 출력 언어의 구문과 의미를 제어하는 규칙을 이해해야 한다. 마지막으로 한 언어(source)로부터 다른 언어(target)으로 내용을 매핑하는 체계(scheme)이 필요하다. 일반적인 컴파일러 구조는 이를 따른다.

 

컴파일러에는 source 언어를 처리하기 위한 프론트엔드(Front End)가 있고, target 언어를 처리하기 위한 백엔드(Back End)가 있다. 그리고, 프론트엔드와 백엔드를 연결하면서 두 언어에 거의 독립적인 중간 형태(intermediate form)로 프로그램을 표현하기 위한 형식 구조(formal structure)를 갖는다.

 

예를 들어, 'I am a boy'라는 영어 문장을 한국어로 번역한다고 생각해보자. 우리는 직관적으로 '나는 소년이다'라고 해석할 수 있지만, 컴퓨터는 그렇지 않다. 아마도 몇 단계에 걸쳐서 문장을 분석하고 최종적으로 한국어 문법에 맞게 번역할 것이다. 그 과정을 간단히 요약하면 다음과 같을 수 있다.

  1. 입력 문장이 어떤 요소로 구성되어 있는지 파악. 이 문장에서는 I, am, a, boy라는 네 가지 단어가 사용되었음을 알아낸다. - 어휘 분석(lexical analysis)
  2. I, am, a, boy가 각각 어떤 품사에 속하는지 확인하고, 주어, 동사, 목적어 등으로 구분. 문장의 형식을 검사하여 문장이 주어+동사+보어로 구성되었다는 것을 알아낸다. - 구문 분석(syntax analysis)
  3. 다음으로 단어 대 단어 번역이 아닌 한글 문법에 맞게 번역한다. - 의미 분석(semantic analysis)
  4. 한글 단어 가운데 더 알맞는 단어로 번역하는 최적화 단계를 거친다.
  5. 마지막으로 한글로 번역한다.

컴파일러도 위의 과정과 비슷한 단계를 거쳐서 번역하게 된다.

  1. 먼저 주어진 문장(statement)이 어떤 단어들을 포함하고 있는지 확인하는데, 이러한 의미 있는 단어들을 토큰(token)이라고 부른다. 즉, 프로그래밍 언어를 기계어로 번역하기 위해 첫 번째로 할 일은 언어에서 어떤 토큰이 사용되었는지 구분하는 것이며, 컴파일러에서는 이를 어휘 분석(lexical analysis)라고 부른다.
  2. 다음으로 이러한 단어들이 문장의 구성 요소 가운데 어디에 맞는지 확인한다. 즉, 토큰들이 문법에 맞는지 검사하는데, 컴파일러에서는 이를 구문 분석(syntax analysis)라고 부른다.
  3. 세 번째는 한글의 의미를 검사하는 것과 같은 의미 분석(semantic analysis)를 수행한다.
  4. 그런 다음, 의미 분석으로 생성된 코드의 실행 시간을 줄이거나 메모리를 줄이기 위한 코드 최적화(code optimization)을 수행한다.
  5. 마지막으로 target의 특성을 고려하여 목적 코드(target-machine code)로 번역한다.

Compiler Structure

일반적으로 컴파일러의 구조는 프론트엔드와 백엔드로 나뉜다. 프론트엔드는 타겟과 독립적인 부분으로 이와 관계없이 소스 코드를 분석하고 중간 형태의 코드를 생성한다. 백엔드는 타겟에 의존적인 부분으로 프론트엔드에서 생성한 중간 코드를 특정 머신에 대한 목적 코드로 번역한다. 프론트엔드와 백엔드 사이에서는 중간 코드를 최적화하는 optimizer가 존재하며, 중간 코드는 중간 표현(Intermediate Representation; IR)이라고 부른다.

컴파일러는 처리하는 코드를 표현하기 위해 일부 데이터 구조를 사용하는데, 이를 IR(Intermediate Representation)이라고 한다.

위의 구조를 갖는 전형적인 컴파일러 구조를 조금 더 자세히 살펴보면 아래와 같다. IR을 생성하기 전 단계들을 묶어서 프론트엔드라 부르며,  IR을 입력으로 받는 부분부터 이후 단계를 백엔드라고 부른다.

위 과정에서 볼 수 있듯이 optimizer는 IR-to-IR 트랜스포머이며 IR을 몇 가지 방법으로 향상시킨다. optimizer는 IR을 분석하고 다시 IR을 write하게 되며, 여러 단계의 rewrite 과정이 포함될 수 있다.

 

개념적으로 위와 같은 Front End - Optimizer - Back End의 3-phase 구조는 전형적인 최적화 컴파일러를 보여준다. 실제로 각 단계는 위의 과정과 같이 일련의 패스로 구분된다. 각 phase와 개별 패스는 공통의 인프라를 공유하며, 그림으로 표현하면 다음과 같다.

Overview of Translation

한 프로그래밍 언어로 작성된 코드를 타겟 머신에서 실행가능한 코드로 번역하기 위해 컴파일러는 수 많은 단계를 통해 실행된다. 예를 들어, 아래의 표현식을 실행 가능한 코드 생성하는데 필요한 단계들을 고려해보자. 아래 표현식에서 a, b, c, d는 변수(variables)이며, 왼쪽 방향의 화살표는 할당(assignment)를 의미하고 X는 곱셈에 대한 연산자를 의미한다.

\[ a \leftarrow a \times 2 \times b \times c \times d \]

The Front End

컴파일러는 표현(expression)을 실행 가능한 target-machine 코드로 번역하기 전에 반드시 이 표현의 형태(form) 또는 구문(syntax)와 표현의 의미(meaning or sementics)를 이해해야 한다. 프론트엔드에서는 구문과 의미 관점에서 입력 코드의 형태가 잘 구성되어 있는지 확인한다. 만약 코드가 유효하다고 판단하면 컴파일러의 IR 형태의 코드 표현을 생성한다. 유효하지 않다면 진단 에러 메세지와 함께 유저에게 코드에 문제가 있다고 리포트한다.

 

Checking Syntax

입력의 구문을 체크하기 위해 컴파일러는 프로그램의 구조를 언어의 정의와 비교해야 한다. 이를 위해서 적절한 형식적 정의(formal definition)와 입력이 해당 정의를 충족하는지 여부를 테스트하기 위한 효율적인 메커니즘, 허용되지 않는 입력을 처리하는 방법에 대한 플랜이 필요하다. 수학적으로 source language는 문법(grammer)라고 하는 유한한 규칙에 의해 정의된 문자열(strings)의 집합(일반적으로 무한하다)이다.

 

프론트엔드에서는 스캐너(scanner)와 파서(parser)라고 하는 두 개의 개별 패스가 입력 코드를 검사하여 실제로 문법에 의해 정의된 유효한 프로그램 집합의 구성(subset)인지 여부를 결정한다. 프로그래밍 언어 문법은 일반적으로 systantic category라고 하는 품사(parts of speech)를 기반으로 단어를 나타내는데,  품사에 기초한 문법 규칙을 사용하면 하나의 규칙으로 많은 문장을 설명할 수 있다. 예를 들어, 영어에서는 많은 문장이 다음과 같은 형식을 갖는다.

  • Sentence -> Subject verb Object endmark

여기서 verb와 endmark는 품사이며, Sentence, Subject, Object는 구문 변수(syntectic variables)이다. Sentence(문장)는 이 규칙에 설명된 형식의 모든 문자열을 나타낸다. '->' 심볼은 "derives"를 의미하며 오른쪽(right-hand side; RHS)의 인스턴스가 왼쪽(left-hand side; LHS)의 구문 변수로 추상화될 수 있음을 의미한다.

 

"Compilers are engineered objects"라는 문장을 예시로 살펴보자. 이 문장의 구문을 이해하는 첫 번째 단계는 입력 프로그램에서 고유한 단어를 식별하고 각 단어를 품사로 분류하는 것이다. 컴파일러에서 이 작업은 스캐너(scanner)라는 단계에 속한다. 스캐너는 문자 스트림을 받아서, 이를 분류된 단어의 스트림, 즉, (p, s)의 형태의 쌍으로 변환한다. 여기서 p는 단어의 품사이고, s는 스펠링에 해당한다. 예를 들어, 스캐너는 이 문장을 다음과 같이 분류된 단어의 스트림으로 변환한다.

  • (noun, "Compilers"), (verb, "are"), (adjective, "engineered"), (noun, "objects"), (endmark, ".")

다음 단계에서 컴파일러는 분류된 단어의 스트림을 입력 언어의 구문으로 지정하는 규칙과 일치시키려고 한다. 예를 들어, 영어에는 다음과 같은 규칙이 포함된다.

  1. Sentence -> Subject verb Object endmark
  2. Subject -> noun
  3. Subject -> Modifier noun
  4. Object -> noun
  5. Object -> Modifier noun
  6. Modifier -> adjective
  7. ...

구문 변수 Sentence로부터 파생이 시작되어 각 단계에서 prototype sentence의 용어 하나를 다시 작성하여 용어를 해당 규칙에서 파생될 수 있는 RHS 용어로 바꾼다.

"Compilers are engineered objects"라는 문장은 위의 규칙 1부터 6까지 설명된 언어(language)에 속하며, 이 규칙으로 이 문장이 유효하다는 것을 확인할 수 있다. 즉, 이 문장은 문법적으로 정확하다는 것이다. 이렇게 파생어를 찾는 프로세스를 파싱(parsing)이라고 부른다.

 

문법적으로 올바르지만 의미가 없는 문장일 수도 있다. 예를 들어, "Rocks are green grass"라는 문장은 위의 "Compilers are engineered objects"와 동일한 품사를 갖지만 의미는 이상하다. 이 두 문장의 차이를 이해하려면 software system, rocks, vegetables에 대한 문맥적 지식이 필요하다.

 

컴파일러가 프로그래밍 언어를 추론하는데 사용하는 의미 모델(semantic models)은 자연어를 이해하는 데 필요한 모델보다 간단하다. 컴파일러는 프로그램에서 특정 종류의 불일치를 탐지하는 수학적 모델을 구축하며, 타입의 일관성을 확인한다. 예를 들어, \(a \leftarrow a \times 2 \times b \times c \times d\) 표현식은 문법적으로 올바른 형태일 수 있지만, b와 d가 문자열인 경우에는 해당 문장이 유효하지 않을 수 있다.

 

컴파일러는 특정 상황에서 숫자의 일관성도 확인한다. 예를 들어, 배열 참조는 배열이 선언된 랭크와 동일한 수의 차원을 가져야 하고, 함수 호출은 함수 정의에서와 동일한 수의 인수를 지정해야 한다.

Intermediate Representations

컴파일러의 프론트엔드에서 마지막으로 처리되는 것은 IR 형태의 코드를 생성하는 것이다. 컴파일러는 소스 언어, 타겟 언어, 그리고 컴파일러가 적용하는 특정 변환에 따라 다양한 종류의 IR을 사용한다. 일부 IR은 프로그램을 그래프로 표현한다. 아래 코드는  \(a \leftarrow a \times 2 \times b \times c \times d\) 표현식이 low-level IR에서 어떻게 표현되는지를 보여준다.

모든 소스 언어 구성에서 컴파일러는 이를 어떻게 IR 형태로 구현할 지에 대한 전략이 필요하다. 이 선택에 따라서 코드를 변환하고 개선하는 컴파일러의 능력이 달라질 수 있다.

The Optimizer

프론트엔드가 입력 프로그램을 IR로 추출할 때, 프론트엔드는 코드를 만난 순서대로 한 번에 하나씩 처리한다. 따라서, 초기 IR에는 모든 주변 문맥에서 잘 동작하는 일반적인 구현(general implementation) 전략이 포함되어 있다. 런타임에서 코드는 더 제한적이고 예측 가능한 문맥에서 실행된다. Optimizer는 코드의 IR 형태를 분석하여 해당 문맥에 대한 사실들을 발견하고 해당 문맥적 정보 또는 지식을 사용하여 코드를 다시 작성한다. 따라서 더 효율적인 방식으로 동일한 답을 계산하게 된다.

 

더 효율적이다라는 것은 많은 의미를 가질 수 있는데, 일반적으로 어플리케이션의 실행 시간을 줄이는 것이 이에 해당한다. 또 다른 경우에서는 컴파일된 코드의 크기일 수도 있고, 프로세서가 코드를 처리하는데 소비하는 에너지와 같은 속성일 수도 있다. 예를 들어, 아래 코드를 살펴보자.

(a)의 코드를 살펴보면 루프 내에서 a와 d만 변경되며, 2, b, c의 값은 루프 내에서 변하지 않는다. Optimizer가 이 사실을 발견하면 최적화하여 (b)의 코드로 다시 작성할 수 있다.

 

대부분의 최적화는 분석(analysis)와 변환(transformation)으로 구성된다.

Analysis

분석은 컴파일러가 안전하고 효율을 증가시키도록 최적화 기법을 적용할 수 있는 위치를 결정한다. 컴파일러는 여러 종류의 분석을 통해 변환을 서포트한다. 이 포스팅에서는 간단히 이러한 분석에 Data-flow analysis와 Dependence analysis가 있다는 것만 언급하고 넘어간다.

Transformation

코드를 개선하려면 코드르 분석하는 것 이상이 필요하다. 즉, 컴파일러는 분석 결과를 이용하여 코드를 보다 효율적인 형태로 다시 작성해야 한다. 코드의 실행 시간 및 공간의 요구 사항을 개선하기 위해 수 많은 transformation이 개발되었다. 예를 들어, loop-invariant computations를 발견하고 이를 덜 자주 실행되는 위치로 이동하는 작업은 프로그램의 실행 시간을 향상시킨다. 코드를 더 간결하게 만드는 것도 있다. 이에 대한 내용은 매우 방대하며, 하나의 주제로 하나 이상의 별도의 책으로 작성할 수 있을 정도로 그 내용이 크고 깊다.

The Back End

컴파일러의 백엔드는 IR 형태의 코드를 탐색하고 타겟 시스템에 대한 코드를 생성한다. 백엔드는 각 IR 연산을 구현하는 타겟 머신의 연산을 선택하고, 이 연산이 효율적으로 실행되는 순서를 선택한다. 또한, 레지스터에 상주할 값과 메모리에 상주할 값을 결정하고 이에 대한 코드를 삽입한다. 백엔드에는 아래와 같은 처리 단계들이 있다.

  • Instruction Selection: 각 IR 연산을 하나 이상의 타겟 머신 연산으로 매핑
  • Register Allocation: Instruction Selection 단계에서는 타겟에서 제한된 레지스터가 있다는 사실을 무시하고 작성된다. Register Allocator는 가상의 레지스터를 실제 머신의 레지스터에 매핑한다. 이 과정에서 레지스터의 사용을 최소화할 수 있도록 코드가 재작성된다.
  • Instruction Scheduling: 더 빠르게 실행되는 코드를 생성하기 위해 타겟 머신의 특성 성능 제약을 반영하도록 작업 순서를 변경할 수 있다. 이 변경이 해당 단계에서 수행된다.
  • Interactions Among Code-Generation Components

 

댓글

​

티스토리툴바