[컴파일러] Bottom-up 파싱이란? 그리고 shift-reduce parsing (이동-감축 구문분석)

Bottom-up parsing

  Top-down 파싱은 시작기호로부터 인풋 문자열을 최종적으로 유도해간다. 파싱테이블을 이용해 확장, 제거해가며 인풋 문자열을 구성해나간다. 좌단 유도 순서로 구문분석하여 직관적이다.

  반면 Bottom-up 파싱은 인풋 문자열에서 시작하여 감축해가며 시작기호를 찾아간다. 우단 유도의 역순으로 구문분석한다. 여기서 배울 것은 Bottom-up parsing이고, 감축과 핸들의 개념을 기본적으로 알고 가야 한다.

 

∨ 감축, reduce : 생성규칙의 역순으로 대체하는 것

                      즉 감축 대상이 어떤 규칙의 right hand side와 동일하면 left hand side로 대체한다.

∨ 핸들, handle : 감축 대상

 

바텀업 파싱을 간단히 말하자면,

핸들을 결정하여 감축감축 해가면서 생성 규칙의 시작 기호까지 도달해야 Bottom-up 파싱에 성공하는 거다.

 

---

Bottom-up parsing 종류

1. shift-reduce parsing (이동-감축)

2. operator precedence parsing (연산자 우선순위) : 공부 안 할 거다!

3. LR parsing (left to right & right parse)

└> 현재 가장 보편적인 파싱 방법!

 

 

하나하나 공부해 볼 거다.

지금은 shift-reduce parsing을 공부하자.

이 파싱법은 bottom-up 파싱 과정이 명확하게 보인다!

 

---

shift-reduce parser의 구성

ㄴ stack

ㄴ input buffer

$ : 스택의 bottom marker, 입력 문자열의 끝을 가리키는 end marker

 

---

Shift와 Reduce

 

∨ shift : 입력 버퍼에 있는 문자를 스택에 시프트시키는 것

∨ reduce : 스택 탑에서 핸들을 발견하면 생성규칙의 left hand side로 감축하는 것

 

=> shift-reduce 구문 분석 과정

ⓐ 인풋 스트링을 스택에 shift해가는데, 언젠가 핸들을 발견한다.

ⓑ 스택에서 핸들을 찾으면 reduce하고 부분 파스트리를 구성한다.

ⓒ 위 두과정 반복

ⓓ 결론적으로 스택에서 시작심볼(S)로 감축 성공하면 구문분석 성공!

  즉 인풋스트링은 맞는 문장이 된다.

 

---

예제 2개

- 미완성 -

 

익숙한 단골 예제들로 공부해보잣

 

예제1

<이젠 넘 익숙한 예제>

인풋 문장 : id+id*id

생성규칙

1. E -> E + T

2. E -> T

3. T -> T * F

4. T -> F

5. F -> (E)

6. F -> id

 

 

예제2

인풋 문장 : id+id*id

생성규칙

1. E -> E + E

2. E -> E * E

3. E -> id

4. E -> (E)

 

 

 

 

 

---

shift-reduce의 문제점

(예제에서 보았듯이)

 

① 핸들을 어떻게 찾을 건데?

    == shift를 더 할지, 그만 reduce할지 선택 문제

 

② 찾은 핸들에 어떤 생성규칙을 적용할 건데?

    == reduce 방법이 여러가지 있는 경우

    == 스택 탑에서 어디까지를 handle로 볼지의 문제

    (문법이 모호하지 않더라도 이런 상황이 가능함)

 

위 두가지가 문제이다!

그치만 해결 방안으로 LR 파싱이 있다 - 가장 보편적인 파싱 방법이다.

LR파싱은 다음 글에 정리하는 걸루..