[Compiler] Parser 동작

요 근래 학교 과제가 있어서 블로그에도 글을 잘 못올렸다. 이번에 나온 과제는 compiler의 구성물중 parser를 만드는 것이었다. 프로그래밍 실력도 없는데 compiler를 만들어보라고 해서 애를 많이 먹었지만 그래도 덕분에 C++에 대해서 복습할 기회도 있어서 여러모로 좋은 기회였다.

 지난 포스트는 scanner를 통해서 각 token을 뽑고 그 token이 어떤 성향을 띄는지를 출력할 수 있다는 것을 보여줬다. 그렇게 얻은 token들을 parser에 넣게되면 어떤 문법과 일치하는지 비교해주는게 대략적인 내용이다. 아무튼 그렇게 비교하기 위해서는 처음에 grammar에 대한 specification이 나와있어야 했고, 그 부분은 과제를 하기 전에 미리 주어졌다.

위에 제시된 형태가 EBNF로 표현된 grammar의 일부이다. 그래서 각 token의 sequence를 판단한 후 어떤 grammar와 일치하는지를 봐야 한다. 예를 들어서

a := a + b + c;

라는게 입력으로 들어오면 parser를 거친 후에는 아 이게 assignment의 형태를 띄는구나 라는 것을 compiler 자체가 알 수 있어야 한다는 것이다. 

 기본적인 수행은 다음과 같다. 해당 구문이 들어간 코드부를 하나의 module처럼 생각해서 다음에 인식되는 token이 무엇인지를 미리 알고, 만약 정해진 grammar와 일치하면 token은 없어지는 형태이며, 이를 위해서는 token이 일종의 linked list로 구성되어 있다. 그래서 Consume()이라는 함수를 통해서 token이 들어가면 자동으로 다음 token이 저장된 곳을 가리키게 하고 이같은 과정이 token이 없어질 때까지 반복된다. 

 그런데 여기서 몇가지 고려해야 될 사항이 있다. 앞에서 다음에 인식되는 token에 대한 이야기를 했었는데 지난 포스트에서 다룬 내용 중에서는 이를 lookahead라고 볼 수 있다. 그래서 다음 token 1개를 미리 보는 형식이기 때문에 LookAhead의 depth는 1이다. 그런데 위에서 assignment 문법과 subroutineCall  문법을 잠깐 살펴보자. 둘다 시작을 ident 라는 terminal로부터 시작한다. 앞에서 언급한 바에 따르면 다음 token으로 넘어가지 위해서는 현재 token이 반드시 Consume되어야 하는 것인데 알다시피 ident는 해당 문법내에서도 할당과 연관된 중요한 역할을 하기 때문에 쉽게 Consume할수가 없다. 간단히 말해서 Consume하지 않고 다음다음 token을 비교해야 assignment와 subroutineCall을 구분할 수 있다는 것이다. 

 해결 방법은 두가지가 있는데 첫번째는 앞에서 말한 LookAhead의 depth를 2로 늘리자는 것이다. 말그대로 미리 보는 token의 갯수를 2개로 늘리고 그에 대한 대비를 하자는 것인데, 사실 잘 보면 알겠지만 위에 제시된 specification상에서 LookAhead depth =2를 요구하는 문법이 별로 없다. 그래서 사실 별 도움이 되지 않을 거 같았고, 그다음으로 생각해본 것이 symbol table을 만들어보자는 것이다. 달리 표현하면 해당 token들의 FIRST와 FOLLOW를 구해서 그 결과에 따라 구분을 두자는 것이다. 이를 이용해서 두개를 구분했고, 아무튼 이런 우여곡절을 겪은 끝에 parser를 만들 수 있었다.

 예시로 제공된 test case는 다음과 같다.

//

// test08

//

// fibonacci and factorial

//

module test08;

var a : integer;

    b : boolean;

// fib(n): integer

//

// compute the fibonacci number of n.

// n >= 0

function fib(n): integer;

begin

  if (n <= 1) then

    return n

  else

    return fib(n-1) + fib(n-2)

  end

end fib;

// fact(n): integer

//

// compute the factorial of n.

// n >= 0

function fact(n): integer;

begin

  if (n = 1) then

    return n

  else

    return n*fact(n-1)

  end

end fact;

// print(x)

//

// print value x

procedure print(x);

begin

  Output(x)

end print;

begin

  a := Input();

  b := a >= 0;

  // loop until the user enters a number < 0

  while (b = true) do

    print(fib(a));

    print(fact(a));

    a := Input();

    b := a >= 0

  end

end test08.

일단 parser를 거친 이상 위 코드에 대한 결과물은 하나의 parser tree로 나타나야 하며, 이를 dot이라는 일종의 graphical format으로 변환하면 다음과 같은 parse tree가 생성된다. 

아무튼 조금 힘든 부분도 있었지만 해보면서 parser가 이렇게 동작하는 것이라는 걸 조금더 확실하게 알 수 있었던 계기였었다.

참고 : http://www.richelbilderbeek.nl/ClConvertDotGraph.htm