Next: , Previous: Rules, Up: Grammar File


3.4 再帰的規則

resultである非終端記号が規則の右側にも現れる場合に、 その規則は再帰的(recursive)であるといいます。 Bison文法の大部分は再帰的規則を使います。 なぜならば、任意の数の並びを定義する唯一の方法が、 再帰的規則だからです。 1つ以上のカンマで区切られた式の並びの定義を考えてみましょう。

     expseq1:  exp
             | expseq1 ',' exp
             ;

expseq1で使われている再帰は、規則の右側の中でもっとも左側にあるので、 このような再帰を左再帰(left recursion)と呼びます。 逆に、同じ構造を右再帰(right recursion)を使って書いてみます。

     expseq1:  exp
             | exp ',' expseq1
             ;

あらゆる並びを、左再帰を使っても、右再帰を使っても、定義できます。 しかし、限られたスタック容量で任意の数の並びを走査できるので、 つねに左再帰を使うべきです。 右再帰では、規則が適用される前にすべての要素をスタックに積む必要があるので、 要素の数に比例するスタック領域を消費します。 詳細については、See The Bison Parser Algorithm

規則の結果が直接その右側には含まれず、 右側にある非終端記号の中に含まれるとき、 間接(indirect)すなわち相互(mutual)再帰が起きます。

例を示します。

     expr:     primary
             | primary '+' primary
             ;
     
     primary:  constant
             | '(' expr ')'
             ;

この例では、それぞれの規則が互いに参照しているので、 2個の相互再帰が定義されています。