19 - Top Down Parsing (avoid Left-Recursion)

탑다운 파싱을 하다보면 Left-Recursion이라는 문제가 생길 수 있다.

 

Left-Recirsion이란, A -> Ab와 같은 식에서 점진적으로 진행을 할때,

b가 나올때 까지 계속 포인터가 진행하게 되어 무한 루프에 빠질 수 있는 위험을 말한다.

그래서 탑다운 파싱을 쓰기 위해서는 Left-Recursion을 제거해야만 하는데

이를 피할 수 있는 방식이 Left-Recursion을 Right-Recursion으로 바꾸어 검증 가능하도록 만드는 것이다.

 

 

Left-Recursion 변환

---

A -> Aa | b 가 있다.

이 식은 최종적으로 ba*를 만들지만 A 가 Aa를 만드므로 A를 검사하지 못해 무한 루프가 돈다.

이를 Right Recursion으로 변환하면

A -> bB
B -> aB

이렇게 된다.

두 단계로 나누어 표현했고, b가 먼저 나오고 B도 aB로 치환되어 바로 포인터가 검사할 수 있게 되었다.

이와 같이 탑다운 파싱에서는 Left-Recursion을 Right-Recursion으로 변경해야하는 과정이 필요하다.