Left-recursion 이란?
- 어떤 a에 대해 A +=> Aa의 유도 과정이 있는 nonterminal A가 존재하는 경우를 말함.
- Left-recursion을 없애주기 위해서는 다음 3단계의 과정이 필요함.
- eliminate ε-productions (impossible to generate ε!)
- eliminate cycles (A +⇒A)
- eliminate left-recursion
먼저, eliminating ε-productions 과정부터 알아보자
1. eliminating ε-productions
S → XX | Y
X → aXb | ε
Y → aY b | Z
Z → bZa | ε
이러한 CFG가 있다 했을 때,
S,X,Y,Z 는 모두 ε을 파생할 수 있다.
따라서
Z → bZa | ε => Z → bZa | ba 와 같이 엡실론을 없애 주어야 한다.
이 과정을 거치면
S → XX | X | Y
X → aXb | ab
Y → aY b | ab | Z
Z → bZa | ba
의 결과값을 얻게 된다.
2. eliminate cycles (A +⇒A)
S → X | Xb | SS
X → S | a
cycles를 제거 한다면,
S → a | Xb | SS
X → Xb | SS | a
3. Eliminating “immediate” left recursion
direct left-recursion
- 생성규칙에서 A->Aa와 같이 direct하게 나타난 경우를 뜻함
- 제거 방법은 다음과 같음
A -> Aα | β
=>
A -> βA'
A' -> αA' | ε
cf)
A-> αβ | αγ
=>
A->αA'
A'->β|γ
indirect left-recursion
- 유도 과정을 진행하던 중 left-recursion이 나타난 경우
(example 1)
S -> Aa | b
A -> Ac | Sd | e
이때, A->Sd에서 S가 A보다 앞섰기 때문에 S 생성규칙을 대입할 수 있음. 모두 대입하자
A -> Ac | Aad | bd | e
대입했을 때, direct-left recursion이 나타남. 제거해주자.
A -> bdA' | eA'
A' -> cA' | adA' | ε
따라서 모두 제거된 생성 규칙은 아래와 같다.
S -> Aa | b
A -> bdA' | eA'
A' -> cA' | adA' | ε
예시 문제 (중요)
S → SX | SSb | XS | a
X → Xb | Sa | b
- 먼저, S에 대해 eliminating left-recursion을 진행
S → XSS′ | aS′
S′ → XS′ | SbS′| ǫ
X → Xb | Sa | b
- X->Sa 에서, S가 선행조건이므로 S를 X에 대입할 수 있다. 따라서,
X → XSS′a | aS′a | Xb | b
- 그 과정에서, X에 대한 left-recursion이 나왔다. 제거해주자
X → bX′ | aS′aX′
X′ → SS′aX′ | bX′ | ǫ
- 결과 값
S → XSS′ | aS′
S′ → XS′ | SbS′| ǫ
X → bX′ | aS′aX′
X′ → SS′aX′ | bX′ | ǫ
특이 case (β값이 존재 X)
-> 'A' cannot appear n a derivation
(ex) A->AA|Ab의 경우,
A'-> AA' | bA' | ε
으로 나타낼 수 있다. (A는 존재하지 않음)
예외 경우 (left-recursion 존재 X)
- X → X | a 와 같은 경우 일반적으로 left-recursion이 존재 X
따라서
X → aX′
X′ → X′
이렇게 나타낼 수 있다.
S → X | b
X → S | a
(1) left recursion 존재 X
(2) S가 X보다 선행조건이므로, X->S를 X->X|b 로 교체한다.
따라서 X->X|b|a 가 된다
(3) 결과 값
X → bX′ | aX′
X′ → X′
이렇게 표현이 가능하다.
참고: https://lesslate.github.io/compiler/Left-recursion/
