🎆Bottom-up parsing

Bottom-up parsing and reverse rightmost derivation

S에서 rightmost Derivation 수행하면 위와 같은 식을 얻을 수 있다. A->β 처럼 바꾸는 것은 production이라고 하면 반대로 돌아갈 때에는 handle β를 사용한다고 한다. leaves에서 root로 올라가면서 작업하고 그 과정을 reduction이라고 부른다

Formally,

right sentential form γ의 handle이 < A->β, k> (k는 위치, A->β는 production rule) 라면 k위치에 있는 β를 A로 바꾼다.

Handle pruning

handle을 찾고, reducing 하는 과정

---

Example

---

🎆Shift-reduce Parsing

LR(0) Example

Input: x + ( y + z )

1. stack에 invalid를 넣는다.
2. 시작 state인 s0를 넣는다. (shifting)
   
3. 빨간색 원이 아니므로 수식중x를 push한다.
   s0에서 x에 해당하는 i를 따라서 간다. 그리고 그 state를 push 한다.
   (i를 push 하고, s5를 push 함)
   
4. 이때는 빨간색 원안에 들어갔으므로 reduction 과정을 진행한다.
   s5는 T -> i•이다. 화살표 오른쪽의 문자 개수 2배를 pop 해준다. 그리고 T를 push 한다. T아래쪽에 s0가 있으므로 s0에서 T를 따라간 s6도 push 해준다.
   
5. 이때도 빨간색 원안에 들어갔으므로 reduction 과정을 진행한다.
   s5는 E -> T•이다. 화살표 오른쪽의 문자 개수 2배를 pop 해준다. 그리고 E를 push 한다. T아래쪽에 s0가 있으므로 s0에서 E를 따라간 s1도 push 해준다.
   
6. 이제는 검정색 동그라미 안으로 들어왔으므로 Input: x + ( y + z ) 중에 x 다음인 +를 push 해주고 s1에서 +를 따라 s3으로간다(push).
   
7. 이제는 검정색 동그라미 안으로 들어왔으므로 Input: x + ( y + z ) 중에 x 다음인 (를 push 해주고 s1에서 (를 따라 s7으로간다(push).
   

... 이 과정을 반복한다.