E : = ee+| ee- | id에 대한 제거 좌측 재귀

Question

다음 문법에 대한 왼쪽 재귀를 제거하는 방법은 무엇입니까?

E := EE+|EE-|id

일반적인 절차 사용 :

A := Aa|b

변환 :

A := b|A'
A' := ϵ| Aa 

이것을 원래 문법에 적용하는 것은 다음과 같습니다.

A = E, a = (E+|E-) and b = id

그러므로:

E := id|E'
E' := ϵ|E(E+|E-)

그러나이 문법은 틀 렸습니다

ϵE+ -> ϵ id +

유효하지만 이는 잘못된 포스트 픽스 표현식입니다.

Answer 1

"일반적인 절차"가 잘못 인용되었습니다. Dragon Book에서 가져 오기 :

A := Aα | β

becomes

A  := βA′
A′ := αA′ | ϵ

… 수율 :

E  := id E′
E′ := (E + | E -) E′ | ϵ