たくまけい: 左再帰を取り除くメモ

2009年12月17日木曜日

左再帰

A : A B0
  | A B1
  ...
  | A Bn
  | C0
  | C1
  ...
  | Cn

※1 B0 ... Bn はε(空)ではない

※2 C0 ... Cn は A を先頭に持たない

左再帰を消す

A : C0 A_tail?
  | C1 A_tail?
  ...
  | Cn A_tail?

A_tail : B0 A_tail?
       | B1 A_tail?
       ...
       | Bn A_tail?