Top-Down 구문 분석 방식에서 비효율적인 backtracking을 피하기 위해서는 left-recursion을 갖지 않아야하고, left-factoring되어야 한다. 해보니까 쉬운데 왜 시험 땐 못풀었을까…?ㅠㅠㅠㅠㅜㅠㅜㅜㅠㅠㅜㅠㅜㅠㅜㅠㅜㅠㅠㅜ교수님나빠여

Left Recursion 제거

A→Aa와 같이 Left Recursion이 생기면 A를 택해야 할 지 Aa를 택해야 할 지 모르기 때문에 결정적으로 분석할 수 없게 된다. 그래서 Left Recursion을 제거해 주어야 한다.

1. 먼저 문법을 정규 표현식으로 바꾼다.
2. Right Recursion의 형태로 만든다.
3. Right Recursion 되는 부분을 다른 문자로 대치한다.
4. 그 문자에 대한 식을 작성한다.

1. T = T*F + F
2. T = F(*F)^*  
3. *F를 T' 로 대치한다.  
4. T → FT'  
T' → *FT' | ε  

Left Factoring

1. 시작하는 부분이 공통될 경우 그 부분으로 묶는다.
2. 공통된 부분을 다른 문자로 대치한다.
3. 그 문자에 대한 식을 작성한다.

예시) S → aA | abA

1. S → a(A | bA)  
2. S → aS'  
3. S' → A | bA