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