type - みる会図書館


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

1. 月刊 C MAGAZINE 2000年5月号

静的変数である tmp,tmpint,tmpint2 は命 str() , push ー ptr ( ) のいずれかを状況に応 令実行時に一時的に使用されるもので , 再 じて用いることになりますが , 細かな説明 帰的に呼ばれる run ( ) 間で共用されるもの は必要ないでしよう。 トップのデータをポップするには p 叩 ( ) です。 関数の実行に備え , まずはローカル変数 次に , ローカルな fp はフレームの先頭を を使用します。なお , スタックポインタは 領域となるフレームを確保します。この作 指すアドレスです。フレーム ( データセグ スタックに積まれるごとに増加することに メントなどとも呼ばれる ) とは関数呼び出 業は次の 2 行 , 注意してください。 しごとに割り付けられるローカルなデータ fp = sp - func->narg; 領域のことです。 sp = fp + func->framesize; toy ではフレームはスタックから割り振 によって行われています。関数に引数とし て渡されるデータは , 左側の引数から順に られ , 仮引数を含むローカル変数領域とし スタックに積まれているため , スタックポ まず , この関数内で用いられる変数の意 て利用されます。そして vcode は , 実行さ インタ sp から関数の要求する引数の数を引 れる命令の命令アドレスです。 味について簡単に説明しておきます。 実行系 フレームの割り付け 仮想マシン本体 ( 「 un ( ) ) List 7 static stackdata pop( ) return *——sp; static int chk—int ( stackdata x , funcdata * func ) if( x. type = = TYPE-INT ) return x. data. integer ー else{ fprintf(stderr, "RUNTIME ERROR: %s: 整数でないオペランド n ″ func—>name) ー ex 辻 ( -1 return の / * 警告抑制のため * / run. c: 実行系 #include く s セ d 土 0 . h > #include くSセr土n9. h> #include ”に OY. h enum { TYPE—INT=O , TYPE—STR , TYPE_PTR typedef struct stackdata { char type ー union{ int integer ー char *string; struct stackdata *ptr ー }data; } stackdata; #define STACKSIZE 2048 stackdata stk[STACKSI•ZE]; stackdata * sp=stk; stackdata *end—of—stk = stk 十 STACKS I ZE ー static VOid runerror ( const char *msg ) fprintf(stderr, "RUNTIME ERROR: 宅 s n ” ,msg); exit ( ー 1 static void stkoverflow(void) て聞 e てて 0 て ( ”スタックのオーバーフロー” #def ine check—stack ( ) if ( sp > = end—of—stk stkoverflow( static void push ( stackdata data ) check—stack ( *sp 十十 = data; static int is—true ( stackdata x ) return ! ( x. type==TYPE— INT & & x. data. integer== 0 static VOid divbyOerror(void) runerror ( "Divide by 0 ” 朝 -14 」」ョ static VOid modby0error ( void ) runerror( ” 0d ⅵ 0 bY 0 ″ static VOid print ( stackdata *p , int n ) int 土ー fo て ( 土 = 土く i 十十 , p 十十 ) { if( p->tyee = = TYPE—INT ) printf( %d", p->data. integer); else if( p->type = = TYPE—STR ) fputs(p->data. string,stdout); ff lush ( stdout static VOid push—int(int x) check—stack ( sp->type = TYPE—INT; ( sp 十十 ) ->data. integer=x ー static void push—str(char *p) check—stack ( sp->type = TYPE—STR ー ()p 十十 )->data. string = p; void run ( funcdata * func ) stat ic stackdata tmp ー static int tmpint,tmpint2; vmcode—t *vcode ー stackdata *fp; fp = sp ー func->narg; sp = fp 十 func->framesize; check—stack ( ) ・ / * ローカル変薮領域を 0 クリアする * / memset ( fp 十 func—>narg , 0 , (func->framesize-func->narg) *sizeof(stackdata) VCOde = func—>C0de; fo て信 switch ( vcode->code ) { case _LOAD : static void push—ptr(stackdata *p) check—stack ( sp->type = TYPE—PTR ー ()p 十十 )->data. ptr = p; 32 C MAGAZINE 2000 5

2. 月刊 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

3. 月刊 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

4. 月刊 C MAGAZINE 2000年5月号

Standard List Simple iostreams classes / / 単純なストリームバッファ #inc lude <istream> #inc lude く std 土 0. using std: :endl; usxng 8 し d : : 土 OS セ re 明・ using std: :istream; using std: : OSt て eam ・ using std : : streambuf; / / クラス simple—filebuf class simple—filebuf : ub は 0 streambuf public: simple—filebuf( ) : saved ( ー 1 ) vi てセー¯simple—filebuf( ) protected : {saved = (unsigned char)traits—type: : t0 ー cha て - 上 ) ( ch return (traits-type::eof()); / / 単に戻すことはできない else if (traits—type: :eq—int—type(traits—type: :eof( ) , (h) ) return ( a 址 8 ー t ゝ : : eof ( ) / / バッフアは利用中 {if ( 0 く = saved) virtua ー int—type pbackfail ( int—type ch = t て a 土 ts ー e : : eof ( ) ) ? : traits—type: :eof( ) ) return (putchar(traits—type: :to—char—type(ch) ) ! = EOF return (traits—type: :not—eof(ch) {if (traits—type: :eq—int—type(traits—type: :eof( ) , (h) ) virtual int—type overflow(int—type 曲 = traits—type: :eof( ) ) if ( 0 く = ch) {int—type ch = saved; virtual ow ( ) { て e 加て n (pbackfail ( u 0 響 ( ) ) } virtual 土 n ヒー t ) underflow( ) return (ch); } } : istream(&mybuf) 8 土叩厄ー土 fst て eam ( ) public: class 8 土叩厄ー土 fs セて e : public 土 gt て eam { / / クラス叩厄ー土 fst て eam int saved; / / 負の場合、保持している文字なし private : : t て a 辻 8 ー t : :eof( ) ) return ( ()h = getchar( ) ) ! = OF ? ch return (ch); } {saved = ー / / 保持しておいた文字を消す virtual ¯simple—ifstream( ) simple—filebuf *rdbuf( ) const {return ( (simple—filebuf *)&mybuf); } private: simple—filebuf mybuf; / / クラス simp 厄ー 0f8 セて e 明 c ー ass simp le—fstream ・ pub lic 土 ost て e { / / クラス si 叩厄ー fst て eam simple—filebuf mybuf; private : {return ( ( 叩厄ー f 幻曲 uf *)&mybuf); } simple—fi lebuf *rdbuf( ) const virtual ~ si 叩厄ー Ofs にて e 明 ( ) : ostream(&mybuf) simp 厄ー Ofst て e 明 ( ) public: c lass simple—ofstream ・ public 08t て e ( {simple—ofstream Ofs; int main(void) 〃テスト用 simple—filebuf mybuf; private : {return ( (simple—filebuf *)&mybuf); } simple—filebuf *rdbuf( ) const virtual ~ si 叩厄ー fst て eam ( ) : 土 0 て eam ( &mybuf ) simple—fstream( ) public: "hellO againn くく endl; simple—fstream fs; くく x くく endl; X ifstream ifs; "hello world" くく endl; fs くく OfS くく ifs >> x simple— int x; 0f8 くく return ( 0 fS くく = ”くく X くく endl ー fS >> x; Standard C ℃ + + 91

5. 月刊 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

6. 月刊 C MAGAZINE 2000年5月号

ルドアクセスという場合もありえる。 Java では , これらは文脈情報に基づいて属性を 判別している。「文脈情報」による判断が意 味するところは , List 4 の用法を見ると理 解してもらえるだろう。このプログラムで は , メソッド main のなか , (a) ~ (f) の 6 か 所に「 java. awt.image. BufferedImage 」という トークンの並びが登場する。そのうち 3 か 所 (c , d , e) は , ピリオドを挟んでさらに そのあとに別のトークンが続いている。ま ず , 後ろに別のトークンが続かない 3 か所 (a , b , f) について説明すると , これらの うち , (a) と (f) はクラス名の指定であり , (b) のみはコンストラクタの指定である。 一方 , 一見同じように見える (c) , (d) , ( e ) の 3 か所のうち , 最初のふたっ ( c , d) と , 最後 (e) とはまったく違う。最初の (c) と 2 番目の例 ( d ) は , パッケージ「 java. awt. i mage 」のなかに定義されたクラス「 Buffere dlmage 」のフィールドである「 TYPE—USH ORT GRAY 」 (c) および「 TYPE_3BYTE_BG R 」 (d) を意味しているが , これらは全体と してひとつの「名前」を表しているのであっ てフィールドアクセスではない。この「名 前」はとくに「式名」というが , この構文は Fig. 5 に示す規則に基づいている。これを 見ればおわかりのように , 式名を組み立て るためには識別子をピリオドで区切って並 べることしか許されない。 一方 , 3 番目 (e) の「 java. awt. image. Buffer edlmage. TYPE—3 BYTE-B GR 」は , main の ローカル変数として宣言した「 java 」に対し て「 . a 」を付加したフィールドアクセスに さらに「 . image 」を付加したフィールドアク ・・という具合に , フィールドアク セスに・ セスを多重に行っている例である。 式名の場合とは違って , フィールドアク セスの場合 , ピリオドの左側は「一次子」で あればよい。一次子であれば , Fig. 1 に示 したように式をカッコで囲んだ形式が許さ れる。したがって (e) のケースでは , List 5 に示したようにピリオドの左の部分式をカ 96 C MAGAZINE 2 0 5 Java プログラミングリファレンス 詳説 JDK 解体新 / / ローカル変数 java のスコープ内でも , 型名として使用できる。 / / (f) java. awt.image. BufferedImage は型名 . TYPE-3BYTE—BGR); System. out. print ー n ( java. awt. image. BufferedImage / / java. awt ・ image. BufferedImage. TYPE—3BYTE—BGR / / java. awt.image. BufferedImage / / java. awt. image / / java. awt 〃以下はすべてフィールドアクセスである ここで java はローカル変数名であり、 / / ルドアクセス / / (e) java. awt.image. BufferedImage. TYPE—3BYTE—BGR はフィー ZO に java = new ZO し ( / / 末尾まで。 / / ローカル変数「 java 」のスコープはこの宣言から c ね ss st4 の . TYPE—3BYTE—BGR); system. out. println(java. awt. image. BufferedImage / / (d) 「 java. awt. image. BufferedImage. TYPE-3BYTE-BGR 」は「式名」 / / また , java. awt.image. BufferedImage は型名 こで java. awt. image はバッケージ名 $ava. awt.image. BufferedImage. TYPE—USHORT—GRAY); / / (c) 「 java. awt. image. BufferedImage. TYPE—USHORT-GRAY 」は「式名」 new java ・ awt.image. BufferedImage(10, 1 の 〃 (b ) これはコンストラクタ java ・ awt ・ image. BufferedImage bl ー / / ( a ) これはクラス名 pub lic static void main ( String [ ] argv) { class も土 st4 { Zo 日 ) { awt =newBaz(); } Baz awt; class 20t { Baz( ) { image = new Bar( } Bar image; class Baz { て ( ) { BufferedImage = new F00 ( } F00 BufferedImage ー class Bar { double TYPE-3BYTE-BGR = 3.1 class F00 { * コンパイルするには Java 2 ( SDK 1.2 ) が必要 * 多重のフィールドアクセスの例 / * ム is し 4. java ー多重のフィールドアクセスの例 system ・ out ・ println(b2. TYPE—3BYTE—BGR); java. awt.image. BufferedImage b2 = bl; ッコで囲んで記してもかまわない ( それ以外 の部分をカッコで囲むことは許されない ) 。 それに対して , (c) , (d) ではこのような カッコの挿入はいっさい許されない。あく まで「 java. awt.image. BufferedImage. TYPE 3BYTE ー BGR 」全体でひとつの名前であっ て , ピリオドの前後に空白や改行を挿入す ることはできるが , それ以外に表現のバリ 工ーションはない。 とくに注意するべきなのは , (d) と (e) は List 4 のソースの文面上はまったく同じ であるという点である。それなのに両者の 解釈が変わるのは , main メソッドの途中 で「 java 」という名のローカル変数を宣言し ているからである。「 java 」というローカル Fig. 4 List 4 のサンプルラン d : %cmaga*javaref>java List4 5 3 .14 5

7. 月刊 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

8. 月刊 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

9. 月刊 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

10. 月刊 C MAGAZINE 2000年5月号

特集 1 スクリト言 き五 作う びに 1 すっ増加する整数であり , 中間コー 0X0030 _LABEL 以外の命令 ド列に含まれる任意のラベル値 L に対して のように連続して LABEL 命令が現れるこ PUSH a=CONST b=0 は 0 L く N が成立するので , address=add とも考えられるため , 命令の先読みが必要 RET を追加することで , まことに安易な方法で rs [L] という関係を用いてラベル値 L と実 となります。つまり , この例では addrs [ 0 ] はありますが , return 文が用いられないま アドレスとを関連付けられるようになって = addrs [ 1 ] = 0X0030 とされなければなりませ ま関数本体が終端まで実行された場合に 0 います。 ん。 が返されるようにしています。 まず行うべきは , ラベル値と実アドレス 対応表が完成すれば , あとはジャンブ系 の対応表を作ることです。これは中間コー 命令の飛び先アドレスを解決するだけで ド列を先頭から読んでいき , LABEL 命令 す。もうおわかりですね。中間コード列に が現れた場合に 含まれるすべてのジャンブ系命令のパラメ ①次の命令アドレスを p として addrs[ ラ ータ a ( ラベル値 ) からパラメータ p ( 実アド こまでで , 関数に対する中間コード列 ベル値ト p レス ) を , が完成したことになりますが , 重要な仕事 ② LABEL 命令を中間コードから削除す p = addrs[a] がまだ残っています。つまり , 生成された と決定してやればよいわけです。 toy では る 中間コード列のままでは , ジャンプ命令の という作業を行えばよいだけなのですが 中間コード列も仮想マシン命令列も同じリ 飛び先が実アドレスとして決定されていな 場合によっては , スト構造をしているため , 以上の作業によ いため , そのままでは仮想マシンが直接実 り変換された命令列はそのまま仮想マシン 0X0010 LABEL a=0 行するにはまだ不完全なのです。この段階 で実行可能です。 0X0020 LABEL a=l での中間コードはアセンプリ語コードのよ うなものであり , アセンプラがアドレス解 決を行うのと同様に , toy の中間コードに 対してもアドレス解決を行わなければなり ません。 toy の実装では , 中間コード列と仮想マ シンが実行可能な命令コード列の構造は基 本的に同じものですが , LABEL 命令が仮 想マシン命令ではないこと , _JMP , _TJ プログラム上のすべての関数がコンパイ 共用体 data というふたつのメンバで構成さ MP, ー FJMP 命令の飛び先アドレスは中間 ルされれば , 残すところは main 関数を仮 れており , 想マシン上で実行するだけです。では実行 コードではパラメータ a として表されるラ ・ type==TYPE T であれば data. intege 系 ( List7 ) の内部について見ていきましょ ベル値であるのに対し , 仮想マシン命令で r の表す整数テータ あるためにはパラメータ p で表される実ア ・ type==TYPE_STR であれば data. string つ。 ドレスでなければならない点が異なってい を文字列の先頭アドレスとする文字 ます。したがって , 中間コード列に含まれ 列テータ る LABEL 命令をすべて取り除き , ジャン ・ type==TYPE PTR であれば data. ptr で ブ系命令の飛び先を実アドレスとして決定 表されるアドレス する作業が必要です ( Fig. 8 ) 。 のいずれかの状態を持ちます。 toy の仮想マシンは計算あるいは実行状 この変換操作を行う関数 assemble() を こで type==NPE_VPR となるデータは 態の保持のためにスタックを用います。 仮想マシンの内部でのみ使用されるもので 見てみましよう。まず , ラベル値と実アド のスタックの実体として stackdata 型の配 すが , 残りのふたつは式の評価結果あるい レスとの関係を表す大きさ N の配列 addrs 列 stk[STACKSIZE] を用意し , sp=stk をス はローカル変数の指すデータなどとして , を確保していますが , こで N=Iabel_total() タックポインタの初期値とします。 は現在処理中の中間コード列に含まれるラ 実行される関数の側からも使用されます。 スタック上の要素となる stackdata 型は , 仮想マシン中でのスタックに対するブッ ベルの総数です。 toy の実装ではラベル値 積まれたデータのタイプを識別する type , シュ操作は , push ( ) , push—int(), push は 0 から始まり , 新たに割り当てられるた および呼 pe に依存したデータの格納される 直接実行できる命令列 への変換 実行系 スタック 特集 1 スクリプト言語を作ろう 31