[컴개/CI] Bottom-Up 구문 분석, Shift와 Reduce

Top-Down vs. Bottom-Up

아래는 입력이 '(a + a)'가 들어온 경우

Top-Down과 Bottom-Up 방식으로 파싱한 과정이다.

이때, Bottom-Up 방식이 조금 더 자연스럽다.

 

이때, Top-Down에 비해 Bottom-Up 방식이 더 강력한데,

생성 규칙을 선택할 때, Top-Down에 비해 더 많은 토큰을 볼 수 있기 때문이다.

따라서 Top-Down으로 파싱 시 불가능했던 left-recursion을 파싱할 수 있다.

 

위 그림에서 볼 수 있듯이 Top-Down 방식은 파싱 시 root를 찾아야 하지만,

Bottom-Up은 root를 찾을 필요 없이, 아래에서만 파싱할 수 있으므로

표현력이 더 강하다고 볼 수 있다.

 

Bottom-Up Parsing

Bottom-Up = 우파스 = 우측 유도의 역순이다.

terminal symbol로부터 시작하여 시작 심벌을 유도하는데,

해당 과정은 생성규칙의 rhs와 매치되는지 보고, lhs로 바꿔주는 과정을 반복하는 것이다.

위 그림은, 우측 상단의 생성규칙에 따라 '(1+2(3+4))' 문자열을 파싱하는 과정으로 각 과정을 거꾸로 보면 root로부터 시작한 유도와 동일하다는 것을 알 수 있다.

 

LL, LR

LL(k)

입력을 Left-to-Right 스캔하고, Left-Most를 유도한다.(좌측 유도)

k개의 심벌을 lookahead한다.

[Top-Down or recursion descent/perdictive] parsing 또는 LL parser라고 부르며

파스 트리를 pre-order로 순회 및 생성한다.

 

LR(k)

입력을 Left-to-Right 스캔하고, Right-Most를 유도한다.(우측 유도)

k 심벌을 lookahead한다.

[Bottom-up or shift-reduce] parsing 또는 LR parser라고 부르며

파스 트리는 post-order로 순회 및 생성한다.

 

위 형광펜 쳐진 용어만 봐도 LL인지 LR인지 알아 차릴 수 있어야 한다.

 

Reduce

S => αβω이고 A -> β인 생성 규칙이 존재할 때,

문장형태 αβω에서 β를 A로 대치하는 것을 reduce라고 한다.

파싱 결과는 시작 심벌이 나올 때까지 reduce하면 얻을 수 있다.

 

Handle

한 문장 형태에서 reduce 될 부분을 handle라고 한다.

S =>

αAω => αβω의 과정이 있을 때, β를 αβω의 handle라고 한다.

이때, 왼쪽의 가장 아래에 작성되어 있는 생성규칙의 번호(13626246)는

오른쪽의 가장 아래 작성되어 있는 생성규칙의 번호(64264631)를 뒤집은 것과 같다.

 

이때, 같은 문장 형태에서 서로 다른 handle가 두 개 이상 존재할 때,

우리는 문법이 '모호하다'고 할 수 있다.

위와 같은 생성 규칙이 있을 때 입력 문자열이 'id + id * id'라고 하자.

위와 같은 유도식을 만들 수 있는데, 해당 유도식을 거꾸로 올라 갔을 때,

파싱 과정과 동일하다. 아래에서 세 번째 줄까지는 동일하지만

형광펜 부분을 어떻게 파싱하냐에 따라 다른 파싱 트리가 나온다.

 

Shift-Reduce Parsing

Shift

스택의 top에 handle이 나타날 때까지 계속해서 입력 심벌을 스택에 옮겨담기

 

Reduce

handle을 찾으면 생성 규칙을 결정하며 lhs인 non-terminal로 바꿔치기

 

이것을 문법의 시작 심벌에 이를 때까지 반복한 후 수행한다.

 

Actions

shift와 reduce의 action에 대해 알아보자.

 

Shift

lookahead token 하나를 스택에 옮긴다.

- push a

 

Reduce

스택 top에 있는 handle β를 non-terminal 심벌 X로 바꿔준다.

(단, 생성 규칙은 X -> β)

- pop β, push X

 

아래는 shift와 reduce를 적용한 모습이다.

이때, 처리는 stack 안에서 시행되고 모든 터미널은 다 shift된다.