심볼 테이블
심볼 테이블(symbol table)은 컴파일러 또는 인터프리터 같은 언어 변환기(프로그램의 소스 코드의 각 식별자가 자신의 선언 또는 소스에서의 외형과 관련된 정보와 연관되는)에서 사용되는 데이터 구조이다.
구현[편집]
일반적으로 해시 테이블을 사용해서 구현된다. 컴파일러는 모든 심볼들을 위한 큰 심볼 테이블을 사용하거나 스코프에 따라 독립되고 계층적인 심볼 테이블들을 사용한다. 또한 심볼 테이블을 구현하는데 사용되는 트리, 선형 리스트 그리고 자가 구성 리스트(self-organizing list)도 존재한다. 심볼 테이블은 어휘 분석기부터 최적화까지 컴파일러의 대부분의 단계에서 접근된다.
사용[편집]
목적 파일은 외부적으로 보이는 식별자들의 심볼 테이블을 포함할 것이다. 여러 다른 목적 파일들을 링킹하는 동안, 링커는 이러한 심볼 테이블들을 이용해서 resolve되지 않은 참조들을 resolve할 것이다.
심볼 테이블은 상호 작용을 하는 디버깅 세션 동안 같이 오직 변환 과정에서만 존재하거나, 프로그램의 실행 동안이나 이후에 진단 리포트를 포맷화하기 위한 리소스같이 추후 사용을 위한 과정의 결과에 삽입될 수 있다.
실행 파일을 리버스 엔지니어링하는 동안 많은 도구들이 전역 변수와 알려진 함수들에 부여된 주소를 검사하기 위해 심볼 테이블을 찾아 본다. 만약 심볼 테이블이 스트립되었거나 실행 파일로 변환되기 전에 제거되었다면, 도구들은 주소를 결정하거나 프로그램에 대해 이해하는게 매우 힘들어진다.
변수들에 접근하거나 메모리를 동적으로 할당할 때, 컴파일러는 심볼 테이블을 필요로 하는 확장된 스택 같은 많은 작업들을 수행하여야 한다.
예시[편집]
C로 짜인 다음의 프로그램을 보자:
// Declare an external function
extern double bar(double x);
// Define a public function
double foo(int count)
{
double sum = 0.0;
// Sum all the values bar(1) to bar(count)
for (int i = 1; i <= count; i++)
sum += bar((double) i);
return sum;
}
이 코드를 파스하는 C 컴파일러는 적어도 다음의 심볼 테이블 엔트리들을 포함할 것이다:
| 심볼 이름 | 타입 | 스코프 |
|---|---|---|
bar
|
function, double | extern |
x
|
double | function parameter |
foo
|
function, double | global |
count
|
int | function parameter |
sum
|
double | block local |
i
|
int | for-loop statement |
게다가 심볼 테이블은 중간 표현 값(예를 들면 i 루프 변수를 double로 캐스트하는 표현, 함수 bar()에 대한 호출의 반호나 값), 선언 라벨 등을 위해 컴파일러에 의해 생성된 엔트리들을 포함할 것이다.
다른 예시로 작은 프로그램의 심볼 테이블이 아래에 나와 있다. 이 테이블 자체는 GNU 바이너리 유틸리티의 nm을 사용해서 생성되었다. 하나의 데이터 심볼("D" 타입) 그리고 많은 함수들(표준 라이브러리에서뿐만 아니라 직접 정의된)이 존재한다. 첫 번째 칼럼은 메모리에서 심볼이 어디에 위치하는지이고, 두 번째는 "심볼 타입"이며 세 번째는 심볼의 이름이다. 적절한 파라미터들을 넘기면서, 이 심볼 테이블은 주소의 베이스를 정렬해야 한다.
| 주소 | 타입 | 이름 |
|---|---|---|
| 00000020 | a | T_BIT |
| 00000040 | a | F_BIT |
| 00000080 | a | I_BIT |
| 20000004 | t | irqvec |
| 20000008 | t | fiqvec |
| 2000000c | t | InitReset |
| 20000018 | T | _main |
| 20000024 | t | End |
| 20000030 | T | AT91F_US3_CfgPIO_useB |
| 2000005c | t | AT91F_PIO_CfgPeriph |
| 200000b0 | T | main |
| 20000120 | T | AT91F_DBGU_Printk |
| 20000190 | t | AT91F_US_TxReady |
| 200001c0 | t | AT91F_US_PutChar |
| 200001f8 | T | AT91F_SpuriousHandler |
| 20000214 | T | AT91F_DataAbort |
| 20000230 | T | AT91F_FetchAbort |
| 2000024c | T | AT91F_Undef |
| 20000268 | T | AT91F_UndefHandler |
| 20000284 | T | AT91F_LowLevelInit |
| 200002e0 | t | AT91F_DBGU_CfgPIO |
| 2000030c | t | AT91F_PIO_CfgPeriph |
| 20000360 | t | AT91F_US_Configure |
| 200003dc | t | AT91F_US_SetBaudrate |
| 2000041c | t | AT91F_US_Baudrate |
| 200004ec | t | AT91F_US_SetTimeguard |
| 2000051c | t | AT91F_PDC_Open |
| 2000059c | t | AT91F_PDC_DisableRx |
| 200005c8 | t | AT91F_PDC_DisableTx |
| 200005f4 | t | AT91F_PDC_SetNextTx |
| 20000638 | t | AT91F_PDC_SetNextRx |
| 2000067c | t | AT91F_PDC_SetTx |
| 200006c0 | t | AT91F_PDC_SetRx |
| 20000704 | t | AT91F_PDC_EnableRx |
| 20000730 | t | AT91F_PDC_EnableTx |
| 2000075c | t | AT91F_US_EnableTx |
| 20000788 | T | __aeabi_uidiv |
| 20000788 | T | __udivsi3 |
| 20000884 | T | __aeabi_uidivmod |
| 2000089c | T | __aeabi_idiv0 |
| 2000089c | T | __aeabi_ldiv0 |
| 2000089c | T | __div0 |
| 200009a0 | D | _data |
| 200009a0 | A | _etext |
| 200009a0 | D | holaamigosh |
| 200009a4 | A | __bss_end__ |
| 200009a4 | A | __bss_start |
| 200009a4 | A | __bss_start__ |
| 200009a4 | A | _edata |
| 200009a4 | A | _end |
