[Compiler Design] Bottom-Up Parsing

 

 

 

 

 

 

Top-Down 방식은 내가 유도하는 방식 그대로 트리가 완성된다.

Bottom-Up 방식은 들어오는 토큰마다 하나씩 처리하는 식이니 컴퓨터 입장에서는 좀 더 쉽게 처리할 수 있다. 

 

생성규칙의 선택을 token이 더 많이 들어올 때 까지 미룰 수 있어 Top-Down 방식보다 더 강력하고, Left-Recursive 문법도 함께 파싱할 수 있다. 

 

$$
\begin{aligned}
& (1+2+(3+4))+5 \;\Leftarrow\; (T+2+(3+4))+5\\
& \Leftarrow\; (E+2+(3+4))+5 \;\Leftarrow\; (E+T+(3+4))+5\\
& \Leftarrow\; (E+(3+4))+5 \;\Leftarrow\; (E+(T+4))+5 \;\Leftarrow\; (E+(E+4))+5\\
& \Leftarrow\; (E+(E+T))+5 \;\Leftarrow\; (E+(E))+5 \;\Leftarrow\; (E+T)+5 \;\Leftarrow\; (E)+5\\
& \Leftarrow\; E+5 \;\Leftarrow\; E+T \;\Leftarrow\; E
\end{aligned}
\qquad
\boxed{
\begin{aligned}
E &\to E+T \mid T\\
T &\to \mathrm{num} \mid (E)
\end{aligned}}
$$

 

 

Bottom-Up = 우 Parse = 우측유도의 역순 

 

Terminal Symbol부터 시작해서 시작 Terminal을 유도해낸다.

생성규칙의 rhs와 매치되는지 확인하고, 매치된다면 바로 lhs로 변환하는 작업을 반복한다. 

 

 

LL(k)

Top-Down 파싱을 LL 파싱이라고 부른다.

Left-Most 유도를 기반으로 하고, 첫 번째 L은 프로그램을 왼쪽부터 스캔함을 의미한다.

k는 LOOKAHEAD 하는 Symbol의 수를 의미한다. 

 

Recursive Descent, Predictive 파싱이라고 부르기도 한다.

Parse Tree를 Pre-Order로 순회 및 생성 

 

 

LR(k)

Bottom-Up 파싱을 LR 파싱이라고 부른다.

Right-Most 유도를 기반으로 하고, 역시 첫 번째 L은 프로그램을 왼쪽부터 읽어감을 의미한다.

 

Shift-Reduce 파싱이라고 부르기도 한다.

Parse Tree를 Post-Order로 순회 및 생성 

 

 

$$
\begin{aligned}
&\textbf{<Reduce>}\\[4pt]
& S \Rightarrow \alpha \beta \omega \text{이고 } A \to \beta \text{의 생성규칙이 존재할 때,}\\
& \text{문장형태 } \alpha \beta \omega \text{에서 } \beta \text{를 } A \text{로 대치하는 것을 } \textbf{reduce} \text{라 한다.}\\[8pt]
& \text{즉, 우변 } \beta \text{를 좌변 비단말기 } A \text{로 바꾸는 단계이다.}\\[6pt]
& \text{파싱 결과는 시작심벌이 나올 때까지 reduce를 반복하면 얻어진다.}\\[10pt]
& 1.\; S \to aAcBe \quad 2.\; A \to Ab \quad 3.\; A \to b \quad 4.\; B \to d\\[10pt]
& \textbf{Reduce sequence (abbcde)}\\[4pt]
& abbcde \Rightarrow aAbcde \;(\text{reduce 3})\\
& \Rightarrow aAcde \;(\text{reduce 2})\\
& \Rightarrow aAcBe \;(\text{reduce 4})\\
& \Rightarrow S \;(\text{reduce 1})\\[12pt]
\end{aligned}
$$

 

 

Reduce는 그냥 유도의 반대라고 보면 됨.. Reduce를 적용하는 Terminal을 Handle이라고 부르고.

 

모호한 문법에서는 Handle 후보가 여러개 있을 수 있다. 

이런 경우 트리도 여러 개 나오니까.. 그냥 문법을 바꿔야함. 아니면 우선순위나 결합규칙을 설정하던가.

 

 

 

 

Shift는 스택의 top에 Handle이 나타날 때 까지 계속 입력 Symbol을 스택에 옮겨담는 작업을 의미한다.

 

Top-Down 파싱과 마찬가지로.. 스택을 그냥 연습장으로 쓰고, 파싱 테이블 참고하면서 Reduce 반복함.

 

 

 

 

 

근데 컴퓨터가 제대로 하려면 알고리즘이 있어야한다. 다시 확인해보자.

 

 

$$
\begin{array}{|c|c|l|}
\hline
\textbf{스택} & \textbf{입력 버퍼} & \textbf{구문분석행동}\\
\hline
\$ & a+a*a\$ & \text{shift } a\\
\$a & +a*a\$ & \text{reduce } F \to a\\
\$F & +a*a\$ & \text{reduce } T \to F\\
\$T & +a*a\$ & \text{reduce } E \to T\\
\$E & +a*a\$ & \text{shift } +\\
\$E+ & a*a\$ & \text{shift } a\\
\$E+a & *a\$ & \text{reduce } F \to a\\
\$E+F & *a\$ & \text{reduce } T \to F\\
\$E+T & *a\$ & \text{shift } *\\
\$E+T* & a\$ & \text{shift } a\\
\$E+T*a & \$ & \text{reduce } F \to a\\
\$E+T*F & \$ & \text{reduce } T \to T*F\\
\$E+T & \$ & \text{reduce } E \to E+T\\
\$E & \$ & \text{accept}\\
\hline
\end{array}
$$

$$
\begin{aligned}
1.&\; E \to E + T \\
2.&\; E \to T \\
3.&\; T \to T * F \\
4.&\; T \to F \\
5.&\; F \to (E) \\
6.&\; F \to a
\end{aligned}
$$

 

맨 처음에는 스택에 $를, 입력 버퍼에는 입력값과 $를 넣어준다.

이후 Reduce가 되면 스택의 top을 대상으로 계속 Reduce 해준다. Reduce는 입력 버퍼에 영향주지 않음에 주의.

 

근데 Shift 할지 Reduce할지 어떻게 아는지? 그냥 그리디하게 당장 할 수 있는 Reduce가 있으면 바로 해주는게 정답일까?

또 Reduce 가능한게 많으면 그 중 뭘 선택해야 하는지? 

 

이걸 해결하기 위해 파서 상태를 사용한다.

스택에 Symbol을 Shift할 때, 파서 상태도 끼워넣는다.

 

끼워 넣는 파서 상태가 뭔지에 따라서 지금 해야할 게 Reduce인지, Shift인지, 어느 정도를 Stack Top으로 판단할지를 결정할 수 있다.

즉, 이러면 모호할 수가 없다..

 

 

 

당연히 파싱 테이블을 작성할 때도 <상태>X<Symbol> 형태로 작성해야 한다.

 

현재 파서 상태만 변경시킬 때도 필요하니 goto table도 함께 작성한다.

 

 

 

 

 

 

파싱 테이블의 형태가 LL 파싱과는 다르다.

LR 테이블의 파싱 테이블에서는 열의 Header에 Terminal과 Non-Terminal을 배치하고 행의 Header에 파서 상태를 배치한다.

 

테이블 성격이 두 개로 나눠진다고 보면 됨.

Action Table 부분은 파서 상태와 Terminal을 읽어서 다음 상태로 전이하는걸 의미하고

Goto Table 부분은 파서 상태와 Non-Terminal을 읽어서 아무 동작도 하지 않고 다음 상태로 전이하는걸 의미한다.

 

일단 Action Table을 먼저 읽고, Goto Table은 Reduce 하고 나서 읽는다고 생각하면 된다.

Reduce 이후 Stack Top에 있는 이전 상태가 다음 Non-Terminal 에 대해 어느 상태로 가야하는지를 결정하기 때문..

즉, Reduce와 Goto는 하나의 세트로 보자. 다만 Goto 테이블 참조할 때는 스택만 보니까 이거만 주의하면 됨.

 

파싱 테이블을 만들 때는...

파서 상태 후보를 먼저 장하고, 파서 상태간 상태전이도를 만들고 파싱 테이블에 넣어주면 된다.

말은 쉬운데 이게 엄청난 노가다이긴 함;; 

 

 

 

---

 

 

 

 

이전에 어휘분석기를 생성해주는 lex를 배웠는데, 구문분석기를 생성해주는 도구인 yacc도 있다.

그냥 Parser를 만들어주는 도구.. 문법 규칙만 정의해주면 Parser를 만들어준다.

 

자바에서 Lexer와 Parser를 만들 때 lex와 yacc를 사용하는거고..

OCaml에서는 menhir라는 Parser 생성기가 따로 있다. 당연히 다른 언어도 있고.

 

 

 

 

lex랑 형태가 정말 비슷하다.

rules 부분에 모호한 문법을 넣으면.. 동작 하긴 하는데 의도한 대로 동작하지 않을 수 있으니 우선순위를 명확하게 설정해서 모호하지 않은 문법을 넣어주자.

근데 사실 대충 문법 짜고 선언부에서 우선순위만 설정해주면 잘 돌아간다.