[PL] Syntax Analysis : Parsing Approaches & Backtracking, Left Recursion

1. Parsing Approaches

String을 Parse Tree로 만드는 두 가지 방법

1) Top-down Parsing (=LL Parsing)

✔️ 루트 노드부터 leaf 노드로 (Star from starting Non-terminal and work your way down)
✔️ Left-to-Right Scanning (input symbol을 왼쪽에서 오른쪽으로 읽는다)
✔️ Left parse for Derivation Tree Generation (Left-Most derivation)

• Top-down: 루트에서 아래로
• LL Parsing : 왼쪽에서 오른쪽으로 스캔 (a->x->a->y) & Left-most Derivation

📌 장점

이해하기 쉽다.

📌 단점

루프가 무한하게 존재할 수 있기 때문에(Left-recursion) 효율적이지 않다.
백트래킹은 시간이 많이 소요된다.

2) Bottom-up Parsing (=LR Parsing)

✔️ leaf 노드부터 시작하여 루트 노드로 (Start from terminals and work your way up!)
✔️ Left-to-Right Scanning (input symbol을 왼쪽에서 오른쪽으로 읽는다)
✔️ Right parse for Derivation Tree Genenration (Right-Most derivation)

• Bottom-up: 아래에서 루트로
• LR Parsing : 왼쪽에서 오른쪽으로 스캔 (a->x->a->y) & Right-most Derivation

2. Backtracking & Left-recursion

Top-down Parsing의 단점

➡️ 루프가 무한하게 존재할 수 있기 때문에(Left-recursion) 효율적이지 않다.
➡️ 백트래킹은 시간이 많이 소요된다.

1) 백트래킹이란?!

✔️ Top-down Parsing은 시작 symbol부터 시작하여 주어진 production rule을 기반으로 left-parse를 하는 기법이다.
✔️ 그런데 만약 사용된 production rule이 적절한 rule이 아닐 경우에, 다른 production rule을 적용해 가야 한다. 이러한 과정이 iterative하게 반복되는 것을 'backtracking'이라고 한다.
✔️ Backtracking은 시간이 많이 소요될뿐더러 효율적이지 않다.

📌 Example

• 첫 번째 룰인 S->aAd를 적용하면 'aAd'의 첫 번째 'a'가 matching 된다
• 그 다음에 있는 룰 'A->b' 적용 시 'abd'로, 두 번째 'b'가 matching 되지 않는다.
• 그 다음 룰 'A->c' 적용 시 'acd'로, 세 번째 'd'가 matching 되지 않는다.
• 더 이상 적용 가능한 production rule 불가
• 두 번째 룰인 S->aB 적용하면 'a' matching
• 그 다음 'B->ccd' 적용 시 모두 matching
  ➡️반복적 bactracking으로 효율적이지 않음!
  

2) Left-recursion이란?!

📌 정의

✔️ Top-down Parsing을 할 때 production rule을 적용해보고, 생성되는 것을 왼쪽부터 target 문자열과 하나씩 비교해본다.(left- to- right scanning)
ex) 앞선 예시에서 S에서 aAd가 생성됐을 때, a부터 'accd'와 비교해보는 방식

✔️ 그런데! 만약 비교대상이 non-terminal이라면, non-terminal은 어떠한 string으로 바뀔지 모르기 때문에 target character와 비교하지 못하고 계속 production rule을 적용해 보게된다.

✔️ 이러한 경우 Non-terminal이니까 잘못된 production rule이라고 결론을 내릴 수 없어서 계속해서 production rule을 적용해보면서 loop에 빠지게 되는 것이다.

➡️ 원인 : 비교 대상인 왼쪽 Symbol이 Non-terminal이기 때문에 비교를 할 수 없는 것

➡️ 해결법 : Left Recursion은 Infinite Loop를 초래하기 때문에 top-down parsing을 하고자 한다면, 프로그래밍 언어의 grammer에서 left recursion을 제거해야 한다.

📌 종류

1) Direct Left-Recursion

ex) A -> Aa | B
A->Aa 와 같이 Non-terminal이 동일한 Non-terminal이 되는 것

2) Indirect Left-Recursion

ex) S -> Aa | b, A -> Ac|Sd|$\epsilon$
S->Sa, A->Sd처럼 Non-terminal A이 다른 Non-terminal B이 되고, 다른 non-terminal B이 다시 그 Non-terminal A이 되는 것

🌳 Non-terminal Mapping 🌳

Direct Recursion은 바로 찾을 수 있지만, CFG가 복잡하다면 Indirect Recursion 찾기는 어렵기 때문에 Non-terminal Mapping을 해서 찾을 수 있다. Terminal 부분은 제외하고 Mapping 해보기!
S -> A
A -> A
A -> S
이러한 Mapping을 통해서 S->A, A->S의 Cycle을 찾고 indirect recursion을 찾을 수 있다.