2分木の応用ということで、2項演算子の構文木と、意思決定木の説明を行う。また、これらを用いてコンパイラを作るための知識を解説する。
2項演算と構文木
演算子を含む式が与えられたとして、それを保存する場合、演算式の2分木で扱うと都合が良い。
＋ ／ ＼ １ ＊ ／ ＼ ２ ３
演算子の木のノードで、末端は数値であることに注目し、右枝・左枝が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 ) {
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 ) ;
}
}
void main() {
struct Tree* exp =
tree_op( '+' ,
tree_int( 1 ) ,
tree_op( '*' ,
tree_int( 2 ) , tree_int( 3 ) ) ) ;
printf( "%d¥n" , eval( exp ) ) ;
}
コンパイラと言語処理系
高級言語で書かれたプログラムを計算機で実行するソフトウェアは、言語処理系と呼ばれる。その実行形式により
- インタプリタ(interpreter:翻訳)
- ソースプログラムの意味を解析しながら、その意味に沿った処理を行う
- コンパイラ(compiler:通訳)
- ソースプログラムから機械語を生成し、実行する際には機械語を実行
- トランスレーター:ソースから他の言語のソースコードを生成し、それをさらにコンパイルし実行
- バイトコードインタプリタ:ソースからバイトコード(機械語に近いコードを生成)、実行時にはバイトコードの命令に沿った処理を行う
に分けられる。
コンパイラが命令を処理する際には、以下の処理が行われる。
- 字句解析(lexical analysys)
文字列を言語要素(token)に分解 - 構文解析(syntax analysys)
tokenの並び順に意味を反映した構造を生成 - 意味解析(semantics analysys)
命令に合わせた中間コードを生成 - 最適化(code optimization)
中間コードを変形して効率よいプログラムに変換 - コード生成(code generation)
実際の命令コードとして出力
トークンと正規表現
規定されたパターンの文字列を表現する方法として、正規表現(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+23*456″と入力されたものを、“1,+,23,*,456”と区切る処理が、字句解析である。
また、上記バッカス記法の構文に沿って、構文に沿った木を生成するのが構文解析である。
1 + 23 * 456 23 456
数字 ＼ ／
数字 数字 '*' 乗算式 1 *
乗算式 '+' 乗算式 ＼ ／
<---------加算式---------> +
lex と yacc
こういった構文に合わせた処理を行う場合、構文解析を行う場合には、LRパーサ,再帰下降パーサなどが使われる。LRパーサでは、「このトークンの後にくる可能性のあるトークンは何？」といった表を作る必要がある。しかし、こういった作業は単調かつ間違えやすいことから、それらを自動生成するツールなどが用いられる。
有名なツールとして、以下の２つを紹介する。
- lex 字句解析プログラム生成ツール(最近はflex)
- yacc 構文解析プログラム生成ツール(最近はbison)
構文解析などに、興味があるようであれば、専攻科実験テーマ資料を参考にせよ。