間接左再帰
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2016/11/04 01:39 UTC 版)
間接左再帰の単純な例は、次のようなものになる。 A → B α | C {\displaystyle A\rightarrow B\alpha \,|\,C} B → A β | D {\displaystyle B\rightarrow A\beta \,|\,D} この場合、 A ⇒ B α ⇒ A β α ⇒ . . . {\displaystyle A\Rightarrow B\alpha \Rightarrow A\beta \alpha \Rightarrow ...} のような導出となる可能性がある。 より一般化すると、非終端記号群 A 0 , A 1 , . . . , A n {\displaystyle A_{0},A_{1},...,A_{n}} についての間接左再帰は次のように定義できる。 A 0 → A 1 α 1 | . . . {\displaystyle A_{0}\rightarrow A_{1}\alpha _{1}\,|...} A 1 → A 2 α 2 | . . . {\displaystyle A_{1}\rightarrow A_{2}\alpha _{2}\,|...} . . . {\displaystyle ...} A n → A 0 α ( n + 1 ) | . . . {\displaystyle A_{n}\rightarrow A_{0}\alpha _{(n+1)}\,|...} ここで、 α 1 , α 2 , . . . , α n {\displaystyle \alpha _{1},\alpha _{2},...,\alpha _{n}} は非終端記号と終端記号の並びである。
※この「間接左再帰」の解説は、「左再帰」の解説の一部です。
「間接左再帰」を含む「左再帰」の記事については、「左再帰」の概要を参照ください。
- 間接左再帰のページへのリンク