[컴파일러 이론] 4. Top Down Parsing, LL(1) Grammar

 

이전글에 이어서 Parser를 계속 알아보자.

 

 

2025.11.23 - [컴파일러] - [컴파일러 이론] 3. Syntax analysis, Parser, CFG, Parse Tree, AST

[컴파일러 이론] 3. Syntax analysis, Parser, CFG, Parse Tree, AST

이번 글의 목적은 CFG로부터 Parse Tree를 만드는 것이다.

 

Top Down Parsing

먼저 top down parsing이 뭔지 알아보자.

 

아래 같은 간단한 CFG를 생각해보자.

예를들어 (1+2+(3+4))+5 라는 식이 이 CFG에 맞는지 파악을 해야한다.

S

→ E + S

→ (S) + S

→ (E + S) + S

→ (1 + S) + S

...

 

top down parsing은 이런 식으로 leftmost derivation, 즉 매번 왼쪽부터 훑으면서 변환을 수행하는 것이다.

이번에는 다른 예시이다.

사람에게 이 CFG가 (int)라는 문장을 accept하는지 보는 것은 쉽다.

E

→ T

→ (E)

→ (T)

→ (int)

라는 것을 바로 알 수 있다.

하지만 컴퓨터는 E를 바꿀 때 두가지 선택지(T, T+E)중 무엇을 선택할지 모른다.

그래서 컴퓨터는 무식하게 첫번째 선택지부터 해보고 틀리면 되돌리는 방식을 쓴다.

맞는지 틀렸는지는 만들어야하는 문장과 앞에서부터 비교한다.

판단은 terminal이 parse tree에 생기면 그때 수행한다.

step2, step3에서는 만들어야하는 문장의 가장 앞인 '('가 아닌 terminal이 왔다. 따라서 틀렸다고 판단한다.

 

---

Top Down Parsing의 한계

위의 똑같은 CFG에서 이번에는 int · int를 만들어보자.

방금 설명한 방법대로 한다면 컴퓨터는

E → T → int 

이렇게 만들고 끝내버릴 것이다.

int라는 terminal이 나와서 만들어야하는 문장과 앞에서부터 비교했더니 int로 동일하고, 더이상 남은 non-terminal도 없으므로 production을 적용하지 않을 것이다.

 

원인을 찾아보면 T → int, T → int · T 이렇게 같은 걸로 시작하는 다른 production이 있기 때문이다.

이런 현상을 multiple match라고 한다.

 

어쩃든 이게 우리가 원하는 문장은 아니다.

 

따라서 우리는 Grammar를 더 엄격하게 만들어서 이런 문제가 해결된 top down parsing 방법을 만들 수 있다.

 

---

LL(1) Grammar

LL(1) 문법은 multiple match를 없애기 위해 나온 더 까탈스러운 문법이다.

 

left factoring

S → E + S | E

라는 production은 multiple match를 없애기 위해

 

S → ES'

S' → +S | $\varepsilon$

처럼 두 줄로 바꾸면 된다.

 

즉 문제가 되는 두 production의 공통 앞부분을 인수분해하듯이 묶어 새 production으로 만들어버리는 것이다.

이 방법을 left factoring이라고 한다.

 

Left Recursion

S → Sa 

같이 같은 문자가 우변의 좌측에 있어 production은 무한히 적용이 된다.

이런 경우를 left recursion이라고 한다.

 

아래와 같은 경우,

S → Sa | b

 

아래처럼 두 줄로 바꿔 right recursion을 만들 수 있다.

S → bS'

S' → aS' | $\varepsilon$

 

Predictive parsing

위에서 본 것처럼 한가지 production을 적용했다가 틀리면 다시 되돌아가는 backtracking이 있는데,

이 backtracking없이 적합한 production을 선택해 parsing하는 것을 Predictive Parsing이라고 한다.

 

LL(1)의 의미

L : 주어진 입력, 즉 parsing 해야하는 문자열을 Left-to-right방향으로 읽는 것

L : 파싱과정에서 왼쪽 부터 변환하는 Leftmost derivation을 만든다.

1 : 1개의 lookahead token을 사용한다. 파싱이 아직 안된 문자열의 가장 왼쪽 문자 하나를 먼저 보고 어떤 production을 적용할 지 선택한다.

 

parsing table

파싱테이블은 어떻게 파싱을 하면 되는지 알려주는 표이다.

 

아래 예시에서 어떤식으로 동작하는지 보면,

 

1. 시작의 S와 unparsed part인 '('을 보고 S→ES' 을 선택한다.

 

2. ES'의 첫 글자 E와, '('를 보고 E→(S)를 선택한다.

ES' → (S)S' 이 된다.

 

3. 이제 '('는 parsing되었으므로 그 다음 글자 S와 1을 확인한다.

S와 num이므로 S→ES'을 선택하여 (S)S' → (ES')S'이 된다.

 

4. 반복한다.

이런 파싱테이블을 코드로 바꿔 실제 구현하면 컴파일러의 parser 부분을 만들 수 있다.

---

현재 흐름을 잡기 위해 간단히 정리를 해보자.

컴파일러는 아래의 7단계를 거쳐서 우리가 타이핑한 코드 → 어셈블리 코드 로 변환한다.

 

Scanner : 소스코드의 각 단어를 토큰으로 분류하는 과정

1. 각 토큰의 패턴을 RE로 나타낸다.

2. RE를 NFA로 바꾸고, NFA를 DFA로 바꾼다.

3. DFA를 코드로 바꾼다.

 

Parser : 토큰여러개를 모아 어떤 문장의 구조를 분석하는 과정

1. CFG를 통해 원하는 문장의 구조를 표현한다. ex) assign → var = ID ;

2. CFG에 맞는 parse table을 만든다.

3. 주어진 문장을 parse table에 따라 derivation을 거쳐 parse tree로 만든다.

4. parse tree를 보고 문장을 분석한다.

 

이번 글에서 Parser의 2,3번 과정을 다뤘는데, 생략된 부분이 있다.

CFG를 보고 Parsing table를 어떻게 만드는지 그 방법을 얘기하진 않고,

그냥 CFG에 맞는 parsing table을 갑자기 어디선가 가져와서 derivation을 진행했다.

 

다음 글에서는 이 과정을 알아보자.