コンパイラの処理の流れ

構文の構造を表すために、2分木を使うという話をこの後に行うが、その前にコンパイラが機械語を生成するまでの処理の流れについて説明をする。

Cコンパイラのソース
　　↓
プリプロセッサ (#define,#includeなどの処理)
　　↓
コンパイラ
・字句解析(ソースコードをトークンに切り分ける)
・構文解析(トークンから構文木を生成)
・最適化(命令を効率よく動かすために命令を早い命令に書き換え)
・コード生成(構文木から中間コードを生成)
　　|
　　|　リンカでライブラリと結合
　（+）←---ライブラリ
　　↓ 
　機械語

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

通常、コンパイラとかインタプリタの説明をすると、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”と区切る処理が、字句解析である。

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

　　＋
　／　＼
１　　　＊
　　　／　＼
　　23　　　456

2項演算と構文木

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

　　　＋
　　／　＼
　１　　　＊
　　　　／　＼
　　　２　　　３

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

import java.util.*;

class ExpTreeNode {
    String      op_val ;
    ExpTreeNode left ;
    ExpTreeNode right ;
    
    ExpTreeNode( String op , ExpTreeNode l , ExpTreeNode r ) {
        this.op_val = op ;
        this.left   = l ;
        this.right  = r ;
    }
    ExpTreeNode( String val ) {
        this.op_val = val ;
        this.left   = null ;
        this.right  = null ;
    }
}

public class Main {
    public static int eval( ExpTreeNode p ) {
        if ( p.left == null && p.right == null ) {
            return Integer.parseInt( p.op_val ) ;
        } else {
            int l_val = eval( p.left) ;
            int r_val = eval( p.right ) ;
            switch( p.op_val ) {
            case "+" : return l_val + r_val ;
            case "*" : return l_val * r_val ;
            }
            return -1 ; // error
        }
    }
    public static void main(String[] args) throws Exception {
        ExpTreeNode top =
            new ExpTreeNode( "+" ,
                             new ExpTreeNode( "1" ) ,
                             new ExpTreeNode( "*" ,
                                              new ExpTreeNode( "2" ) ,
                                              new ExpTreeNode( "3" ) ) ) ;
        
        System.out.println( eval( top ) ) ;
    }
}

• 2分木による構文木(Paiza.io)

オブジェクト指向を使った構文木(テスト範囲外)

前述の2分木を用いた構文木では、式を構成する「整数値」の式、「式 演算子 式」の演算式の二つのパターンを、無理やり１つのクラスで扱っていた。整数値と演算子の文字列の違いがあるため、数値も文字列で保存したものを parseInt() で数値に変換している。

こういった、大きくは式と分類できるけど、数値を表す式、演算子からなる式と異なるデータの場合、Java では、オブジェクト指向プログラミングの抽象クラスと仮想関数のテクニックを用いる。式を表現する基底クラス ExpNode から、数値を表す ExpNodeInteger , 演算子からなる式を表す ExpNodeOperator を派生させ、式の値を求める際には、各クラスに応じた計算処理を行う仮想関数 eval() を使って処理を行っている。

import java.util.* ;

// 抽象基底クラス
abstract class ExpNode {
    abstract public int eval() ;
}

// 整数で具体化
class ExpNodeInteger extends ExpNode {
    int  value ;
    
    ExpNodeInteger( int i ) {
        this.value = i ;
    }
    // 仮想関数
    public int eval() {
        return this.value ;
    }
}

// 演算子で具体化
class ExpNodeOperator extends ExpNode {
    String  op ;
    ExpNode left ;
    ExpNode right ;
    
    ExpNodeOperator( String s , ExpNode l , ExpNode r ) {
        this.op    = s ;
        this.left  = l ;
        this.right = r ;
    }
    // 仮想関数
    public int eval() {
        int l_val = this.left.eval() ;
        int r_val = this.right.eval() ;
        switch( this.op ) {
        case "+" : return l_val + r_val ;
        case "*" : return l_val * r_val ;
        }
        return -1 ;
    }
}

public class Main {
    public static void main(String[] args) throws Exception {
        ExpNode top =
            new ExpNodeOperator( "+" ,
                                 new ExpNodeInteger( 1 ) ,
                                 new ExpNodeOperator( "*" ,
                                                      new ExpNodeInteger( 2 ) ,
                                                      new ExpNodeInteger( 3 ) ) ) ;

        System.out.println( top.eval() ) ;
    }
}

データをO(log N)で検索するための2分探索木以外の2分木のデータ構造について解説を行う。

意思決定木

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

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

このような判断を行うための情報は、yesの木 と noの木の2つの枝を持つデータである。これは2分木と同じである。左右に枝のあるものは質問であり、yesの枝もnoの枝もない末端は最終決断を表す。このようなデータ構造は意思決定木と呼ばれ、質問と決断の処理は以下のように記述ができる。

import java.util.* ;
import java.util.Scanner ;

class TreeNode {
    String qa ;
    TreeNode    yes ;
    TreeNode    no ;
    
    TreeNode( String s , TreeNode y , TreeNode n ) {
        this.qa  = s ;
        this.yes = y ;
        this.no  = n ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner( System.in ) ;
        TreeNode top =
            new TreeNode( "38.5℃以上の発熱がある?" ,
                          new TreeNode( "胸がひぃひぃ?" ,
                                        new TreeNode( "速攻で病院" ,   null , null ) ,
                                        new TreeNode( "解熱剤で病院" , null , null ) ) ,
                          new TreeNode( "元気がある?" ,
                                        new TreeNode( "様子をみる",    null , null ) ,
                                        new TreeNode( "氷枕で病院",    null , null ) ) ) ;
        TreeNode p = top ;
        while( p.yes != null || p.no != null ) {
            System.out.println( "Question:" + p.qa ) ;
            if ( sc.nextInt() == 1 ) {
                System.out.println( "yes" ) ;
                p = p.yes ;
            } else {
                System.out.println( "no" ) ;
                p = p.no ;
            }
        }
        System.out.println( "Answer:" + p.qa ) ;
    }
}

• 意思決定木(Paiza.io)

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

• decision-tree.cxx

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言語やJavaでは、”a = b = c = 0″ と書くと、”a = (b = (c = 0))” として扱われる。こういった代入演算子は、 右結合の演算子である。

理解度確認

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

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

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