ホーム » 2021 » 11月

月別アーカイブ: 11月 2021

2021年11月
 123456
78910111213
14151617181920
21222324252627
282930  

最新の投稿(電子情報)

アーカイブ

カテゴリー

データベーステスト前授業

本来は、データベースの正規形に関連する話題を説明する予定であったが、後期の中間試験以降の範囲なので、新しい内容の説明は止めることとした。代わりに、過去のテスト問題の事例を示し、レポート課題を作成する時間とした。

銀杏の季節になりました

{CAPTION}

Linux演習

Linux演習資料

理解度確認

B木とデータベース

2分探索木の考え方を拡張したもので、B木がある。

B木の構造

2分木では、データの増減で木の組換えの発生頻度が高い。そこで、1つのノード内に複数のデータを一定数覚える方法をとる。B木では、位数=Nに対し、最大2N個のデータ d0..d2N-1 と、2N+1本のポインタ p0..p2N から構成される。piの先には、di-1< x < di を満たすデータが入った B木のノードを配置する。ただし、データの充填率を下げないようにするため、データは最小でもN個、最大で2N個を保存する。下図は位数2のB木の例を示す。

B木からデータの検索

データを探す場合は、ノード内のデータ di の中から探し、見つからない場合は、ポインタの先のデータを探す。位数がある程度大きい場合、ノード内の検索は2分探索法が使用できる。また、1つのノード内の検索が終われば、探索するデータ件数は、1/N〜1/2Nとなることから、指数的に対象件数が減っていく。よって、検索時間のオーダは、O(logN) となる。

B木へのデータの追加

B木にデータを追加する場合は、ノード内に空きがあれば、単純にデータの追加を行う。ノード内のデータが2N個を越える場合は、以下のような処理を行う。

ノード内のデータと追加データを並べ、その中央値を選ぶ。この中央値より大きいデータは、新たにつくられたノードに移す。中央値のデータは上のノードに追加処理を行う。このような方法を取ることで、2分木のような木の偏りが作られにくい構造となるようにする。

データを削除する場合も同様に、データ件数がN個を下回る場合は、隣接するノードからデータを取ってくることで、N個を下回らないようにする。

B木とデータベース

このB木の構造は、一般的にデータベースのデータを保存するために広く利用されている。

データベースシステムでは、データを効率よく保存するだけでなく、データの一貫性が保たれるように作られている。
例えば、データベースのシステムが途中でクラッシュした場合でも、データ更新履歴の情報を元にデータを元に戻し、データを再投入して復旧できなければならない。データを複数の所からアクセスした場合に、その順序から変な値にならないように、排他制御も行ってくれる。

データベースで最も使われているシステムは、データすべてを表形式で扱うリレーショナル・データベースである。

((リレーショナル・データベースの例))
STUDENT[]                           RESULT[]
ID   | name     | grade | course    ID   | subject | point
-----+----------+-------+--------   -----+---------+-------
1001 | t-saitoh |  5    | EI        1001 | math    | 83
1002 | sakamoto |  4    | E         1001 | english | 65
1003 | aoyama   |  4    | EI        1002 | english | 90
                                   外部キー
((SQLの例 2つの表の串刺し))
-- 60点以上の学生名,科目名,点数を出力 --
select STUDENT.name, RESULT.subject, RESULT.point --射影--
   from STUDENT , RESULT                          --結合--
   where STUDENT.ID == RESULT.ID    -- 串刺し --   --選択--
         and RESULT.point >= 60 ;

((上記SQLをC言語で書いた場合))
for( st = 0 ; st < 3 ; st++ )                   // 結合(from)
   for( re = 0 ; re < 3 ; re++ )
      if ( student[ st ].ID == result[ re ].ID  // 選択(where)
           && result[ re ].point >= 60 )
           printf( "%s %s %d" ,                 // 射影(select)
                   student[ st ].name ,
                   result[ re ].subject ,
                   result[ re ].point ) ;

B+木

データベースの処理では、目的のデータを O(log N) で見つける以外にも、全データに対する処理も重要である。この場合、全てのデータに対する処理では、単純なB木では再帰呼び出しが必要となる。しかし、他の表でも再帰処理を伴うと、プログラムは複雑になってしまう。

そこで、B木のデータを横方向に並べて処理を行う場合に、その処理が簡単になるように B+木が用いられる。
この方法では、末端のノードは、隣接するノードへのポインタを持つ。下図で示すB+木では、青で示す検索用のB木の部分と、赤で示す順次処理を行うためのシーケンスセットの部分から構成される。

ホスト言語とのインタフェースとERモデル

今日は、前半でホスト言語とSQLのインタフェースとその問題点について説明し、後半では次の章の目標となる適切なデータベース設計のための導入を説明する。

ホスト言語とのインタフェースとSQLインジェクション

プログラミング言語によっては、その言語の中でSQLを使うために「組み込み型のSQL」が使えるものがある。
(COBOL,PL/Iなど)

動的メモリ管理が得意な最近のPythonやPHPなどの言語であれば、データベース参照の関数が利用できる。

SQLインジェクション

例えば、PHPでは、SQLからデータを取り出す処理は、以下のようになる。

// 検索するユーザID
$id = "t-saitoh" ;
$pdo = new PDO( '...' ) ; // データベースに接続する関数
$sql = "select name from usertable where id='$id'" ;
$query = $pdo->prepare( $sql ) ;

// 取り出せたデータに関する処理 id がプライマリキーならforeachは1回ループのはず
foreach( $query->fetcAll() as $name ) {
   // $name に取り出した名前が入っている
} 

しかし、$id の部分を、Web の入力フォームなどの値であれば、名前以外の情報が入力される場合もある。

この際に、「 $id = ” ‘ or 1==1 — ‘ ” 」といった値が入っていた場合、SQLで実行される命令は、

$id = "' or 1==1 --'" の場合
$sql = "select name from usertable where id='' or 1==1 -- ''" ;

となってしまい、本来なら1人のデータを抽出する select 命令が、全テーブルに対して該当してしまい、情報漏洩が発生するかもしれない。

「 $id = “‘; drop usertable ; — ‘” 」であれば、usertable が消されてしまい、システムが動かなくなる(サービスを提供できなくする攻撃 = DoS攻撃 – Denial-of-service attack)ことも考えられる。

他にもSQLインジェクションを使う技がある。こちらの CTF の WriteUp などが参考になる。

こういった攻撃手法は、SQLに本来の意図ではないSQL命令を紛れ込ませる攻撃ということで、SQLインジェクションという。

SQLインジェクションで発生した有名な事件では、以下のようなものがある。

対策としては、ユーザが入力したデータを用いて SQL 命令を実行する場合は、ユーザ入力をSQLとして悪用されないように、シングルクオートなどをエスケープするなどの処理が必要となる。さまざまな手法があるので、SQL無効化の専用関数を用いるべき。

また、データベースシステムは、ネットワーク経由でSQLによる処理を行うが、データベースサーバ自体がインターネットに接続されていて、パスワード攻撃によりデータベース本体に不正アクセスが行われる場合もある。一般的なデータベースを用いたシステムは、フロントエンドのWebサーバ、スレーブDBサーバ、マスタDBサーバの三層構成をとることが多いが、バックエンドのデータベースは、インターネットから隔離しフロントエンドのWebサーバのみ接続できるようにするのが一般的である。

データベースに接続する場合はパスワードにより利用者を限定することができるが、データベースシステム自体がインターネットに接続されていると、パスワード総当たり攻撃(ブルートフォース攻撃)や、パスワードスプレー攻撃(総当たり攻撃は、短時間でパスワード失敗が多発するのでシステムで接続拒否するのが一般的。これを回避するために時間をかけて総当たり攻撃をする手法)により、情報漏洩が発生する。


データベースの設計

リレーショナル・データベースでは、データは表形式であればなんでも良い訳ではない。

例えば、学生の成績データが以下のような構造であった場合、

 ID   | name   | grade | subject  | teacher
------+--------+-------+----------+---------
20101 | aoyama |   1   | database | saitoh
20101 | aoyama |   1   | software | murata
20002 | suzuki |   2   | database | saitoh
20002 | suzuki |   2   | compiler | nishi
30203 | yamada |   3   | media    | ogoshi
  • 修正不整合: 授業担当が saitoh → takaku のように変更になったら、複数のテーブルを修正しなければならない。大量のレコード修正は、時間がかかるし、その途中にシステムダウンしたらデータの整合性に問題が発生するかも。
  • 挿入不整合: 新しい科目 internet を追加したいけど、受講学生が決まらないとデータを挿入できない。
  • 削除不整合: yamada が受講を取りやめたら、科目 media も消えてしまう。

これらを考慮すると、以下のような3つの表で設計するべきである。

学生                      受講            科目
ID    | name   | grade    ID   | SubID   SubID | subject | teacher
------+--------+-------  ------+-------  ------+----------+--------
20101 | aoyama | 1       20101 | 1001     1001 | database | saitoh → takaku
20002 | suzuki | 2       20101 | 1002     1002 | software | murata
30203 | yamada | 3       20002 | 1001     1003 | compiler | nishi
                         20002 | 1003     1004 | media    | ogoshi
                  消す→ 30203 | 1004     1005 | internet | foobar → 追加

データベースの設計では、(1)概念設計、(2)論理設計、(3)物理設計が行われる。

  • 概念設計:概念スキーマの決定(実体・関係モデルを使う)。上記の受講データベースの設計例
  • 論理設計:論理スキーマの決定。関係データベースで実装?ほかのデータベース?
  • 物理設計:物理スキーマの決定。データの格納方法や管理方法を決める。

実体関連モデル(ERモデル)

データベース設計では、実体関連モデル(ERモデル:Entity-Relation model)が使われる。 実体とは、モデル化しようとする対象で独立した存在となれるもの。 実体が持つ色々な特性は属性と呼ばれる。 属性の取りうる値の集合を定義域、同一種類の実体の集まりを実体集合と呼ぶ。 関連とは、実体同士の相互関係をモデル化したもの

実体関連図(ER図)では、実体を長方形、関連をひし形、属性を楕円で表現する。 属性で、キーとなるものには下線をつけて表す。

ER図で調べると、実際にはもっと細かい規定で表現が行われている。 参考:IDEF1X表記とIE表記

演算子と2分木による式の表現

2分木の応用として式の表現の説明を行うけど、その前に計算式の一般論の説明を行う。

逆ポーランド記法

一般的に 1*2 + 3*4 と記載すると、数学的には演算子の優先順位を考慮して、(1*2)+(3*4) のように乗算を先に行う。このような優先順位を表現する時に、()を使わない方法として、逆ポーランド記法がある。

演算子の書き方には、前置記法、中置記法、後置記法があり、後置記法は、「2と3を掛ける、それに1を加える」と捉えると、日本語の処理と似ている。

中置記法 1+2*3
前置記法 +,1,*,2,3
後置記法 1,2,3,*,+  # 1と「2と3をかけた値」をたす。

後置記法は、一般的に逆ポーランド記法(Reverse Polish Notation)とも呼ばれ、式を機械語の命令に置き換える際に役立つ。

演算子の右結合・左結合

例えば、”1/2*3″という式が与えられたとする。この結果は、1/6だろうか?3/2だろうか?

一般的な数学では、優先順位が同じ演算子が並んだ場合、左側から計算を行う。つまり”1/2*3″は、”(1/2)*3″を意味する。こういった左側の優先順位が高い演算子は左結合の演算子という。

ただしC言語では、”a = b = c = 0″ と書くと、”a = (b = (c = 0))” として扱われる。こういった代入演算子は、 右結合の演算子である。

理解度確認

以下の式を指定された書き方で表現せよ。

逆ポーランド記法 1,2,*,3,4,*,+ を中置記法で表現せよ。
中置記法 (1+2)*3-4*5 を逆ポーランド記法で表現せよ。

以前の情報処理技術者試験では、スタックの概念の理解の例題として、逆ポーランド記法への変換アルゴリズムのプログラム作成が出題されることが多かったが、最近は出題されることはなくなってきた。

逆ポーランド記法の式の実行

この逆ポーランド記法で書かれた式から結果を求めるプログラムは以下のように記述できる。このプログラムでは式を簡単にするため、数値は1桁の数字のみとする。

// 単純な配列を用いたスタック
int stack[ 10 ] ;
int sp = 0 ;

void push( int x ) {
   stack[ sp++ ] = x ;
}
int pop() {
   return stack[ --sp ] ;
}

// 逆ポーランド記法の計算
int rpn( char* p ) {
   for( ; *p != '
// 単純な配列を用いたスタック
int stack[ 10 ] ;
int sp = 0 ;

void push( int x ) {
   stack[ sp++ ] = x ;
}
int pop() {
   return stack[ --sp ] ;
}

// 逆ポーランド記法の計算
int rpn( char* p ) {
   for( ; *p != '\0' ; p++ ) {
      if ( isdigit( *p ) ) {
         //         ~~(A)
         // 数字はスタックに積む
         push( *p - '0' ) ;
         //    ~~~~~~~~(B)
      } else if ( *p == '+' ) {
         // 演算子+は上部2つを取出し
         int r = pop() ;
         int l = pop() ;
         // 加算結果をスタックに積む
         push( l + r ) ;
      } else if ( *p == '*' ) {
         // 演算子*は上部2つを取出し
         int r = pop() ;
         int l = pop() ;
         // 乗算結果をスタックに積む
         push( l * r ) ;
      }//~~~~~~~~~~~~~(C)
   }
   // 最終結果がスタックに残る
   return pop() ;
}

void main() {
   printf( "%d\n" , rpn( "123*+" ) ) ;
}
' ; p++ ) { if ( isdigit( *p ) ) { // ~~(A) // 数字はスタックに積む push( *p - '0' ) ; // ~~~~~~~~(B) } else if ( *p == '+' ) { // 演算子+は上部2つを取出し int r = pop() ; int l = pop() ; // 加算結果をスタックに積む push( l + r ) ; } else if ( *p == '*' ) { // 演算子*は上部2つを取出し int r = pop() ; int l = pop() ; // 乗算結果をスタックに積む push( l * r ) ; }//~~~~~~~~~~~~~(C) } // 最終結果がスタックに残る return pop() ; } void main() { printf( "%d\n" , rpn( "123*+" ) ) ; }

逆ポーランド記法の式の実行は、上記のようにスタックを用いると簡単にできる。このようなスタックと簡単な命令で複雑な処理を行う方法はスタックマシンと呼ばれる。Java のバイトコードインタプリタもこのようなスタックマシンである。

Cプログラママニア向けの考察

上記のプログラムでは、int r=pop();…push(l+r); で記載しているが、

push( pop() + pop() ) ;

とは移植性を考慮して書かなかった。理由を述べよ。

最初の関数電卓

初期の関数電卓では複雑な数式を計算する際に、演算子の優先順位を扱うのが困難であった。このため、HP社の関数電卓では、式の入力が RPN を用いていた。(HP-10Cシリーズ)

2項演算と構文木

演算子を含む式が与えられたとして、古いコンパイラではそれを逆ポーランド変換して計算命令を生成していた。しかし最近の複雑な言語では、計算式や命令を処理する場合、その式(または文)の構造を表す2分木(構文木)を生成する。。

   +
  / \
 1   *
    / \
   2   3

演算子の木のノードで、末端は数値であることに注目し、右枝・左枝がNULLなら数値(data部にはその数値)、それ以外は演算子(data部には演算子の文字コード)として扱うとして、上記の構文木のデータを作る処理と、その構文木の値を計算するプログラムを示す。

struct Tree {
   int  data ;
   struct Tree* left ;
   struct Tree* right ;
} ;
struct Tree* tree_int( int x ) // 数値のノード
{
   struct Tree* n ;
   n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
   if ( n != NULL ) {
      n->data = x ;
      n->left = n->right = NULL ;
   }
   return n ;
}
struct Tree* tree_op( int op , // 演算子のノード
                   struct Tree* l , struct Tree* r ) {
   struct Tree* n ;
   n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
   if ( n != NULL ) {     // ~~~~~~~~~~~~~~~~~~~~~(D)
      n->data  = op ;
      n->left  = l ;
      n->right = r ;
   }
   return n ;
}
// 与えられた演算子の木を計算する関数
int eval( struct Tree* p ) {
   if ( p->left == NULL && p->right == NULL ) {
      // 数値のノードは値を返す
      return p->data ;
   } else {
      // 演算子のノードは、左辺値,右辺値を求め
      // その計算結果を返す
      switch( p->data ) {
      case '+' : return eval( p->left ) + eval( p->right ) ;
      case '*' : return eval( p->left ) * eval( p->right ) ;
      }              // ~~~~~~~~~~~~~~~(E)      ~~~~~~~~(F)
   }
}

void main() {
   struct Tree* exp =  // 1+(2*3) の構文木を生成
      tree_op( '+' ,
               tree_int( 1 ) ,
               tree_op( '*' ,
                        tree_int( 2 ) ,
                        tree_int( 3 ) ) ) ;
   printf( "%d¥n" , eval( exp ) ) ;
}

理解度確認

  • push(),pop() のスタックは、保存と取り出しの順序を表す単語の頭文字4つを使って何と呼ばれるか?
  • 上記プログラム中の(A)~(F)の型を答えよ。

GROUP BY HAVINGとビューテーブル

GROUP BY HAVING

GROUP BY-HAVING では、指定されたカラムについて同じ値を持つレコードがグループ化される。SELECT 文に指定される集約関数は、グループごとに適用される。HAVING は、ある条件を満たす特定のグループを選択するための条件で、WHERE と違い、集約関数が使える。

SELECT SG.商品番号, SUM(SG.在庫量)
  FROM SG
  GROUP BY SG.商品番号 HAVING SUM(SG.在庫量) >= 500 ;

このSQLを実行すると、SG のテーブルから、商品番号が同じものだけをあつめてグループ化される。そのグループごとに在庫量のデータの合計SUMを集約し、500以上のデータが出力される。

CREATE VIEW

今までで述べてきたSQLでは、実際のテーブルを対象に、結合・選択・射影を行う命令であり、これは概念スキーマと呼ばれる、対象となるデータベース全体を理解したプログラマによって扱われる。

しかし、プログラムの分業化を行い、例えば結果の表示だけを行うプログラマにしてみれば、全てのデータベースの表を考えながらプログラムを作るのは面倒である。そこで、結合・選択・射影の演算の結果で、わかりやすい単純な表となったものであれば、初心者のデータベースプログラマでも簡単に結果を扱うことができる。このような外部スキーマを構成するための機能が、ビューテーブルである。

-- 優良業者テーブルを作る --
CREATE VIEW 優良業者 ( 業者番号 , 優良度 , 所在 )
    AS SELECT S.業者番号, S.優良度, S.所在
         FROM S
         WHERE S.優良度 >= 15 ;

-- 優良業者テーブルから情報を探す --
SELECT *
  FROM 優良業者
  WHERE 優良業者.所在 = '福井' ;

ビューテーブルに対する SQL を実行すると、システムによっては予め実行しておいた CREATE VIEW の AS 以下の SQL の実行結果をキャッシュしておいて処理を行うかもしれない。システムによっては SQL の命令を 副クエリを組合せた SQL に変換し、処理を行うかもしれない。しかし、応用プログラマであれば、その SQL がどのように実行されるかは意識する必要はほとんど無いであろう。

ただし、ビューテーブルに対する 挿入・更新・削除といった演算を行うと、データによっては不整合が発生することもあるので注意が必要である。

SQL言語

教科書の流れに沿ってSQLの言語について、再掲

  • スキーマ定義
    • CREATE – 実テーブル、ビューテーブルの定義
    • GRANT – 権限の定義
  • スキーマ操作
    • DROP – 実テーブル、ビューテーブルの削除
    • REVOKE – 権限の削除
    • ALTER – テーブルの変更
    • ADD – カラムの追加
  • データ操作
    • SELECT, INSERT, DELETE, UPDATE – レコードの検索、追加・削除・更新
    • トランザクション処理
      • データベースでは、原子性などを満たすためにデータベースへの更新履歴を保持している。これらの更新履歴をデータベースに反映させ確定する処理がトランザクション処理。
      • COMMIT – データベースの更新処理を確定
      • ROLLBACK – データベースの更新処理を取り消す

昨年度の資料では、次のネタも入っていたけど、後半の授業を演習時間とするため、説明はここまで。

WebAssembly環境の構築

卒研で WebAssembly を使った開発をしてもらっているけど、自分でも試したいので環境の構築。

Debian emscripten パッケージだけではダメだった

卒研の学生さんが、emscripten 使っているという話だったので、”aptitude search emscripten” を実行したら、パッケージがあったので、”aptitude install emscripten” を実行。鉄板の hello world をコンパイルしようとしたら、”LLVM version appears incorrect (seeing “11.0”, expected “10.0”)”というエラーが出て、コンパイルに失敗。

llvm の C コンパイラとのバージョンが合わない様子。ということで、git より環境を構築してみる。

git で emsdk 環境の構築

通常ユーザであれば、”git clone https://github.com/juj/emsdk.git” を実行すると、その PATH 直下に環境が作られるみたい。こういう使い方は好きじゃないので…

$ sudo bash
((( ひとまず emscripten は必要みたい )))
# apt-get install emscripten # 導入後は不要?
((( emsdk のインストール )))
# cd /usr/local
# git clone https://github.com/juj/emsdk.git
# cd emsdk
# ./emsdk install latest
# ./emsdk activate latest

Hello World を試す

((( 自分の環境で以下のコマンドにより環境変数をセット )))
$ source /usr/local/emsdk/emsdk_env.sh
((( Hello World をコンパイル )))
$ cd ~/public_html
$ mkdir test
$ cd test
$ vi hello.c
#include 
int main( int argc , char* argv[] ) {
   printf( "Hello World\n" ) ;
   return 0 ;
}
$ emcc test.c -s WASM=1 -o test.html
$ ブラウザで test.html を開く http://...URL.../~t-saitoh/test/test.html

ブラウザから自分のC言語(wasm)を呼び出し結果を出力

$ mkdir html_template
$ cp /usr/local/emsdk/upstream/emscripten/src/shell_minimal.html html_template
$ vi html_template/shell_minimal.html
((( C言語側を呼び出すボタンを埋め込む )))
<textarea class="emscripten" id="input"></textarea>
<input type="button" value="CALL WASM" onclick="Module._ems_func();"/>

((( test.cxx )))
#include <stdio.h>
#include <emscripten/emscripten.h>
#include <string>

int main( int argc , char* argv[] ) {
  return 0 ;
}

// void* getElementValue_( char const* id ) { ... } が作られる
EM_JS( void* , getElementValue_ , (char const* id) ,
{
  var e = document.getElementById( UTF8ToString( id ) ) ;
  var str = e.value ;
  var len = lengthBytesUTF8( str ) + 1 ;
  // コンパイル時に -s EXPORTED_FUNCTIONS="['_malloc']" しないとエラーがでる
  var heap = _malloc( len ) ;

  stringToUTF8( str , heap , len ) ;
  return heap ;
 } ) ;

// std::string型はC++の文字列処理の型
//   std::string s( "abcde" ) ;
//   s.c_str() で、C言語のNULターミネータ付きの文字列を参照できる。

std::string getElementValue( std::string const &id )
{
  void *p = getElementValue_( id.c_str() ) ;
  std::string s( (char const*) p ) ;
  free( p ) ;
  return s ;
}

void setElementValue( std::string const &id , std::string const &value )
{
  EM_ASM( {
      var e = document.getElementById( UTF8ToString( $0 ) ) ;
      e.value = UTF8ToString( $1 ) ;
    } , id.c_str() , value.c_str() ) ;
}

#ifdef __cplusplus
extern "C" {
#endif

  /* HTMLに埋め込んだ onclick=_ems_func() で呼び出される*/
  void EMSCRIPTEN_KEEPALIVE ems_func() {
    std::string input = getElementValue( "input" ) ;
    setEnvironmentValue( "output" , input ) ;
  }

#ifdef __cplusplus
}
#endif

((( test.cxx をコンパイル )))
$ source /usr/local/emsdk/emsdk_env.sh
$ em++ -o test.html test.cxx -O3 -s WASM=1 -s EXPORTED_FUNCTIONS="['_main','_malloc']" --shell-file html_template/shell_minimal.html

意思決定木と構文解析

前回までの授業で2分探索木の説明をしてきたが、このデータ構造は他のデータを扱う際にも用いられる。ここで、意思決定木と構文木を紹介する。

意思決定木

意思決定木の説明ということで、yes/noクイズの例を示しながら、2分木になっていることを 説明しプログラムを紹介。

   ((意思決定木の例:うちの子供が発熱した時))
       38.5℃以上の発熱がある?
      no/         \yes
   元気がある?        むねがひいひい?
 yes/    \no      no/     \yes
様子をみる 氷枕で病院  解熱剤で病院  速攻で病院

このような判断を行うための情報は、yesの木 と noの木の2つの枝を持つデータである。これは2分木と同じであり、このような処理は以下のように記述ができる。

struct Tree {
   char *qa ;
   struct Tree* yes ;
   struct Tree* no ;
} ;
struct Tree* dtree( char *s ,
                    struct Tree* l , struct Tree* r )
{  struct Tree* n ;
   n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
   if ( n != NULL ) {
      n->qa = s ;
      n->yes = l ;
      n->no = r ;
   }
   return n ;
}
void main() {
   struct Tree* p =
      dtree( "38.5℃以上の発熱がある?" ,
             dtree( "胸がひぃひぃ?" ,
                    dtree( "速攻で病院",NULL,NULL ) ,
                    dtree( "解熱剤で病院",NULL,NULL ) ) ,
             dtree( "元気がある?" ,
                    dtree( "様子をみる",NULL,NULL ) ,
                    dtree( "氷枕で病院",NULL,NULL ) ) ) ;
   // 決定木をたどる
   struct Tree* d = p ;
   while( d->yes != NULL || d->no != NULL ) {
      printf( "%s¥n" , d->qa ) ;
      scanf( "%d" , &ans ) ;
      // 回答に応じてyes/noの枝に進む。
      if ( ans == 1 )      // yesを選択
         d = d->yes ;
      else if ( ans == 0 ) // noを選択
         d = d->no ;
   }
   // 最終決定を表示
   printf( "%s¥n" , d->qa ) ;
}

コンパイラと言語処理系

2分木の応用の構文木について、この後説明を行うが、構文木を使うコンパイラなどの一般知識を事前に説明しておく。

高級言語で書かれたプログラムを計算機で実行するソフトウェアは、言語処理系と呼ばれる。その実行形式により

  • インタプリタ(interpreter:通訳)
    • ソースプログラムの意味を解析しながら、その意味に沿った処理を行う
  • コンパイラ(compiler:翻訳)
    • ソースプログラムから機械語を生成し、実行する際には機械語を実行
  • トランスレーター
    • ソースから他の言語のソースコードを生成し、それをさらにコンパイルし実行
      最初のC++の実装では、C++をトランスレータにかけてC言語を生成し、C言語のコンパイラで動かしていた。
  • バイトコードインタプリタ
    • ソースからバイトコード(機械語に近いコードを生成)、実行時にはバイトコードの命令に沿った処理を行う
  • エミュレーター
    • 異なるCPUのコンピュータで、システムの動作や機能を模倣して動かすシステム。
      近々の例であれば、AppleのARMベースM1チップで intel CPU の動きを真似て動作させる Rosetta2 がトピック。パソコンで古いファミコンのソフトを動かすといった技術もエミュレータ。

      • 同じCPUで異なるOSを動かす場合は、CPU仮想化。

に分けられる。

C言語で機械語が生成されるまで

C言語のプログラムから、機械語の命令が生成されるまでは、以下のような処理が行われる。
一般的にコンパイラの処理というと、ソースコードから機械語を生成するまでの処理を指すが、C言語ではプリプロセッサ処理を含んだり、コンパイラの処理(ソースコードからオブジェクトファイル生成まで)のほかにリンク処理を含んで使われることも多い。

foo.c C言語のソース
↓     プリプロセッサ処理
foo.c(#行の無いC言語のソース)
↓     コンパイラ
foo.obj(オブジェクトファイル/中間コード)
↓
(+) ← ライブラリ(scanf,printfなどの組み込み関数などをまとめたもの)
↓     リンカ(リンケージエディタ)
foo.exe

コンパイラの処理

コンパイラが命令を処理する際には、以下の処理が行われる。

  1. 字句解析(lexical analysys)
    文字列を言語要素(token)に分解
  2. 構文解析(syntax analysys)
    tokenの並び順に意味を反映した構造を生成
  3. 意味解析(semantics analysys)
    命令に合わせた中間コードを生成
  4. 最適化(code optimization)
    中間コードを変形して効率よいプログラムに変換
  5. コード生成(code generation)
    実際の命令コード(オブジェクトファイル)として出力

バイトコードインタプリタとは

例年だと説明していなかったけど最近利用されるプログラム言語の特徴を説明。

通常、コンパイラとかインタプリタの説明をすると、Java がコンパイラとか、JavaScript はインタプリタといった説明となる。しかし、最近のこういった言語がどのように処理されるのかは、微妙である。

(( Java の場合 ))
foo.java (ソースコード)
 ↓       Java コンパイラ
foo.class (中間コード)
 ↓
JRE(Java Runtime Engine)の上で
中間コードをインタプリタ方式で実行

あらかじめコンパイルされた中間コードを、JREの上でインタプリタ的に実行するものは、バイトコードインタプリタ方式と呼ぶ。

ただし、JRE でのインタプリタ実行では遅いため、最近では JIT コンパイラ(Just-In-Time Compiler)により、中間コードを機械語に変換してから実行する。

また、JavaScriptなどは(というか最近のインタプリタの殆どPython,PHP,Perl,…は)、一般的にはインタプリタに分類されるが、実行開始時に高級言語でかかれたコードから中間コードを生成し、そのバイトコードをインタプリタ的に動かしている。

しかし、インタプリタは、ソースコードがユーザの所に配布されて実行するので、プログラムの内容が見られてしまう。プログラムの考え方が盗まれてしまう。このため、変数名を短くしたり、空白を除去したり(…部分的に暗号化したり)といった難読化を行うのが一般的である。

トークンと正規表現(字句解析)

規定されたパターンの文字列を表現する方法として、正規表現(regular expression)が用いられる。

((正規表現の書き方))
選言     「abd|acd」は、abd または acd にマッチする。
グループ化 「a(b|c)d」は、真ん中の c|b をグループ化
量化    パターンの後ろに、繰り返し何回を指定
      ? 直前パターンが0個か1個
       「colou?r」
      * 直前パターンが0個以上繰り返す
       「go*gle」は、ggle,gogle,google
      + 直前パターンが1個以上繰り返す
       「go+gle」は、gogle,google,gooogle

正規表現は、sed,awk,Perl,PHPといった文字列処理の得意なプログラム言語でも利用できる。こういった言語では、以下のようなパターンを記述できる。

[文字1-文字2...] 文字コード1以上、文字コード2以下
      「[0-9]+」012,31415,...数字の列
^     行頭にマッチ
$     行末にマッチ
((例))
[a-zA-Z_][a-zA-Z_0-9]* C言語の変数名にマッチする正規表現

構文とバッカス記法

言語の文法を表現する時、バッカス記法(BNF)が良く使われる。

((バッカス記法))
<表現> ::= <表現1...> | <表現2...> | <表現3...> | ... ;

例えば、加減乗除記号と数字だけの式の場合、以下の様なBNFとなる。

((加減乗除式のバッカス記法))
<加算式> ::= <乗算式> '+' <乗算式>
          | <乗算式> '-' <乗算式>
          | <乗算式>
          ;
<乗算式> ::= <数字> '*' <乗算式>
          | <数字> '/' <乗算式>
          | <数字>
          ;
<数字>   ::= [0-9]+
          ;

上記のバッカス記法には、間違いがある。”1+2+3″を正しく認識できない。どこが間違っているだろうか?

このような構文が与えられた時、”1+23*456″と入力されたものを、“1,+,23,*,456”と区切る処理が、字句解析である。

また、バッカス記法での文法に合わせ、以下のような構文木を生成するのが構文解析である。

  +
 / \
1   *
   / \
  23   456

理解度確認

  • インタプリタ方式で、処理速度が遅い以外の欠点をあげよ。
  • 情報処理技術者試験の正規表現,BNF記法問題にて理解度を確認せよ。