左再帰

yacc パーサーによって使用されるアルゴリズムには、いわゆる左再帰構文規則が頻繁に利用されます。以下の形式の規則はこのアルゴリズムに一致します。

name : name rest_of_rule ;

シーケンスとリストの仕様を作成するときには、以下のような規則を頻繁に使用します。

list     : item 
          | list ',' item 
          ;

次に :

seq      : item 
         | seq item 
         ;

どちらの場合でも、最初の規則は最初の項目についてだけ還元され、2 番目の規則は 2 番目とそれ以降のすべての項目について還元されます。

以下のような右再帰規則を使用した場合には、パーサーのサイズが多少大きくなります。認識された項目は、右から左に向かって還元されます。

seq     : item 
        | item seq 
        ;

問題点は、非常に長いシーケンスを読み取った場合に、パーサーの内部スタックがオーバーフローを起こす可能性があることです (ただし、現在の yacc は、かなり大きなスタックを処理できるようになっています)。したがって、なるべく左再帰の方を使用するようにしてください。

ゼロのシーケンスに意味があるかどうかについて考えてみましょう。たとえば、空の規則を使用して以下のシーケンス仕様を作成した場合について考えます。

seq      : /* 空 */
         | seq item 
         ;

最初の規則は最初の項目が読み取られる前に必ず 1 回だけ還元されます。2 番目の規則は、読み取られた各項目ごとに 1 回還元されます。空のシーケンスを許可すると、一般性が高くなることがよくあります。ただし、どの空シーケンスを認識したのかを、まだ十分に認識していない段階で yacc が判断するように要求された場合には、衝突が発生する可能性があります。