이 간접적 인 왼쪽 재귀의 단계적 제거

Question

this algorithm 왼쪽 재귀를 모두 제거 할 수 있어야합니다. 는 그러나 나는이 특정 문법 문제로 실행 해요 : 내가 루프 또는 여전히 간접 왼쪽 재귀 문법으로 끝낼려고 무엇이든

A -> Cd 
B -> Ce 
C -> A | B | f 

.

this algorithm을이 문법에 올바르게 구현하는 단계는 무엇입니까?

Answer 1

규칙은 비 터미널에 대해 일종의 순서를 설정 한 다음 간접 재귀가 발생하는 모든 경로를 찾는 규칙입니다. 비 - 터미널 C의 순환하는 < B < C 것 이때 순서

, 가능한 경로

C=> A => Cd 

및 C가 될 것이다위한

C=> B => Ce 

그래서 새로운 규칙 것

C=> Cd | Ce | f 

이제 직접 왼쪽 재귀를 제거 할 수 있습니다.

C=> fC' 
C'=> dC' | eC' | eps 

그 결과 비 재귀 문법이 될 것이다 :이이 프로그램 만 CS 이론을 아무 상관이 없기 때문에

A => Cd 
B => Ce 
C => fC' 
C' => dC' | eC' | eps 

Answer 2

이미 알아 냈습니다.

혼란은이 순서대로 알고리즘이 아무 것도하지 않는 것처럼 보였으므로 잘못 입력했음을 알았고 첫 번째 반복에서 A -> Cd를 바꾸기 시작했습니다 (j는 무시할 수 없지만 무시할 수 없음) 무한 루프 . 규칙을 재정렬함으로써

1) - B가 아직 J의 범위에서되도록두고 직접 교체

C -> A | B | f 
A -> Ad | Bd | fd 
B -> Ce 

3) 씨디>

C -> A | B | f 
A -> Cd 
B -> Ce 

2)에서 C를 대체

C -> A | B | f 
A -> BdA' | fdA' 
A'-> dA' | epsylon 
B -> Ce 

4의 왼쪽 재귀) B에서 C를 대체 ->

세륨

C -> A | B | f 
A -> BdA' | fdA' 
A'-> dA' | epsylon 
B -> Ae | Be | fe 

5) 아직 완료되지 않았습니다. 또한 새로운 룰 B를 교체 할 필요 -> 애

C -> A | B | f 
A -> BdA' | fdA' 
A'-> dA' | epsylon 
B -> BdA'e | fdA'e | Be | fe 

6)을 떠올리게

C -> A | B | f 
A -> BdA' | fdA' 
A'-> dA' | epsylon 
B -> fdA'eB' | feB' 
B'-> dA'eB' | eB' | epsylon 

B

의 제작에 직접 왼쪽 재귀 대체 (A의 생산 J의 범위이다)! left-recursion 무료 문법!