하향식 파싱

하향식 파싱

하향식 파싱(top-down parsing)은 시작 기호로부터 시작해 주어진 단말 기호의 문장을 유도함으로써 문장이 문법에 맞는지 검사하는 파싱 방법입니다. 하향식 파싱은 대개 가장 왼쪽에 있는 비단말 기호를 생성 규칙에 따라 치환해보는 좌측 유도(leftmost derivation)를 하면서 주어진 문장과 왼쪽부터 맞춰나가는 방식으로 이루어집니다.

재귀 하향 파싱

재귀 하향 파싱(recursive descent parsing)은 각 비단말 기호에 대해 하나의 함수를 작성해 해당 비단말 기호를 치환하는 방식으로 동작합니다. 예제 1로 설명하자면 $S$를 생성 규칙에 따라 치환하는 함수를 만드는데, 치환한 결과에서 $S$가 다시 나오는 경우(첫 번째 생성 규칙) 단말 기호를 매칭한 후 이 함수를 재귀적으로 다시 호출합니다. 만약 유도한 기호열과 주어진 문장의 기호가 서로 매칭되지 않는다면 잘못된 생성 규칙을 적용한 것이므로 다시 되돌아가서 다른 생성 규칙을 적용하는 백트래킹이 필요합니다.

아주 직관적인 알고리즘답게 코드도 간단합니다.

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

def S(s, i):
    # S -> aSbS | ε
    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 -> aSbS
    if (i := match(s, i, 'a')) is None:
        return None
    if (i := S(s, i)) is None:
        return None
    if (i := match(s, i, 'b')) is None:
        return None
    if (i := S(s, i)) is None:
        return None
    return i

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

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

위 코드에서는 각 생성 규칙을 S0와 S1이라는 이름으로 따로 구현했습니다. 마지막에 주어진 문장을 모두 매칭했는지도 반드시 확인해야 한다는 것에 주의합시다.

당연하겠지만 문법이 좌재귀를 가지면 재귀 하향 파싱은 무한 루프에 빠지게 됩니다.

LL 문법

사실 위 코드는 의도적으로 백트래킹을 사용한 것이고, 실제로는 처음 예제와 같이 다음으로 매칭할 기호(lookahead)를 보고서 어떤 생성 규칙을 사용할 지 결정할 수 있습니다.

예를 들어 앞 $n$개 단말 기호를 다음과 같이 매칭했고, 이제 비단말 기호 $X$를 치환해야 한다고 합시다.

$X$에 대한 생성 규칙이 $X \to \alpha_1 \mid \alpha_2 \mid \cdots \mid \alpha_m$와 같으면 첫 기호로 $a_{n+1}$을 만들어 낼 수 있는 생성 규칙이 유일해야 합니다. 즉, 기호열 $\alpha$에 대해 $\alpha$에서 유도되는 기호열들의 첫 기호의 집합을 $\text{FIRST}(\alpha)$라 하면 다음을 만족해야 합니다.

그런데 만약 $\alpha_i \stackrel{*}{\Rightarrow} \epsilon$인 경우 $X \to \alpha_i$를 적용했을 시 $X$가 $\epsilon$으로 치환되고 $X$ 다음에 오는 첫 기호가 $a_{n+1}$과 매칭되어야 합니다. 즉, 문장에서 $X$ 다음에 올 수 있는 기호의 집합을 $\text{FOLLOW}(X)$라 하면 다음을 만족해야 합니다.

식 \eqref{eq:first}과 \eqref{eq:follow}를 만족하는 문법을 LL 문법이라고 합니다.조금 더 자세하게는, 다음으로 매칭할 단말 기호 하나만 고려하기 때문에 LL(1) 문법이라고 합니다. LL은 왼쪽에서 오른쪽(Left-to-right)으로 문장을 읽어나가면서 좌측 유도(Leftmost derivation)를 한다는 뜻입니다.

$\text{FIRST}$는 다음과 같은 규칙을 따라 계산할 수 있습니다. 빈 기호열의 $\text{FIRST}$를 공집합이 아닌 ${\epsilon}$으로 정의함에 유의합시다. 이렇게 정의하면 기호열이 빈 기호열로 유도되는지의 여부를 $\text{FIRST}$가 $\epsilon$을 원소로 가지는지로 쉽게 판단 가능합니다.

1. $X \to \alpha_1 \mid \alpha_2 \mid \cdots \mid \alpha_m$ 이면 $\text{FIRST}(X) = \bigcup_{i=1}^m \text{FIRST}(\alpha_i)$
2. 비어있지 않은 기호열 $\alpha$와 $\beta$에 대해,
   1. $\epsilon\not\in\text{FIRST}(\alpha)$이면 $\text{FIRST}(\alpha\beta)=\text{FIRST}(\alpha)$
   2. 그렇지 않으면 $\text{FIRST}(\alpha\beta) = \left[ \text{FIRST}(\alpha) \setminus \{\epsilon\} \right] \cup \text{FIRST}(\beta)$
3. $\text{FIRST}(a) = \{a\}$
4. $\text{FIRST}(\epsilon) = \{\epsilon\}$

한편 $\text{FOLLOW}$의 규칙은 다음과 같습니다.

1. 시작 기호 $S$에 대해 $\$ \in \text{FOLLOW}(S)$
2. $A \to \alpha B \beta$, $\beta \neq \epsilon$이면 $\text{FIRST}(\beta) \setminus \{\epsilon\} \subseteq \text{FOLLOW}(B)$
3. $A \to \alpha B$ 또는 $A \to \alpha B \beta$, $\beta \stackrel{*}\Rightarrow \epsilon$이면 $\text{FOLLOW}(A) \subseteq \text{FOLLOW}(B)$

문헌에 따라 $\text{LOOKAHEAD}$를 정의하여 LL 문법을 정의하기도 합니다. $\text{LOOKAHEAD}(X \to \alpha)$는 생성 규칙 $X \to \alpha$를 이용해 $X$를 치환할 때 다음으로 매칭될 수 있는 단말 기호의 집합입니다.

이때 LL 문법은 임의의 비단말 기호 $X$에 대해 각 단말 기호를 포함하는 $\text{LOOKAHEAD}(X \to \alpha_i)$가 둘 이상이지 않은 것으로 정의됩니다.