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 이렇게 된..

2021.08.09