21 - Bottom Up Parsing

Bottom-up Parsing은 string 에서 식을 조합하여 스타팅 포인트로 가는 방법이다.

 

S -> aAcBe
A -> Ab
A -> b
B -> d

이러한 식이 있고,

abbcde 라는 string 이 주어졌을때, 치환하면서 스타팅 포인트로 갈 수 있다.

 

먼저 b를 non-terminal A로 치환하면, aAbcde가 된다.

여기서 Ab를 A로 치환하면 aAcde가 되고,

d를 B로 치환하면 aAcBe가 된다.

이는 스타팅 포인트 이므로 결론에 도달하였으니 올바르게 선언된 string이라고 볼 수 있다.

 

 

 

Shift-Reduce 개념

---

E -> E + T
E -> T
T -> T * F
T -> F
F -> a

이 식의 + *는 터미널의 이름일 뿐이고, 연산자가 아니다.

SHIFT는 왼쪽부터 Syntax Analysis 스택에 옮기는 작업을 말하고,

REDUCE는 치환하는 과정을 말한다.

a + a * a가 주어졌을때 SHIFT 와 REDUCE를 통해 결론을 만들 수 있다.

 

1. 먼저 a를 shift한다. 이제 stack에는 a가 존재한다.

2. stack의 a는 reduce를 통해 F로 치환된다.

3. reduce를 통해 F는 T로 치환된다.

4. reduce를 통해 T는 E로 치환된다.

5. +를 shift (현재 E +)

6. a를 shift (E + a)

7. reduce를 통해 a를 F

8. reduce를 통해 F는 T

9. *를 shift (현재 E + T *)

10. a를 shift (E + T * a)

11. a를 F로 reduce (E + T * F)

12. T*F를 T로 reduce (E + T)

13. E+T를 E로 reduce (E)

스타팅 심볼로 돌아왔으므로 유효한 string 이다.