Lex - みる会図書館


検索対象: 月刊 C MAGAZINE 2000年5月号
11件見つかりました。

1. 月刊 C MAGAZINE 2000年5月号

特集 1 五ロ 三 - ロ を List 6 List 6 }else{ / * 値渡しをされる仮引数 * / vdata->vartype = VARTYPE—VAR ー fdata->argtype [ fdata->narg ] = ARGTYPE—VALUE; fdata->narg 十 )while( Lex. type = = COMMA if( も ex. セ e , , 。 , ( " 数言部が ) で終っていません ' static void funcdef ( void ) char *ident ー funcdata *fdata; getlex( if( Lex. type ! = IDENT ) { if( Lex. is ident ) e てて 0 て ( ”別子 %s は関数名として認められません” Lex. detail . ident e て ro て ( ”関数名は識別子でなければなりません” ident = Malloc(char, strlen(Lex. detail.ident) 十 1 strcpy(ident, Lex. detail . ident); fdata = Malloc(funcdata,1); fdata->name = ident; hash—store(ident, FUNC, fdata); add—hashtab 厄 ( init( parse—arg ( fdata block(LABEL—INVAL,LABEL—INVAL); add—code ( —PUSH , CONST , 0 , NULL add-code ( —RET , 0 , 0 , NULL remove-hashtab ( if( do—not—run ) asmprint ( r00 セ′ ident fdata->code = assemb 尾 ( fdata->framesize = framesize( static VOid reserve(void) hash—store( ”土 f ” , IF, NULL); hash—store( "then" ,THEN,NULL); hash—store( ” e e ” ELSE' NULL) ・ "while , WHILE, NUIÆ); hash—store ( hash—store( ” dO ” ,DO NULL); hash—store( nreturn , RETURN, NULL); hash—store( "printn, PRINT, NULL); hash—store( "break" , BREAK, NULL); hash—store( "continue" , CONTINUE, NULL); hash—store( , VAR, NULL); hash—store( "def" , DEF, NULL); hash—store( "begin" , BEGIN, NULL); hash—store( "end" , END, NULL); funcdata* compile(const char *filename) int ー 00P = TRUE; funcdata *mainfunc ー open—source( filename add-hashtable( reserve ( while(loop) switch(getlex( ) , Lex. type) { case DEF : funcdef ( break; case LEX—EOF : OP = FALSE ー break; defau 比 : err 。 r ( ″関数定義ではありません” break; close—source( ) ー if( ! hash—search( "mainn , NULL, (void**) &rnainfunc) ) e てて or ( ″ main 関数が定義されていません” else if( mainfunc->nar 〉 0 ) e てて 0 て ( " main 関数は引年しで宣言して下さい ' mainfunc ー if( Lex. し e ! = SEMICOLON ) e 。 0 , ( " 数言文が一で終結していません ' void lf(int brk, int cont) int LI ー expression( if( Lex ・ type ! = THEN ) e て ror ( ” if 文のテスト式の後に then がありません” も 1 = label-next( add—code ( —FJMP , LI , FALSE , NULL block(brk,cont); getl ex ( if( Lex. type = = ELSE ) { int L2; も 2 = ね b 引 -next ( add—code ( JMP 0 , NULL) ・ L2 , add-code ( —LAB{L , LI , block(brk,cont); 0 , add-code ( —LABEL , L2, )else{ ungetl ex ( add—code( —LABEL, 0 , NULL); LI , ! = RPAR ) void While(void) int も 1 , L2; LI = label—next( L2 = label-next( add—code(—LABEL, LI, 0 , NULL expression( if( Lex ・ type ! = DO ) erro て ( ” wh e 文のテスト式の後に do がありません” add-code(—FJMP, L2, 0 , NULL); block(L2, LI add—code(—JMP, LI, 0 , NULL); add-code(—LABEL, L2, 0 , NULL); void print ( void ) int n=0 ー do { expression( n 十十一 }while( Lex. type = = CO if( Lex. type ! = SEMICOLON ) error("print 文が一で終っていません” add—code(-PRNT, n, 0 , NULL); void Return(void) expression ( ) ー if ( Lex. type ! = SEMICOLON ) error("return 文が一で終っていません” ) ・ add—code(—RET, 0 , 0 , static VOid parse—arg ( funcdata *fdata ) vardata *vdata ー fdata->narg = の getlex( if( Lex. type ! = LPAR ) e て ro て ( ” ( が必要です” getlex( if( Lex. type = = RPAR ) { return ・ }else ungetlex( ヨ do { if( fdata->nar > NARG 。。。て ( " 仮引が多すぎっ . getl ex ( if( ! Lex. is ident ) er て。て ( ″仮引数名が識別子ではありません″ vdata = Malloc(vardata, 1 if( ! hash—store(Lex. detail . ident, LOCALVAR, vdata) e てて 0 て ( の重複宣言” , Lex. detail . ident); vdata->0ffset = alloc—offset( 1 ); getlex( if( Lex.type = AND ) { / * 参照渡しされる仮引数 * / vdata—>vartype = VARTYPE—REFER ー fdata->argtype[fdata->narg] = ARGTYPE—REFER. ・ getlex( 特集 1 スクリプト言語を作ろう 27

2. 月刊 C MAGAZINE 2000年5月号

解析部 ( List5 ) を順に見ていくことにしま せん。 B が評価されるのは , A が偽である となり , これを実現するコードを生成する す。 expr3() から expr6() まではすでに説明 場合にかぎられます。対して Pascal などで 必要があります。 exprl() では , 仮想マシ は A の値にかかわらず常に B も評価されま ン命令の仕様 (Table 3 ) に基づき , した再帰下降解析の典型といえるもので ( 左オペランドの評価コード ) す。ここではそれ以外の部分について考察 す。 toy では前者 , つまり A の評価結果に応 じて B を評価するかどうかを決定する方式 することにします。 TJMP a=L1 b=TRUE ( 右オペランドの評価コード ) を採用しています。この方式の論理 OR 演 Ⅱ演算子の処理 ( exp 「 1 ( ) ) 算を実現するには , A の評価結果に応じた LABEL a=L1 分岐コードを生成させなければなりませ という中間コードが生成されます。 toy のⅡ演算子は , C 言語と同様に論理 ん。つまり流れとしては , & & 演算子の処理 ( exp 「 2 ( ) ) OR 演算を行う演算子です。ご存じのこと A を評価→ 真であれば , 真をブッシュして LI と思いますが , C 言語をはじめとして多く の言語では論理 OR 演算 , 論理 OR 演算同様 , & & 演算子による論理 に飛ぶ→ A Ⅱ B B を評価 AND 演算についても , toy では C 言語流の において , A が真の場合には B を評価しま 評価法を採用します。つまり , / * * / 演算子の優先順位 * / void expr6 ( int 料 val ue ) int op = 0 ー expr7( lvalue); fo て ( ) { switch ( Lex. type ) { case STAR : OP = —MUL; break; case SLASH : -DIV; break ・ case PERC : op = ー 0 break; default: return ー expr7( lvalue); add-code ( op , 0 , 0 , NULL *lvalue = FALSE; / * 単項演算子の優先順位 * / VOid expr7(int * lvalue) getlex( if( Lex. type = = MINUS expr7 い val ue add—code ( ー INVT , の *lvalue = FALSE; factor い val ue LI : List 5 List 5 void var(void) vardata *vdata ー vdata = (vardata*) Lex. data; if( vdata->vartype & (VARTYPE-ARRAYIVARTYPE—REFER) ) { getlex( if( Lex. type ! = LBRACK ) { ungetlex( add—code ( —PUSH , CONST, 0 , NULL else{ expression( if( Lex. type ! = RBRACK ) e てて 0 て ( 勹がありません″ add—code ( —LOAD , vdata->0ffset , vdata->vartype , NULL void call (void) funcdata * fdata; int n=0 ー ( funcdata* ) Lex. data; fdata getl ex ( if ( Lex. t e ! = LPAR ) 000 , ( 。数呼び出しに ( がありません " if( fdata->narg ) { do { if( fdata → argtype[n] = = ARGTYPE-REFER ) { / * 参照渡し * / int ー va ー ue=TRUE ー exprl(&lvalue); if ( ! ⅳ引 ue ) { error("%s の呼び出し : 第記引数は参照渡しでなければならない” fdata->name, n 十 1 chg—code ( —ADDR else / * 値渡し * / expression( n 十十一 }while( n く fdata->narg & & Lex. type = CO 鳳 getlex( if ( Lex. t e ! = RPAR ) e , , 0 て ( " 数呼び出しが ) で終結していません " if ( fdata->nar ! = n ) e てて。て ( " 関数び出しにおける引数の個数が間違っています " add—code( —CALL, 0 , の fdata); void factor(int *lvalue) int is—lvalue = FALSE ・ = LPAR ⅱ if( Lex. type expression( if( Lex. type ! = RPAR ) error ( ″ ) がありません” else if( Lex. type = = CONST ) add—code ( —PUSH , CONST , Lex. detail . number , NULL ま STRING ) else if( Lex. type add—code ( —PUSH ′ STR I NG , 0 , Lex. detai 匚 string else if( Lex. type = = LOCALVAR ) { var ( is—lvalue = TRUE; else if( Lex ・ type = = FUNC) call(); erro て ( ”式に不正な要素が含まれています” if( ! is-lvalue ) *lvalue = FALSE; getlex( 22 C MAGAZINE 2 側 0 5

3. 月刊 C MAGAZINE 2000年5月号

ける字句の種類はこれだけであり , 字句解 析部はこの定義を元に設計していくことに なるのですが , どうすれば効率的に字句を 抽出することができるでしようか 0 まず最初の関門は字句の種類を判別する ことです。 toy の字句定義を見ると , 最初 に入力された文字 ( 先頭の文字 ) を調べるこ とで字句の種類をほば決定できることがわ かります。先頭が数字であれば , 字句定義 によりその字句は定数であることが特定で き , " \ " " であれば文字列 , 英字か " ー " であ c = ' ' ・ break; れば識別子であることがすぐにわかりま す。予約語については識別子集合の部分集 合となっているので , いったん識別子とし て抽出を行い , その後予約語であるか ( 予 約語として使用される識別子か ) を調べれ ばよいことになります。そして , それ以外 の文字であれば , 字句は特殊記号であるは ずだと推測できるわけです。 このように考えると字句解析は簡単なよ うに思われますが , 字句解析が簡単になる か難しくなるかは言語の設計によって変わ ってきます。仮に , toy の予約語定義に 20a という予約語を追加したとします。このよ switch( getchr( ) int int type=O; List 1 うな予約語を追加することで字句定義その ものが複雑になることはありませんが , 字 句解析部にとっては複雑な問題が発生する ことになります。なぜなら , 「先頭が数字 である場合は定数である」という分類規則 が通用しなくなるのです。解析部は先頭に 数字が現れる字句をまず定数だと「推測」し ます。そして定数として読み進み , その定 数が 20 であればさらに読み進み " a " の存在 を調べなければなりません。つまり , 先読 みしなければ定数 20 であるか予約語 20a で あるかを判別できなくなるのです。 List 1 / * 文字列の抽出 * / static void lex—string ( VOid ) enum{ TMPBUF—SIZE = 64 char tmp[ TMPBUF—SIZE char *buf = NULL• int pos = 0 , cursize = int c; while( c=getrawchr( ) , c ! = if ( c ー c = getrawchr( switch( c ) ( ! = EOF case ' n C = セ break; case case case case case Case case case case Case case case case case case case = PLUS; break; = MINUS; break; = STAR; break; = SLASH; break; = PERC; break; = LPAR; break; = RPAR ー break; : type = LBRACK; break; : type = RBRACK; break; = CO break; = SEMICOLON; break; 'type=EQUAL,type=EQEQ); break ・ ,unknown-symbol( ) ,type=NOTEQ); break; ' & ' : check( ' & ' ,type=AND,type=ANDAND) ;break; : check( ' ド , unkno 1 ー s 日 ) , セ e = OROR ) ゆて ea 塒 'type=LT,type=LE); break; ,type=gr,tyrFGE); break; く : check( ' : check( ' : check( ' : check( ' if ( pos > = TMPBUF—SI ZE ) ( if ( ! buf ) e ー se buf = Malloc(char,TMPBUF—SIZE); strncpy(buf 十 cursize, tmp, TMPBUF—SIZE); buf = Realloc(char, buf, cursize 十 TMPBUF—SIZE); erro て ( ″文字列が終了していません″ ); if ( c = = EOF ) e ー se tmp[pos + + ] = (char) c ・ pos = の cursize 十 = TMPBUF—SI ZE ー static VOid unknown—symbol( ) Lex. detail . string = buf; Lex. is—ident = FALSE; Lex. type = STRING; buf[cursize 十 posl = ' ' strncpy(buf 十 cursize, tmp, pos); buf = Realloc(char, buf, cursize 十十 1 else{ buf[pos] strncpy(buf, tmp, buf = MaIIoc(char, 十 1 if( ! buf ) { static void lex—other ( void ) / * 特殊記号の抽出 * / else{ ungetchr(c); actionl; } if( (c=getchr( ) ) = b2 ) ( action2; } \ #define check(b2,action1,action2) err 。て ( ″未定義の特殊記号が現われました” default: unknown—symbol( Lex. type = type; Lex. is—ident = FALSE ー static int lex—unget = FALSE; / * 次の字句を抽出する * / void getlex(void) int if( lex-unget ) ( / * 字句が書き戻されていた場合には そのままリターンする * / lex—unget = FALSE ー return ・ skipspace ( c = getchr( if( isalpha(c) Ⅱ c = = ー ungetchr(c); lex—ident( else if( isdigit(c) ) { ungetchr(c); lex—const( e lse if ( c = = 冖 ) lex—string( else if( c = = EOF ) Lex. い2e = LEX—EOF; else{ ungetchr ( c lex—other( / * 字句の書き戻し * / void ungetlex(void) ( lex—unget = TRUE; ) 14 C MAGAZINE 2 0 5

4. 月刊 C MAGAZINE 2000年5月号

特集 1 五ロ - 三ロ を を抽出する作業を字句解析といいますが , は“ ' が 0 個以上後続するものをいいます 必ずしも一度にすべての字句を抽出し字句 が これは正規表現を用いて , の列に変換する必要はなく , 字句解析の次 識別子 = ( 英字に一・ ) ( 英数字に ' ) * の段階である構文解析とともにひとつのパ と簡潔に定義することができます。同様に スにまとめられる場合が多いようです。つ C 言語の符号なし整数に対しても , まり , 構文解析部で次の字句が必要になる 自然言語における単語は名詞・動詞・接 符号なし整数 = たびに , 字句解析部に字句を抽出させるの 続詞・記号などいくつかに分類できます ( 数字・数字 * 川 ( 数字・数字 * ) ' L ' です。この方法は人間が文章を読む際の作 が , コンピュータ言語においても字句はい と定義できます。 業と似ており , 感覚的にも自然なものであ くつかに分類されます。たとえば識別子 では , 今回設計するインタブリタ言語 to るといえます。本稿で例題として作成する ( 名前 ) ・特殊記号 ( 演算子など ) ・整数・実 y の字句定義を見ていきましよう (TabIe 1)0 インタブリタ言語 toy でも字句解析部と構 数などがそうです。 C 言語における識別子 文字列の定義が多少複雑なことを除いて , 文解析部は 1 パスにまとめられています は英字あるいは・ " で始まり英数字あるい かなりシンプルになっています。 toy にお toy の字句解析部 が これについては後述します。 字句定義 LiSt 1 List 1 / * 次の 1 文字を素直に読み込む * / static int getrawchr(void) if( unget ) { unget = FALSE ー return unget—chr ー )else return fgetc ( srcf 厄 x. 。 : 字句解析系 #include <stdio. h> #include く string. h> #include <ctype. h> #include <stdarg. h> #include ″ toy. h ” ー ex—t Lex ー static FILE *srcf; void char * filename) = fopen(filename,nr"); if( ! srcf ) { fprintf(stderr, ”宅 s : CouIdn't open file.%nn, filename); exit(-l); static void ungetchr ( 土 n ヒ c ) unget = TRUE ー unget—chr = C ー static void skipspace ( void ) int c ー while( c = getchr(), isspace(c) ) ungetchr ( c / * 識別子の抽出 * / static void lex—ident( void ) int c, pos = の int type ー void *data ー void c lose—source ( void ) { fcl ose ( srcf } / * 現在処理中の行番号 * / static 土 n セ cur ー ine = 1 ー void error(const char *format va—list は s fprintf(stderr, "ERROR!%rßd : va—start い ist , format vfprintf ( stderr , format , は s し va—end( list); fprintf(stderr,"%n"); 0 lose—source ( ex 辻 ( -1 cu ては ne while( c = getchr(), isalnum(c) Ⅱ c = = if( pos く IDENT—MAXLEN ) Lex. detail.ident[ 00S 十十 ] = (char) ungetchr ( c Lex. detail.ident[pos] = 0 ' ・ if( hash—search( Lex. detail.ident &type, &data) ) { / * 登録済み識別子 ( 予約語や関数名籌 ) の場合 * / Lex. type = type; Lex. data = data; else / * 未登録の識別子 * / Lex.type = IDENT; Lex. is—ident = TRUE; / * 定数の抽出 * / static void lex—const ( void ) int c ー unsigned int num=O; while( 0 = getchr(), isdigit(c) ) num = num * 10 十 (unsigned) ( c ungetchr ( c Lex. type = CONST; Lex. is—ident = FALSE ー Lex. detail . = num; static int unget = FALSE ー static int unget—chr ・ / * 1 文字読み込むただしコメントは除去される * / static int getchr ( void ) if( unget ) ( unget = FALSE; return unget—chr ー )else{ int c = fgetc ( srcf cur line 十十一 ' # ' ) { / * コメント行の除去 * / 引 se if (c - while( c = fgetc(srcf), c ! = '%n' & & c ! = EOF curl ine 十 return c; 特集 1 スクリプト言語を作ろう 13

5. 月刊 C MAGAZINE 2000年5月号

List 6 文の処理部 c 。叩 e て . c : 構文解析系 & コード生成系 ヨ #include ” toy. h ″ 卩 static 土 n セ labelnum; static int cur—framesxze; static vmcode—t * r00 に , * curcode ー static void init(void) labelnum = cur_framesize = 0 ー ⅱ て 00t = curcode = NULL ・ ヨ vardecl(void) , lf(int,int), While(void) , print ( void ) , Return ( void #define LABEL-INVAL ー 1 / * 無効なラベル値 * / static void block(int brk, 土 n セ cont) int ー oop=TRUE ー int has—hashtab = FALSE; do { getlex( 1 switch( Lex. type ) { case BEGIN: block(brk,cont); break; case END ・ if( op ) op = FALSE; break; case VAR: if( ! has-hashtable ) { add—hashtable( has-hashtable = TRUE; vardecl ( break; case IF: lf(brk,cont); break; case WHILE: Whi 尾 ( break; case PRINT: print( break; case RETURN ・ Return( break; case SEMICOLON: / * 空文 * / break; case BREAK ・ if( brk = = LABEL—INVAL ) error ( ″この文脈で b て eak 文は使えません” add-code(-JMP, brk, 0 , NULL); break ー case CONTINUE: if( cont = = LABEL—INVAL ) e てて 0 て ( ″この文脈で cont 土 nue 文は使えません”潺 add—code ( —JMP , cont , 0 , NULL break; case ELSE : e て r 。 r ( ″無効な引 se 文です” break; defau 比 : / * 式文 * / ungetlex( expression( ) ー if ( Lex. t e ! = SEMICOLON ) 。。。 , に文が一で終了していません " add-code(—POP, 0 , 0 , NULL); break; )while( op ); if( has_hashtable ) remove—hashtable( 土 n しね b —next ( void ) { return ね b 引 num 十 } static int ね b 引ー tOt 引 (void) { return labelnum ・ static 土 n し alloc—offset(int n) int offset; offset = cur—framesize; cur—framesize 十 = n; return Of f set ー ヨ static 土 n し framesi ze ( VOid ) { return cur—framesize , void add-code(int code, 土 n しも int b, void *p) vmcode—t *vmcode ー vmcode = Ma Ⅱ oc ( vmcode—t, 1 vmcode—>next = NULL ー ヨ vmcode—>C0de = COde ー vmcode—>a = a ー vmcode->b = b ー vmcode—>p = p ー if ( ! curcode ) て 00t = curcode vmcode; else{ curcode—>next = vmcode ー curcode = vmcode ー void chg-code ( int code ) { curcode —>COde COde static vmcode—t* assemble(void) vmcode—t * *addrs , *p , *prev ー addrs = Malloc(vmcode—t* , ね b 引ーし 0 し引 ( ) prev = NULL; p = て 00t ー while( p!=NULL ) { LABEL) { if( p->code vmcode—t *save,*jmpp; save = p; do { p = p->next; }while( p->code = = —LABEL jmpp = p; p = save; while( p ! = jmpp ) { addrs[ p->a ] Jmpp; save = p—>next ー free ( p p = save; if ( prev ) prev->next root Jmpp; prev = )•rnpp; p = jmpp->next; }else{ prev = p; p = p->next; void vardecl(void) char ident [ I DENT—MAXLEN 十 1 嵭 vardata *vdata ー do { getlex( if( ! Lex. is—ident ) e て r 。 r ( ”変数宣言には識別子が必要” strcpy ( ident , Lex. detai l. ident vdata = Malloc(vardata,1); getlex( if( Lex. type = = LBRACK ) { / * 配列の宣言 * / getlex( if( Lex. t e ! = CONST ) 。。。 , ( " 列の宣言が間違っています " vdata->0ffset = alloc—offset( Lex. detail.number vdata->vartype = VARTYPE—ARRAY; ヨ getl ex ( if( Lex. t e ! = RBRACK ) error( 列宕言に 丿 ] がありません” getl ex ( }else { vdata->0ffset = alloc—offset( 1 ); vdata—>vartype = VARTYPE—VAR ー if( ! hash—store(ident, LOCALVAR, vdata) ) e て r 。 r ( ″識別子 %s の宣言が重複しています” ident }while( Lex. type = = CO ・ 1 ーー 41 ーす第は 1 第ー、 17 ヨー「ーー 1 )mpp; 0 0 0 0 一 3 cd td て O O O 0 ー諸ド ~ static VOid 26 C MAGAZINE 20 5

6. 月刊 C MAGAZINE 2000年5月号

特集 1 五ロ - 三ロ を 果となることを確認できるはずです。つま と思われる再帰下降解析 (recursive descen ように構文木から後置記法への変換ルール り , スタック式仮想マシンを想定した場合 tparsing ) と呼ばれる方法に基づいていま はきわめて簡単であり , 構文木を生成する 後置記法から直接に式の評価コードを生成 す。 アルゴリズムを多少変形すれば字句を読み できるわけです。 この手法では , 演算子のプライオリティ ながら直接に後置記法へと変換するアルゴ toy の式解析部の実装では構文木を作ら に応じて木の生成ルーチンを個別に用意し リズムを得ることもできます (List 4 ) 。 ず , 字句を読みながら一気に中間コードを ます。それぞれのルーチンでは , そのルー 以上で , 後置記法への変換が構文木を生 生成するという手法をとっていますが , そ チンの担当とする演算子のオペランドとな 成せずとも行えるということを理解してい の手法を解説する前に , 素直に構文木を生 る部分木を次に高いプライオリティを担当 ただけたと思います。そして , 後置記法か 成するアルゴリズムを見ておきましよう するルーチンに生成させます。この方法を らは直接に式の評価コードを生成すること (List 3 ) 。これは 4 種類の二項演算子 ( + , とれば , 各ルーチンは自身の処理すべき問 ができるため , 後置記法を生成するアルゴ * , / ) のみで構成される式に対して構文木 題のみを扱えばよいことになり , たいへん リズムを少々変形させるだけで , 字句を読 を生成するきわめて簡略化されたプログラ シンプルな構造となるのです。 みながら直接に中間コードを生成するアル ムですが , 字句を読みながら構文木を生成 ゴリズムを導出できるのです。 このように , 構文木を生成するアルゴリ ズムは単純なものです。そして , 前述した するアルゴリズムとしてはもっとも一般的 では , 式の構文規則 ( Fig. 7 ) に基づく式 式の構文規則に基づく式解析部 List 5 / * = = ! = 演算子の優先順位 * / void expr3(int *lvalue) int optype ー expr4(IvaIue); for(; optype = Lex. type ・ switch( Lex. type ⅱ case EQEQ : case NOTEQ: expr4(IvaIue); add—code(—CMP, optype, 0 , NULL); *lvalue = FALSE; break ー defau 比 : return ・ expr. c: 式解析系 #include ” toy. h ” static void exprO (int* ) ,exprl(int* ) expr2(int*) expr3(int*) , expr4(int* ) expr5(int* 5, expr6(int*5,expr7(int*) , factor(int*5, var( ) , call ( void expression(void) 土 n に lvalue=TRUE; exprO(&IvaIue); / * 代入演算子 * / void exprO(int *lvalue) exprl( lvalue); if( Lex. type = = EQUAL ) { if ( ! * ⅳ引 ue ) er て。て ( ”非左辺値への代入” ); chg—code ( —ADDR expression( add—code( —ASGN, 0 , 0 , NULL); *lvalue = FALSE; / * Ⅱ演算子 * / void exp て 1(土nセ * lvalue) 土 n セ LI ー expr2( lvalue); while( Lex. type = = OROR LI = ね b 引 -next( add—code( —TJMP , LI, TRUE, NULL); expr2(lvaIue); 0 , NULL); add—code ( —LABEL , LI , *lvalue = FALSE; / * & & 演算子の優先順位 * / void expr2(int *lvalue) 土 n セ LI ー expr3(IvaIue); while( Lex ・ tYEE = = ANDAND ) ( LI = ー abel —next( add—code( —FJMP , LI, TRUE, NULL); expr3(IvaIue); add—code( -LABEL , も 1 , 0 , NULL); *lvalue = FALSE; / * くく = > > = 演算子の優先順位 * / void expr4(int *lvalue) int optype ー expr5(IvaIue); optype = Lex. type ・ switch( Lex. type ⅱ case LT: case LE: case GT: case GE: expr5(IvaIue); add—code(—CMP, optype, 0 , NULL); *lvalue = FALSE; break; defau 比 : return ー / * + - 演算子の優先順位 * / void expr5(int *lvalue) int op = 0 ー expr6(IvaIue); switch ( Lex 北 e ) { case PLUS : break; op = —ADD; case MINUS : -SUB; break; default: return ー expr6( lvalue); add-code(op, 0 , 0 , NULL); *lvalue = FALSE; 特集 1 スクリプト言語を作ろう 21

7. 月刊 C MAGAZINE 2000年5月号

五ロ - 三ロ …トう を とくにこのような先読みしなければ字句 のアルゴリズムは次のようなものです。ま 識別子空間 ず先頭の 1 文字を読み込み , 字句定義に従 タイプを決定できない問題は FORTRAN に 多く見られることが知られています。しか って抽出すべき字句タイプを決定します。 し , 大半の言語では , ほとんど先読みしな toy の字句定義は先ほど見たように単純な 最初に toy の言語仕様および構文規則に ついて見ておきます (Table2, Fig. 4)。 くても字句タイプを決定できるように字句 ので , 字句タイプの判別は容易です。次に を定義しています。字句定義をそのように 決定された字句タイプに基づいて下請けの toy ではプロック中で変数を宣言した場 抽出ルーチンに字句を抽出させます。たと 合 , その変数は宣言されたプロックのスコ シンプルにしておくことで解析部の設計は 容易になりますし , 何より高速な字句抽出 えば , 先頭が数字であれば下請けの lex ー co ープにおいて有効となります。上位のプロ nst ( ) に抽出させ , あるいは先頭が " ¥ " " で が可能となります。 ックで同一名称の変数が宣言されていたと あれば文字列として lex-string() に抽出を 独自の言語 ( とくに解釈を高速に行うこ しても , 新しいスコープに属する変数とい とを要求されるインタブリタ言語 ) を設計 任せます。 うことになり名前の衝突は起こりません。 する場合 , これは重要なポイントとなるで 抽出を担当するルーチンの側では , 字句 したがって字句解析部では , 変数名が現 定義に従って字句を抽出し , 最終的に得ら れたスコープに依存してその実体が決定さ しよう。 れた字句の正当性を評価しなければなりま れる必要があります。 toy ではスコープに せん。文字列抽出ルーチンでは , 最低限 より階層化された識別子空間から文脈に依 存して決定される正しい実体を得る ( ある ド¥ " " で文字列が終結しているか ? 』といっ いは登録する ) ために , ハッシュ表そのも たチェックを行わなければなりませんし , 特殊記号の抽出ルーチンでは得られた記号 のを階層化させています ( 次の「ハッシュ それでは , toy の字句解析部を見ていき ましよう (List 1) 。また , toy 全体で使用さ を特殊記号の定義と照合して正当であるか 表」を大叩 ) れる構造体などの諸定義は List 2 のとおり どうかを検証する必要があります。正当性 が確認されれば , 字句情報を格納するグロ です。 このなかで字句の抽出を行っている関数 ーバル変数 Lex に得られた字句の情報を格 が getlex() です。この関数が行う字句抽出 納し , 字句抽出は完了します。 Fig. 4 toy の構文 ( BNF 記述 ) = def く識別子 > ( ) くプロック > ー く関数定義 > def く識別子 > 仮引数宣言リスト > ) くプロック > く仮引数宣言リスト > . = く仮引数宣言 > ーく仮引数宣言リスト > . く仮引数宣言 > = く識別子 > ーく識別子 > & く仮引数宣言 > くプロック > = く文並び > end ー end = く文 > ーく文並び > く文 > く文並び > = く va 「文 > ーく if 文 > ー <WhiIe 文 > ーく break 文 > く continue 文 > く文 > く p 「 int 文 > ー <return 文 > ーく式文 > ーく空文 > <begin5 ロック > = if く式 > then くプロック > else くプロック > ー く f 文 > if く式 > then くプロック > <while 文 > =while く式 > dO くプロック > <break 文 > = break : <continue 文ゝ = continue ー <print 文 > = print く式リスト > , = く式 > ーく式リスト > , く式 > く式リスト > <return 文 > = return く土 > く式文 > = く式 > く空文 > <beginüロック > = begin くプロック > く va 「文 > = va 「く変数宣言リスト > : = く変数宣言 > ーく変数宣言リスト > , く変数宣言 > く変数宣言リスト > = く識別子 > ーく識別子 > [ く定数 > ] く変数宣言 > 字句解析部の実装 ハッシュ表 ハッシュ表 ( 付録 CD - ROM に収録されて いる hash. c を参照 ) は , 字句解析にかぎら ずデータ処理の基本ともいえる重要なデー タ構造 ( およびアルゴリズム ) です。ハッシ ュ表はデータベースなどさまざまな用途で 活用されるばかりか , Per1 などの最近のイ ンタブリタ言語の大半では , 最初から基本 的なデータ型あるいはオプジェクトとして 組み込まれています。つまり , それだけデ ータ処理には不可欠なものといえます。 効率的かつ高速なハッシュ表の設計は簡 単ではなく , これだけで 1 冊の本になるく らいよく研究されている分野なのですが 本稿で実装する toy インタブリタはそれほ ど規模の大きな問題を扱うことを想定して いないので , 以下のように簡単な実装とな っています。 まず , 大きさ M の配列 hash ね hle を用意し , すべての要素を事前に NULL で初期化して おきます。登録に際してはキーとなる文字 列 key からなるべく一様な整数を作り , M スクリプト言語を作ろう 特集 1 15

8. 月刊 C MAGAZINE 2000年5月号

で割って 0 以上 M 未満のなるべく一様なハ ッシュ値を得ます (hash ( ) ) 。 ノ、ツシュイ直 hashval が得られたら p=hashtable [hashval] を参照し , p = = NULL であればその場所に 新しく生成したリストのポインタを格納し ます。すでにリストが格納されていれば , 単に新しい要素をリストに追加するだけで す。 #endif define #ifndef FALSE #endif #ifndef TRUE 2 ist toy で使用される構造体などの諸定義 #define TRUE 1 FALSE 0 / * t 。 y で使用する字句のタイプ * / 検索の際には同じ方法でハッシュ値を計 算し , 同様に p=hashtable [hashval] を得ま す。 こで p = = NULL であれば , そのキー は明らかにハッシュ表中には存在しませ ん。そうでなければ , リスト p を順に終端 まで探索しキーが存在するか否かを調査し ます。この方法は考え方そのものが簡単で あり実現も容易であることから , 小規模問 List 2 題への適用は有用だと思われますが , その 反面いくつかの欠点もあります。 規模の大きい問題ではリストの代わりに で落ちてしまうということです。もう少し ( 最良の場合で ) N / M に比例する程度にま 納される数 N が増大すれば , 探索時間も 高速にしたものにすぎず , ハッシュ表に格 つまり , この方法は結局線形探索を多少 extern extern extern extern extern extern extern / * t が IÆALV 飆か F c の場合に付随データへのポインタ ぎ納される * / VOid error(const char *format, int do—not—run; ー ex—t Lex ー VOid *data; enum IDENT, CONST , STRING, LOCALVAR , FUNC, DEF , BEGIN, VAR, IF, ELSE , WHILE, CONTINUE, PRINT, RETURN PLUS , MINUS, STAR, SLASH , PERC , LPAR , RPAR ′ LBRACK , RBRACK , CO 語マ SEMI COLON , EQUAL , ANDAND , OROR, EQEQ , NOTEQ, LEX—EOF , / * 識別子 * / / * 整数 * / / * 文字列リテラル * / / * ローカル変数 * / / * 関数 * / / * begin * / / * then * / / * else * / / * while * / / * break * / continue * / / * print * / / * return * / / * ファイルの終端 * / void getlex(void) , ungetlex(void); void add—hashtab 厄 ( void ) , remove—hashtab 厄 ( void int hash—search(const char*, int *type—r' VOid **data—r); int hash—store(const char*, int rpe , VOid *data); / * 識別子として意味を持つ最大の長さ #define IDENT—MAXLEN 32 / * 字句構造体 * / typedef struct vmcode—t struct vmcode—t *next ー 土 n し code, a, VOid *p; } vmcode—t; #define NARG—MAX 10 typedef struct struct vmcode—t *COde ー char *name ・ int framesi ze ー int narg; int argtype[NARG—MAX]; } vardata; int vartype ー int offset; typedef struct ARGTYPE—VALUE ARGTYPE—REFER , enum VARTYPE—REFER = 0X04 VARTYPE—ARRAY = 0X02 , VARTYPE—VAR enum } funcdata; = 0X01 , extern funcdata* compile(const char *fname); extern VOid expression(void); extern VOid c ー ose—source ( VOid extern void open—source ( const char * fname ) ・ extern VOid chg—code ( int code extern void add—code(int code,int a,int b,void *p); extern int ね b 引 -next( void typedef struct 土 n し type; 土 n is—ident ー union ( / * 字句タイプ * / / * 識別子 ( 予約語や関数名等 ) であれば真 * / extern void run ( funcdata * func extern VOid asmprint(vmcode—t *p,const char *funcname); / * type==CONST の場合に定数データが格納される * / unsigned int number; / * 土 s ユ dent が真の場合に識別子が格納される * / char ident [ IDENT—MAXLEN 十 1 ==STRING の場合に , 文字列の先頭を指す ンタが格納される * / char * string; } detail; enum / * ・命・・令 * / —LOAD, —ADDR, —SUB, —MUL, —RET , —JMP , —LABEL , —PUSH , —DIV, —FJMP, —POP, —MOD, —TJMP, —ASGN, —INVT, —CALL, —PRNT, —CMP, —ADD, / * メモリ割当用マクロ * / #include く s セ d は b. h 〉 #define ReaIIoc(type,p,n) (type*)realloc(p,sizeof(type)*(n)) #define calloc(type,n) (type*)calloc((n),sizeof(type)) #define MaIIoc(type,n) (type*)malloc(sizeof(type)*(n)) 16 C MAGAZINE 2000 5

9. 月刊 C MAGAZINE 2000年5月号

パイラ部は「関数定義」か「プログラムの終 端」のいずれかの入力状態のみを受け取る ことになり , それ以外の状態を受け取った 場合は入力されたプログラムに誤りがある ことを意味します。ループ中では , まず字 句を抽出し , DEF ( ' def ' ) であれば関数定 義であるため funcdef ( ) に関数定義を行わ せ , LEX ー EOF であればプログラムの終端 を意味しているためループから抜け次の段 階に進みます。得られた字句がそのどちら でもなければ , 入力されたプログラムは不 正であることになるため , 工ラーを発生さ せ即座にコンパイルを中止します。 こまでの段階で問題が発生しなけれ ば , プログラムは正常にコンパイルされた と判断できます。なお , この時点でプログ ラムは最後まで走査されており , もはや参 照する必要もないため , ソースファイルは クローズ (close_source()) しておきます 最後に main 関数が正しい形式で定義されて いるかをチェックし , 誤りがなければ main 関数の関数構造体を返却し , コンパイラ部 の処理は完了します。 関数の定義とコンバイル 30 C MAGAZINE 2000 5 い。関数本体のコンパイルを開始する前に 数名の登録となることに注意してくださ であり , よってプログラムスコープへの関 のハッシュ表の階層構造は常にルートのみ ッシュ表に登録してやります。この時点で ば , まずこれからコンパイルする関数をハ 関数名が正当なものとして認められれ あるか否かによって行えます。 字句タイプが未定義の識別子 ( IDENT ) で れません。このチェックは , 字句を抽出し , や def などの予約語と重複することは許さ ーのものでなければならず , ほかの関数名 表により表される識別子空間 ) において唯 グラムスコープ ( つまりルートのハッシュ 義部について見ていきます。関数名はプロ コンパイラ部の重要な仕事である関数定 関数名を登録してしまうことについて , 不 自然に思われる方もいるかと思いますが もしコンパイルの完了したあとに登録を行 うという方法をとった場合 def foo(n) if n > 0 then f00 ( n -1 ) end end のような再帰呼び出しコードにおいて , 関 数呼び出しに現れた fo 。は未定義のままで ありエラーを生じてしまうことになります。 つまり , t 。 y の仕様では関数を再帰的に呼 び出すことを許しているため , 本体をコン パイルする前に関数名を登録しておく必要 があるのです。 次に , 本体をコンパイルするために必要 な初期化処理として , 関数スコープのため 中間コード列 ( 命令アドレスは仮定 ) Fig. 8 中間コード列から仮想マシン命令列への変換 のハッシュ表を作成し (add-hashtable() ) , init ( ) によりラベル値などの初期化を行っ たあと , parse-arg() を呼び出し仮引数宣 言部を処理させます。 このなかでの処理はそれほど複雑ではな いのでコードを追っていただければと思い ますが , 仮引数に割り当てられるオフセッ トがフレームの先頭領域を占有することに 注意しておいてください ( これは実行時に 意味を持ちます ) 。 仮引数宣言部を処理し終われば , 残るは 関数本体のコンパイルです。構文規則から 明らかなように本体はプロックなので , コ ード生成は単に block ( ) を呼ぶだけで完了 します。 最後に , 生成された中間コード列の終端 命令アドレス 0X0010 0x0020 OX0030 0x0050 0x0040 ↓ 変換 ↓ 仮想マシン命令列 0x0050 0x0040 0x0030 0x0020 0x0010 命令アドレス ロ卩丁 ] LABEL a=0 FJMP a=l b=FALSE LABEL a=l JMP a=0 FJMP b=FALSE p=0x0040 ロ卩 - ロ J M P p = 0X0010

10. 月刊 C MAGAZINE 2000年5月号

特集 1 を 五ロ 三 - ロ 性を犠牲にしてもよいのならインラインア とができれば = 1.6 となり多少高速となり なくても ) を理解しているか否かで , それ ます。さらに C= は , 1 , 引が実現可能なら , らのツールに対する理解の度合いもきっと センプラを使うのも手かもしれません。 異なるはずです。 = 1.3 にまで改善できたことになります。 命令の選択時間の短縮 つまり , 簡単にいえば , 『あまり出現し そして第 2 の理由 , 実はこれが最大の理 ない命令の選択時間を犠牲にしてでも出現 由なのですが , 代表的な自動生成系のほと 仮想マシンのなかでは , 命令を実行する 率の高い命令の選択時間は短縮せよ』 , と んどは C のコードを吐くように作られてい ために , 命令が行うべき処理を選択しなけ いうことです。このセオリーに基づけば , ることです。本稿で例として用いた toy イ ればなりません。この部分に消費される処 ンタブリタも C で書かれていますし , Perl toy の実装のようにひとつの switch 文です べての命令を選択させる方法はそれぞれの 理時間も仮想マシンの実行性能に影響を及 や Python などほとんどが C で書かれてお 命令の出現率が等しくないかぎり望ましい り , むしろそれ以外の言語でインタブリタ ばす重要なファクタです。 やコンパイラを記述することのほうが稀か こで , n 種類の命令を処理する仮想マ ものではないことになります。たとえば統 シンを想定します。 l(i), i=l, n を命令 , 計をとるなどして各命令の出現率を推定 もしれません。しかし , 字句解析や構文解 P ( i ) を I ( i ) の出現率に P ( j ) = 1 ) , c(i) を l(i) し , 出現率に基づいた優先される命令グル 析を必要とするプログラムを常に C で書く ープとそうでない命令グループとに分け , が選択されるまでの時間とすれば , とはかぎりません。コンピュータの性能は = äP(j)C(j) 実行時には常に優先される命令グループか 著しく向上しており , インタブリタ自体を ら選択が試みられるようにするだけでも多 インタブリタ言語で書いてしまうことも , は命令全体に対する選択時間の期待値とな ります。つまり , ある命令が選択されるま 少は高速になる可能性があります。 今後それほど珍しいことではなくなるでし よう。そのような場合でも , ある程度以上 でには平均してそれだけのコストが毎回か のデータ構造の表現力を持ち , 再帰呼び出 かっているということです。この時間を短 しを許す言語であれば , 本稿で紹介した再 縮することができれば , 理論的には仮想マ シンの実行速度も上がることになるはずで 帰下降解析法を用いて比較的容易に実装で きるはずです。 す。では , どうすればよいでしよう ? 言語の設計からインタブリタの実装ま 本特集によってインタブリタに興味を持 で , そのひとつの手法を駆け足で紹介して 命令の出現率 P ( i ) は命令の意味によりほ っていただけたら , 実際に使われているイ ば決定されてくるものであり , これは固定 きましたが , いかがでしたでしようか ? されているものとします。ここでは , C (i) 今回はあえて lex や yacc などのパーザ自動 ンタブリタを調べてみることをぜひお薦め 生成ツールを使わず , 解析部を一から書き を可変として , よりよいを得ることを考 します。 Windows 用のソフトウェアでは ソースコードが公開されているものは少な えます。まず , 最良のはいうまでもなく 起こすという方法をとったため , それらの = 0 つまり C ( 1 ) = C ② = … = C ( n ) = 0 の場合で ツールを使う場合に比べて実装にかかる労 いでしようが , UN Ⅸ系では大部分がオー すが , 現実の仮想マシンではとうてい実現 力は大きなものとなっています。たしかに プンソースソフトウェアとして公開されて それらのツールを用いればインタブリタや 不可能なので , 以下では C ( j ) が固定され , います。 PerI など世界中で利用されている C ( i ) の最小値 ( 0 は不可 ) が与えられている 言語のインタブリタ内部を調べてみること コンパイラをラクに作ることができるので で , インタブリタに対する理解はより深ま という条件を付けることにします。このよ すが , あえてまだるっこしい方法を選んだ ることでしよう。インターネット上を探せ うな条件のもとに最良のを求めることは のには筆者なりの意図があります。 ば , 世界中に無数に存在するあらゆる言語 線形計画に属する問題であり , 通常最良の 第一の理由は , 初心者にとってそれらの のインタブリタのソースコードを入手する 4 を一意に決定できるでしよう。ただし , ツールはしばしばプラックポックスとなる ことができます。また , 拙作である Formu それはあくまで理論上の最良値であり , 仮 ことです。「内部構造なんて知らなくても la もソースコードを公開しているので何ら いいやん」といわれればまあそれはそうな 想マシンの実装に反映させることはきわめ て困難であるといえます。そこで , 普通は んでしようが , 内部でどのように処理が行 かの参考になるかもしれません。 最後になりましたが , 言語処理はおもし 実現可能な範囲内で〃をなるべく最良値に われているかをイメージできるかできない ろい分野であり , かっ実践的で日常の仕事 近付けることになります。 かで , そういう便利ツールの使い方も変わ 例として n = 3 , P = 6 , 0.3 , 0. 乢 C=12, 2 , にすぐ活用できるものでもあります。拙稿 ってくるように思えるのです。どんなに簡 単なものであっても , 字句解析や構文解析 幻の場合を考えます。このとき / = 2.0 とな がその有用性のいくぶんかでも伝えること りますが , 仮に C= は , 2.5 , 2. 引とするこ の原理 ( それが数ある手法のひとつにすぎ ができたのなら幸いです。 終わりに 特集 1 スクリプト言語を作ろう 37