이 왼쪽 재귀를 제거하는 방법

Question

컴파일러 생성에서 할당을 수행하고 왼쪽 재귀에 문제가 있습니다. JavaCC는 아래에 나와있는 expression()과 condition()에 대해 "Left recursion detected"오류를 표시합니다. 두 번째 줄은 모두 동일하므로 문제가 있다고 가정합니다.

→ Aα | β

→ βA '

A'→ ε | αA '

이 왼쪽 재귀를 제거하는 방법을 보여주기 위해 사용되는 식이었다. 나는 강의와 온라인 비디오 및 설명에서이 개념을 이해해 왔지만 여기에 적용하는 방법을 알아낼 수는 없습니다. 누군가가 왼쪽 재귀를 제거하는 방법을 보여줄 수 있습니까?

void expression() : 
{ } 
{ 
    fragment() binary_arith_op() fragment() 
| <OPAREN> expression() <CPAREN> 
| <ID> <OPAREN> arg_list() <CPAREN> 
| fragment() 
} 

void fragment() : 
{ } 
{ (<MINUS_SIGN>)? <ID> | <NUM> | <TRUE> | <FALSE> | expression() } 

void condition() : 
{ } 
{ <TILDE> condition() 
| <OPAREN> condition() <CPAREN> 
| expression() comp_op() expression() 
| condition() (<OR> | <AND>) condition() 
} 

Answer 1

유사한 예는 컴파일하는 모든 책에서 찾을 수 있습니다. 또한 내 튜토리얼 Parsing Expressions by Recursive Descent을 살펴볼 수도 있습니다. 또는 다른 많은 무료 자습서 중 하나.

다음은 해결책입니다. 먼저이 표현을 약간 다시 작성하겠습니다.

void expression() : 
{ } 
{ 
    expression() binary_arith_op() expression() 
| 
    simpleExpression() : 
} 

void simpleExpression() : 
{ } 
{ (<MINUS_SIGN>)? <ID> | <NUM> | <TRUE> | <FALSE> 
| <OPAREN> expression() <CPAREN> 
| <ID> <OPAREN> arg_list() <CPAREN> } 

이제 alpha와 beta가 무엇인지 분명하게 알 수 있습니다. 그래서 우리는 얻을

void expression() : 
{ } 
{ 
    simpleExpression() expressionPrime() 
} 


void expressionPrime() : 
{ } 
{ 
    binary_arith_op() expression() 
| 
    {} 
} 

그러나 JavaCC에서 우리는 루프 (즉, Kleene 스타)를 사용할 수도 있습니다. 조건

왼쪽 재귀 제거

void condition() : 
{ } 
{ 
    simpleCondition() ((<OR> | <AND>) simpleCondition())* 
} 

void simpleCondition() : 
{ } 
{ 
    <TILDE> condition() 
| <OPAREN> condition() <CPAREN> 
| expression() comp_op() expression() 
} 

비슷하게

void expression() : 
{ } 
{ 
    simpleExpression() (binary_arith_op() simpleExpression())* 
} 

void simpleExpression() : 
{ } 
{ (<MINUS_SIGN>)? <ID> | <NUM> | <TRUE> | <FALSE> 
| <OPAREN> expression() <CPAREN> 
| <ID> <OPAREN> arg_list() <CPAREN> } 

.

여전히 선택의 여지가 없습니다. 구문 표기법을 사용하여 제거 할 수 있습니다. 연산자 우선 순위도 처리하는 것이 좋겠지 만 간단합니다. 내 튜토리얼의 "고전적인"솔루션을 참조하십시오.