[Compiler Design] LL Parsing

 

 

 

LL 파싱은 Top-Down 파싱을 구현하는 방법으로 입력 문자열을 왼쪽에서 오른쪽으로 차례차례 읽고, 문법 전개 시 좌측유도를 따르는 파싱 방법이다. 

 

단순히 Top-Down 파싱만 사용한다면 어떤 규칙을 적용할지, 이 규칙을 적용했을 때 입력과 맞을지를 사람이 직접 고민해야 했는데,

LL 파서는 FIRST / FOLLOW 집합을 계산하고 Parsing Table을 만들어 LOOKAHEAD를 하나만 보면 규칙이 자동으로 정해지도록 한다. 

 

일반적인 Top-Down 파싱에서는 시작 심벌의 첫 번째 생성규칙에서 유도를 시작해 문자열을 생성한다.

 

유도 과정에서 생성된 문자열과 입력 문자열을 차례로 비교하고, 유도된 문자열과 입력된 문자열이 같으면 계속 비교를 이어가고,

다르다면 직전 생성 규칙을 잘못 적용했다고 인지하고 원위치 시키고 다른 생성 규칙을 적용한다. (Backtracking)

비교와 백트래킹을 이어가다가 더 이상 적용할 생성 규칙이 없다면 입력 문자열은 틀린 문장으로 인식한다. 

 

반면 LL 파싱에서는 현재 입력 문자와 생성된 Terminal이 같지 않으면 틀렸다고 간주하고, 백트래킹 하지 않아 빠르다.

제대로 된 LL(1) 문법이라면 선택지가 2개 이상일 수가 없다. 그러니 백트래킹을 하지 않아도 됨이 보장된다.

 

Left to Right Scanning - 입력 문자열은 왼쪽부터 오른쪽으로 차례대로 읽는다.

Leftmost Derivation - 좌측유도를 따라 Parse Tree를 구성한다.

 

다만 모호한 문법을 처리할 수 없으니 문법을 LL-Friendly하게 변환해줘야 한다. 

 

초기에는 Top-Down 파싱도 많이 사용했고, 일반적인 gcc에서도 Top-Down 파싱을 많이 사용하지만.. 

백트래킹때문에 파싱 속도가 느리다. (오류가 있는 구문을 줬을 때 컴파일 속도가 느리다. 모두 찾아야 하니..)

 

 

입력 문자를 보고 적용될 생성 규칙을 결정적으로 선택하여 유도한다. 

즉 애초에 LL으로 가능한 문법만 처리할 수 있고, 입력 문자에 대해 적용할 생성 규칙을 미리 뽑아 두고 시작해야 하는데

여기서 FIRST / FOLLOW / LOOKAHEAD가 필요하다.

 

 

$$ \text{FIRST}(A) = \{\, a \in V_T \cup \{\varepsilon\} \mid A \Rightarrow^{*} a\gamma, \; \gamma \in V^{*} \,\} $$

 

 

FIRST는  Nonterminal A로부터 유도돼서 첫 번째로 나타날 가능성이 있는 Terminal의 집합을 의미한다. 

파싱 테이블을 만들기 위해 모든 Nonterminal에 대해 FIRST(X) 를 구해야한다.

 

X가 Terminal이면 당연히 FIRST(X)는 자기 자신이 되고, X -> ab 생성규칙이 있으면 a가 FIRST(X)에 포함된다.

이 때 생성규칙이 NULL을 포함한다면 FIRST(X)에도 NULL이 포함되고, A가 NULL을 유도할 수 있다면 A는 NULLABLE 하다.

 

A -> XXX 규칙에서 A는 Left Hand Side이고 XXX는 Right Hand Side이다.

 

\[
\text{if } \varepsilon \notin A \quad \text{then } \; A \oplus B = A
\]
\[
\text{if } \varepsilon \in A \quad \text{then } \; A \oplus B = (A - \{\varepsilon\}) \cup B
\]

 

Ring Sum (⊕) 연산자는 여러 FIRST 집합을 합칠 때 사용한다. 

 

 

A → aB | bC

 

 

이런 생성규칙이 있다고 하자. FIRST 집합은 LL 파싱에서 어떤 생성 규칙을 선택할지 결정할 때 사용된다.

입력이 a인 경우 aB를 선택한다. 입력이 b인 경우 bC를 선택한다.

 

FIRST(aB) = { a } FIRST(bC) = { b }

이렇게 미리 계산해둔다면 파서가 입력을 보자마자 어떤 생성규칙을 판단할 수 있다. 

그러니 LL 파서를 만들기 위해 문법에 등장하는 모든 기호(Nonterminal + Terminal + NULL) 에 대해 FIRST 집합을 구해 둬야 한다.

그래야 Parsing Table을 만들 수 있고, 파싱 할 때 lookahead 기호 하나만 보고 규칙을 확정할 수 있다.

 

 

FIRST 구하기 

 

1. 초기에 모든 Nonterminal의 FIRST를 공집합으로 설정한다. (아직 규칙을 보지 않은 상태)

2. 규칙에서 바로 Terminal 또는 NULL이 나오는 경우 한 번 반영하면 더 이상 고려하지 않아도 되니 FIRST에 반영 후 제거한다.

3. 남은 생성 규칙은 Nonterminal로 시작하니 Ring Sum 연산으로 반복하며 FIRST를 갱신한다.

 

즉, 한 번에 끝나는게 아니고 여러 차례 반복해야 FIRST를 제대로 구할 수 있다. 

\[
FIRST(A) = FIRST(\alpha_1) \cup FIRST(\alpha_2) \cup \cdots \cup FIRST(\alpha_n)
\]

 

 

LL 파싱 시 FIRST만으로는 해결되지 않는 규칙이 있다. 이 규칙을 해결하기 위해 FOLLOW를 함께 구해야 한다. 

 

S → Ab
S → c
A → a | ε

 

이런 생성규칙에서 입력이 b인 경우 Ab를 사용하려고 한다.

A는 NULL으로도 유도될 수 있으니 Ab 는 b로 유도되지만, FIRST만 가지고는 A를 전개할 때 a로 갈지 NULL으로 갈 지 결정할 수 없다.

 

당연히 사람은 저걸 보고 NULL로 유도하겠지만 LL 파서는 lookahead 한 글자만 보고 기계적으로 규칙을 선택해야 한다.

이 때 선택의 기준은 FIRST와 FOLLOW집합 뿐이다.

 

NULL을 선택했을 때, 그 다음 기호 b와 일치하는지는 그 다음에 나올 FOLLOW(A)를 확인해야 알 수 있다. 

FOLLOW(A)는 A뒤에 올 수 있는 터미널의 집합으로, 위의 규칙에서 FOLLOW(A)에는 b가 들어간다. 

 

lookahead가 b인데 b는 FOLLOW(A) 에 속하니 파서는 A를 NULL로 유도하면 된다고 판단한다.

 

 

\[
\mathrm{FOLLOW}(A) = 
\{\, a \in V_T \cup \{\$\} \mid S \;\Rightarrow^{*}\; \alpha A a \beta,\; \alpha,\beta \in V^* \,\}
\]

 

$는 입력 스트링의 끝을 표기하는 심벌이고, 시작심벌은 $를 초기값으로 가진다.

 

 

FOLLOW 구하기 

 

1. if A → αBβ, β ≠ ε then
FOLLOW(B) = FOLLOW(B)U(FIRST(β)-{ε})

2. if A → αBβ then
FOLLOW(B) = FOLLOW(B) U FOLLOW(A)

 

 

1 - B 뒤에 β가 있으면 B 다음에 보일 수 있는 첫 번째 터미널은 β가 시작할 수 있는 터미널이다.

그러니 FIRST(β) 에서 NULL을 뺀 결과를 FOLLOW(B)에 넣어준다. 

 

2 - A가 있던 자리를 aBβ가 대체했고 β가 사라질 수 있으면 결국 B가 A가 있던 자리의 끝부분으로 붙게 된다.

그러니 FOLLOW(A)가 B 다음에도 그대로 올 수 있다. 

 

\[
\text{예제 문법:} \quad
E \to T E', \qquad
E' \to + T E' \mid \varepsilon, \qquad
T \to a
\]
\[
\text{FIRST 집합:} \quad
FIRST(\{a\}) = \{a\}, \quad
FIRST(E') = \{+, \varepsilon\}, \quad
FIRST(T) = \{a\}
\]
\[
\text{초기화:} \quad
FOLLOW(E) = \{\$\}, \quad
FOLLOW(E') = \varnothing, \quad
FOLLOW(T) = \varnothing
\]
\[
(1)\; FOLLOW(E) = \{\$\}
\]
\[
(2)\; E \to T E' \;\;\Rightarrow\;\;
FOLLOW(T) \supseteq FIRST(E') - \{\varepsilon\} = \{+\}
\]
\[
(3)\; E \to T E' \;\;\text{에서 } E' \Rightarrow^* \varepsilon \;\;\Rightarrow\;\;
FOLLOW(E') \supseteq FOLLOW(E), \qquad
FOLLOW(T) \supseteq FOLLOW(E), \; FOLLOW(E')
\]
\[
FOLLOW(E') = FOLLOW(E') \cup FOLLOW(E) 
= \varnothing \cup \{\$\} 
= \{\$\}
\]
\[
FOLLOW(T) = FOLLOW(T) \cup FOLLOW(E) \cup FOLLOW(E') 
= \{+\} \cup \{\$\} \cup \{\$\} 
= \{+, \$\}
\]
\[
\text{따라서 최종 결과:}\quad
FOLLOW(E) = \{\$\}, \qquad
FOLLOW(E') = \{\$\}, \qquad
FOLLOW(T) = \{+, \$\}
\]

 

FIRST와 FOLLOW 집합은 서로 전파되면서 채워지는 구조이니 한 번 적용하는거로는 모두 구할 수 없다.

특히 NULLABLE 규칙이 적용된다면 전파가 꼭 필요하다.

그러니 보통 모든 규칙을 적용하고, 결과를 확인하고 변화가 없을 때 까지 규칙 적용을 반복한다.

 

FIRST와 FOLLOW는 LL파서가 사용할 수 있는 문법을 만들기 위해 구한다.

일반 파싱은 백트래킹 사용하기에 너무 느리다. 결정적인 LL 파서를 사용한다. 

 

LL 파서에서 현재 보고 있는 입력 토큰이 어느 규칙을 선택하는지 결정할 때 FIRST 집합을 사용한다.

NULLABLE 규칙 때문에 FOLLOW 집합을 참고한다.

 

 

 

 

Left-Recursion은 무한 루프의 가능성이 있다. 

예시만 보더라도, 기계는 언제 두 번째 규칙을 적용해 E를 T로 변환하는지 알 수 없다. 

 

그러니 Right-Recursion으로 무한 루프의 가능성을 제거한다.

LL 파서에서는 Right-Recursion으로 문법을 정의하는게 유리하다. 

 

문법이 주어지고, 그 문법에서 LL 문법을 찾아내는 알고리즘이 있으면 좋겠지만..

아직 그런건 없으니 모호성 제거 / Left-Recursion 제거 등을 수행하고 문법이 LL문법을 만족하는지 확인한 후 LL 파싱을 진행해야 한다.

 

어떤 규칙이 적용됐을 때 제일 처음에 나올 수 있는 Terminal을 LOOKAHEAD라고 부른다.

 

$$
\text{LOOKAHEAD}(A \to X_1 X_2 \ldots X_n) 
= \text{FIRST}(X_1) \oplus \text{FIRST}(X_2) \oplus \cdots \oplus \text{FIRST}(X_n) \oplus \text{FOLLOW}(A)
$$

 

 

 

즉, LL(1) 문법인지 확인하기 위해 FIRST FOLLOW를 구했고 교집합이 있는지 확인한다.

LOOKAHEAD를 통해 LL(1) 문법인지 확인하는 절차를 더 간단하게 수행하는 것.. 한 번에 검사할 수 있으니까. 

 

LL 문법은 모호하지 않아야 하고, Left Factoring이 없어야 하고, Left Recursion도 없어야 한다.

이 세 가지를 잘 조작해서.. LL(1) 문법을 만들고, 문법을 만들었으면 LOOKAHEAD를 계산해서 제대로 된 LL 문법인지 확인하자.

 

 

---

 

 

 

 

LL(1) Parser를 구현하는 방법으로는 두 가지가 있다. 

 

1. Recursive Descent Parser

재귀를 사용하고 Non-Terminal 마다 한 개의 프로시저로 처리한다.

 

void pa(){
    if (nextSymbol == ta )
	    nextSymbol = get_nextSymbol();
    else error();
}
void pb() {
    if (nextSymbol == tb )
	    nextSymbol = get_nextSymbol();
    else error();
}

void pS() {
    if (nextSymbol == ta) {
	    pa(); pA(); pb();
    }
}
void pA() {
    switch (nextSymbol) {
        case ta : pa();pS(); break;
        case tb : pb(); break;
        default: error();
    }
}

 

 

$$
S \;\to\; a \, A \, b \\
A \;\to\; a \, S \;\mid\; b
$$

 

이 문법을 실제로 구현할 때 저렇게 하나씩 프로시저와 매칭시킨다.

gcc도 이 방식으로 구현됐고.. 보통 ANTLR같은 도구를 통해 자동으로 만든다.

 

 

 

2. Predictive Parser

Recursive Descent Parser는 직관적이지만 프로그램의 생성 규칙이 바뀌면 새로 작성해야 한다는 단점이 있다.

문법이 자주 변하는 경우 Predictive Parser를 사용하자.

 

Push Down Automata를 기반으로 만들어진다.

 



 

 

지금 들어온 심볼과 지금 읽고 있는 규칙으로 Table을 만들어 두면 기계적으로 파싱할 수 있다.

 

다음 토큰 및 규칙을 확인하고, LHS와 RHS로 현재 Symbol과 Alpha를 읽는다.

더 이상 읽을 토큰이 없을 때 까지 반복 

 

Table을 만들 때, LL(1) 문법이 되기에는 모호성이 있어 여러 조건으로 전이될 수 있다면 LL(1) 문법이 아니다.

즉, 테이블을 만들 때는 LL 조건, Strong LL 조건을 모두 만족하는걸 확인한 후..

 

 

 

 

 

스택을 두고 입력을 한 글자씩 읽어간다고 보면 된다. 

스택의 Top이 Non-Terminal이면 파싱 테이블을 참조해서 규칙을 적용하고,

스택의 Top이 Terminal이면 pop + advance

 

 

LL(n) 문법에서 n이 커질수록 문법을 대충 써도 결정적인 문법이 되니 LL(1) 문법을 만드는 과정을 밟지 않아도 되지만,

LOOKAHEAD 토큰을 복잡하게 관리해야 하고 테이블이 지수적으로 커져 실용성이 낮다.

 

그러니 대부분의 프로그래밍 언어는 LL(1) 문법이나 LR Parser를 사용한다.