直接左再帰の除去
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/11/04 01:39 UTC 版)
直接左再帰を除去する一般的なアルゴリズムは次の通りである。このアルゴリズムには Robert C. Moore の "Removing Left Recursion from Context-Free Grammars" で説明されているものを含めて、いくつかの改善策がある。なお、文法をLL(1)にするために必要なことがある「左くくりだし」は似ているが違うものなので注意すること。 次のような形式の生成規則があるとする。 A → A α 1 | . . . | A α n | β 1 | . . . | β m {\displaystyle A\rightarrow A\alpha _{1}\,|\,...\,|\,A\alpha _{n}\,|\,\beta _{1}\,|\,...\,|\,\beta _{m}} ここで: A は左再帰の非終端記号である。 α {\displaystyle \alpha } は空でない( α ≠ ϵ {\displaystyle \alpha \neq \epsilon } )終端記号と非終端記号の並びである。 β {\displaystyle \beta } は終端記号と非終端記号の並びであり、先頭は A ではない。 A の生成規則を次の生成規則で置き換える。 A → β 1 A ′ | . . . | β m A ′ {\displaystyle A\rightarrow \beta _{1}A^{\prime }\,|\,...\,|\,\beta _{m}A^{\prime }} そして、次の新たな非終端記号を生成する。 A ′ → ϵ | α 1 A ′ | . . . | α n A ′ {\displaystyle A^{\prime }\rightarrow \epsilon \,|\,\alpha _{1}A^{\prime }\,|\,...\,|\,\alpha _{n}A^{\prime }} この新たな記号は "tail" または "rest" と呼ばれるので、慣例として "元の記号名_tail" ないし "元の記号名_rest" といった名前を付けられることが多い。
※この「直接左再帰の除去」の解説は、「左再帰」の解説の一部です。
「直接左再帰の除去」を含む「左再帰」の記事については、「左再帰」の概要を参照ください。
- 直接左再帰の除去のページへのリンク
