20 - Indirect Left-Recursion

Indirect Left-Recursion이란 간접적으로 Left-Recursion을 만들어 무한루프에 빠지게 만드는 상황을 말한다.

 

S -> Aa|b
A -> Ac|Sd|e

이와 같은 식이 있을 때,

S가 A를 가리키고 진행중인데 A가 다시 S를 호출하는 상황이 나오게 된다.

이렇게 되면 무한루프에 빠질 수 있게되고 top-down에서 나올 수 없는 역방향 참조가 나타난다.

그리고, A -> Ac에서 Direct Left-Recursion이 나타나고 있다.

 

 

Indirect Left-Recursion 제거

---

위 식 A -> Sd 부분을 치환하여

A -> Aad|bd로 바꾼다. S 가 Aa|b 이므로 치환법칙을 이용한 것이다.

이렇게 되면 A -> Ac | Aad | bd | e 가 되고 Direct Left-Recursion으로 변환되었다.

이제 Direct Left-Recursion을 저번에 설명한 방식대로 Right-Recursion으로 변환해 나가면 된다.

 

S -> Aa | b

A -> Ac | Aad | bd | e 에서 변환하면

 

A -> bdB | eB //recursion이 아닌건 새로운 터미널을 추가한다.

B -> cB | adB //새 터미널에서 left를 right으로 바꾸어 준다