[Compiler] Intermediate Code Generation 실습

과제가 너무 밀려 있어서 한동안 블로그에 글을 못 올렸다.

학교 과제로 제시되었던 내용은 지난 포스트에서 소개했던 Abstract Syntax Tree로 x86 assembly code를 만들기 위한 준비과정을 이행하는 것이었다. 그리고 블로그를 통해서 소개하지는 않았지만 이 AST를 만드는 과정 중에도 operation이나 parameter, condition 등에 대한 type checking 이 수행되어야 한다. 자세하게 말하자면 data type이 다른 연산을 코드 수행과정 내에서 최대한 배제시키려는 목적에서 이런 type checking을 수행하는 것이다. 가령 숙제의 reference grammar로 제시되었던 data type인 boolean과 integer 사이에서도 연산이 이뤄지지 않게끔 일종의 장치를 마련하자는 것이다. 컴파일러를 구현하는 데 있어서 중요한 과정 중 하나이며, 지금과제를 수행하던 중 생각나는 main goal 중 하나 였던 걸로 생각난다. 

 아무튼 지난번 과제의 결과로는 다음과 같은 AST를 뽑아낼 수 있었다.

이 tree형태만 봐도 현재 scope안에 어떤 local variable을 가지는지, 또는 어떤 연산이 먼저 수행되는지, data type은 연결이 잘 되어 있는지를 확인할 수 있다. 하지만 문제는 이것만 가지고는 컴퓨터가 알아들을 수 없다. 최종적으로 컴퓨터가 computation을 하기 위해서는 컴퓨터만 알아들을 수 있는 assembly code로 바꿔줘야 한다. 그런데 그걸 바로 바꾸기에는 사용자의 readability가 너무 떨어지게 된다. 또한 target machine의 종류에 따라서 assembly code가 무척 다르고, 이를 바로 적용하기 위해서는 복잡한 과정을 거쳐야 한다. 그래서 중간 단계로 특정 code를 만들어서 일종의 machine independent한  code로 생성하는 것이 필요하고, 이 과정에서 나오게 된 것이 Intermediate Code 이다. 즉 지금 이렇게 하고 있는 과정이 일종의 Intermediate Code Generation 이 되는 것이다. 줄여서 IR 이라고 하는데 수업에서는 이중에서도 Three Address Code 방식을 적용했다.  Three Address Code란 말 그대로 3주소, 즉 src1, src2, dst로 구성된 코드 형태를 말한다. 그래서 엄청 긴 수식으로 된 코드라도 앞에서 소개한 것처럼 3주소 형태로 나눠서 구현된다. 위키에서는 다음과 같은 예시를 보여주고 있다.

# Calculate one solution to the [[quadratic equation]]. x = (-b + sqrt(b^2 - 4*a*c)) / (2*a)

t1 := b * b  t2 := 4*a  t3 := t2 * c  t4 := t1 - t3  t5 := sqrt(t4)  t6 := 0 - b  t7 := t5 + t6  t8 := 2 * a  t9 := t7 / t8  x := t9

조금 이상하게 느껴지겠지만 위의 두 식은 같은 결과를 출력하는 코드이다. 그래서 수차례 시행착오를 거치고 아래와 같은 결과를 얻을 수 있었다.

잘 보면 알겠지만 각 코드 내에는 개별 procedure가 있을 것이고, 그 procedure가 수행하는 내용이 다를 것이다. 혹은 그 procedure안에는 조건문이 들어 있어서 조건을 만족한 경우와 만족하지 않을 경우에 대해서 고려해보고 해당 부분으로 jump 하는 과정도 삽입되어야 한다. 아무튼 여기까지가 machine independent 한  case이고 다음 포스트에서 아마 machine에 따른 assembly code 를 생성하는 과정을 소개할 수 있을 듯 하다. 현재 과제에서는 x86을 target으로 삼고 있다.