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 が判断するように要求された場合には、衝突が発生する可能性があります。