ホーム » スタッフ

スタッフ」カテゴリーアーカイブ

2019年11月
« 10月    
 12
3456789
10111213141516
17181920212223
24252627282930

最近の投稿(電子情報)

アーカイブ

カテゴリー

B木とデータベース

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

B木の構造

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

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の例))
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++ )                   // 結合
   for( re = 0 ; re < 3 ; re++ )
      if ( student[ st ].ID == result[ re ].ID  // 選択
        && result[ re ].point >= 60 )
           printf( "%s %s %d" ,                 // 射影
                   student[ st ].name ,
                   result[ re ].subject ,
                   result[ re ].point ) ;

B+木

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

そこで、B木のデータを横方向に並べて処理を行う場合に、その処理が簡単になるように B+木が用いられる。
この方法では、末端のノードは、隣接するノードへのポインタを持つ。

GROUP BY-HAVINGとCREATE VIEW

先週に引き続き、2つのSQLとそれと同じ処理のプログラム作成の課題に取り組む。

演習だけでは進度が少ないので、SQL で説明できなかった、GROUP BY-HAVING と CREATE VIEW の説明

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 がどのように実行されるかは意識する必要はほとんど無いであろう。

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

春江東小学校でIchigoJam出前授業

11/17(日)に、春江東小学校さんからの依頼により、IchigoJam でのプログラミング体験の出前授業を行いました。

{CAPTION}

HIT2019にて優秀賞

第6回ビジネスモデル発見&発表会 北陸大会と第6回G空間×ICT北陸まちづくりトライアルコンクール、起業家甲子園・起業家万博 北陸予選を兼ねたHIT2019にて、3EIの佐野くんが優秀賞となりました。

ポインタの先には何がある?

学生さんから「ポインタの先には何があるの?」との質問があった。

私が「そのポインタの型のデータ」と答えると、さらに「ポインタはメモリの場所。でもメモリには int や char や double といった色んなデータがある。そんな色々なデータの中からデータを取り出すんだから、そこにはどんなデータが入っているのか判らないとデータを取り出せないんじゃ?」と疑問をぶつけてきた。

なるほど、本当の疑問点が見えてきた。

最近のPython等の動的型付け言語の場合

# ポインタの質問だから、C言語の場合を答えればいいんだけど…

最近の Python , PHP といった変数が型を持たない「動的型付け言語」は、まさに質問の通り。データを取り出すためには、型の情報が必要。こういう言語は、基本型以外のデータはすべて参照型(要はポインタ)なので、変数の指し示す先には型情報とそのデータがペアで保存されているので、その型情報をみてデータを取り出している。

C言語の場合(静的型付け言語)

C言語では、ポインタは単なるメモリの場所を表すだけ。ポインタの先にはデータがある。(だからデータしかないって!)

メモリからデータを読み出すときに、int 4byte で取り出すのか、 double 8byte で取り出すかどうやってわかるの?と思うかもしれないけど、そのポインタの変数がどういう型へのポインタで定義されているかプログラムを読めばわかる。それに従って取り出せばいい。こういう言語は「静的型付け言語」という。

となると「じゃあ int のデータを char として読めるの?」と思うかもしれないけど「読めるよ!」

#include <stdio.h>
int main() {
   // 型を偽って参照するのは間違いの元なので型のチェックは厳格。
   //   だから 以下の様なヤバイことをする時は、型キャスト で
   //   だますことが定番。
   int x = 0x41424344 ; 
   char* p = (char*)( &x ) ; // int型の場所をchar型にする 
   printf( "%c\n" , *p ) ;

   // int型は4バイト、次のアドレスは?
   int y[] = {
      0x11223344 , 0x12345678 ,
   } ;
   printf( "%p %p\n" , y , y + 1 ) ; 
   int *r = y + 1 ;
   printf( "%04d\n" , *r ) ; // 12345678 が表示

   // intの1byteとなりをintとして読める?
   int *q = (int*)((char*)( &y ) + 1) ;
   printf( "%04x\n" , *q ) ; // 処理系によってはメモリエラー

   // ポインタは番地を表す数値だよね?
   //  0x100番地のデータは読める?
   int* s = (int*)0x100 ;
   printf( "%d\n" , *s ) ; // Segmentation Fault.

   return 0 ;
}

さて、上記のプログラムをみてどう思った?

C言語って自由奔放で、やばくね? — ポインタなんか使えるからだよね、そう思うんなら Java 使え。ポインタなんか使えないから。

でも型宣言が面倒なんだよねPython, Ruby などの動的型付けな言語使え。

でも変数参照でいちいち型情報しらべる言語って遅くね? — あるよ。「型推論」。型を明記しなくても、プログラムの文脈から型を推論してくれる静的型付け言語。Go , Swift , Kotlin…といった、今 流行りのプログラム言語がソレ。最新のJavaやC++も型推論機能が使えるようになってるよ。んで、今話題の中学生が作ったプログラム言語 Blawn も、型推論の言語!すげーな。

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

2分木の応用として、式の表現を行うけどその前に…

逆ポーランド記法

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

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

中置記法 1+2*3
前置記法 +,1,*,2,3
後置記法 1,2,3,*,+

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

理解度確認

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

逆ポーランド記法 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 != '\0' ; p++ ) {
      if ( isdigit( *p ) ) {
         //         ~~(A)
         // 数字はスタックに積む
         push( *p - '0' ) ;
      } 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 ) ;
      }//~~~~~~~~~~~~~(B)
   }
   // 最終結果がスタックに残る
   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 ) {     // ~~~~~~~~~~~~~~~~~~~~~(C)
      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 ) ;
      }              // ~~~~~~~~~~~~~~~(D)      ~~~~~~~~(E)
   }
}

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 ) ) ;
}

理解度確認

  • 上記プログラム中の(A),(B),(C),(D)の型を答えよ。

const char*s, char* const sの違い

専攻科実験のサンプルコードで、警告がでたことについて質問があったので説明。

(( サンプルコード sample.cxx ))
#include <stdio.h>
void foo( char* s ) {
  printf( "%s¥n" , s ) ;
}
int main() {
  foo( "ABC" ) ;
  return 0 ;
}

(( コンパイル時の警告 ))
$ g++ sample.cxx
test.cxx:6:6: warning: conversion from string literal
      to 'char *' is deprecated
      [-Wc++11-compat-deprecated-writable-strings]
  foo( "abcde" ) ;
       ^
1 warning generated.

警告を抑止する “-Wno-…” のオプションをつけて “g++ -Wno-c++11-compat-deprecated-writable-strings sample.cxx” でコンパイルすることもできるけど、ここは変数の型を厳格にするのが鉄則。

この例では、引数の “ABC” が書き換えのできない定数なので、const キーワードを付ければよい。ただし、宣言時の const の付け場所によって、意味が違うので注意が必要。

void foo( char const* s ) { // const char* s も同じ意味
   *s = 'A' ; // NG ポインタの先を書き換えできない
   s++ ;      // OK ポインタを動かすことはできる
}
void foo( char *const s ) {
   *s = 'A' ; // OK ポインタの先は書き込める
   s++ ;      // NG ポインタは動かせない
}
void foo( char const*const s ) {
   *s = 'A' ; // NG ポインタの先を書き換えできない
   s++ ;      // NG ポインタは動かせない
}

const を書く場所は?

int const x = 123 , y = 234 ; の場合、yは定数だろうか?

(( おまけ ))
#include <stdio.h>
int main() {
  int const x = 123 , y = 234 ; // x は定数だけど yは定数?
  x++ ; // 予想通りエラー
  y++ ; // yも定数なのでエラー
  int const s = 345 , const t = 456 ; // sもtも明らかに定数っぽい
  //                  ^ここで文法エラー

  // おまけのおまけ
  char* s , t ;   // s は文字へのポインタ、t は文字
  char  *s , *t ; // s は文字へのポインタ、t も文字へのポインタ
  return 0 ;
}

意思決定木と構文解析

前回までの授業で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:通訳)
    • ソースプログラムから機械語を生成し、実行する際には機械語を実行
  • トランスレーター
    • ソースから他の言語のソースコードを生成し、それをさらにコンパイルし実行
  • バイトコードインタプリタ
    • ソースからバイトコード(機械語に近いコードを生成)、実行時にはバイトコードの命令に沿った処理を行う

に分けられる。

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

  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記法問題にて理解度を確認せよ。

Visual Studio Code で印刷

実験や授業課題のレポート提出で、プログラムを印刷したものを提出してくれるけど、行を移動しながら何度もスクリーンキャプチャで保存した画像ファイルをWordに貼り付けて提出している人が多い。

いままでなら、「秀丸エディタで印刷してよ…」とか言ってたけど、最近は Visual Studio Code を利用しているみたいで、「プログラムの印刷の仕方がわからない」という人が多いようだ。

実際、Visual Studio Code はたまにしか使わないけど、確かに基本機能の中には印刷機能がないな….

今時、プログラムリストなんて紙媒体で印刷しないもんなんだろうけど、プログラム課題のレポートなら、コードは証拠だからな。

Visual Studio Code の PrintCode

こういう場合は、Visual Studio Code の拡張機能の PrintCode をインストールすればいい。

印刷する時は、F1 キーを押して、拡張コマンドの入力で printcode と打てば印刷される。

ただし、PrintCode は JavaScript を使って HTML を生成し印刷を行うため、Windowsでデフォルトブラウザが Internet Explorer の場合は動かない。このためデフォルトブラウザの変更により Chrome などを使う様に変更しておく必要あり。

Sublime Text なら Print to HTML

同じく、エディタが Sublime Text を使っているのなら、これも印刷機能が付いていないので、”Print to HTML”パッケージをインストールし、あとは、Shift+Alt+P で HTML 用に出力できるのでブラウザ側で印刷を行う。

コンパイラの技術と関数電卓プログラム(2)

前半では、1文字の数字と簡単な演算子で表現される計算式を再帰下降パーサで計算する処理で、 演習を行った。

後半は、さらに実際のコンパイラに近いものとして、 C言語で広く使われている、字句解析ツール(lexical analyzer : lex or flex)、 構文解析ツール(parser : yacc or bison) を使って、 さらに現実的な関数電卓プログラムを作ってみる。

lex or flex による字句解析

lexは、字句解析のプログラムを自動生成するツール。 “%%”行の内側に、正規表現によるルールとその処理(アクション)を書き並べる。 また、“%{ … %}”の内側に、その処理に必要なC言語のソースを書き、 lex で処理を行うと、lex.yy.c というC言語のソースを出力する。

lex.yy.c の中には、yylex() という関数が自動的に作られ、構文解析ツールから呼び出される。

# flex は、lex の改良版。

(( mycalc.l ))
%{
#include <stdio.h>
// yaccが出力するヘッダファイル
#include "y.tab.h"

int yywrap( void )
{
   // 1: スキャナ終了
   // 0: yyin を切り替えて継続
   return 1 ;
}
%}
%%
"+"  return ADD ;
"-"  return SUB ;
"*"  return MUL ;
"/"  return DIV ;
"\n" return CR  ;
[0-9][0-9]* {
   // 入力はyytextに格納されている。
   int temp ;
   sscanf( yytext , "%d" , &temp ) ;
   yylval.int_value = temp ;
   // 返り値は、字句(トークン)の種別を表す定数
   return INT_LITERAL;
}
%%

このプログラムを、lex で処理させると、“+” 記号に ADD という定数記号を割り振るとか、数字列” [0-9][0-9]* “をみつけると、文字列から数値を生成(sscanf)して、その場合の記号に INT_LITERAL という定数記号を割り振る…といった処理のプログラムを生成してくれる。(INT_LITERALは構文解析側で定義する定数)

yacc or bison

yacc ( Yet Another Compiler Compiler ) もしくはその改良版の bison は、構文解析のプログラムを自動生成してくれるツールである。構文をBNF記法で記載すると、字句解析ツール(lex等)を呼び出しながら構文に合わせたトークンの出現に応じた状態遷移のための「遷移テーブル」を自動生成し、 その遷移テーブルを用いた処理のプログラムをC言語で出力してくれる。

字句解析プログラムは、様々なトークンとデータを返す。このデータには様々な場合考えられるので、 そのトークンに合わせたデータの型を “%union” の中に記載(C言語の共用体参照)する。 “%%”〜”%%” の間には、BNF記法の(ルール)と、それに対応する処理(アクションは“{ }”の中の部分)を記載する。最初の“%{ … %}”の間には、処理に必要なC言語を記載する。

# bison(水牛)は、yacc(山牛)の改良版。

(( mycalc.y ))
%{
#include <stdio.h>
#include <stdlib.h>

// yacc が定義する内部関数のプロトタイプ宣言
#define YYDEBUG 1
extern  int  yydebug ;
extern  int  yyerror( char const* ) ;
extern  char *yytext ;
extern  FILE *yyin ;

// 最初に呼び出される関数yyparse()
extern  int  yyparse( void ) ;

// 字句解析を呼び出す関数yylex()
extern  int  yylex( void ) ;
%}

// 字句(トークン)の定義
%union {
   int  int_value;
}
%token <int_value>  INT_LITERAL
%token ADD SUB MUL DIV CR
%type  <int_value>   expression term primary_expression

%%
// 構文の定義
line_list  : line                // 行の繰り返し
           | line_list line
           ;

line       : expression CR       { printf( ">>%d\n" , $1 ) ; }
           ;

expression : term
           | expression ADD term { $$ = $1 + $3 ; }
           | expression SUB term { $$ = $1 - $3 ; }
           ;

term       : primary_expression
           | term MUL primary_expression { $$ = $1 * $3 ; }
           | term DIV primary_expression { $$ = $1 / $3 ; }
           ;

primary_expression
           : INT_LITERAL
           ;
%%

// 補助関数の定義
int yyerror( char const* str )
{
   fprintf( stderr , "parser error near %s\n" , yytext ) ;
   return 0 ;
}
int main( void )
{
   yydebug = 0 ;        // yydebug=1 でデバッグ情報表示
   yyin = stdin ;
   if ( yyparse() ) {   // 構文解析を開始
      fprintf( stderr , "Error ! Error ! Error !\n" ) ;
      exit( 1 ) ;
   }
}

このプログラムを、yacc で処理すると、expression$1 ADD$2 term$3のルール「加算式($1) +($2) 乗算式($3)」という文になっている部分を見つけると、そのルールに対応するアクション“{ $$ = $1 + $3 ; }”「$1(加算式部分の値)と、$3(乗算式の部分)の値を加えて、$$(式の結果)を求める」といった処理を生成してくれる。yyparse() 関数を呼び出すと、構文の一番最上部の line_list に相当する処理が起動される。yyerror()は、構文解析の途中で文法エラーになった時に呼び出される関数。

生成されるパーサの内容に興味があるなら、生成される y.tab.c の内容を読むと良い。

make と Makefile

これらのプログラムでは、字句解析プログラム mycalc.l から生成された lex.yy.c, y.tab.h と, 構文解析プログラム mycalc.y から生成された y.tab.c を組合せて1つの実行ファイルにコンパイルする。 これらの手順は煩雑なので、make ツールを使う。

make は、 Makefile に記載されている“ターゲット”と、それを作るために必要な“依存ファイル”、 “依存ファイル”から”ターゲット”を生成する処理“アクション”から構成される。 make は、ターゲットと依存ファイルの更新時間を比較し、 必要最小限の処理を行う。

基本的な Makefile の書き方は、

ターゲット: 依存ファイル...
        アクション       # アクションの前はタブ

の様に書き、依存ファイルが更新されていたら、アクションを実行し、ターゲットを更新する。

以下に、今回の課題で使用する Makefile を示す。

(( Makefile ))
# 最終ターゲット
mycalc:	y.tab.o lex.yy.o
        gcc -o mycalc y.tab.o lex.yy.o

# 構文解析処理
y.tab.o: mycalc.y
        bison -dy mycalc.y	# -dy : yacc互換モード
        gcc -c y.tab.c

# 字句解析処理
lex.yy.o: mycalc.l mycalc.y
        flex -l mycalc.l        # -l : lex互換モード
        gcc -c lex.yy.c
clean:; rm mycalc y.tab.c y.tab.h lex.yy.c *.o

(( ファイルの依存関係のイメージ図 ))
mycalc.l           mycalc.y
  |     \           |
lex.yy.c  y.tab.h  y.tab.c
  |            \    |
lex.yy.o        y.tab.o
        \    /
         mycalc

この課題にあたり、後半の実験では flex, bison などの unix 系プログラミング環境を利用する。

macOS の利用者であれば MacPorts や、Windows 利用者であれば、wsl(Windows subsystem for Linux) などをインストールし実行すること。

今回の実験であれば、linux(Debian系)ならば、”sudo apt-get install flex bison gcc make” にて、必要なパッケージをインストールして実験を行うこと。