먹깨비B의 식사시간

5. 상향식 파싱(Bottom-Up Parsing)

5.0 소개

일반적인 상향식 파싱 기법은 3장에서 소개되었다. 이 장에서는 몇 가지 상향식 파싱 알고리즘을 설명한다.

간략히 말하면, 파싱은 한 언어로 된 입력 스트링과 그 언어의 문법이 주어지면 파스 트리를 구성하는 것이다. 상향식 파서는 밑에서 위쪽으로, 즉, 단말 노드로부터 루트까지의 방향으로 파스 트리를 구성한다.

5.1 LR 문법

하향식 파싱을 위한 문법이 LL문법인 것과 마찬가지로, 상향식 파싱을 위한 문법은 LR 문법이다. 여기에서 L은 입력 스트링을 왼쪽에서 오른쪽으로 읽는다는 것을 나타내고, R은 우측 유도를 생성해낸다는 것을 의미한다.(Left to right scanning Right most derivation) 이때 실제 유도는 역순으로 구성된다.

5.1.1 LR(k) Grammars

3장에서 정의되었던 핸들(handle), 문장형태(sentential form), 우측 유도(right derivation) 등의 용어를 써서 LR(k) 문법을 정의하여 보자.

한 문법이 LR(k)라면, 다음 조건을 만족한다.

우측 유도에서 다음과 같은 문장형태가 있을 때,

αβω

여기에서 ω 와 α 가 빈 스트링으로 유도될 수 있고, ω(if non empty) 가 터미널 심볼들로만 이루어진다면, 핸들 β 는  ω의 좌측 k개 심볼들을 보고서 구분될 수 있다.

실제에서는 k = 1 로 문법을 기술하고, 이를 LR(1) 문법이라 한다. 대부분의 프로그래밍 언어들의 문법은  LR(1)문법이다. LR(0) 문법은 핸들 다음의 심볼을 보지 않고도 파싱할 수 있음을 나타내므로 잘 쓰이지 않으며, 대부분의 프로그래밍 언어의 문법을 LR(0)문법으로 기술하기가 어렵다.

예1) 다음 문법은 LR(0)이 아니다.

1. E → E + T

2. E → T

3. T → T * F

4. T → F

5. F → (E)

6. F → Id

문장형태 "E + T * Id"에서 미리보기(lookahead)가 없다면, 핸들을 E + T(즉, rule 1)로 결정할 수 밖에 없다. 따라서 문장형태는 E * Id로 축소된다. 여기에서 다음 핸들은 Id가 되어(즉, rule 6) 문장형태는 E * F로 되고, 다음 핸들은 F(rule 4)여서 문장형태는 E * T가 된다. 이어서 다음 핸들은 T (rule 2)이어서 문장형태는 E * E로 축소된다. 이때, 이 문장형태에서는 핸들을 발견할 수 없어서 이 문장 형태는 오류가 된다. 즉, 다음과 같은 과정을 밟는다.

E + T * Id  핸들 E + T

E * Id       핸들 Id

E * F        핸들 F

E * T        핸들 T

E * E        핸들 없음

따라서, 이 문법은 LR(1) 문법이다.

예2) 다음문법은 LR(0)이다.

S → a S a

| b S b

| c

한 문법이 LR(k)라는 것을 보이는 것은 그것이 LR(k)가 아니라는 것을 보이는 것보다 어려운 일이다.

L(S) = c, aca, bcb, abcba, aabbbcbbbaa ........ , 즉,  c를 중앙에 가진 a 와 b의 대칭 스트링(symmetric string)의 언어이다. 이 언어의 어떤 문장형태에서도 지나간 심볼을 보지 않고 핸들을 찾고 축소하는 것이 가능하다.

LR(0)문법과 LR(1)문법 사이에는 한 가지 관심이 가는 문법이 있는데, 이것이 SLR(1) 문법이다. 여기에서 S는 간단함(Simple)을 뜻한다. 이 문법으로 많은 프로그래밍 언어들의 구성 요소들을 기술할 수 있다. 이들 문법들 사이의 차이는 우리가 파서를 구성할 때 파싱 테이블을 만드는 방법에 차이가 있다.

5.2 LR 파싱

LR 파서들은 효율적(빠름)이고 오류의 발견이 빠르다. LR 파서의  파싱테이블을 손으로 만들기는 매우 어렵지만, 오늘날에는 주어진 언어의 문법으로 LR 파싱 테이블을 구성해주는 도구들이 많다. 우리는 이들 파서 생성 도구들이 어떻게 동작하는지 알기 위해 LR 파싱 기법을 공부한다.

LL 파서와 마찬가지로, LR 파서도 두부분, 즉, 파싱 테이블과 드라이브 루틴으로 구성할 수 있다.

LR파싱 테이블의 구성하는 과정은 다음의 두 단계이다.

1) item set들로 구성되는 파싱 상태들을 구한다.

2) 구해진 파싱 상태로부터 테이블을 구성한다.

파싱 상태들을 구할 때 미리보기(lookahead)를 쓰지 않으면, LR(0) 파서를 구성한 것이며, 이것은 구성이 쉬우나 언어의 수용 범위가 작게 된다.

상태들을 구할 때 한 개의 미리보기( lookahead)를 쓰면, 이는 LR(1) 파서를 구성한 것이며, 이는 구성하기 어렵고 테이블의 크기가 너무 커지나 수용 언어의 범위가 크게 된다.

따라서, 절충형인 SLR(1)을 씀 -- 상태 구할 때는 lookahead를 쓰지 않고, 테이블을 구할 때만 lookahead 를 쓴다. SLR 파서는 대부분의 프로그래밍 언어를 수용할 수 있다.

LR 파싱의 개념을 익히기 위해서, 이장에서는 SLR(1) 파서를 설명한다. 파싱 테이블을 구성하는 알고리즘을 설명하기 전에, 파싱 테이블을 어떻게 사용하는지를 보인다. 파싱 알고리즘은 shift-reduce 파싱 알고리즘이다.

5.2.1 Shift-Reduce 파싱

LR파서는 Shift-Reduce라 부르는 파싱 형식을 사용한다. 이 방식은 이전에 파싱된 상황을 기록하고 있는 파싱 스택을 사용한다. 이 파서는 스택의 내용과 입력을 참고하여, 다음에 취해야 할 행동을 결정한다.

파싱 스택은 이미 만들어져 있다고 가정한다.

파싱 테이블 구조는 상태 X 문법 심볼의 이차원 테이블이다. 테이블은 두 부분으로 구성되는데, 행동(action) 부분과 GOTO부분이다. 행동 부분은 "shift-reduce"행동을 나타내는데, 상태들이 행을 구성하고, 터미날 심볼들이 열을 구성한다. GOTO부분의 열도 상태들로 구성되고, 행은 난터미널 심볼들로 구성된다.

LR 파싱 테이블:

Shift-Reduce 파서의 4 가지 행동:

Error : 테이블에서 빈자리, 문법 오류를 말함.

Accept: 입력 스트링이 문법적으로 맞음. 파싱 종료 상태

Shift: S#가 가리키는 상태로 전이, 입력 심볼과 S#를 스택에 Push

Reduce: R#는 문법의 생성규칙 번호 임. 스택의 top은 이 생성규칙의 rhs를 가지고 있으므로 이를 pop하여 lhs로 대치함. 다음 상태는 GOTO 에서 가리키는 상태임.

알고리즘:

LR 파싱

스택을 상태 0로 초기화한다.

입력 스트링의 끝에 $를 붙인다.

While Action ≠ Accept AND Action ≠ Error DO

{Stack = s₀x₁s₁ ... x_ms_m and remaining Input = a_ia_i+1 .... $

s는 상태 번호, x는 문법 심볼(terminal or nonterminal)}

Case Table[s_m, a_i] is

S# : Action := Shift

R# :Action := Reduce

Accept: Action := Accept

Blank: Action := Error

EndWhile

예 3  다음 문법에 대하여 파싱 테이블을 구성하고 문장을 파싱하여 보자.

1. E → E + T

2. E → T

3. T → T * F

4. T → F

5. F → (E)

6. F → Id

다음과 같이 파싱 테이블이 이미 구성되어 있다고 간주하자. 파싱 테이블은 상태 수 X 문법 심볼 수의 크기로 구성된다.

위의 문법과 주어진 LR파싱 테이블을 가지고 다음의 입력 문장을 파싱해 보자

id * ( id + id )

다음은 파싱 과정을 보인다. 이어서 각 단계를 설명한다. 스택의 탑은 오른쪽이다.

     스택(Stack)              입력(Input)               행동(Action)

(1)  0                       id * ( id + id ) $        S5

(2)  0id5                       * ( id + id ) $        R6

(3)  0F3                        * ( id + id ) $        R4

(4)  0T2                        * ( id + id ) $        S7

     0T2*7                        ( id + id ) $        S4

     0T2*7(4                        id + id ) $        S5

     0T2*7(4id5                        + id ) $        R6

     0T2*7(4F3                         + id ) $        R4

     0T2*7(4T2                         + id ) $        R2

     0T2*7(4E8                         + id ) $        S6

     0T2*7(4E8+6                         id ) $        S5

     0T2*7(4E8+6id5                         ) $        R6

     0T2*7(4E8+6F3                          ) $        R4

     0T2*7(4E8+6T9                          ) $        R1

     0T2*7(4E8                              ) $        S11

     0T2*7(4E8)11                             $        R5

     0T2*7F10                                 $        R3

     0T2                                      $        R2

     0E1                                      $        Accept

과정 1

파싱은 스택에 상태 0를 넣고, 입력의 끝에는 $를 추가하여 시작한다.

스택              입력 스트링            행동

(1) 0               id * (id + id) $

파싱 알고리즘에 따라 테이블을 참조하면, 상태 0에서 입력 심볼 id는 행동 S5, 즉, 입력 심볼을 스택에 넣고 상태 5로 전이하라는 것이다.

과정 2

스택              입력 스트링        행동

(1) 0              id * (id + id) $      S5

(2) 0 id 5        * (id + id) $

이때, 테이블을 참조하면, 상태 5에서 입력 심볼 *는 행동 R5로 생성규칙 6번의 오른쪽이 축소할 핸들임을 말한다. 따라서, 스택에서 핸들에 해당하는 부분을 모두 지우게 되는데, 이 부분이 id 5이다. 따라서 스택에는 0만이 남는다. 생성 규칙 6의 왼쪽 부분(F)이 스택에 넣어지기 때문에, 테이블에서 상태 0과 F에 해당하는 GOTO부분을 참조하여야 한다. 이 엔트리는 3이므로 이것을 스택에 넣는다.

과정 3

스택                입력 스트링        행동

(1) 0                id * (id + id) $      S5

(2) 0 id 5          * (id + id) $          R6

(3) 0 F 3           * (id + id) $

이제, 스택의 탑은 상태 3이고, 현재 입력 심볼은 * 이므로, 테이블은 생성규칙 4번으로 축소하라는 행동 R4이다. 따라서 생성규칙 4번의 오른쪽은 스택의 탑 부분인 핸들이다. 알고리즘은 스택의 탑을 제거하고 생성규칙 4번의 왼쪽인 T를 넣고, 상태 0에서 T 일 때의 GOTO테이블에서 다음 상태인 상태 2를 얻어 스택에 넣는다.

이와 같은 방법으로 나머지 과정을 수행하고 나면, 우리는 마지막 과정인 과정 19에 다다른다.

과정 19

스택의 탑은 상태 1이고 입력 심볼은 $이다. 이때, 테이블은 행동 Accept를 표시하고 있으므로, 파싱은 완저히 성공적으로 끝나게 된다. R2부터 R6까지의 파싱 과정의 축소 행동을 역으로 따라가면, 우리는 파스 트리를 만들 수 있다.

파싱 과정 중, 우리는 항상 다음과 같은 스택과 입력 스트링의 상태를 유지했다.

Stack                  Input

s₀x₁s₁ ... x_ms_m         a_ia_i+1 .... $}

여기서 s는 상태를 표시하고, x는 터미널과 난터미널의 나열을 표시하며, a는 입력 심볼들이다. 이것은 스택의 탑이 지금까지의 파싱 과정에 대한 정보를 누적하고 있는 유한 상태 기계와 같이 보인다.

우리는 무엇을 하여야 하는지 알기 위해서 단지 스택의 탑과 입력 심볼을 보아야 한다.

5.2.2 SLR 테이블 만들기

우리는 문법의 생성규칙들로부터 각각의 상태가 아이템(item)들의 집합인 위와 같은 유한 상태 기계를 구성할 수 있다.

Items: 포지션 마크("·")가 있는 생성규칙, 즉 LR(0) Item

   ex) E → E · + T

   즉, 파싱 과정 중 E로부터 유도될 수 있는 스트링 중 E는 이미 확인했고, 앞으로 + T를 보려한다.

Item들을 모아서 Item set을 구성하고, 한 Item set이 한 상태가 된다.

알고리즘:

Constructing States

(0) 새 nonterminal S'를 만들어 S' → S인 새로운 생성규칙을 문법에 추가한다.

(1) S가 시작 심볼이면, S' → ·S를 시작상태 상태0에 추가한다.

(2) Closure: 상태에 A → x ·Xα가 있으면, 문법에 있는 모든 X → ω에 대하여 Item X → ·ω를 상태에 추가한다.

(3) 새로운 상태를 생성하기: 현재 상태에 있는 모든 A → x ·zω에 대하여 A → xz ·ω를 가지는 새 상태를 만든다. 새 상태는 서로 다른 모든 z에 대하여 만든다.

(4) 더 이상 새로운 상태가 만들어지지 않을 때까지 (2)와 (3)을 반복한다.

예4) 다음 문법의 상태들을 만들어 보자.

1. E → E + T

2. E → T

3. T → T * F

4. T → F

5. F → (E)

6. F → Id

Step 0

E' → E를 문법에 추가한다.

0. E' → E

1. E → E + T

2. E → T

3. T → T * F

4. T → F

5. F → (E)

6. F → Id

Step 1

State 0

E' → ·E

Step 2

Sttate 0의 Closure를 구하여 State 0에 추가한다.

State 0

E' → ·E

E → ·E + T

E → ·T

T → ·T * F

T → ·F

F → ·(E)

F → ·Id

Step 3

State 0에 대하여 알고리즘의 (3)을 적용하여 새로운 상태들을 만든다.

State 1

E' → E·

E → E ·+ T

State 2        State 3        State 4        State 5        State 6

E → T·         T → F·           F → (·E)       F → Id·        E → E +· T

T → T·* F                          E → ·E + T                       T → ·T * F

                                          E → ·T                              T → ·F

                                          T → ·T * F                         F → ·( E )

                                           T → ·F                               F → ·Id

                                            F → ·( E )

                                            F → ·Id

State 7        State 8        State 9        State 10       State 11

T → T *·F    F → ( E·)     E → E + T·   T → T * F·   F → ( E )·

F → ·( E )    E → E·+ T    T → T·* F

F → ·Id

SLR(1)테이블 구성

이 상태들을 이용하여 LR(0) 파싱테이블을 구성할 수 있다. 그러나 이 문법이 LR(0)문법이 아니기 때문에(예 1과 같이), 이들을 SLR Item으로 보고 lookahead를 동원하여 SLR(1)테이블을 구성한다.

알고리즘

Constructing of an SLR(1) Parsing Table

(1) Shift:

   상태 m에 A → x·aω가 있고, 입력 a 에 대하여 상태 n에 A → xa·ω가 있으면, Table[m,a] = Sn 이다.

(2) Reduce:

   상태 n에 A → ω·가 있으면 Table[n,a] = Ri이다. 이때 I 는 생성규칙 A → ω의 번호이고, a 는 FOLLOW(A)이다.

(3) Accept:

   상태 n에 S' → S·가 있으면, Table[n,$] = Accept이다.

(4) GOTO's:

   상태 m에 A → x·Bω가 있고, 상태 n에 A → xB·ω가 있으면, Table[m,B] = n 이다.

예5) 예4에서 구해진 상태들을 이용하여 SLR(1)파싱 테이블을 구성하자.

5.2.3 Shift-Reduce 충돌

때때로, 파서는 한 생성규칙에 대하여 쉬프트를 계속할 것인지, 또는, 다른 생성규칙으로 축소할 것인지를 결정할 수 없는 때가 있다.

shift-reduce충돌은 한 상태에서 하나의 lookahead에 대하여 Shift해야 할지, 아니면, 스택의 핸들을 Reduce해야 할지 결정할 수 없는 상태로, 파싱테이블을 구성할 때 한 엔트리에 두 개 이상의 행동이 기록된다. 이것은 문법이 SLR(1)문법이 아님을 (혹은 LR(1)테이블이라면, LR(1)문법이 아님을)말하고 있다.

한 가지 해결책은 문법을 다시 기술하는 것이고, 다른 방법은 가능하다면, 상황을 분석하여 어느 행동이 적합한지를 결정하는 것이다.

대개의 경우, 축소되는 생성규칙과 입력 심볼의 순위를 비교하여, 생성규칙의 순위가 높으면 축소(reduce)를, 그렇지 않으면 쉬프트(shift)를 선택한다. 같은 우선순위의 경우는 결합법칙을 이용하여, 좌측 결합을 만족하면 축소(reduce)를, 우측 결합을 만족하면 쉬프트(shift)한다.

5.2.4 Reduce-Reduce충돌

때때로, 파서는 여러 개의 생성규칙에 대하여 축소하여야 하는 상황이 발생할 수 있다. 즉, reduce-reduce충돌은 스택의 핸들이 한 개 이상의 생성규칙에 대하여 축소(reduce)를 표시하는 경우이다. shift-reduce충돌 때와 마찬가지로, 문법이 SLR(1) 문법이 아니면, 테이블의 한 엔트리에 축소할 한 개 이상의 생성규칙이 표시된다.

이 경우의 충돌 해결은 축소되는 생성규칙들의 우선순위를 비교하여, 우선 순위가 높은 것을 선택한다.

5.2.5 LR파서의 종류

LR(0)파서

SLR(1)파서

LR(1)파서

LALR(1)파서

5.2.6 LR 파서 생성기

지금까지의 하향식 파싱 알고리즘을 논의한 결과로, 실제의 프로그래밍 언어를 위한 LR 파서를 손으로 만든다는 것은 매우 어려운 일임을 알게 되었을 것이다. 따라서, 수많은 프로그래머들이 LR 파서를 생성하는 파서 생성기들을 제작하였고, 우리는 이들을 선택하여 사용할 수 있게 되었다. 이들중 가장 유명한 것은 아마도 유닉스 운영체제에서 LALR(1) 파서를 생성하는 YACC(Yet Another Compiler Compiler)일 것이다.

우리는 7장에서 YACC를 사용하여 파서를 자동 생성하는 예를 보게된다.