기호 테이블

이 글은 검증을 위해 추가 인용문이 필요합니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.출처 : '기호표'– 뉴스 · 신문 · 서적 · 학자 · JSTOR (2012년 11월) (이 템플릿 메시지 삭제 방법 및 삭제 시기 확인)

컴퓨터 과학에서 심볼 테이블은 컴파일러나 인터프리터와 같은 언어 번역자에 의해 사용되는 데이터 구조이며, 여기서 프로그램의 소스 코드의 각 식별자, 상수, 프로시저 및 함수는 소스의 선언 또는 표시와 관련된 정보와 관련된다.즉, 심볼 테이블의 엔트리는 엔트리의 대응하는 ^[1]심볼에 관한 정보를 격납한다.

배경

심볼 테이블은 변환 프로세스 중에 메모리에만 존재하거나 나중에 사용하기 위한 ABI 오브젝트 파일 등 변환 출력에 포함될 수 있습니다.예를 들어 인터랙티브 디버깅세션 중에 사용하거나 프로그램 ^[2]실행 중 또는 실행 후에 진단 보고서를 포맷하기 위한 리소스로 사용할 수 있습니다.

묘사

변환자 및 중간 표현(IR)이 사용하는 기호 테이블에 포함된 최소 정보에는 기호 이름과 위치 또는 주소가 포함됩니다.재배치 가능성의 개념을 가진 플랫폼을 대상으로 하는 컴파일러의 경우 재배치 가능 속성(절대, 재배치 가능 등) 및 재배치 가능 심볼에 필요한 재배치 정보도 포함됩니다.고급 프로그래밍 언어용 기호 테이블에는 기호의 유형(문자열, 정수, 부동소수점 등), 크기, 치수 및 한계를 저장할 수 있습니다.이 모든 정보가 출력 파일에 포함되는 것은 아니지만 디버깅에 사용할 수 있습니다.대부분의 경우 심볼의 상호 참조 정보는 심볼 테이블과 함께 저장되거나 심볼 테이블과 링크됩니다.대부분의 컴파일러는 이 정보의 일부 또는 전부를 ^[1]심볼 테이블 및 상호 참조 목록으로 번역이 끝날 때 인쇄합니다.

실행

테이블 구현에는 다양한 데이터 구조를 사용할 수 있습니다.트리, 선형 목록 및 자체 구성 목록을 모두 사용하여 기호 테이블을 구현할 수 있습니다.기호 테이블은 사전 분석에서 시작하여 최적화까지 컴파일러의 대부분의 단계에서 액세스됩니다.

컴파일러는 모든 심볼에 대해 하나의 큰 심볼 테이블을 사용하거나 다른 범위에 대해 분리된 계층적 심볼 테이블을 사용할 수 있습니다.예를 들어, Algol 또는 PL/I와 같은 스코프 언어에서는 기호 "p"를 여러 절차에서 개별적으로 선언할 수 있으며, 아마도 다른 속성을 사용할 수 있습니다.각 선언의 범위는 "p"에 대한 참조가 해당 선언에 대해 해결되는 프로그램의 섹션입니다.각 선언은 고유 식별자 "p"를 나타냅니다.기호 테이블에는 서로 다른 "p"에 대한 참조를 구분하는 몇 가지 방법이 있어야 합니다.

심볼 테이블을 구현하기 위해 사용되는 공통 데이터 구조는 해시 테이블입니다.해시 테이블에서 검색하는 시간은 테이블에 저장된 요소의 수와 독립적이기 때문에 다수의 요소에 대해 효율적입니다.또한 해시 ^[3]키 계산에 분류를 포함시킴으로써 표 형식의 리터럴 분류를 간소화합니다.

어휘 분석기가 심볼 표를 찾는 데 많은 시간을 소비하기 때문에, 이 활동은 컴파일러의 전체 속도에 결정적인 영향을 미칩니다.심볼 표는 가능한 한 빨리 엔트리를 찾을 수 있도록 구성되어야 합니다.해시 테이블은 보통 기호 테이블을 구성하는 데 사용됩니다. 여기서 키워드 또는 식별자는 배열 첨자를 생성하기 위해 해시됩니다.해시 테이블에서는 충돌이 불가피하며, 이러한 충돌을 처리하는 일반적인 방법은 테이블의 사용 가능한 다음 빈 공간에 동의어를 저장하는 것입니다.

적용들

객체 파일에는 외부에서 볼 수 있는 식별자의 기호 테이블이 포함됩니다.다른 오브젝트 파일을 링크하는 동안 링커는 이러한 심볼 참조를 식별하고 해결합니다.일반적으로 정의되지 않은 모든 외부 기호는 하나 이상의 개체 라이브러리에서 검색됩니다.이 기호를 정의하는 모듈이 발견되면 해당 모듈은 첫 번째 개체 파일과 함께 링크되며 정의되지 않은 외부 식별자가 조회되는 식별자 목록에 추가됩니다.이 프로세스는 모든 외부 참조가 해결될 때까지 계속됩니다.프로세스 종료 시 하나 또는 여러 개가 해결되지 않은 상태로 남아 있으면 오류가 발생합니다.

실행 파일을 리버스 엔지니어링하는 동안 많은 도구는 기호 테이블을 참조하여 글로벌 변수와 알려진 함수에 할당된 주소를 확인합니다.실행 파일로 변환되기 전에 심볼 테이블이 제거되거나 지워진 경우, 툴은 주소를 확인하거나 프로그램에 대한 내용을 이해하는 것이 더 어려워집니다.

예

C로 작성된 다음 프로그램을 고려합니다.

// 외부 함수 선언 외부 이중으로 하다 막대기(이중으로 하다 x);  // 공용 함수 정의 이중으로 하다 후우(인트 세어보세요) {     이중으로 하다 합 = 0.0;      // 모든 값 bar(1)를 bar(카운트)로 합계     위해서 (인트 i = 1; i <=> 세어보세요; i++)         합 += 막대기((이중으로 하다) i);     돌아가다 합; } 

이 코드를 해석하는 C 컴파일러에는 적어도 다음 심볼테이블 엔트리가 포함됩니다.

또한 심볼 테이블은 컴파일러에 의해 생성된 중간 표현 값(예를 들어 캐스트하는 표현)에 대한 엔트리를 포함합니다.i에 변수를 루프하다double및 기능하는 콜의 반환값bar()), 스테이트먼트라벨 등입니다.

예:SysV ABI

심볼 테이블의 예는 SysV Application Binary Interface(ABI) 사양에 기재되어 있습니다.ABI 사양은 바이너리 파일에 심볼을 배치하는 방법을 규정합니다.이것에 의해, 다른 컴파일러, 링커, 및 로더가 모두 컴파일 오브젝트내의 심볼을 일관되게 검색해 조작할 수 있게 됩니다.

SysV ABI는 GNU binutils의 nm 유틸리티로 구현됩니다.이 형식은 정렬된 메모리 주소 필드, "기호 유형" 필드 및 기호 식별자("이름")^[4]를 사용합니다.

SysV ABI의 기호 유형(및 nm의 출력)은 기호 테이블의 각 엔트리의 특성을 나타냅니다.각 기호 유형은 단일 문자로 표시됩니다.예를 들어 초기화 데이터를 나타내는 심볼 테이블 엔트리는 문자 "d"로 표시되고 함수의 심볼 테이블 엔트리는 기호 타입 "t"를 가진다(실행 가능 코드가 오브젝트 파일의 텍스트 섹션에 위치하기 때문이다).또한 기호 유형의 대문자는 링크 유형을 나타냅니다. 소문자는 기호가 로컬임을 나타내며 대소문자는 외부(글로벌) 링크를 나타냅니다.

예: Python 기호 테이블

Python 프로그래밍 언어는 심볼 ^[5]테이블을 만들고 조작하는 광범위한 지원을 포함합니다.쿼리할 수 있는 속성에는 특정 기호가 자유 변수인지 바인딩된 변수인지, 블록 범위인지 전역 범위인지, 가져올지 여부 및 소속된 네임스페이스가 포함됩니다.

예:동적 기호 테이블

일부 프로그래밍 언어에서는 언제든지 기호를 추가할 수 있도록 런타임에 기호 테이블을 조작할 수 있습니다.라켓은 그런 언어의 ^[6]한 예이다.

LISP와 Scheme 프로그래밍 언어 모두 임의의 범용 속성을 각 ^[7]기호와 연결할 수 있습니다.

프롤로그 프로그래밍 언어는 본질적으로 심볼 테이블 조작 언어이며, 심볼은 원자라고 불리며, 심볼 간의 관계를 추론할 수 있습니다.마찬가지로 OpenCog는 지식 표현에 사용되는 atomspace라는 동적 기호 테이블을 제공합니다.

「 」를 참조해 주세요.

• 디버깅 기호

레퍼런스

참고 문헌

• Copper, Keith D.; Torczon, Linda (18 January 2011). Engineering a Compiler (2 ed.). Houston, Texas: Elsevier, Rice University. doi:10.1016/C2009-0-27982-7. ISBN 978-0-12-088478-0.