[밑바닥부터 만드는 컴퓨팅] 11장 컴파일러 1 : 코드 생성

1. 배경

프로그램은 기본적으로 데이터를 조작하는 연산들의 나열입니다. 그러므로 고수준 프로그램을 저수준 언어로 컴파일할 때는 데이터 번역과 명령 번역이라는 두 가지 주요 문제가 있습니다.

1.1 데이터 번역

프로그램은 정수나 불(boolean)같은 단순한 타입에서, 배열이나 객체 같은 복잡한 타입까지 여러 종류의 변수 타입ㄷ들을 조작합니다. 변수의 생명주기와 범위의 종류도 중요한 요소입니다. 즉, 변수가 지역변수인지 전역변수인지, 인수인지에 ㄸ따라 다르게 처리하는 것이 중요합니다.

컴파일러는 프로그램 안에서 만나는 변수들마다 대상 플랫폼에서 변수 타입이 적절하게 수용되도록 매핑해야 합니다. 추가로 컴파일러는 변수의 종류에 따라 생명 주기와 범위를 관리해야 합니다.

1.1.1 기호 테이블

고수준 프로그램은 다양한 식별자를 도입합니다. 컴파일러는 식별자를 만나면 해당 식별자가 무엇을 나타내는지 알아야 합니다. 해당 식별자가 변수명인지, 글래스명인지, 함수명인지 알아야 하고, 변수라면 객체 필드인지 함수 필드인지, 변수 타입은 무엇인지를 알아야 합니다.

대부분의 컴파일러는 이러한 식별자를 매핑할 수 있는 테이블을 이용하여 관리합니다. 컴파일러는 소스코드에서 처음으로 새로운 식별자가 나타날 때 마다 그 상세 내용을 테이블에 추가합니다. 그리고 식별자가 다른 곳에서 나타나면 테이블을 참조해서 필요한 정보들을 모두 가져옵니다. 아래는 식별자를 저장하는 테이블의 예시입니다.

이름	타입	종류	#
—	—	—	—
nAccounts	int	static	0
id	int	field	0
name	String	field	1
balance	int	field	2
sum	int	argument	0
status	Boolean	local	0

예시로 balance=balancersum 라는 명령문이 있다면 valance가 필드번호 2 이고, sum이 필드번호가 0이라는 정보를 알아내서 계산하게 됩니다.

식별자들은 식별자가 인식되는 영역을 뜻하는 범위(scpoe)를 가집니다. 일반적으로는 바깥쪽 범위에서 안쪽 범위의 정의는 접근할 수 없습니다.

int a = 1
int main() {
  int b = 2;
  {
    int c = 3;
  }
  printf(“a : %d\n”, a);
  printf(“b : %d\n”, b); 
  printf(“c : %d\n”, c);  //error
  return 0;
}

위의 예제 코드는 main 함수에서 안쪽에서 생성된 변수인 c에 접근시 에러가 발생함을 확인할 수 있는 예제입니다. 컴파일러에서는 식별자를 찾을 때 자신의 지역에서 찾고, 없으면 바깥쪽으로 이동하여 찾습니다. 따라서 식별자의 볌위도 테이블에 기록해야 합니다.

1.1.2 변수 처리

컴파일러가 해결해야 할 역할 중 소스코드에 선언된 다양한 타입의 변수를 메모리에 매핑하는 일이 있습니다. 이 작업은 간단하지는 않습니다.

• 변수 타입에 따라 메모리 크기가 다르므로 1:1 매핑이 아님
• 변수 종류에 따라 생애주기가 다름
  • 정적 변수는 프로그램이 종료될때까지 유지됨
  • 객체 인스턴스들은 객체가 소멸될 때 메모리 반환이 되야 함

2단계 컴파일러 아키텍쳐에서는 변수들의 메모리 할당을 VM의 백엔드에서 처리하도록 하였습니다.

1.1.3 배열 처리

배열은 대부분 연속된 메모리 위치에 저장됩니다. 배열 이름은 보통 메모리에 할당된 RAM 블록의 시작 주소를 가리킵니다. 보통 OS에서는 size 만큼의 크기를 갖는 가용 메모리 블록을 찾아서 그 시작 주소를 반환하는 malloc 간은 함수가 있습니다. 만약 arr = new int[10] 과 같은 명령문은 컴파일러에서 arr = alloc(10) 과 같은 저수준 코드로 번역하게 됩니다.

위의 그림은 bar[k] = 19 를 실횅한 직후의 샘플입니다. bar = new int [10]; 를 하여 bar에는 int 배열의 시작주소가 저장됩니다. bar[k] = 19; 를 수행하면 bar 주소로부터 k 만큼 떨어진 주소에 19를 저장하게 됩니다.

1.1.4 객체 처리

어떠한 클래스 Employee 의 객체 인스턴스는 name, salary 와 같은 데이터 항목들과 이를 조작하는 메서드들이 캡슐화되어 있습니다. 컴파일러는 데이터와 연산을 상당히 다르게 처리합니다.

먼저 데이터 처리부터 보겠습니다. 데이터 처리는 배열 처리와 유사하여 객체 인스턴스의 필드들이 연속된 메모리 위치에 저장됩니다. 대부분의 객체 지향 언어에서는 클래스 타입 변수가 선언될 때 컴파일러는 포인터 변수만 할당합니다. 이후 생성자가 호출되어 실제 객체가 생성될 때 저장할 메모리 공간이 할당됩니다. 따라서 컴파일러가 클래스의 생성자를 컴파일할때는 먼저 클래스 필드의 개수와 타입을 보고, 객체 인스턴스를 메모리에 올리기 위한 크기를 계산하여야 합니다.

객체들은 시작 주소를 가리키는 포인터 변수로 표현되며, 객체에 캡슐화된 데이터는 시작 주소에서 시작하는 인덱스를 통해 접근이 가능합니다.

위 그림은 Complex 클래스와 이를 사용하는 함수가 메모리상에 어떻게 나타나는지에 대한 예시입니다.

1.2 명령 번역

해당 절에서는 고수준 명령이 어떻게 대상 언어로 변역되는지에 대해 살펴보려 합니다.

1.2.1 표현식 평가하기

위 그림은 x+g(2, y, -z) * 5 라는 구문을 분석하는 방법입니다. 이와 같은 트리를 파스 트리라 합니다. 코드 생성 알고리즘은 스택기반 플랫폼에서는 열폴란드 표기법으로 알려진 접미사 표기 형식으로 트리를 출력하면 됩니다.

표현식을 스택기반 코드로 번역하는 방법은 파스트리를 재귀적인 후위순회하는 방식으로 구성하면 됩니다.

1.2.2 흐름 제어하기

고수준 프로그래밍 언어는 if, while, for, switch 와 같은 다양한 흐름 제어 구조를 갖추고 있습니다. 반면 저수준 언어는 일반적으로 조건에 따른 goto만을 제공합니다.