[c++] Symbol Table 정리!

열혈 C++을 통해 빠르게 C++을 공부하고 있다. 각 파트가 끝날때마다, 내용과 관련해 궁금한 사항을 조사하여 블로그에 정리할 계획이다.

우선 오늘은 Symbol Table에 대해 알아봤다.

우선 이전에 공부한 symbol table은 어셈블러 레벨에서 바라본 시선이었다. (ref :http://csmylov.blogspot.com/2018/07/system-programming-build-program-2_19.html)

어셈블리 파트에  LABEL, INSTRUCTION, OPERAND가 존재한다. 여기서 LABEL은 data를 가리키는 data label,  instruction을 알려주는 instruction label이 있다. 어셈블러는 해당 어셈블리어를 기계어로 바꾸기 위해 2-path를 거치는데, 1st path에서 각 LABEL과 ADDRESS를 맵핑해주는 SYMBOL TABLE을 만든다. 만들어진 SYMBOL TABLE은 2nd path에서 OPERAND를 보고 실제 주소를 위한 displacement를 계산하는 데 사용되는 것이다. 여기서 Hash table을 이용한다고 말한 바 있다.

(**체크 : 어셈블러, 컴파일러의 Symbol table이 서로 같은 것인지 다른 것인지!)

이번에는 컴파일러 입장에서 Symbol table을 바라볼 것이다. (ref : https://www.tutorialspoint.com/compiler_design/compiler_design_symbol_table.htm)

1. Symbol table은 다음과 같은 정보를 저장하기 위해 컴파일러에서 생성하는 자료구조이다.

• Variable name
• Function name
• Objects, Classes, Interfaces

이를 통해 name(label)을 체계적으로 관리한다. 또한, 선언 여부, type checking, scope checking 등을 할 수 있다.

Symbol table의 각 element는 다음과 같이 구성된다.

<symbol name, type, attribute>

ex) static int interest -> <interest, int, static>

여기서 attribute는 value, state, scope, type 등을 포함한다.

(**value가 이해가 안된다.주소를 의미하는 건가? 그렇다면 -> 어셈블러의 Symbol table과 같은 녀석을 의미. )

2. Symbol table은 Linear list, Binary Search Tree, Hash table로 구현될 수 있다. 주로 Hash table을 사용하며, 여기서 key 가 name이 된다.

3. Scope Management

compiler은 global symbol table, scope symbol table을 가진다. global symbol table은 모든 함수가 접근할 수 있는 symbol table이며, scope symbol table은 각 scope및 child scope만 접근 가능하다.

아래 예시 코드를 이용하여 컴파일러는 Fig1과 같은 계층구조의 symbol table을 생성한다. 어떤 함수에서 symbol table을 접근하면, 우선 현재 scope의 symbol table을 뒤지고, 없으면 parent로 올라간다. (until global symbol table)

int value=10;

void pro_one()
   {
   int one_1;
   int one_2;
   
      {              \
      int one_3;      |_  inner scope 1 
      int one_4;      | 
      }              /
      
   int one_5; 
   
      {              \   
      int one_6;      |_  inner scope 2
      int one_7;      |
      }              /
   }
   
void pro_two()
   {
   int two_1;
   int two_2;
   
      {              \
      int two_3;      |_  inner scope 3
      int two_4;      |
      }              /
      
   int two_5;
   }

Fig1 Symbol table in scope