左再帰
間接左再帰の単純な例は、次のようなものになる。
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}} は非終端記号と終端記号の並びである。