القضاء غادر العودية لE: = EE + | EE- | معرف

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

ويستشهد الخاص بك "الإجراء السليم" خطأ. أخذه من كتاب التنين:

A := Aα | β

ويصبح

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

... والتي ينتج:

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