仕様の準備に関するヒント

この節では、効果的および明瞭で、変更が容易な仕様を準備するためのさまざまなヒントについて説明します。

入力スタイル

規則に実際のアクションを与え、同時に仕様ファイルも読みやすくするのは簡単なことではありません。スタイルに関するヒントをいくつか以下に示します。

• トークン名にはすべて大文字、非終端名にはすべて小文字を使用してください。このように表記しておくと、デバッグの際に役立ちます。

• 構文規則とアクションを別々の行に置けば、編集が容易になります。

• 左側が同一の規則をまとめて置きます。1 つの規則の左側だけを残して、後の規則はすべて縦棒で始めてください。

• 左側の規則の最後の定義の後にだけセミコロンを置きます。そのセミコロンは別の行に置いてください。これにより、新しい規則を容易に追加できるようになります。

• 規則の本体は 1 個のタブ、アクションの本体は 2 個のタブを使用して字下げしてください。

• 複雑なアクションは、別のファイルで定義されたサブルーチンに入れてください。

  この節の例は、このスタイルに従って書かれています。要点は、アクションのコードの中から規則を認識しやすいように記述することです。

左再帰

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