심볼 테이블

심볼 테이블은 프로그램에 나오는 이름과 그 이름에 딸린 정보를 짝지어 담아 둡니다. 이를테면 total 이라는 이름 옆에 그것이 정수 변수라는 사실을 적어 둡니다. 컴파일러도 링커도 이름을 만나면 이 표를 뒤져 그것이 무엇인지 확인합니다. 이름을 모아 둔 표가 없으면 사람이 이름으로 쓴 코드를 기계가 쓸 주소로 바꿀 수 없습니다.

상세

심볼 테이블이 한 줄에 무엇을 담는지부터 봅니다. 그다음 그 표가 파일에 실려 링커에게 넘어가는 데까지 따라갑니다.

전화번호부 비유

회사 전화번호부를 떠올리면 됩니다. 이름 옆에 부서와 내선 번호가 적혀 있어서, 사람 이름만 알면 어디로 걸어야 하는지 바로 압니다. 번호부가 없으면 이름을 알아도 연결할 방법이 없습니다.

표 한 줄에 담기는 것

프로그램에 나오는 이름을 심볼이라고 부릅니다. 변수 이름도 함수 이름도 타입 이름도 모두 심볼입니다. 사람이 소스에 직접 적은 이름이라는 뜻에서 식별자라고도 부릅니다.

심볼 테이블은 심볼 하나를 한 줄로 담습니다. 이름만 담는 것이 아니라, 그 이름을 다룰 때 필요한 정보를 같은 줄에 붙여 둡니다. 아래가 한 줄에 흔히 들어가는 것들입니다.

다섯 가운데 「위치」만 뒤늦게 채워집니다. 나머지는 소스에 적힌 것을 읽으면 바로 알지만, 주소는 코드를 다 만들어 봐야 정해지기 때문입니다.

컴파일러가 표를 채우는 순서

표를 채우는 일은 앞선 두 단계가 끝난 뒤에 이어집니다. 어휘 분석이 소스를 낱말 단위로 쪼갭니다. 구문 분석이 그 낱말들을 문법에 맞게 나무 모양으로 엮습니다. 심볼 테이블은 그 나무를 훑으며 채워집니다.

채워진 표는 뒤 단계가 받아 씁니다. 이어지는 타입 검사가 이 표를 읽어 대입과 호출이 맞는지 봅니다.

컴파일러는 소스를 앞에서부터 읽어 갑니다. 이름을 선언한 줄을 만나면 표에 새 줄을 넣습니다. 이미 선언된 이름을 쓴 줄을 만나면 표를 뒤져 그 줄을 꺼냅니다.

int total;        // 표에 total 을 넣는다
void add(int n) { // 표에 add · n 을 넣는다
  total += n;     // 표에서 total 을 찾는다
}

넣는 쪽과 찾는 쪽이 같은 표입니다. 그래서 total 을 선언하지 않고 쓰면 찾기가 빈손으로 돌아옵니다. 컴파일러는 「선언되지 않은 이름」이라는 오류를 냅니다. 사람이 오타를 내면 대개 이 대목에서 걸립니다.

한 줄을 읽을 때마다 갈림이 두 번 생깁니다.

flowchart TD
    A["소스의 한 줄을 읽는다"] --> B{"선언인가 사용인가"}
    B -->|"선언"| C["표에 새 줄을 넣는다"]
    B -->|"사용"| D["표를 뒤진다"]
    D --> E{"찾았나"}
    E -->|"찾았다"| F["딸린 정보를 꺼낸다"]
    E -->|"못 찾았다"| G["「선언되지 않은 이름」 오류"]

같은 이름이 범위마다 다를 때

스코프는 한 이름이 통하는 범위입니다. 함수 안에서 선언한 n 은 그 함수 안에서만 통합니다. 다른 함수의 n 과는 남남입니다. 이름이 같아도 가리키는 것이 다르므로 표 한 장에 뭉뚱그려 담을 수 없습니다.

그래서 범위마다 표를 하나씩 두고 안쪽 것을 위에 쌓습니다. 이름을 찾을 때는 가장 안쪽 표부터 봅니다. 없으면 한 겹 바깥 표로 나갑니다. 맨 바깥까지 나갔는데도 없으면 선언되지 않은 이름입니다.

범위는 함수 안에서 한 겹 더 깊어지기도 합니다. 함수 안의 블록에서 선언한 tmp 는 그 블록만의 표에 들어갑니다.

flowchart TD
    subgraph 전역["전역 범위"]
        G["total · add"]
        subgraph 함수["함수 add 의 범위"]
            F["n"]
            subgraph 블록["함수 안 블록의 범위"]
                B["tmp"]
            end
        end
    end
    B -->|"없으면 바깥으로"| F
    F -->|"없으면 바깥으로"| G

안쪽부터 보기 때문에 안쪽 이름이 바깥 이름을 가립니다. 함수 안에 total 이라는 변수를 새로 선언하면 그 함수 안에서는 바깥의 total 이 안 보입니다.

범위를 빠져나가면 그 범위의 표는 버립니다. 그래서 함수 안에서만 쓰는 지역 변수는 함수가 끝나면 이름도 사라집니다. 반대로 전역 변수는 전역 표에 남아 파일 끝까지 통합니다.

컴파일이 끝난 뒤 파일에 남는 표

컴파일러는 소스 하나를 목적 파일 하나로 옮깁니다. 목적 파일은 기계어로 옮겨졌지만 아직 혼자서는 못 도는 중간 결과물입니다.

이 파일에 표 전부를 적어 두지는 않습니다. 함수 안에서만 살다 사라진 이름은 다른 파일이 알 필요가 없기 때문입니다. 그래서 파일 밖과 주고받는 이름만 골라 남깁니다.

남는 이름은 두 갈래입니다. 이 파일이 만들어 내놓는 이름과, 이 파일이 쓰기만 하고 만들지는 않은 이름입니다.

아래쪽 갈래를 미정의 심볼이라고 부릅니다. 컴파일러는 이것을 오류로 보지 않고 표시만 남긴 채 넘깁니다. 그 이름을 어느 파일이 갖고 있는지는 컴파일러가 알 수 없고, 파일을 다 모아 본 다음에야 알 수 있기 때문입니다.

표에 적히는 이름이 소스에 적은 이름과 늘 같지는 않습니다. 이름을 그대로 적지 못하는 언어도 있습니다. C++ 처럼 같은 이름의 함수를 매개변수만 바꿔 여럿 둘 수 있는 언어는 이름 하나로 어느 것인지 가릴 수 없습니다.

그래서 컴파일러가 매개변수 정보까지 섞어 새 이름을 지어 표에 넣습니다. 이 일을 이름 맹글링이라고 부릅니다.

링커의 표 맞추기

링커는 목적 파일 여럿을 이어 붙여 실행 파일 하나로 만듭니다. 이때 하는 일의 절반이 표 맞추기입니다. 한 파일이 「못 찾았다」고 적어 둔 이름을, 그 이름을 정의한 파일의 표에서 찾아냅니다.

flowchart TD
    A["목적 파일 A"] --> T1["심볼 테이블 · add 를 못 찾았다"]
    B["목적 파일 B"] --> T2["심볼 테이블 · add 를 정의했다"]
    T1 --> L["링커가 두 표를 맞춰 본다"]
    T2 --> L
    L --> R["add 를 부른 곳에 주소를 채운다"]

짝이 맞으면 링커는 그 이름에 최종 주소를 정해 줍니다. 그러고 나서 그 이름을 쓴 코드 조각마다 주소를 하나씩 채워 넣습니다. 이 채워 넣는 일을 재배치라고 부릅니다.

표를 언제 맞추느냐로 갈래가 둘 있습니다. 정적 링크는 프로그램을 만들 때 다 맞춰 둡니다. 동적 링크는 일부를 남겨 뒀다가 프로그램을 띄우는 순간에 맞춥니다.

동적 링크를 쓰면 심볼 테이블이 완성된 파일 안에 그대로 실려 다녀야 합니다. 띄우는 순간에 이름으로 찾아야 하기 때문입니다.

이름을 못 찾거나 두 번 찾을 때

표 맞추기는 두 가지로 어긋납니다. 둘 다 빌드가 거의 끝난 대목에서 터집니다. 소스의 어느 줄이 잘못됐는지 바로 짚어 주지 않아 사람을 오래 붙잡습니다.

이름을 아무 파일에서도 못 찾으면 링커가 멈춥니다. 함수를 선언만 해 두고 본문을 안 썼거나, 그 함수가 든 라이브러리를 빌드에 안 넣었을 때 납니다.

같은 이름을 두 파일이 정의하면 링커는 어느 쪽을 쓸지 고를 수 없어 역시 멈춥니다. 이쪽은 중복 심볼이라고 부릅니다. 여러 소스가 함께 #include 하는 헤더 파일에 전역 변수를 정의해 두면 소스마다 정의가 하나씩 생겨 이 일이 납니다.

어긋나는 두 가지는 정의를 몇 개 찾았느냐로 갈립니다.

flowchart TD
    A["이름 하나의 정의를 찾는다"] --> B{"몇 개 찾았나"}
    B -->|"0개"| C["미정의 심볼 · 링커가 멈춘다"]
    B -->|"1개"| D["주소를 정하고 재배치한다"]
    B -->|"2개 이상"| E["중복 심볼 · 링커가 멈춘다"]

표를 뒤지는 데 드는 시간

컴파일러는 이름 하나를 수없이 찾습니다. 소스에 이름이 나올 때마다 표를 뒤지므로, 찾기가 더디면 컴파일 전체가 더뎌집니다. 그래서 심볼 테이블은 대개 해시테이블로 만듭니다.

해시테이블은 표를 여러 칸으로 나눕니다. 이름마다 들어갈 칸을 계산해서 정합니다. 이 칸 하나를 버킷이라고 부릅니다. 한 칸에 이름이 둘 이상 몰리면 그 칸에 사슬처럼 이어 답니다.

flowchart TD
    subgraph 버킷배열["버킷 배열"]
        K0["0번 칸"]
        K1["1번 칸"]
        K2["2번 칸"]
    end
    K0 --> N1["total"]
    N1 --> N2["add"]
    K1 --> N3["비어 있다"]
    K2 --> N4["n"]

보통은 한 칸에 하나라 이름을 바로 꺼냅니다. 한 칸에 몰리면 사슬을 끝까지 따라가야 합니다.

해시테이블로 만들면 이름 하나를 찾는 데 드는 시간이 표에 담긴 이름 수와 거의 무관합니다. 담긴 이름이 백 개든 십만 개든 비슷합니다. 이것을 빅오 표기법으로 평균 O(1) 이라고 적습니다. O(1) 은 데이터가 늘어도 걸리는 시간이 거의 그대로라는 뜻입니다.

모든 이름이 한 칸으로 몰리는 최악에는 담긴 이름 수에 비례하는 O(n) 까지 늘어집니다. 해시테이블은 이름을 사전 순서대로 훑어 주지도 않습니다.

그 순서가 필요하면 순서를 지켜 주는 이진 탐색 트리로 만듭니다. 넣기와 찾기는 O(log n) 으로 조금 더 듭니다. 담긴 이름이 늘어도 걸리는 시간이 아주 천천히만 는다는 뜻입니다.

앞의 이야기를 한 표로 모으면 이렇습니다.

두 구현 모두 담긴 이름 수만큼 공간을 씁니다. 가르는 것은 공간이 아니라 순서를 지켜 주느냐입니다.

완성된 파일에서 표 걷어내기

걷어낼지 정하려면 남겨서 무엇에 쓰는지부터 봐야 합니다.

디버거와 프로파일러는 주소만 남은 프로그램을 사람이 읽게 바꿔 줍니다. 멈춘 주소를 심볼 테이블에서 되짚어 함수 이름을 찾아내는 것입니다. 스택 트레이스에 함수 이름이 줄줄이 찍히는 것도 이 표 덕입니다.

완성된 파일에 실리는 이름은 두 갈래입니다. 프로그램을 띄울 때 찾아야 하는 이름은 남겨야 합니다. 걷어낼 수 있는 것은 사람이 읽으라고 두는 쪽입니다.

그래서 표를 완성된 파일에 남길지는 고르는 문제가 됩니다. 남기면 파일이 커지고 함수 이름이 밖으로 드러납니다. 걷어내면 파일이 줄지만 사람이 볼 이름이 사라져 스택 트레이스에 주소만 찍힙니다.

표를 걷어내는 일을 스트립이라고 부릅니다. 걷어내도 디버깅은 포기하지 않는 길이 있습니다. 이름이 든 부분만 따로 떼어 디버그 심볼 파일로 보관해 둡니다. 문제가 나면 그 파일을 가져와 주소를 이름으로 되돌립니다.

관련 항목

심볼 테이블 한 줄에 담기는 항목과 그 속성

심볼 · 식별자 · 스코프 · 데이터 타입 · 전역 변수 · 지역 변수 · 이름 맹글링 · 네임스페이스

심볼 테이블을 채우고 읽는 도구

컴파일러 · javac · 어셈블러 · 링커 · 동적 링커 · 디버거 · 프로파일러 · 인터프리터 · 정적 분석

심볼 테이블이 만들어지는 컴파일 단계

어휘 분석 · 구문 분석 · 의미 분석 · 타입 검사 · 코드 생성 · 추상 구문 트리

심볼 테이블이 실려 나가는 파일과 그 안의 구역

목적 파일 · 실행 파일 · 섹션 · 디버그 심볼 · 스트립 · 상수 풀

심볼 테이블을 맞춰 붙이는 링크 과정

정적 링크 · 동적 링크 · 재배치 · 심볼 해석 · PLT · GOT · 위치 독립 코드

심볼 테이블을 담는 데 쓰는 자료구조

해시테이블 · 이진 탐색 트리 · 맵 · 연관 배열 · 트라이 · 빅오 표기법

심볼 테이블이 어긋날 때 나는 오류

미정의 심볼 · 중복 심볼 · 링크 오류 · 스택 트레이스 · 세그멘테이션 폴트