左再帰の除去
左再帰のあるような構文から左再帰を除去する
イメージ図
左が左再帰がある文法で、右に書き換える
赤いところがあるのがそもそもの問題点
緑の線はイメージ。無視していい
右再帰を用いて変換するA\rightarrow A\alpha|\betaから左再帰を除去する
\alpha,\betaは任意の終端記号または非終端記号の並び
以下のように変換する
A\rightarrow\beta A'
A'\rightarrow\alpha A'|\epsilon
右再帰の文法に変換するこの方法は厳密には等価な変換ではない(らしい)
>「言語」の外部定義すなわち「構文規則が（受け入れる｜生成する）終端記号列」としては等価な変換だと言えるが、「言語」の内部定義として「構文規則によって作られる構文木」というものを考えるならば、違うものに変換されてしまっているわけである。 ref
chainlのやりかた
具体例
E → E + T | T を以下のように変換する E→T E' E'→ ε | + T E' ループを用いた変換
以下のように変換する
E → T (+ T)* これは
E → (T +)* T と同じ拡張BNF記法を用いて書いている
自転車本のやりかた
手続き型の言語ではwhile文を用いて容易に実装できる
Parsecでもdo記法内で再帰すれば実装可能
らしい