재귀 호출 없는 재귀 하향 파싱

재귀 하향 파싱의 문제점

다음과 같은 LL 문법을 생각해봅시다.

이 문법은 $a$를 0개 이상 포함하는 문장의 집합을 나타냅니다. 재귀 하향 파싱을 구현하면 다음과 같습니다.

def match(s, i, c):
    if s[i:].startswith(c):
        return i + len(c)
    return None

def S(s, i):
    # S -> aS | ε
    if (ni := S0(s, i)) is not None:
        return ni
    if (ni := S1(s, i)) is not None:
        return ni
    return None

def S0(s, i):
    # S -> aS
    if (i := match(s, i, 'a')) is None:
        return None
    if (i := S(s, i)) is None:
        return None
    return i

def S1(s, i):
    # S -> ε
    return i

s = 'aaaaa'
i = S(s, 0)
assert i is not None and i == len(s)

그렇다면 문장이 주어졌을 때 함수 S()는 몇 번 호출될까요? 당연히 문장의 길이만큼입니다. 그것도 재귀로요. 즉, 이 코드는 논리적으로는 문제가 없지만 너무 긴 문장이 주어지면 스택 오버플로우가 발생할 수 있습니다. 이 예시는 문법이 단순해서 그나마 괜찮지만, 실제 프로그래밍 언어를 파싱할 때에는 짧은 코드에서도 문제가 발생할 수 있습니다.

재귀 호출 없애기

스택 오버플로우가 재귀 호출 때문에 발생하는 것이니, 문제를 해결하고 싶다면 재귀 호출 없이 재귀를 구현해야 합니다.

여기서는 함수형 프로그래밍에서 자주 사용되는 트램펄린(trampoline) 기법을 사용해보겠습니다. 먼저, 비단말 기호를 파싱하는 함수들이 전부 다른 파싱 함수를 함수의 제일 마지막에서만 호출하도록 수정합니다. 중간에서 호출한다면, 호출 이후의 구문들을 전부 다른 함수로 분리해주는 방법을 쓸 수 있습니다. 예시를 보면 바로 감이 오실 겁니다.

def match(s, i, c):
    if s[i:].startswith(c):
        return i + len(c)
    return None

def S(s, i):
    return S_sub0(s, i, S0(s, i))

def S_sub0(s, i, r):
    if (ni := r) is not None:
        return ni
    return S_sub1(s, i, S1(s, i))

def S_sub1(s, i, r):
    if (ni := r) is not None:
        return ni
    return None

def S0(s, i):
    if (i := match(s, i, 'a')) is None:
        return None
    return S0_sub0(s, i, S(s, i))

def S0_sub0(s, i, r):
    if (i := r) is None:
        return None
    return i

def S1(s, i):
    return i

s = 'aaaaa'
i = S(s, 0)
assert i is not None and i == len(s)

이제 모든 파싱 함수는 어떤 값을 반환하거나, 두 함수를 차례로 호출하여 얻은 반환값을 반환하는 형태가 됩니다. 이 중 후자의 경우에 실제로 두 함수를 호출하지 않고, 단순히 어떤 함수를 호출할 것인지만 반환한 뒤, 함수 바깥에서 실제로 두 함수를 호출해주면 재귀 호출이 없는 구조를 만들 수 있습니다. 트램펄린이라고 부르는 이유도 함수를 옮겨다니면서 호출하는 모양이 트램펄린을 연상시키기 때문입니다.

저수준의 관점에서 설명하자면 두 번째 함수는 첫 번째 함수를 호출한 후 반환한 값을 들고 돌아갈 위치를 의미합니다. 즉, 함수 호출 시의 스택 동작을 직접 구현한 것입니다.

def match(s, i, c):
    if s[i:].startswith(c):
        return i + len(c)
    return None

def trampoline(x):
    while True:
        match x:
            case (func, args, post):
                x = post(*args, func(*args))
            case _:
                return x

def S(s, i):
    return S0, (s, i), S_sub0

def S_sub0(s, i, r):
    if (ni := r) is not None:
        return ni
    return S1, (s, i), S_sub1

def S_sub1(s, i, r):
    if (ni := r) is not None:
        return ni
    return None

def S0(s, i):
    if (i := match(s, i, 'a')) is None:
        return None
    return S, (s, i), S0_sub0

def S0_sub0(s, i, r):
    if (i := r) is None:
        return None
    return i

def S1(s, i):
    return i

def end_trampoline(s, i, r):
    return r

s = 'aaaaa'
i = trampoline((S, (s, 0), end_trampoline))
assert i is not None and i == len(s)

이제 $a$를 엄청나게 많이 포함한 문장도 재귀 호출 제한 없이 잘 파싱할 수 있습니다.