[컴파일러] 04. Symbol Table

• Symbol table : 토큰의 속성을 저장 관리하기 위한 테이블 (자료구조)

토큰 분석 단계에서 identifier (symbol)에 관한 정보를 수집하여 저장하고,

구문 분석 단계에서 저장된 정보의 의미 검사 및 처리하여

올바른 target code가 생성될 수 있도록 한다.

Hash table에 새롭게 입력받은 identifier를 직접 저장하지 않고 SymbolTable에 스트링을 저장한 후 인덱스를 hash table에 저장하는 방식 : 

- token 수가 많아지면 search, insert, delete 등에 대한 효율적인 심벌테이블 구조와 운영이 필요함.

- 메모리 측면 저장 공간을 효율적으로 하는게 필요함

 

*시간 측면

- Unordered symbol table : symbol 정의된 순서대로 insert, linear search

- Ordered symbol table : symbol을 알파벳 순서대로 insert, binary search

- Tree structure symbol table : binary tree, AVL tree

 

• Hash Symbol Table

해시 테이블은 가장 효율적인 탐색 중 하나인 해싱을 제공

x를 symbol이라고 할때

x의 주소값 H(x) = (f(x)mod m)+1

m = size of hash table

f(x) = sum of ordinal values of x's characters

 

• 연쇄 해시 테이블 (Chained hash table)

- 버킷에 자료를 저장하는 해시 테이블

- 각 버킷은 충돌을 조정하기 위해 필요한 만큼 커지는 연결리스트

- 특정 위치에 많은 충돌이 발생하면 버킷이 점점 길어져 그 버킷의 항목에 접근하는 시간이 오래걸림