재귀-하강 파싱 (Recursive-descent parsing)

재귀하강 파싱 방법은 함수들의 재귀를 통해 파싱하는 방법을 말해요

 

다음 문법을 예시로 들어볼게요

 

<if-stat>  ->  if <expr> [ else <expr> ]
<param>  ->  <identifier> { , <identifier> }

 

대괄호 안에 있는 구문은 옵션으로 있거나 없을 수 있다는 뜻이에요

중괄호 안에 있는 구문은 있거나 없을 수 있지만 여러개 있을수도 있다는 뜻이에요

 

int get_token() {
    // 토큰을 구해주는 함수
}

void expr() {
    // 모든 expression 처리하는 함수
    // if 문이 또 나올수도 있다.
}

void if_stat() {
    int token = get_token();
    if (token == IF) {
    	// 여는 괄호
        if (get_token() == LEFT_PAR) {
          expr();
          
          // 닫는 괄호
          if (get_token() != RIGHT_PAR)
          	error();
          
          // else 문
          if (get_token() == ELSE)
              expr();
        } else {
	        error();
        }
    } else {
    	error();
    }
}

void param() {
    get_token();
    int token = get_token();
    if (token == COMMA)
    	param();
}

 

이처럼 param 이  param 을 재귀호출하는 방식은 직접적으로 눈에 보이죠?

if_stat() 같은 경우에도 expr() 문을 내부적으로 호출하지만 expr() 은 굉장히 광범위한 함수라서 돌고돌다보면 if_stat() 을 다시 호출할 수 있어요. ( 결국 재귀죠 )

한계

좌순환(Left recursion) 문제

A -> AB

이런 규칙이 있을 때 A는 A를 만들고 만들어진 A는 또 A를 만들게되는 무한 루프에 빠지는 문제가 있습니다.

이런 문제를 직접 좌순한(Direct left recursion) 문제라고 하는데 이는 다음과 같은 방법으로 해결할 수 있습니다.

 

E -> E + T | T

 

를 수정한 모드

 

E -> TE`
E` -> + T  |  e

e는 입실론을 표현한 문자로 빈 문자(empty) 라고 생각하면 됩니다.

 

아래와 같은 간접 좌순환 문제도 해결할 수 있는데 알고리즘이 복잡해서 다루지는 못하고, 가능하긴하다~ 정도로 알고계시면 좋습니다.

 

A -> B
B -> A

파서의 올바른 RHS 선택 문제

쉽게말해서 올바른 규칙을 언제나 선택할 수 있느냐에 대한 확신이 없다는 것입니다.

이를 알기 위해서는 집합쌍 공통 테스트(pairwise disjointness test) 를 해야합니다.

 

이 테스트를 하기 위해 FIRST 라는 것을 정의할게요

 

FIRST(A) = { a | A => * aB }

 

=> * 라는건 0개 이상으로 derivation 될 수 있어야 한다는 뜻입니다.

쉽게 말해서 A 라는 규칙을 시작점으로 하여 최초(맨 왼쪽)의 terminal로 나올 수 있는 terminal의 집합을 구하는 거에요.

 

예시를 하나 들어볼게요

 

A -> aB | bAb | Bb
B -> cB | d

 

A -> aB 를 적용하면 최초의 terminal a 가 나왔죠?  따라서 { a } 추가

A -> bAb 를 적용하면 최초의 terminal b 가 나왔죠. 따라서 { b } 추가

A -> Bb 를 적용하면 최초(맨 왼쪽)가 아직 terminal 이 아니에요. ( B 는 Nonterminal )

         B -> cB 를 적용하면 cBb 로 c 가 최초의 terminal,

         B -> d 를 적용하면 db로 d 가 최초의 terminal 이 가능하므로 { c, d } 추가

따라서 FIRST(A) = { {a}, {b}, {c, d} } 에요.

세 번째 A->Bb 규칙에서 B로 인에 두 갈래로 나뉜 c,d 는 하나의 집합으로 묶인다는 것이 중요해요

 

그래서 FIRST 를 정의했는데 얘를 어떻게 해야하냐

 

FIRST(ai) ∩ FIRST(aj) = 0    // 모든 i, j에 대해

 

이것도 쉽게 말하면 {a}, {b}, {c, d} 간에 겹치는 원소가 없어야한다는거에요.

지금 같은 경우에는 겹치는게 없기 때문에 문제가 없습니다.

문제되는 경우

A -> aB | BAb
B -> aB | b

 

FIRST(A) = { {a}, { a, b } }

이 경우 { a } ∩ { a, b } 는 공집합이 아니죠? { a } 가 겹치기 때문에 문제가 생기는 것입니다.

그래서 뭐가 문젠데?

문제가 생긴다고는 했는데 무슨 문제인지는 아직 밝히지 않았어요

컴파일러 입장에서 현재 상태가 A이고, 읽어들인 토큰이 b 라면 바로 A -> BAb 규칙을 적용시킬 수 있습니다. 당장 b를 만들어야하기 때문이입니다.

하지만 읽어들인 토큰이 a라면 어떨까요? A->aB 규칙을 써도 a가 만들어지고, A->BAb->aBAb 규칙을 써도 a가 만들어져요.

즉 터미널만 보고서는 규칙을 특정할 수 없다는 문제가 생기고, 이러면 이후 터미널도 보도록 구현해야하는데 이게 매우 복잡해요

결론

Recursive-descent parsing은 Top-down 파서의 대표적인 예시에요

함수 재귀 호출 방식으로 파스 트리를 만들어가는만큼 일반 개발자들이 이해하기 쉽죠

하지만 Left-recursive 문제, 파서의 올바른 RHS 선택 문제를 해결하는게 중요해요.

이 문제들은 비단 Recursive-descent parsing 문제에 국한되진 않아요. 모든 Top-down 파서들의 문제이기도하답니다.