中置記法から前置記法への変換 CIT-BACHの制約式を生成する
組み合わせ生成エンジンのCIT-BACHは制約式に前置記法を用いているという特徴があります。前置記法とは演算子が引数の前に置かれる記法でプログラミング言語LISPで用いられている記法です。今回はPctMasterで実現している前置記法の制約式を生成する方法を説明します。
私たちが一般に用いる記法は中置記法といい、演算子が引数の間に置かれる記法です。この他に後置記法という記法もあり、引数の後に演算子が置かれる記法です。後置記法は別名、逆ポーランド記法とも呼びます。前置記法はポーランド記法と呼びます。
各記法の記述例を次に示します。
中置記法 1 + 2 * 3 + 4
後置記法 2 3 * 1 + 4 +
前置記法 (+ 1 (* 2 3) 4)
中置記法では演算子の優先順位を考慮する必要があり、解析処理が複雑になります。後置記法はあらかじめ優先順位に応じて引数と演算子が配置されているので解析処理が簡単になります。前置記法は演算の優先順位が括弧で明示されるのでこちらも解析処理が簡単になります。また括弧を用いることにより加減乗除や論理演算などの演算子の引数に任意個の引数を指定できます。その反面、式が複雑になると括弧が何重にもなり、人間では理解することが難しくなります。
ユーザの制約指定をCIT-BACHが採用している前置記法の制約式に変換するには工夫が必要とされます。PictMasterでは制約表の制約指定を中置記法を採用しているPICTの制約式に変換していますが、この処理にはそれほど難しい点はありませんでした。しかし、制約表の制約指定から直接CIT-BACHの前置記法の制約式に変換することは処理が複雑になりすぎるため断念しました。
後置記法の書き方に関する情報はネット上にたくさんありますが、前置記法の書き方に関する情報はほとんどありません。調べた結果、前置記法の書き方には２つの方法のあることが分かりました。
１つ目は中置記法から構文木と呼ぶツリー形式のグラフを作成し、その枝をたどることで前置記法に変換する方法です。この方法では構文木さえ作成できればそれから前置記法に変換することはかなり簡単になります。この方法はCIT-BACHを生成エンジンに使用しているQumiasが採用している方法です。ただこの方法は中置記法から構文木を作成する点に難しさがあります。Qumiasではこの構文木の作成はユーザの役割となっています。
２つ目は中置記法の構文を変形して前置記法に変換する方法です。PictMasterではPICTのために中置記法の制約式を生成しているので、これを変形して前置記法の制約式に変換することにしました。前置記法への変換はいくつかのステップに分けて段階的に行なうようにします。
PICTの制約式からCIT-BACHの制約式への変換例を次に示します。
PICTの制約式
([B] = "b1" or [B] = "b2") and ([C] = "c1") or ([C] = "c1" or [C] = "c2") and ([D] = "d1" or [D] = "d2") ;
① ダブルクォーテーションを削除する。値の名称に空白は使えなくなる。行末のセミコロンを削除する。
([B] = b1 or [B] = b2) and ([C] = c1) or ([C] = c1 or [C] = c2) and ([D] = d1 or [D] = d2)
② 間に２項演算子（=と<>）がある２つの引数のうち、括弧で囲まれていない引数を括弧で囲む。
(([B] = b1) or ([B] = b2)) and ([C] = c1) or (([C] = c1) or ([C] = c2)) and (([D] = d1) or ([D] = d2))
③ 引数の間にある２項演算子（=と<>）を前に移動する。
((== [B] b1) or (== [B] b2)) and (== [C] c1) or ((== [C] c1) or (== [C] c2)) and ((== [D] d1) or (== [D] d2))
④ 括弧で囲まれている多項演算子（or）を前の"(("の間に移動する。
(or (== [B] b1) (== [B] b2)) and (== [C] c1) or (or (== [C] c1) (== [C] c2)) and (or (== [D] d1) (== [D] d2))
⑤ 括弧で囲まれていない多項演算子（２つのand）を左側の先頭の括弧の前に"("付きで移動し、右側の末尾の括弧に")"を付ける。
(and (or (== [B] b1) (== [B] b2)) (== [C] c1)) or (and (or (== [C] c1) (== [C] c2)) (or (== [D] d1) (== [D] d2)))
⑥ 括弧で囲まれていない多項演算子（1つのor）を左側の先頭の括弧の前に"("付きで移動し、右側の末尾の括弧に")"を付ける。
CIT-BACHの制約式
(or (and (or (== [B] b1) (== [B] b2)) (== [C] c1)) (and (or (== [C] c1) (== [C] c2)) (or (== [D] d1) (== [D] d2))))
実際の制約式ではここで示した制約式よりも複雑な構文のものがあるため、変換に必要な処理はもう少し多くかかる場合がありますが、ここで示した比較的簡単な変形を段階的に加えることによって中置記法から前置記法への変換を行なうことができます。
私たちが一般に用いる記法は中置記法といい、演算子が引数の間に置かれる記法です。この他に後置記法という記法もあり、引数の後に演算子が置かれる記法です。後置記法は別名、逆ポーランド記法とも呼びます。前置記法はポーランド記法と呼びます。
各記法の記述例を次に示します。
中置記法 1 + 2 * 3 + 4
後置記法 2 3 * 1 + 4 +
前置記法 (+ 1 (* 2 3) 4)
中置記法では演算子の優先順位を考慮する必要があり、解析処理が複雑になります。後置記法はあらかじめ優先順位に応じて引数と演算子が配置されているので解析処理が簡単になります。前置記法は演算の優先順位が括弧で明示されるのでこちらも解析処理が簡単になります。また括弧を用いることにより加減乗除や論理演算などの演算子の引数に任意個の引数を指定できます。その反面、式が複雑になると括弧が何重にもなり、人間では理解することが難しくなります。
ユーザの制約指定をCIT-BACHが採用している前置記法の制約式に変換するには工夫が必要とされます。PictMasterでは制約表の制約指定を中置記法を採用しているPICTの制約式に変換していますが、この処理にはそれほど難しい点はありませんでした。しかし、制約表の制約指定から直接CIT-BACHの前置記法の制約式に変換することは処理が複雑になりすぎるため断念しました。
後置記法の書き方に関する情報はネット上にたくさんありますが、前置記法の書き方に関する情報はほとんどありません。調べた結果、前置記法の書き方には２つの方法のあることが分かりました。
１つ目は中置記法から構文木と呼ぶツリー形式のグラフを作成し、その枝をたどることで前置記法に変換する方法です。この方法では構文木さえ作成できればそれから前置記法に変換することはかなり簡単になります。この方法はCIT-BACHを生成エンジンに使用しているQumiasが採用している方法です。ただこの方法は中置記法から構文木を作成する点に難しさがあります。Qumiasではこの構文木の作成はユーザの役割となっています。
２つ目は中置記法の構文を変形して前置記法に変換する方法です。PictMasterではPICTのために中置記法の制約式を生成しているので、これを変形して前置記法の制約式に変換することにしました。前置記法への変換はいくつかのステップに分けて段階的に行なうようにします。
PICTの制約式からCIT-BACHの制約式への変換例を次に示します。
PICTの制約式
([B] = "b1" or [B] = "b2") and ([C] = "c1") or ([C] = "c1" or [C] = "c2") and ([D] = "d1" or [D] = "d2") ;
① ダブルクォーテーションを削除する。値の名称に空白は使えなくなる。行末のセミコロンを削除する。
([B] = b1 or [B] = b2) and ([C] = c1) or ([C] = c1 or [C] = c2) and ([D] = d1 or [D] = d2)
② 間に２項演算子（=と<>）がある２つの引数のうち、括弧で囲まれていない引数を括弧で囲む。
(([B] = b1) or ([B] = b2)) and ([C] = c1) or (([C] = c1) or ([C] = c2)) and (([D] = d1) or ([D] = d2))
③ 引数の間にある２項演算子（=と<>）を前に移動する。
((== [B] b1) or (== [B] b2)) and (== [C] c1) or ((== [C] c1) or (== [C] c2)) and ((== [D] d1) or (== [D] d2))
④ 括弧で囲まれている多項演算子（or）を前の"(("の間に移動する。
(or (== [B] b1) (== [B] b2)) and (== [C] c1) or (or (== [C] c1) (== [C] c2)) and (or (== [D] d1) (== [D] d2))
⑤ 括弧で囲まれていない多項演算子（２つのand）を左側の先頭の括弧の前に"("付きで移動し、右側の末尾の括弧に")"を付ける。
(and (or (== [B] b1) (== [B] b2)) (== [C] c1)) or (and (or (== [C] c1) (== [C] c2)) (or (== [D] d1) (== [D] d2)))
⑥ 括弧で囲まれていない多項演算子（1つのor）を左側の先頭の括弧の前に"("付きで移動し、右側の末尾の括弧に")"を付ける。
CIT-BACHの制約式
(or (and (or (== [B] b1) (== [B] b2)) (== [C] c1)) (and (or (== [C] c1) (== [C] c2)) (or (== [D] d1) (== [D] d2))))
実際の制約式ではここで示した制約式よりも複雑な構文のものがあるため、変換に必要な処理はもう少し多くかかる場合がありますが、ここで示した比較的簡単な変形を段階的に加えることによって中置記法から前置記法への変換を行なうことができます。
生成エンジンCIT-BACHに対応したPictMaster 6.0 をリリースしました
PictMasterバージョン6.0をリリースしました。
バージョン6.0では、組み合わせ生成エンジンCIT-BACH（シットバック）に対応しました。CIT-BACHは、大阪大学の土屋達弘教授が開発したフリーソフトとしては国産初の本格的な組み合わせテストツールです。土屋教授にはバージョン6.0のリリースにあたってCIT-BACHを同梱して配布することを快諾していただきました。
PictMaster バージョン6.0では、生成エンジンをPICTとCIT-BACHのふたつからテスト対象に合わせて自由に選択することができるようになります。
CIT-BACHは機能の多様さではPICTに譲りますが、極めて複雑な制約指定を行なっても短時間に生成が完了するという特長があります。また最小テストケース生成が生成エンジン内部で行なわれるため、PICTよりも短時間に最小テストケース生成を行なうことができます。
通常はCIT-BACHを使用し、PICTの機能が必要な場合のみPICTを使用するという使い方がよいかもしれません。
PictMasterバージョン6.0は次のサイトからダウンロードすることができます。
http://sourceforge.jp/projects/pictmaster/
バージョン6.0では、組み合わせ生成エンジンCIT-BACH（シットバック）に対応しました。CIT-BACHは、大阪大学の土屋達弘教授が開発したフリーソフトとしては国産初の本格的な組み合わせテストツールです。土屋教授にはバージョン6.0のリリースにあたってCIT-BACHを同梱して配布することを快諾していただきました。
PictMaster バージョン6.0では、生成エンジンをPICTとCIT-BACHのふたつからテスト対象に合わせて自由に選択することができるようになります。
CIT-BACHは機能の多様さではPICTに譲りますが、極めて複雑な制約指定を行なっても短時間に生成が完了するという特長があります。また最小テストケース生成が生成エンジン内部で行なわれるため、PICTよりも短時間に最小テストケース生成を行なうことができます。
通常はCIT-BACHを使用し、PICTの機能が必要な場合のみPICTを使用するという使い方がよいかもしれません。
PictMasterバージョン6.0は次のサイトからダウンロードすることができます。
http://sourceforge.jp/projects/pictmaster/
まもなく組み合わせ生成エンジン CIT-BACH に対応したPictMasterをリリースします
CIT-BACHは、大阪大学の土屋教授が開発したフリーソフトとしては国産初の本格的な組み合わせテストツールです。PictMaster バージョン6.0では、生成エンジンをPICTとCIT-BACHのふたつからテスト対象に合わせて自由に選択することができるようになります。
今回、PictMasterがCIT-BACHをサポートするようにした理由としては、PictMasterでデシジョンテーブルのテストケースを生成しようとした場合に、複雑な制約指定ではPICTの場合に長時間かかり、実用的でなくなるという問題を解決したいと思ったからです。こうした場合でもCIT-BACHでは短時間でテストケースを生成することができます。
CIT-BACHはPICTほど多機能ではありませんが、PictMasterの側で機能を補うことでPICTを使用する場合と機能面ではほとんど変わらないようにしました。
作りこみはほぼ完了し、後はマニュアルの追記・変更と全体的なテストが残っています。今後１～２週間程度でリリースできる予定です。
CIT-BACHは次のサイトからダウンロードすることができます。
http://blog.livedoor.jp/chavannes/archives/51858712.html
今回、PictMasterがCIT-BACHをサポートするようにした理由としては、PictMasterでデシジョンテーブルのテストケースを生成しようとした場合に、複雑な制約指定ではPICTの場合に長時間かかり、実用的でなくなるという問題を解決したいと思ったからです。こうした場合でもCIT-BACHでは短時間でテストケースを生成することができます。
CIT-BACHはPICTほど多機能ではありませんが、PictMasterの側で機能を補うことでPICTを使用する場合と機能面ではほとんど変わらないようにしました。
作りこみはほぼ完了し、後はマニュアルの追記・変更と全体的なテストが残っています。今後１～２週間程度でリリースできる予定です。
CIT-BACHは次のサイトからダウンロードすることができます。
http://blog.livedoor.jp/chavannes/archives/51858712.html
デシジョンテーブルの圧縮で任意値を使うとテスト漏れが起きる 正しい具体値を指定し圧縮する必要あり
圧縮したデシジョンテーブルでテスト漏れが起きることはこれまで何度か取り上げてきましたが、今回はテスト対象のプログラム構造に合わせて安全に圧縮する方法を考えてみます。
例題としてある映画館の入場料金を決定するデシジョンテーブルとします。この入場料金は次の表で決定されます。ただしレイトショーと障害者の場合は1000円となります。
このモデルで生成したテストケースを次に示します
この入場料金を決定するテスト対象の制御フローを次に示します。
次に単純に圧縮したデシジョンテーブルの制約表を示します。
この制約表で生成したテストケースを次に示します。
一見するとこの６件のテストケースで問題がないように見えます。ですがこのテストケースではテスト漏れが起きます。テスターが任意値の「-」の部分に適当な値を選択してテストを行なうことになっていますが、選択した値によってはシニアと中学生以下の場合がテストされないケースが生じます。任意値のレイトショーと障害者のどちらかに真を指定してテストを行なうと、制御フローでのシニアと中学生以下のルート（すべてが偽）が網羅されず、テスト漏れとなるのです。
テスト対象のプログラム構成に合わせて正しく圧縮したデシジョンテーブルとなる制約表を次に示します。
この制約表で生成したテストケースを次に示します。
この例で示したように、圧縮したでジョンテーブルでテストする場合にはテストケースに任意値（「-」など）を含めずに、テスト対象のプログラム構造を理解したうえで正しい具体値を記入しておく必要があります。そうでない場合にテスト漏れとなることがあります。ここまでくるとほとんどホワイトボックステストの世界です。
例題としてある映画館の入場料金を決定するデシジョンテーブルとします。この入場料金は次の表で決定されます。ただしレイトショーと障害者の場合は1000円となります。
このモデルで生成したテストケースを次に示します
この入場料金を決定するテスト対象の制御フローを次に示します。
次に単純に圧縮したデシジョンテーブルの制約表を示します。
この制約表で生成したテストケースを次に示します。
一見するとこの６件のテストケースで問題がないように見えます。ですがこのテストケースではテスト漏れが起きます。テスターが任意値の「-」の部分に適当な値を選択してテストを行なうことになっていますが、選択した値によってはシニアと中学生以下の場合がテストされないケースが生じます。任意値のレイトショーと障害者のどちらかに真を指定してテストを行なうと、制御フローでのシニアと中学生以下のルート（すべてが偽）が網羅されず、テスト漏れとなるのです。
テスト対象のプログラム構成に合わせて正しく圧縮したデシジョンテーブルとなる制約表を次に示します。
この制約表で生成したテストケースを次に示します。
この例で示したように、圧縮したでジョンテーブルでテストする場合にはテストケースに任意値（「-」など）を含めずに、テスト対象のプログラム構造を理解したうえで正しい具体値を記入しておく必要があります。そうでない場合にテスト漏れとなることがあります。ここまでくるとほとんどホワイトボックステストの世界です。
デシジョンテーブルテストと組み合わせテストを同時に行なう
デシジョンテーブルは複雑な論理関係のテストに使用しますが、この組み合わせと他の組み合わせで問題が起きないことを確認したいと思ったことはないでしょうか。例えば、何種類かある要因がそれぞれ同じ複雑な論理関係のある処理にかかわっている場合には、どの要因と組み合わせても問題は起きないはずですが念のために問題が起きないか確認したい場合です。これはデシジョンテーブルテストと組み合わせテストの併用になります。
デシジョンテーブルテストと組み合わせテストの併用は、PictMasterの「拡張サブモデル」の機能で行なうことができます。
例として次に示すモデルをあげます。このモデルでパラメータD～Hの５個はデシジョンテーブルのパラメータとします。パラメータA～Cがデシジョンテーブルと組み合わせる要因です。
５１件のうち、４８件は５つのパラメータの全数組み合わせによるものです。残りの３件が他の要因との２パラメータ間の組み合わせを指定したために増えた件数です(*1)。このようにデシジョンテーブルテストと組み合わせテストを併用してもテストケース数はほとんど増えません。
デシジョンテーブルテストと組み合わせテストの併用は、比較的よく使われることになると思います。PictMasterを使用してデシジョンテーブルテストのテストケースを生成する場合は、こうした使い方も可能です。
*1: 正確にいうと、件数が増えたのは拡張サブモデルを用いたことによるものです。このモデルを拡張サブモデルを使わずに単純に組み合わせるパラメータに２を指定して生成するとテストケース数は12件となります。デシジョンテーブルによる件数の48件はこれよりはるかに多い数ですから、このデシジョンテーブルに組み合わせテストでの組み合わせるパラメータを追加しても、このモデルの場合は48件よりも本来は増加はしません。４件の増加は拡張サブモデルを機能させるためにワーク的に生じたものです。
デシジョンテーブルテストと組み合わせテストの併用は、PictMasterの「拡張サブモデル」の機能で行なうことができます。
例として次に示すモデルをあげます。このモデルでパラメータD～Hの５個はデシジョンテーブルのパラメータとします。パラメータA～Cがデシジョンテーブルと組み合わせる要因です。
５１件のうち、４８件は５つのパラメータの全数組み合わせによるものです。残りの３件が他の要因との２パラメータ間の組み合わせを指定したために増えた件数です(*1)。このようにデシジョンテーブルテストと組み合わせテストを併用してもテストケース数はほとんど増えません。
デシジョンテーブルテストと組み合わせテストの併用は、比較的よく使われることになると思います。PictMasterを使用してデシジョンテーブルテストのテストケースを生成する場合は、こうした使い方も可能です。
*1: 正確にいうと、件数が増えたのは拡張サブモデルを用いたことによるものです。このモデルを拡張サブモデルを使わずに単純に組み合わせるパラメータに２を指定して生成するとテストケース数は12件となります。デシジョンテーブルによる件数の48件はこれよりはるかに多い数ですから、このデシジョンテーブルに組み合わせテストでの組み合わせるパラメータを追加しても、このモデルの場合は48件よりも本来は増加はしません。４件の増加は拡張サブモデルを機能させるためにワーク的に生じたものです。