Bottom-up parsing

input string에 대해 parse tree를 만들 때, 리프부터 시작한다.

Bottom-up parsing에는 shift-reduce parsing이 있다.

Shift-reduce parsing

• string w를 2개의 substring으로 나눈다.
  w = a | b
• 각각 step에서 shift나 reduce를 진행한다.
  - shift : |를 오른쪽으로 이동 시킨다.
  - reduce : 좌측 substring의 접미사를 감축시킨다. (production의 RHS에 맞아야 함)
  

하지만 2가지 문제가 있다.

• Shift-reduce conflict

  각각의 step에서 우리는 shift를 할건지 reduce를 할건지 결정해야 한다.

• Reduce-reduce conflict

  2개의 production이 존재할 때 어떤 reduction을 사용할 지 결정해야 한다.

-> 해결을 위해 handle과 viable prefix를 알아보기

handle

X -> b가 있을 때
ab|w =>(reduce) aX|w 가 가능하면 b는 abw의 handle이다.

어떻게 handle인지 아닐지 알 수 있을까?
-> viable prefix 사용

viable prefix

a|b에서 a=prefix_1 prefix_2 ... prefix_n이고, prefix_i가 RHS의 접미사일 때,

• prefix_k (1<=k<n)은 handle이 아니다.
• 만약 prefix_n이 handle이라면, reduce된다.
• prefix_n이 handle이 아니라면, prefix_n+1, prefix_n+2와 연결되어 결국 handle이 된다.
  

$ab|$b$w$이고, $ab$가 viable prefix일 때,

• 만약 $X$ -> $b$이고, $aX$가 viable prefix일 때, $b$는 $ab|$b$w$의 handle이고, reduction 된다.
• 만약 $ab$의 접미사가 handle이 아니고, $ab$b가 viable prefix이면 shift를 진행한다.
• 이외의 경우이면 reject한다.