간접적 인 왼쪽 재귀를 제거합니다.

제 뇌가 튀어서 프로덕션 규칙에서 일부 왼쪽 재귀를 제거하려고합니다. 나는 JavaCC에있는 컴파일러를 짓고 있어요 그리고 난 다음이 생성 규칙을 사용해야합니다간접적 인 왼쪽 재귀를 제거합니다.

expression := fragment ((+ | - | * | /) fragment)* 

fragment := identifier | number | (+ | -) fragment | expression

을 그러나 문제는 단편 조각, 즉 관련이 표현과 관련이 있다는 것입니다 : 간접 왼쪽 재귀.

저는 인터넷을 둘러 보았고 모든 사람들이이 알고리즘을 사용하는 것으로 보입니다.이 알고리즘은 here입니다.

void expression(): {} 
{ 
    fragment() 
    (
    (<PLUS>|<MINUS>|<DIVIDE>|<ASTERISKS>) 
    fragment() 
)* 
} 

void k(): {} 
{ 
    (
    ((<PLUS>|<MINUS>|<DIVIDE>|<ASTERISKS>)fragment())*k() 
    | fragment() 
) 
} 

void fragment(): {} 
{ 
    (
    <ID>k() 
    | number()k() 
    | (<PLUS>|<MINUS>)fragment()k() 
) 
}

그들은 JavaCC에 사용되는 코드로 작성하는 것은 너무 잘하면 당신이 그들을 이해할 수있다 : 그 사이트는이 같은 규칙을 끝낼 here

찾을 수 있습니다 직접 왼쪽 재귀 제거를 설명하지 않습니다 . 기본적으로 나는 K의 처음 부분은 아무 것도 없어 질 수 있기 때문에 문제가 여전히 존재한다는 것을 제외하고는 재귀를 다루기 위해 규칙 K를 도입했다. 왜냐하면 더 많이 남아있는 K -> k()로 당신을 떠나는 * (0 번 이상)이기 때문이다. 재귀 !!

여기에서 어디로 가야할지 모르고 머리를 많이 잃었습니다. 모든 통찰력은 인정 될 것입니다! 다음과 같이

출처

2012-12-12 carlmango11

대개 'term','expression' 그리고 터미널 심볼을 가질 수 있습니다. 왜 여기서 충분하지 않습니까? –

'fragment '가 잘못 정의 된 것 같습니다. 'expression : = ... '('expression ')''과 같은 식의 괄호 사이에 'expression'이 나타나면 안됩니까? 그렇지 않으면'fragment' 레벨에서'expression'을 갖는 것은 의미가 없습니다. 특히 JavaCC에 익숙하지는 않지만 다른 파서 생성기에서는 문제가 될 수 있습니다. – user1201210

나는 똑같은 것을 tenterhook라고 생각하고 있었다. 프래그먼트의 '표현식'이 사용되는 경우를 생각할 수 없습니다. 그러나 그들이 강사로 결정되면서 규칙은 꽤 많이 던져졌습니다. 아마도 나는 그에게 연락해야 할까? H2CO3 : 조금 더 설명해 주시겠습니까? '용어'규칙을 만들어야한다는 뜻입니까? 무엇이 포함됩니까? 나는 실제로 그물 주위에'term'을 사용하는 사람들을 보았지만 그 알고리즘을 따르는 것이 더 좋을 것이라고 생각했습니다. – carlmango11

나는 expression에 대한 규칙을 다시 작성하는 것이 좋습니다 :

expression := (identifier | number | (+ | -) fragment) ((+ | - | * | /) fragment)*

효과적으로, 이것은 Kleene 운영자가 편리하게 몇 가지 용어를 흡수 원래 정의 fragment 단지 대체입니다.

물론 원래의 규칙을 반영한다고 가정 할 경우 구문 분석을 통해 만들어진 구조가 무엇이든 수용해야합니다.

출처

2012-12-22 00:42:34

간접적 인 왼쪽 재귀를 제거합니다.

답변

관련 문제