터미널에서 왼쪽 재귀 제거

다음 규칙에서 왼쪽 재귀를 제거하려면 어떻게합니까?터미널에서 왼쪽 재귀 제거

S -> aSAbb | aA

나는 그것을 S -> SA에서 수행하는 방법을 알고있다. A

이것은 S -> A |가된다. 같이'; S '-> A | AS '라고 말하지만,이 질문에서 터미널은 나를 버린다.

편집 : 재귀가 왼쪽 무엇

죄송합니다, 분명히 나는에 혼동되었다. 나는 왼손 기호를 오른쪽에서 제거하는 방법을 물어야했다.

2010-12-14 A B

재귀가 남아 있지 않으므로 힘든 시간을 보내고 있습니다. 왼쪽 재귀는 생성하려고하는 것과 동일한 비 터미널 (예 : S -> S ...)으로 규칙을 시작해야합니다. –

나는 그것이 가능하지 않다고 생각한다. 문법은'a^n aA (Abb)^n' 인 것처럼 보이며 재귀없이 두 개의 'n'을 묶을 방법이 없다고 생각합니다. – BCS

규칙

S -> aSAbb | aA

재귀 남아 있지 않습니다. 레프트 재귀 규칙 형태 U는 단자 비끝의 서열이다

A -> Au

있다. S 규칙의 오른쪽에서 기호 S를 제거하려면, 고려 :

S => aSAbb 
    => a(aSAbb)Abb 
    => a^n(aA)(Abb)^n

S에 재귀의 역할이 순서를 생산하는 것입니다. 동등한 문법은 지금

S -> aKAbb | aA 
K -> aSAbb | aA

문법이 도출에

S => aSAbb 
    => a(aSAbb)Abb 
    => a(a(aSAbb)Abb)Abb

때문에, 동일 단지 유도

S => aKAbb 
    => a(aSAbb)Abb 
    => a(a(aKAbb)Abb)Abb

되며, 각각의 유도가 aA에 의해 종료 (내 생각 : 내가 틀렸다면 나를 바로 잡아주세요.)

2010-12-15 13:06:02 danportin

답변