재귀-하강 파싱 (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 파서들의 문제이기도하답니다.