심볼 테이블
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
심볼 테이블은 컴파일러, 링커, 디버거 등에서 사용되는 자료 구조로, 식별자(심볼)와 해당 심볼에 대한 정보를 저장하고 관리한다. 해시 테이블과 같은 자료 구조를 사용하여 구현되며, 컴파일 과정에서 변수 타입, 스코프, 메모리 주소 등의 정보를 저장하고, 링킹 과정에서 외부 참조를 해결하며, 디버깅 및 리버스 엔지니어링 과정에서 코드와 데이터를 분석하는 데 활용된다. 일부 프로그래밍 언어는 런타임에 심볼 테이블을 조작하는 기능을 제공하며, 파이썬과 같은 언어에서도 심볼 테이블을 생성하고 조작할 수 있다.
더 읽어볼만한 페이지
| 심볼 테이블 | |
|---|---|
| 심볼 테이블 | |
 | |
| 개요 | |
| 종류 | 자료 구조 |
| 사용 분야 | 컴파일러 인터프리터 |
| 목적 | 소스 코드에 사용된 식별자에 대한 정보 저장 |
| 정보 종류 | 이름 자료형 범위 주소 |
| 동작 | |
| 추가 | 새로운 식별자 정보 추가 |
| 검색 | 식별자에 대한 정보 검색 |
| 삭제 | 더 이상 필요하지 않은 식별자 정보 삭제 |
| 구현 | |
| 일반적인 구현 | 해시 테이블 트리 |
| 장점 | |
| 효율적인 검색 | 빠른 식별자 정보 접근 |
| 범위 관리 | 변수의 유효 범위 추적 |
| 형 검사 | 자료형 일치 여부 확인 |
| 단점 | |
| 메모리 오버헤드 | 심볼 테이블 자체의 메모리 사용량 |
| 구현 복잡성 | 효율적인 자료 구조 및 알고리즘 필요 |
2. 구현
심볼 테이블은 주로 해시 테이블을 사용하여 구현되지만, 트리, 선형 리스트, 자체 정렬 리스트 등 다양한 자료 구조를 사용할 수도 있다.[1] 컴파일러는 스코프에 따라 독립적이고 계층적인 심볼 테이블을 사용하거나, 모든 심볼을 위한 큰 심볼 테이블을 사용할 수 있다.
예를 들어, 알골이나 PL/I과 같이 범위가 있는 언어에서 "p"라는 심볼은 여러 프로시저에서 별도로 선언될 수 있으며, 서로 다른 속성을 가질 수 있다. 각 선언의 범위는 "p"에 대한 참조가 해당 선언으로 해결되는 프로그램의 섹션이다. 각 선언은 고유한 식별자 "p"를 나타내므로, 심볼 테이블은 서로 다른 "p"에 대한 참조를 구별하는 수단을 가져야 한다.
일반적으로 해시 테이블이 심볼 테이블 구현에 사용된다. 해시 키 계산에 분류를 포함시켜 표 형식의 리터럴 분류를 단순화할 수도 있다. 어휘 분석기는 심볼 테이블을 찾는 데 상당한 시간을 소비하므로, 이 작업은 컴파일러의 전체 속도에 큰 영향을 미친다. 따라서 심볼 테이블은 항목을 가능한 한 빨리 찾을 수 있도록 구성되어야 한다.
컴파일러나 인터프리터 등의 처리 시스템은 하나의 큰 심볼 테이블로 모든 것을 처리하거나, 네임스페이스별로 분할된 심볼 테이블을 사용하기도 한다. 전자의 경우, 다른 네임스페이스에 있는 동일한 이름이 충돌하지 않도록 하는 조치가 필요하다.
2. 1. 해시 테이블
해시 테이블은 심볼 테이블 구현에 널리 사용되는 자료 구조이다. 해시 테이블에서의 검색 시간은 테이블에 저장된 요소의 수와 관계없이 일정하므로, 많은 수의 요소를 다룰 때 효율적이다.[1] 해시 테이블은 키워드나 식별자를 '해싱'하여 배열 첨자를 생성하는 방식으로 구성된다.[1] 해시 충돌은 해시 테이블에서 불가피하게 발생하며, 이를 처리하는 일반적인 방법 중 하나는 동의어를 테이블에서 다음으로 사용 가능한 빈 공간에 저장하는 것이다.[1]2. 2. 기타 자료 구조
트리, 선형 리스트, 자체 정렬 리스트를 사용하여 심볼 테이블을 구현할 수 있다.[1] 심볼 테이블은 어휘 분석부터 최적화까지 컴파일러의 대부분의 단계에서 접근된다.[1]3. 사용
심볼 테이블은 컴파일 과정과 프로그램 실행 과정 등 여러 단계에서 중요한 역할을 한다.
- 컴파일러: 컴파일러는 어휘 분석 단계부터 최적화 단계까지 심볼 테이블을 사용하여 변수, 함수 등의 정보를 저장하고 참조한다.
- 링커: 링커는 여러 목적 파일을 연결하여 하나의 실행 파일을 만들 때 심볼 테이블을 사용하여 정의되지 않은 심볼을 찾고 참조를 해결한다.
- 디버거: 디버거는 심볼 테이블을 사용하여 변수 값을 확인하고, 코드를 단계별로 실행하며, 오류를 찾는 등 디버깅 작업을 수행한다.
- 리버스 엔지니어링: 리버스 엔지니어링 도구는 심볼 테이블을 참조하여 전역 변수와 함수에 할당된 주소를 확인한다.[1]
심볼 테이블은 번역 과정 중에만 메모리에 존재할 수도 있고, 나중을 위해 ABI 오브젝트 파일과 같이 번역의 출력에 포함될 수도 있다.[1]
3. 1. 컴파일러
일반적으로 해시 테이블을 사용하여 구현한다. 컴파일러는 모든 심볼을 위한 큰 심볼 테이블을 사용하거나 스코프에 따라 독립되고 계층적인 심볼 테이블을 사용한다.[1] 고급 프로그래밍 언어의 심볼 테이블은 심볼의 유형(문자열, 정수, 부동 소수점 등), 크기, 차원 및 범위를 저장할 수 있다.다양한 자료 구조를 사용하여 테이블을 구현할 수 있는데, 트리, 선형 리스트, 자체 정렬 리스트 등이 사용될 수 있다. 심볼 테이블은 어휘 분석부터 최적화까지 컴파일러의 대부분 단계에서 접근된다.
컴파일러는 모든 심볼에 대해 하나의 큰 심볼 테이블을 사용하거나, 다른 범위에 대해 분리되거나 계층적인 심볼 테이블을 사용할 수 있다.
심볼 테이블 구현에는 주로 해시 테이블이 사용된다. 해시 테이블은 검색 시간이 테이블에 저장된 요소 수와 관계없이 효율적이다.
3. 2. 링커
링커는 여러 목적 파일의 심볼 테이블을 결합하여 최종 실행 파일을 생성한다. 여러 목적 파일을 링킹하는 동안, 링커는 이러한 심볼 테이블들을 이용해서 해결되지 않은 참조들을 해결한다.[1] 이 과정에서 정의되지 않은 외부 심볼은 하나 이상의 오브젝트 라이브러리에서 검색된다.[4] 해당 심볼을 정의하는 모듈이 발견되면, 그 모듈은 첫 번째 오브젝트 파일과 함께 링크되며, 정의되지 않은 외부 식별자는 찾아야 할 식별자 목록에 추가된다.[4] 이 과정은 모든 외부 참조가 해결될 때까지 계속되며, 하나 이상의 참조가 해결되지 않은 상태로 남아 있으면 오류가 발생한다.[4]실행 파일을 리버스 엔지니어링하는 동안, 많은 도구들이 전역 변수와 알려진 함수들에 부여된 주소를 검사하기 위해 심볼 테이블을 참조한다.[3] 만약 심볼 테이블이 스트립되었거나 실행 파일로 변환되기 전에 제거되었다면, 도구들은 주소를 결정하거나 프로그램에 대해 이해하기가 매우 어려워진다.[3]
3. 3. 디버거
심볼 테이블은 대화형 디버거를 이용한 디버깅이나 성능 분석 도구 등에 의한 실행 시 성능 정보 수집 등에서 이용된다.[1]3. 4. 리버스 엔지니어링
리버스 엔지니어링 도구는 실행 파일에서 심볼 테이블을 찾아 전역 변수와 알려진 함수에 할당된 주소를 확인한다.[1] 심볼 테이블이 스트립되었거나 실행 파일 변환 전에 제거되면, 도구는 주소를 파악하거나 프로그램 동작 방식을 이해하기 어려워진다.[1]4. 예시
C, 파이썬 등 다양한 프로그래밍 언어에서 심볼 테이블이 사용된다.
C 언어의 경우, 컴파일러는 소스 코드에 나타나는 함수, 변수 등의 심볼 정보를 심볼 테이블에 저장한다. 이 정보는 코드 생성 및 최적화에 활용된다. GNU 바이너리 유틸리티의 nm 명령어를 사용하면 컴파일된 프로그램의 심볼 테이블을 확인할 수 있다.
파이썬은 심볼 테이블 생성 및 조작을 위한 기능을 제공한다.[3] 이를 통해 심볼의 자유/바운드 여부, 범위, 네임스페이스 등의 속성을 확인할 수 있다.
4. 1. C 언어 예시
C로 작성된 다음의 프로그램을 보자:// 외부 함수 선언
extern double bar(double x);
// 공개 함수 정의
double foo(int count)
{
double sum = 0.0;
// bar(1)에서 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()에 대한 호출의 반환 값), 선언 라벨 등을 위해 컴파일러에 의해 생성된 항목들을 포함할 것이다.
4. 2. GNU Binutils nm 예시
GNU 바이너리 유틸리티의 nm으로 생성된 작은 프로그램의 심볼 테이블 예시다. 하나의 데이터 심볼("D" 타입)과 (표준 라이브러리 및 직접 정의된) 여러 함수들이 있다. 첫째 열은 메모리에서 심볼의 위치, 둘째 열은 "[http://sourceware.org/binutils/docs-2.17/binutils/nm.html#nm 심볼 타입]", 셋째 열은 심볼 이름이다. 적절한 파라미터를 사용하면 심볼 테이블은 주소 베이스를 기준으로 정렬된다.[2]| 주소 | 타입 | 이름 |
|---|---|---|
| 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 |
4. 3. 동적 심볼 테이블
래킷,[4] LISP, Scheme,[5] 프롤로그와 같은 일부 프로그래밍 언어는 런타임에 심볼 테이블을 조작하여 언제든지 심볼을 추가할 수 있도록 허용한다. 프롤로그에서 심볼은 '원자(atoms)'라고 불리며, 심볼 간의 관계를 추론할 수 있다. OpenCog는 지식 표현에 사용되는 'atomspace'라는 동적 심볼 테이블을 제공한다.4. 4. 파이썬 심볼 테이블
파이썬 프로그래밍 언어는 심볼 테이블을 생성하고 조작하는 광범위한 지원을 포함한다.[3] 쿼리할 수 있는 속성에는 주어진 심볼이 자유 변수인지 바운드 변수인지, 블록 범위인지 전역 범위인지, 가져왔는지 여부, 그리고 속한 네임스페이스가 무엇인지 등이 있다.참조
[1]
서적
Linux Dictionary
https://books.google[...]
2004
[2]
웹사이트
nm
http://sourceware.or[...]
2020-05-30
[3]
Python documentation
symtable
https://docs.python.[...]
[4]
Racket Documentation
Symbols
https://docs.racket-[...]
[5]
Guile Documentation
Symbols
https://www.gnu.org/[...]
[6]
Solaris マニュアル
シンボルテーブル (リンカーとライブラリ)
https://docs.oracle.[...]
Sun Microsystems
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com