[컴파일러] 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
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파싱은 다음 글에 정리하는 걸루..