次へ: 8 状況を保存するアルゴリズム 上へ: C のソースからプロトタイプ宣言を作成 前へ: 6 単純なアルゴリズム (PDF ファイル: awktg.pdf)

7 パターンマッチ中心のアルゴリズム

6 節のプログラムの構造は、 単純なフローチャートから書いているので考えやすいかもしれませんが、 getline を内部で 2 回使用していますし、 while(1) ループを 2 重に使っていて、 AWK スクリプトとしてはあまり読みやすいものではなく、 処理のわかりにくいものになっています。 今度は、より AWK らしいアルゴリズムを考えてみます。

「ア」$\sim$「オ」は、行の種類の判別になっていますが、 そのような行の性質ごとに処理を書くのはより AWK らしい書き方だと言えます。 そもそも、AWK の行処理部分は、

  {
      コード部分
  }

以外にも、

  条件 1 {
      コード 1
  }
  条件 2 {
      コード 2
  }
  ...

のように、条件を満たす行に対してのみ実行するコードを別々に書くことが できるようになっていて、さらにその条件が行全体 ($0) に対する パターンマッチングである場合は、「$0 ~ /パターン/」という条件式を、 単に「/パターン/」のように書けばよいことになっています。

これを利用して、「ア」$\sim$「オ」のパターン毎の処理を考えてみることに します。 このうち、「ア」「ウ」「エ」は行頭に関係していてお互いに排他的³ですし、「イ」「オ」は行末に関係し排他的なので、それらに分けて考えてみます。

なお、「ア」や「ウ」の処理の後には、同じ行を「イ」(や「オ」) のチェックにも回さなければいけないことに注意します。 よって、そのために「フラグ」(フラグ 1) を使って、 「イ」に「ア」や「ウ」の処理の後であることをわからせることにします。

(1) 「ア」ならば、リセットして保存してフラグ 1 をセット

(2) 「ウ」ならば、現在保存した行がなければ next、あればこの行も保存 してフラグ 1 をセット

(3) 「エ」ならば、それが「イ」の次の行であれば (フラグ 2 がセットさ れている場合) 保存しているものに `;' をつけて出力してリセットして next、 そうでなければリセットして next

(4) 「イ」ならば、「ア」か「ウ」の次ならば (フラグ 1 がセットされて いれば) フラグ 2 をセットして next、されていなければ next

(5) フラグ 1 でなければリセット

ここでの「リセット」は、保存しているものをクリアすることと フラグ 2 をクリアすることを意味します。 これをフローチャートにしたのが図 2 です。

図 2: パターン中心のフローチャート

この場合は、6 節にはほとんど必要なかった「リセット」と いう作業、および「フラグ」というものが含まれていて、 逆に明示的な (暗黙のもの以外の) getline はなく、「オ」もありません。

フラグは上にも説明しましたが、次のような意味を持つ 0 か 1 の値を取る変 数です⁴。

• フラグ 1 : 「ア」か「ウ」を通過したかどうかを表す
• フラグ 2 : 前の行が「イ」であったことを表す

この行毎の処理の場合、例えば「イ」である行を見つけたとしても、 それ単独では、その行が「ア」を通過してきたものなのか、 「ウ」を通過してきたものなのか、またはそのいずれも通過しなかったもの なのかが判別できません。しかし、「ア」か「ウ」を通過した場合のみ 「イ」は意味がありますので、そのためにフラグ 1 が必要になります。

同様に「エ」は「イ」の次の行でのみ意味を持ちますので、 それを示すためにフラグ 2 が必要となります。

「ウ」や「エ」のリセットは、 関数定義ではないと判別された場合に各変数を初期化して、 また一から関数定義を探す、という目的の為に入れてあります。 そのリセットがないと、 関数定義ではないところで「エ」が出力してしまう恐れがあります。 最後の「フラグ 1 でなければリセット」の部分も同様の理由で入れてありま す。

これを疑似コードにしてみると、例えば以下のようになります。

  { flag1=0 }
  「ア」{ (リセットして保存) ; flag1=1 }
  「ウ」{
      if( (保存したものがある) ){ (追加して保存); flag1=1 }
      else{ (リセット) ; next }
  }
  「エ」{
      if(flag2==1){ (出力) }
      (リセット); next
  } 
  「イ」{ if(flag1==1) flag2=1; next }
  (flag1==0){ (リセット) }

この最初の実行コードブロックには条件がついていませんが、 条件のついていないコードブロックは、すべての行が実行対象になります。

先頭のブロックや「ア」、「ウ」の実行ブロックは、 next がない、あるいはあっても必ずしも実行されるとは限りませんので、 そのブロックが終ったら、同じ入力行に対して次のブロックの条件判断に 動作が移ります。 これに対し、「エ」、「イ」のブロックでは最後に必ず next が実行されますの で、これらのブロックに入った場合はその下のブロックは実行されずに 次の入力行に動作が移ります。

フラグが 2 つあるので少しわかりにくいかもしれませんが、特にループも使 用しておらず、AWK スクリプトとしてはすっきりした構造になっています。

なお、このスクリプトだと「ア」のチェックをしたあとで「ア」でない 場合にも「ウ」であるかどうかをチェックしていますが、「ア」「ウ」「エ」 は互いに排他的なので、これは無駄です。 つまり、フローチャートは、図 2 よりもむしろ 図 3 の方が望ましいかもしれません。

図 3: パターン中心のフローチャート (改良版)

これは、AWK の 「if$\sim$ else if$\sim$ else」のような書き方を使えば実 現できます。つまり、図 3 の疑似コードは 以下のようになります。

  { flag1=0 }
  {
      if(「ア」){ (リセットして保存) ; flag1=1 }
      else if(「ウ」){
        if( (保存したものがある) ){ (追加して保存); flag1=1 }
        else{ (リセット); next }
      }
      else if(「エ」){
        if(flag2==1){ (出力) }
        (リセット); next
      }
  } 
  「イ」{ if(flag1==1) flag2=1; next }
  (flag1==0){ (リセット) }

このように、「ア」「ウ」「エ」を一つの実行ブロック内に書いてしまえば if else 文でその無駄を排除することができます。ただ、ここまでするなら、 先頭ブロックや「イ」のブロック、最後のブロックを外に出しているのもあま り意味はありませんので、いっそ全部を一つの実行ブロックにして、 以下のようにしてもいいでしょう。

  {
      flag1=0
      if(「ア」){ (リセットして保存) ; flag1=1 }
      else if(「ウ」){
        if( (保存したものがある) ){ (追加して保存); flag1=1 }
        else{ (リセット); flag2=0; next }
      }
      else if(「エ」){
        if(flag2==1){ (出力) }
        (リセット); flag2=0 ; next
      }
      if(「イ」){ if(flag1==1) flag2=1; next }
      if(flag1==0){ (リセット); flag2=0 }
  }

次へ: 8 状況を保存するアルゴリズム 上へ: C のソースからプロトタイプ宣言を作成 前へ: 6 単純なアルゴリズム