間接左再帰の除去
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/11/04 01:39 UTC 版)
文法に ϵ {\displaystyle \epsilon } -生成規則がない場合（ A → . . . | ϵ | . . . {\displaystyle A\rightarrow ...|\epsilon |...} のような形式の生成規則がない）、そして環状でない場合（任意の非終端記号 A から A ⇒ . . . ⇒ A {\displaystyle A\Rightarrow ...\Rightarrow A} という形の導出がありえない場合）、次のアルゴリズムで間接左再帰を除去できる。 非終端記号を何らかの固定の順序 A 1 {\displaystyle A_{1}} , ... A n {\displaystyle A_{n}} で並べる（ループさせるため）。 for i = 1 to n { for j = 1 to i – 1 { 現在の A j {\displaystyle A_{j}} 生成規則を次のようにする。 A j → δ 1 | . . . | δ k {\displaystyle A_{j}\rightarrow \delta _{1}|...|\delta _{k}} 各生成規則 A i → A j γ {\displaystyle A_{i}\rightarrow A_{j}\gamma } を次で置き換える。 A i → δ 1 γ | . . . | δ k γ {\displaystyle A_{i}\rightarrow \delta _{1}\gamma |...|\delta _{k}\gamma } A i {\displaystyle A_{i}} についての直接左再帰を除去する。 } }
※この「間接左再帰の除去」の解説は、「左再帰」の解説の一部です。
「間接左再帰の除去」を含む「左再帰」の記事については、「左再帰」の概要を参照ください。
- 間接左再帰の除去のページへのリンク
