FrontPage

2008/05/16からのアクセス回数 5920

第5章　セマンティックス上の制限事項 †

かたくるしい言語認識の一般的問題から、プログラム・テキストを解析し翻訳した実行可能 なものを生成する、という明確な問題に移ることにしよう。したがってここでは、文章の代わ りにプログラムという言葉を用いることにする。これは、終端記号の列として定義され、ある 文法に対応した唯一のパーズ・トリーが構成できるもののことである。この章でプログラムに どのような付加制限を加えるかを扱って、コンパイラの解析部の設計を完了する。以下の章で は、プログラムによって記述されたアルゴリズムの実行可能バージョンの合成について述べる。

↑

問題点 †

プログラムは構文的に正しくても、意味的な誤りを含むことがある。典型的な例として、次 のようなものが挙げられる。

ラベルは、可視範囲のやっかいな問題の一つの例である。ユーザが定義したオブジェクトは、 名前の可視範囲として知られているプログラム・テキストの特定の範囲でのみ認識される。 BASICでは、変数名の可視範囲はプログラム・テキスト全体である(ただし、ユーザ定義関数 の引数名は例外)。FORTRANでは、変数名はプログラム単位、すなわち一つのfunctionまた はsubroutine内でのみ認識される。そして、プログラム単位名と。ommonエリア名は、実行さ れる一つのファイルであるイメージに束縛されるすべてのモジュールから認識される。Pascal やその他のAlgo1系言語では、ユーザが定義した名前は、ブロック、すなわちそれが定義され ているプログラム・テキストの文法的に区切られた一部分でのみ認識される。フロックは入れ 子構造をとることができ、外側のブロックの名前の定義は、内側のフロックで同じ名前を定義 することにより、内側のフロック内で覆い隠すことができる。C言語では、Algolのブロック 構造と、FORTRANのモジュールの概念を結合している。複合文は、入れ子構造をとることが できるブロックであり、宣言を持つことができ、その可視範囲は限定される。関数名は、広域 的に認識することができ、呼び出される前に宣言される必要はない。さまざまなオブジェクト に対する適切なアクセスを提供するコードを生成することと同様、ユーザが定義した名前がそ れぞれに対応した可視範囲内で正しく使われているかどうかをモニターするのも、コンパイラ の仕事である。

通常、名前は一つのコンテクスト中で二度宣言することはできない。たとえば、二つのパラ メータは同じ名前であってはならず、同じブロック内の二つの局所変数には別の名前を使わな ければならず、また同じstruct、mion、recordの二つの構成要素は異なっていなければなら ない。C言語では、structと他の名前が同一になってもいいことになっているが、C言語のい くつかのバージョンでは、異なる構造体であっても、構成要素の名前は異なっていなければな らないという制限があるものもある。

プログラムにおける宣言は、コンパイラに対し、一つの名前の意図した使われ方を伝達する。 いったんユーザが合意すれば、誤った使われ方をされないようにしなければならない。次のよ うなことを考えてみよう。

固定した、同一の旬の最大数を数え上げるのは、BNFにおいては扱いにくいテクニックであ る。BNFはまた、プログラミング言語に通常見られる、次のようないくつかの特徴を扱うこと もできない

多くのセマンティックス上の制限は、定数、型、変数、サブプログラム、およびラベルとい ったユーザ定義のオブジェクトを扱う。そこで、宣言および定義から得られるすべての情報を 入れ、ユーザ定義名称が参照された時はいつでも参照することができるような記号テーブルを 必要とする。

いくつかのセマンティックス上の制限が、単純なシンタックス上での解決を拒むという問題 を扱う。次のようなことを考えてみよう。

これらの制限事項は、特定の構成要素に関連する局所的テストをある程度必要とする。我々 のsampleCでは、別々のスタックによって、breakや。continueをどのようにチェックするこ とができるかを示すようにしている。一般には、ある程度の精巧な仕掛けを必要とするが、そ れはこれらの問題が、単一的な枠組には合わないからである。

↑

記号テーブルの原理 †

記号テーブルは、コンパイラがユーザの定義した名前や定数に関連するすべての情報を保持 する中心地である。記号テーブル・エントリをどのように設計するかは、コンパイラがどのよ うな情報を必要とするかに依存しており、プログラムの宣言部から得ることができる。一方、 検索のためのエントリの構成はその言語の可視範囲に影響する。

記号テーブル・エントリにはどのような情報が置かれるのであろうか。後で検索する必要が あるので、エントリからユーザ定義の名前に対してアクセスできなければならない。また、使い 方を検証するために、オブジェクトの型を表現しておかなければならない。さらに、コード生 成の時にオブジェクトの表現方法に関する、スタック上の位置、オフセットまたは絶対アドレ ス、長さなどの情報を持っていなければならない。

オブジェクトの型を表現するのはむずかしいかもしれない。FORTRANではほんのわずか な型しか存在せず、さらにオブジェクトは一つの配列として次元が与えられているかもしれな い。これは、記号テーブルの中で二、三の整数値で表わすことができる。PascalやC言語のよ うな、豊富なデータ型構成要素がある言語では、通常、記号テーブル上で他のエントリヘのポ インタになるような、再帰的記述方法を取り入れなければならない。

名前検索は、非常に多くのテクニックが存在する別の領域の問題である、一般に、字句解析 を行なう関数が、ユーザ定義の名前やリテラル定数をアセンブルすると、それは直ちに記号テ ーブルに置かれるか、それがまた未知である場合に記号テーブルに入れられるかである。以降 は、記号テーブル・エントリに対するポインタがパスされ、それによりその記号に関する情報 へのアクセスが提供されるので。記号テーブルを一回以上検索することを避けることができる。 したがって、最初の検索は、字句解析部からだけ呼び出されるルーチンによって行なわれる。 この検索をスピードアップするため、記号テーブル自身の他に、八ツシュテーブルのようなデ ータ構造が用いられるかもしれない。字句解析部が名前検索に非常に多くの処理時間を費すの で、テーブル検索を主題とした文献がたくさんある。手始めとして、W、McKeemanによる [Bau76]の3.D章などを参考にするとよい。

↑

例 †

sampleCでは、エントリを線型リストで表現した記号テーブル・スタックで我慢することに する。できるだけ単純化するため、検索をスピードアップする目的だけの付加データ構造は用 いないことにした。これについては例題として残しておくことにする。エントリは、calloc()お よび。cfree()といったライブラリ・ルーチンを用いることにより、動的に管理される。

記号テーブル・スタックは、もっとも新しいものから古いものへと逆向きに検索される。こ の方式によれば、複合文の処理を終えた時に局所的エントリをスタックから取り除くことによ り、一つの名前のもっとも内側の宣言が最初に見つかる。

したがってここでは、各オープン・ブロックの局所的宣言がどこから始まるかを知る必要が ある。これは、オープン・フロック記述子のスタックによって実現でき、そこから出るリンク ・リストが関連する記号テーブル・エントリをつないでいる。単純化のため、ブロック終了時 に処理時間をかけても、複合文の入れ子の深さに対する広域的カウンタを保持し、ある記号の 一つの宣言が完了した時に、それぞれの記号テーブル・エントリにこのカウンタの現在値をコ ピーすることにする。これにより、記号テーブル・スタック上の局所エントリは現時点の入れ 子の深さを正面奮にマークしたものになる。また、バグのあるプログラムでは、宣言されていな い記号がいくつかありうることになる。この場合、それらの入れ子の深さのフィールドは初期 値でマークされ、またブロック終了時に削除される。

関数は、使う前に定義する必要がないということから、一つの問題が生じる。しかし、関数 は入れ子になれないので、この問題は、関数に対する記述子をもっとも外側のフロックに置く ことにより解決できる。ここで採用している動的にリンクする方法では、これは非常に簡単に 実現できる。すなわち、記号テーブル・スタックの底部に関数記述子を再リンクするだけで良 い。ここでは、単一パスの、解釈即実行型コンパイラを作っているので、関数記述子は必ず退 避する必要がある。なぜならば、イメージ・アセンブリを行なえるリンカはないので、参照さ れた関数すべてが実際に定義されているかを自らチェックしなくてはならないからである。

別の、比較的小さな問題として、C言語では仮引数がはっきりと定義される必要がないとい うことがある。名前が引数リストに入れられると、省略時解釈としてそれらはint型変数とな る。これは、名前が最初にparameter_listにある時は、記号テーブルの中で引数をチェーンに することで処理できる。parameter_declarationsがいったん分類されてしまえば、チェーンを 追跡したり、また残っている宣言されていない仮引数に省略時解釈を与えることができる。

必ずしも必要なことではないが、ここでは関数が矛盾なく使われているかどうかをチェック する。すなわち、少なくとも関数が常に同じ数の実引数を伴って呼び出されているかを数える ことにする。

sampleCにおいては、大きな簡素化が一つ行なわれている。すなわち、この言語ではデータ 型としてintのみしかサポートしていない。したがって、ここではデータ型の不整合について心 配する必要がない。一般に意味的制限事項はこの点において強制される必要がある。これはパ ーサによってさまざまな演算を認識することで結果の型を計算し、それをyaccのスタックに 渡しておくことでうまく処理することができる。結果の解析はかなりかさばるので、ここでは 他のデータ型をサポートしないことでこれを避けることにした。

まず最初に記号テーブル・エントリを設計し、フィールドのいくつかに対する値を定義する ことにする。この情報はsymtab.hの中にある。

/*
 *	sample c -- header file for symbol table
 */

struct symtab {
	char *	s_name;		/* name pointer */
	int	s_type;		/* symbol type */
	int	s_blknum;	/* static block depth */
	union {
		int s__num;
		struct symtab * s__link;
		} s__;
	int	s_offset;	/* symbol definition */
	struct symtab * s_next;	/* next entry */
	
#define s_pnum	s__.s__num	/* count of parameters */
#define NOT_SET	(-1)		/* no count yet set */
#define	s_plist	s__.s__link	/* chain of parameters */

/*
 *	s_type values
 */

#define UDEC	0	/* not declared */
#define FUNC	1	/* function */
#define	UFUNC	2	/* undefined function */
#define	VAR	3	/* declared variable */
#define	PARM	4	/* undeclared parameter */

/*
 *	s_type values for S_TRACE
 */

struct symtab *	link_parm();	/* chain parameters */
struct symtab *	s_find();	/* locate symbol by name */
struct symtab *	make_parm();	/* declare parameter */
struct symtab *	make_var();	/* define variable */
struct symtab *	make_func();	/* define function */

/*
 *	typed library functions
 */

char * strsave();		/* dynamically save a string */
char * calloc();		/* dynamically obtain memory */

s_nameは名前検索に用いられる。strsave()は新しい名前を文字列として動的に退避する ために使う。s-blknumは、その名前が定義された可視範囲の入れ子の深さを持っている。 s_offsetは、後で一つのオブジェクトに対する実行時のアクセスに影響することになるが、現 在のところ省略することができる。S_neXtは、記号テーブル要素をスタックにリンクする。

s__こは二重の役割がある。s__inkは便宜上s_plistとして定義する。これは一つの関数の すべての引数を一緒にリンクするために用いる。これにより、宣言されていない引数に対し、 容易に省略時解釈を与えることができる。s_pnumとして定義されている別のフィールド s__numがあり、関数名が矛盾なく使われているかどうかをチェックするために用いられる。こ のフィールドには、値NOT-SETが初期値として設定される。関数が最初(値がNOT SETで あることで示される)に定義または参照されると、その時に指定されている仮引数または実引数 の数がs_pnumに設定される。したがって、それ以降の参照(値がNOT-SETでないことによ って示される)で引数の数を検査することができる。

s-typeは、最終的に記号テーブル・エントリのタイプを表わしていなければならない。ここ ではこの要素は単純に扱われ過ぎていて、(構造体は言うまでもなく)ポインタやベクトルが言 語に追加された場合、もっと複雑な表現方法を設計しなければならないが、今のところほんの 少しだけで良い。すなわち、名前は初期状態で未宣言(UDEC)として現われる。名前が参照され たが、関数として定義されていなければ、s_typeにUFUNCが設定される。関数が定義される と、この値はFUNCに変更される。そうでなければ、名前は引数(PARM)または変数(VAR) として参照されているかもしれないが、いずれの場合も整数である。

トレースの目的で記号テーブルをダンプすることがある。s_typeを数値表現で表示しないで 済むように、数値表現と同時に、SYMmapを管理している。数値を記号化するのは、記号テー ブルを扱うルーチンを安全に改造できないという点で危険性があるが、ここでは少なくともこ れら二つの表現を非常に接近させてある。

プログラミング・スタイル上のもう一つの点として、記号テーブル・エントリを表わす構造 体のすべての構成要素の名前に、同じs_というプレフィックスを付けるという暗黙の慣習を守 っているということに注意してほしい。

有名な清書プログラムで採用されている方法に従い、記号テーブル操作に関する関数すべて を一つのファイルsymtab.cに集めておくことにする。文法は、意味テストのために、これら のユーティリティを呼び出したアクションにより拡張されている。sampleCでは、基本的に Identifierの出現はすべてチェックされなければならない。breakおよびcontinueもまたチェ ックされなければならないが、ここではこの問題をコード生成の時まで延期することにした。 これにより、適切なジャンプの実現に関する問題を同時に扱うことができる。

追加されたアクションについて、文法と記号テーブル・ユーティリティに分けて議論する代 わりに、パーサとユーティリティ関数に平行して追加されているものについて述べることにす る。これが、ここにおける実際の実現の流れである。すなわち、文法規則をガイドとして用い、 Identifierの一つ一つの出現を順番に考慮していって、何をチェックしなければならないかを 判断し、公式化の一つのアクションとしてユーティリティ関数呼出しを追加し、そのようなユ ーティリティ関数をsymtab.cに実現する。文法のテーブルとしての特性は、すべての可能な 場合を考慮するということを明確にしてくれる。文法は、実現プロセスをガイドする理想的制 御構造のように働く。すべてのユーティリティ関数のリストが、付録のA.4節にある。

さて、必要となる広域変数を定義することから始めよう。それらは記号テーブル・マネージャ の排他的所有物であるから、staticとして定義される。このような方法で、symtab.cでは固 有データをコンパイラの他のモジュールから見えないようにしている。同様に、広域的名前に はstatic属性を指定しないことによって、パーサ・モジュールのアクションから実際に呼ばれ る関数のみを、このモジュールの外部から参照できるようにする。すべての内部的ユーティリ ティは、staticオブジェクトとして隠されている。

/*
 *	sample c -- symbol table definition and manipulation
 */

#include "symtab.h"
#include "y.tab.h"

/*
 *	symbol table
 */

static	struct symtab
	symtab,			/* blind element */
	* s_gbl;		/* global end of chain */
#define	s_lcl	(& symtab)	/* local end of chain */

/*
 *	block table
 */

static int blknum = 0;		/* current static block depth */

記号テーブルは、次のような動的構造を持つ。

fig_5.3_1.jpg

s_gblは変更されないブラインド要素を指していて、新たなエントリはその後に追加される。 このチェーンに沿って、スタックの底に広域的エントリがあるが、それらは本質的にポップさ れることがない。関数s_create()は、引数として与えられたアン前に対して新たな局所エントリ を記号テーブルに追加する。この新エントリは未定義であるとマークされる。

static struct symtab * s_create(name)
	register char * name;
{	register struct symtab * new_entry = (struct symtab *)
			calloc(1, sizeof(struct symtab));
	
	if (new_entry)
	{	new_entry->s_next = s_lcl->s_next;
		s_lcl->s_next = new_entry;
		new_entry->s_name = strsave(name);
		new_entry->s_type = UDEC;
		new_entry->s_blknum = 0;
		new_entry->s_pnum = NOT_SET;
		return new_entry;
	}
	fatal("No more room for symbols");
	/* NOTREACHED */
}

s_gblは最後の広域要素をマークしている。ある関数記述がそのチェーンの広域側の端点に 移動されると、それもs_gblの次に来るように移動される、すなわちs-gblがそれを指すように なる。これは、s_move()というルーチンによって行なわれる。引数は一つで、移動されるエン トリヘのポインタである。

static s_move(symbol)
	register struct symtab * symbol;
{	register struct symtab * ptr;
	
	/* find desired entry in symtab chain (bug if missing) */
	for (ptr = s_lcl; ptr->s_next !- symbol; ptr = ptr->s_next)
		if (! ptr->s_next)
			bug("s_move");
	
	/* unlink it from its present position */
	ptr->s_next = symbol->s_next;
	
	/* relink at global end of symtab */
	s_gbl->s_next = symbol;
	s_gbl = symbol;
	s_gbl->s_next = (struct symtab *) 0;
	
}

エントリは、記号テーブル・スタックの異なった位置にリンクされるだけであることに注意し てほしい。すなわち、エントリ自身はメモリの上を移動させられたわけではない。したがって、 その要素を参照していて引数として渡されるポインタの値は変更されない。

ここでは記号テーブル・スタックの先頭にブラインド要素を置いてあるので、移動しようと しているのが現在のスタックの先頭であるかどうかをチェックする必要がない。すなわちs_lcl を特別扱いしなくて良い。

しかし初期状態では、s_gblはブラインド要素を指していないかもしれない。もしそうであれ ば、s_gblに引き続く最初の(広域的)定義を追加し、局所定義がs_gblとこの広域定義の間にあ るようにし、いつかはそれらのうちの一つが広域的になるように移動されるかもしれない。こ れが一般的にやりすぎという結果になる。s_gblは広域的エントリを指すように初期化されな ければならない。つまり、そこにある一つのブラインド要素が記号テーブルを半分に分割し、 したがってもう一つの特別な場合を作り出すことになる。幸いにも、便利な広域的エントリが 存在する。すべてのsampleCのプログラムは関数main()を含んでいる。したがって、初期設定 処理としては一番外側のブロックをオープンし、s_gblが未定義関数mainに対するエントリ を指すように初期化することにする。

init()
{
	blk_push();
	s_gbl = s_create("main");
	s_gbl->s_type = UFUNC;
}

init()は記号テーブルがアクセスされる前に呼び出されなければならない。したがって、コン パイラ自身のmain()関数の中に、yyparse()に先立ってinit()の呼出しを置くことができる。 別の、もっと視覚的解決として、init()をパーサ自身の初めの部分から呼び出すという方法があ る。これはパーサに付加された最初のアクションである。

program
	:	{ init(); }
	definitions
		{ blk_pop(); }

このようにして、init()をは字句解析ルーチンのすべての呼出しに先立って呼び出されることに なる。

init()をはフロックのスタックをプッシュする。

blk_push()
{
	++ blknum;
}

blk_push()の呼出しは、記号テーブル・スタックから未定義関数などを見つけ出したり、そ こから後はアクセスできない記号をポップしてしまったりするための関数blk_pop()の呼出し とバランスしていなければならない。blk_pop()については、記号が実際にどのようにして記号 テーブルに入れられるかを決めるまで後回しにする。

ユーザが定義した名前は、最初に字句解析部によって識別される。yylex()はすべての記号 を、もしそれがすでに記号テーブルにあるのでなければ、そこに入れなければならない。この ため、すでに関数s_lookup()の呼出しを字句解析部に置いてある。s_lookup()は、yytext[]の 中にある終端記号表現および適当な終端記号の値ConstantまたはIdentifierを引数として呼 び出される。sampleCでは、Constantのテキストは動的に退避すれば十分である。Identifier は記号テーブルに入れられなければならない。

s_lookup(yylex)
	int yylex;		/* Constant or Identifier */
{	extern char yytext[];	/* text of symbol */

	switch (yylex) {
	case Constant:
		yylval.y_str = strsave(yytext);
		break;
	case Identifier:
		if (yylval.y_sym = s_find(yytext))
			break;
		yylval.y_sym = s_create(yytext);
		break;
	default:
		bug("s_lookup");
	}
}

どちらの場合でも、結果的にyylvalがユーザ定義終端記号に関する意味情報へのアクセスを提 供するポインタを持っている。s_lookup()は、ConstantやInteger以外の値を引数として呼び 出されることはないのはわかっているが、頑丈なコーディングにするということで引数の検証 を行なうことにする。

エントリを名前で記号テーブルに置くという問題を後回しにしてあった。次のルーチンは、 このコンパイラにおける効率の悪いものの一つである。

struct symtab * s_find(name)
	char * name;
{	register struct symtab * ptr;

	/* search symtab until match or end of symtab chain */
	for (ptr= s_lcl->s_next; ptr; ptr = ptr->s_next)
		if (! ptr->s_name)
			bug("s_find");
		else
			/* return ptr if names match */
			if (strcmp(ptr->s_name, name) == 0)
				return ptr;
	/* search fails, return NULL */
	return (struct symtab *) 0;
}

yylex()は、s_lookup()を用いてすべてのIdentifierが記号テーブルにあるように調整して いる。新たなエントリはUDECであるが、もし以一前にその名前が現われていたら、yylvalは正 しいエントリを指しているかもしれないし、いないかもしれない。Identifierが文法的に現われ た時はいつでも、訂正ないしチェックする必要がある。

C言語における名前は、関数のそれは例外として、使われる前に宣言されていなければなら ないので、宣言が最初に分類される。では、一つのIdentifierがparameter_listに現われる、 すなわちIdentifierが新しいパラメータになるポイントについて考えてみよう。

parameter_list
	: Identifier
		{ $$ = link_parm($1, 0); }
	| parameter_list ',' Identifier
		{ $$ = link_parm($3, $1);
		  yyerrok;
		}
	| error
		{ $$ = 0; }
	| parameter_list error
	| parameter_list error Ideitifier
		{ $$ = link_parm($3, $1);
		  yyerrok;
		}
	| parameter_list ',' error

link_parmOとyaccの値スタックは、すべての引数名のチェーンをparameter」istに作るた めに使われる。1ink-parm()はまた、Identifierが記号テーブルの中でPARMになるようにす る役割りも与えられている。後で、引数のチェーンを用いて未宣言引数に省略時の値を与え、 また引数の数を数えることにする。最初にlink_parm()を見てみよう。

struct symtab * link_parm(symbol, next)
	register struct symtab * symbol, * next;
{	
	switch (symbol->s_type) {
	case PARM:
		error("duplicate parameter %s", symbol->s_name);
		return next;
	case FUNC:
	case UFUNC:
	case VAR:
		symbol = s_create(symbol->s_name);
	case UDEC:
		break;
	default:
		bug("link_parm");
	}
	symbol->s_type = PARM;
	symbol->s_blknum = blknum;
	symbol->s_plist = next;
	return symbol;
}

yy1ex()がそのIdentifierをすでに記号テーブルに入れており、そのエントリがlink_parm()に 渡される。このエントリのs_typeフィールドが、次に何をしなければならないかを決定する。 すなわち、

関数link_parm()の設計は比較的簡単である。なぜならば、文法が意味解析のこの部分の前 後関係を分離し、記号テーブル・エントリのs_type構成要素の考えられる値が可能となるすべ ての場合を、そっと教えてくれるからである。C言語では関数は入れ子になることができない から、状況としては扱いが比較的簡単である。

引数の宣言は、わずかではあるが、もっと複雑である。これは、Identifierがparameter_ declarator_listにあった時に起こる。

paramater_declarator_list
	: Identifier
		{ make_parm($1); }
	| parameter_declarator_list ',' Identifier
		{ make_parm($3);
		  yyerrok;
		}
	| error
	| parameter_declarator_list error
	| parameter_declarator_list error Identifier
		{ make_parm($3);
		  yyerrok;
		}
	| parameter_declarator_list ',' error

make_parm()は、記号テーブルの中のPARMをVARに変更しなければならない。すなわ ち、これにより引数の宣言を行なう。いったんparameter-declarationsが処理されると、残り のすべてのPARMエントリを整数変数、すなわちVARとして宣言する必要がある。

make_parm()は記号テーブル・エントリにより与えられるが、これはyylex()がs_lookup() を通じて見つけたかまたは作り出したものである。s_typeの取りうる値をすべてもう一度考え 直すと、いくつかの考えられる誤りを見つけ出すことになる。

struct symtab * make_parm(symbol)
	register struct symtab * symbol;
{	
	switch (symbol->s_type) {
	case VAR:
		if (symbol->s_blknum == 2)
		{	error("parameter %s declared twice",
				symbol->s_name);
			return symbol;
		}
	case UDEC:
	case FUNC:
	case UFUNC:
		error("%s is not a parameter", symbol->s_name);
		symbol = s_create(symbol->s_name);
	case PARM:
		break;
	default:
		bug("make_parm");
	}
	symbol->s_type = VAR;
	symbol->s_blknum = blknum;
	return symbol;
}

変数定義に移ろう。これは、文法的コンテクストとしては引数の宣言と同等である。しかし、 必要となる意味的アクションはまったく異なっている。したがって、変数定義と引数宣言につ いて、文法規則をそれぞれ分けて指定することにする。もしsampleCをC言語の方に向かって 拡張していくのであれぱ、どのような方法にしろ、これらを区別しなければならない。すなわ ち、変数は初期化されるかもしれないが、引数はそうでない。

declarator_list
	: Identifier
		{ make_var($1); }
	| declarator_list ',' Identifier
		{ make_var($3);
		  yyerrok;
		}
	| error
	| declarator_list error
	| declarator_list error Identifier
		{ make_var($3);
		  yyerrok;
		}
	| declarator_list ',' error

make_var()は、定義を記号テーブルに反映させる責任を与えられている。したがってこの引 数は、yylexOが見つけてきた記号テーブル・エントリを参照する。このエントリにはs_typeの ために定義された値の一つがあるので、ここでも個々の場合について考えてみることにしよう。

struct symtab * make_var(symbol)
	register struct symtab * symbol;
{	
	switch (symbol->s_type) {
	case VAR:
	case FUNC:
	case UFUNC:
		if (symbol->s_blknum == blknum
		    || symbol->s_blknum == 2 && lknum == 3)
			error("duplicate name %s", symbol->s_name);
		symbol = s_create(symbol->s_name);
	case UDEC:
		break;		
	case PARM:
		error("unexpected parameter %s", symbol->s_name);
		break;
	default:
		bug("make_var");
	}
	symbol->s_type = VAR;
	symbol->s_blknum = blknum;
	return symbol;
}

このルーチンはブロック構造のほとんどすべての面に対してうまく対処できなければならない。 考慮すべきことは、s_typeの取る値と、入れ子レベルの値であり、これらを以前の記号を処理 している時に扱う。

関数定義の時に行なうべき2、3の仕事はすでにわかっている。parameter_listの長さは、計 算されチェックされ、または関数定義の中に入れられていて、引数固有の入れ子レベルを管理 しなければならない。この問題は、引数操作を囲むようにしたblk-push()とblk_pop()の組の 呼出しを追加することによって処理する。シンタックス上の関数定義を考えてみよう。

function_definition
	: Identifier '('
		{ make_func($1); blk_push(); }
	optional_parameter_list rp
	declarations
		{ chk_parm($1, parm_default($4)); }
	compound_statement
		{ blk_pop(); }

optional_parameter_list
	: /* null */
		{ $$ = 0;  /* no formal parameters */ }
	| parameter_list
		{ $$ = $1; /* chain of formal parameters */ }

make_fmc()は関数を記号テーブルの中に定義しなければならない。chk_parm()には、そのよ うな関数に関する記号テーブル・エントリヘのポインタが与えられ、引数の個数も指定される。 このルーチンはすべてがうまくいっているか調べ、また最初のアクセスの時には引数の個数を 設定しなければならない。parm_default()はparameter_1istの中で名前を挙げられているが、 引数宣言部では宣言されないような引数すべてを扱う。C言語では、それらの引数はint型変数 として省略時解釈される。すなわち、それらはPARMでなければならず、VARとして宣言す る。parm_default()はさらに、引数の数を数え、それらの数を返す必要がある。今度は関数を 考えてみよう。

struct symtab * make_func(symbol)
	register struct symtab * symbol;
{	
	switch (symbol->s_type) {
	case UFUNC:
	case UDEC:
		break;		
	case VAR:
		error("function name %s same as blobal varialble", 
			symbol->s_name);
		return symbol;
	case FUNC:
		error("duplicate function definition %s", 
			symbol->s_name);
		return symbol;
	case PARM:
	default:
		bug("make_func");
	}
	symbol->s_type = FUNC;
	symbol->s_blknum = 1;
	return symbol;
}

make_func()が呼び出される時は、広域的入れ子レベルにいるのであるから、記号テーブル・ エントリを動かす必要がない。UDECまたはUFUNCエントリは関数として簡単に定義する ことができ、VARまたはFUNCは複製が作られるものであり、それら以外に現われることは ない。

現在のところ、make_var()、make_parm()およびmake_func()は、結果を返す必要がな い。しかしいったんコード生成を開始すると、記号テーブルヘの適切なポインタが必要になる ので、変数の位置、または関数の開始アドレスのような情報を追加することができる。これが、 上の3つの関数が調整された記号テーブルヘのポインタを返すように設計されている理由であ る。もし何がまずいこと、たとえば二重定義に出くわした場合は、あまりうまくっくろうこと ができない。コンパイラは千里眼を持つことを要求されているわけではないが、ユーザが乱暴 に使っても、クラッシュしないことが期待されている。

引数の個数のチェックまたは設定は非常に簡単である。

chk_parm(symbol, count)
	register struct symtab * symbol;
	register int count;
{
	if (symbol->s_pnum == NOT_SET)
		symbol->s_pnum = count;
	else if ((int) symbol->s_pnum != count)
		warning("function %s should have %d argument(s)",
			symbol->s_name, symbol->s_pnum);
}

未宣言引数に省略時処理をするのも、同じように簡単である。ここでは記号テーブルのチェ 一ンをたどる必要がまれにある。

int parm_default(symbol)
	register struct symtab * symbol;
{	register int count = 0;

	while (symbol)
	{	++ count;
		if (symbol->s_type == PARM)
			symbol->s_type = VAR;
		symbol = symbol->s_plist;
	}
	return count;
}

これで最後になるが、記号を記号テーブルに入れた後、それらをブロック句を処理している 間、どのようにして取り返すのかということについて考えてみることにしよう。blk_pop()は、 広域ブロックに対してはprogramに関連付けられたアクションから、また最終的に。compound_ statementに関連付けられたアクションから呼び出される。

compound_statement
	: '{'
		{ blk_push(); }
	 declarations statements rr
		{ blk_pop(); }

記号テーブルの中の現在の入れ子レベルをたどるようなループが必要である。なぜならば、 このループにより、すべての局所エントリを切り離したり、解放したりすることができるから である。未定義エントリがあった場合、通常先にそれに対して警告を発する。しかし、未定義 関数は広域ブロックを解放した時に見つかる。

blk_pop()
{	register struct symtab * ptr;

	for (ptr = s_lcl->s_next;
	     ptr &&
	     (ptr->s_blknum >= blknum || ptr->s_blknum == 0);
	     ptr = s_lcl->s_next)
	{
		if (! ptr->s_name)
			bug("blk_pop null name);
#ifdef TRACE
	{	static char * type[] = { SYMmap };
	
		message("Popping %s: %s, depth %d, offset %d,
			ptr->s_name, type[ptr->s_type],
			ptr->s_blknum, ptr->s_offset);
	}
#endif TRACE
		if (ptr->s_type == UFUNC)
			error("undefined fuction %s",
				ptr->s_name);
		cfree(ptr->s_name);
		s_lcl->s_next = ptr->s_next;
		cfree(ptr);
	}
	-- blknum;
}

最初のブラインド要素は無視しなけらぱならない。記号テーブルの範囲を出て、nullのポイン タを手繰ってはならないし、実際そのようなポインタがあってはならない。また、現在の入れ 子レベル、だぶんblknumに対して、すべてのエントリを考慮しなければならない。入れ子レ ベルO、すなわち初期化されていないエントリのレベルでは2、3のエントリしかなく・それら はたとえぱエラー回復処理中に残された結果の記号である、もちろん、このリデュース・アク ションが見たこともない記号にも出会うこともあるだIろう。

blk_pop()は、トレース出力を置くために良い場所であり、何が起こっているかを見ることが できる。ここでは。記号テーブル・エントリが解放される時に、そのすべての構成要素を印刷 するような命令を条件付きで挿入する。

これまでは、情報を記号テーブルに入れることから遠のいていたが、今こそこれらを役立て よう。Identifierが式の中で使われた時はいつでも、コンテクストと記号テーブル・エントリを 比較し、その使用が正当なものであるかどうかを見分けなければならない。sampleCでの考慮 すべき点は、本質的に2個所だけである。一つは次のものである。

binary
	: Identifier
		{ chk_var($1); }
	| PP Identifier
		{ chk_var($2); }
	| Identifier '=' binary
		{ chk_var($1); }

(ここでは、非常に似通ったいくつかの式を省略した。) chk_var()は、引数として渡されたIdentifierが割当ての両サイドで一つの変数として参照す ることができるかどうかを決定しなければならない。ここでもまた、s_typeのいくつかの値が 答を与えてくれる。

chk_var(symbol)
	register struct symtab * symbol;
{
	switch (symbol->s_type) {
	case UDEC:
		error("undeclared variable %s", symbol->s_name);
		break;		
	case PARM:
		error("unexpected parameter %s", symbol->s_name);
		break;		
	case FUNC:
	case UFUNC:
		error("function %s used as variable", 
			symbol->s_name);
	case VAR:
		return;
	default:
		bug("chk_var");
	}
	symbol->s_type = VAR;
	symbol->s_blknum = blknum;
}

ここでは、たった一つのうっかり定義し忘れた変数または引数が、なだれのようなエラー・メ ッセージを引き起こさないようにしている。すなわち、そのような変数または引数があった時 は、それに関する警告を一度だけ行ない、現在のフロックに定義してしまう。このようにして、 それ以降の警告を避けることができる。これが、記号テーブル上で現在の入れ子レベルにおけ るループ・トラバースにおいて、なぜ現在のブロック番号よりも大きいブロック番号に行き当 ることがあるかということを説明している。すなわち、上のような対処の結果である。

このテストは、関数呼出しにおける関数名としてのIdentifierの使われ方を調べる。また、前 に作った関数。chk_parm()を用いて、引数の数もチェックする。ただし、今回は引数の個数を自 分で数えなければならない。

binary
	: Identifier '('
		{ chk_func($1); }
	  optional_argument_list rp
		{ chk_parm($1, $4); }

optional_argument_list
	: /* null */
		{ $$ = 0; /* # of actual arguments */ }
	| argument_list
		/* $$ = $1 = # of actual arguments */

argument_list
	: binary
		{ $$ = 1; }
	| argument_list ',' binary
		{ ++ $$;
		  yyerrok;
		}
	| error
		{ $$ = 0; }
	| argument_list error
	| argument_list ',' error

最後の記号テーブル・ユーティリティ。chk_func()は次のようなものである。

chk_func(symbol)
	register struct symtab * symbol;
{
	switch (symbol->s_type) {
	case UDEC:
		break;		
	case PARM:
		error("unexpected parameter %s", symbol->s_name);
		symbol->s_pnum = NOT_SET;
		return;		
	case VAR:
		error("variable %s used as function", 
			symbol->s_name);
		symbol->s_pnum = NOT_SET;		
	case UFUNC:
	case FUNC:
		return;
	default:
		bug("chk_func");
	}
	s_move(symbol);
	symbol->s_type = UFUNC;
	symbol->s_blknum = 1;
}

これが呼び出された時に、関数名があるべきところに新しい名前があると、それは暗黙的に関 数名として定義される。この場合、記号テーブルの中でそのエントリを再配置しなければなら ず、s_move()を用いて行なう一さらに、宣言されていない、広域的に入れ子になった関数とし てマークしておかなければならない。

以前に入力エラーをしていなければ、引数はない。もし一つでもあれば、以降の。chk_parm() の呼出しにおいてメッセージを出さないようにできる。すなわちここでは、この関数らしきも のの引数の数がNOT_SETであるようなふりをすることにする。間違えて関数として使われ ている変数もまた、同じように扱える。

これで、記号テーブル処理ルーチンの説明を終えることにするが、エラー・メッセージや警 告メッセージを出力する、次のような2、3のルーチンがあるという仮定をしている。

これらのルーチンは、ライブラリ関数printfOとちょうど同じように、一つの書式と・表示され るいくつかの値を伴って呼び出される。これらのルーチンは付録のA・3節にある。

次のような、たくさんのエラーを故意に含ませたプログラムを考えてみよう。

/*
 *	symtab demonstration, including errors
 */
 
main(a,b) int a,b;
{	a=b;
	{a;b;}
	if (a==b) {a;b;}
	if (a==b+1) a; else b;
	while (a==b) {a; break;}
	return
}
int f() { int x; int y; return x+y;}
f(a,b)			/* 14: duplicate function definition */
	int a;		/* undeclared parm b (not an error) */
{	int b,c;	/* 16: symbol b duplicates parm b */
	int c,d;	/* 17: duplicate symbol c */
	e=b;		/* 18: undeclared e */
	f=c+d;		/* 19: use func for var */
	a(b);		/* 20: use var for func */
	g();		/* 21: undefined function g */
}
h(a,a)			/* 23: duplicate parameter */
	int f;		/* 24: not a parameter */
	int a;
	int a;		/* 26: duplicate parameter */
{ }

このプログラムの構文および意味解析の結果は、次のようなメッセージになる。（ただし、 TRACEが定義されているものとする。）

line 12 near "}": Popping b: variable, depth 2, offset 0
line 12 near "}": Popping a: variable, depth 2, offset 0
line 13 near "}": Popping y: variable, depth 3, offset 0
line 13 near "}": Popping x: variable, depth 3, offset 0
[error 1] line 14 near "(": duplicate function definition f
[warning] line 16 near "{": function f should have 0 arguments(s)
[error 2] line 16 near "b": duplicate name b
[error 3] line 17 near "c": duplicate name c
[error 4] line 18 near ";": undeclared variable e
[error 5] line 19 near ";": function f used as variable
[error 6] line 20 near "(": variable a used as function
line 22 near "}": Popping e: variable, depth 3, offset 0
line 22 near "}": Popping d: variable, depth 3, offset 0
line 22 near "}": Popping c: variable, depth 3, offset 0
line 22 near "}": Popping c: variable, depth 3, offset 0
line 22 near "}": Popping b: variable, depth 3, offset 0
line 22 near "}": Popping b: variable, depth 2, offset 0
line 22 near "}": Popping a: variable, depth 2, offset 0
[error 7] line 23 near "a": duplicate parameter a
[error 8] line 24 near "f": f is not a parameter
[error 9] line 26 near "a": parameter a declared twice
line 27 near "}": Popping f: variable, depth 2, offset 0
line 27 near "}": Popping a: variable, depth 2, offset 0
line 27 Popping h: function, depth 1, offset 0
line 27 Popping f: function, depth 1, offset 0
line 27 Popping main: function, depth 1, offset 0
line 27 Popping g: undefined function, depth 1, offset 0
[error 10] line 27: undefined function g
↑

値スタックの型付け †

記号テーブルの機能と、意味チェックをインプリメントするために、値スタックを頻繁に使 ってきた、たとえば、終端記号Identifierに関して、記号テーブルへのポインタを字句解析部か らサーバへと渡す。また、終端記号Constantについては、動的に確保した文字列領域へのポイ ンタを渡す。すなわち、parameter_listを記号テープルヘのポインタを用いてチェーンにし、 同様に値スタック上にあるargument_listの中の式の数を数える。まずいことに、このような使 い方をすると、値スタックを型のunionを使って定義しなければならない。ここでは、int型を 用いて数えるが、記号テーブルに対しては、ポインタ・データ型を用いる。C言語ではポイン タは任意の型にキャストできるので、文字列や記号テーブルをポインタを用いて示すのに、異 なるデータ型定義を行なうのはうまい方法である。

unionにしても、値スタックは3.6節で述べたような型付けが行なわれる。しかしながら、 いったんアクションの中で$iを用いてスタック要素を参照してしまえば、それぞれの場合につ いてunionのどの要素が参照されるべきかをyaccに知らせることができる。これを別の方法 で行なうには、構文的にmionの要素として表現されるデータ型を、$iや$$を用いてyaccか ら参照するすべての記号に対応付けなければならない。もちろんこれには、現在のyaccの構文 記述規則を拡張する必要がある。

ここでは、すべてのアクションを構成するため、独立した編集パスにおいて文法に「型付け を行なう」ことにする。このパスでは、値スタック上で参照されるすべての終端記号および非 終端記号を覚えておき、対応する値スタックの要素に対してデータ型を決めなければならない。 実際に値を渡すために、デフォルト・アクション、

{ $$ = $1; }

に頼るのであれば、それが明示的に指定されていなくても、関連する記号について考えなけれ ばならない。(これが、yaccの仕様記述のデフォルト・アクションに頼るという点を述べる一 つの理由である。)

型を付ける記号と、すべてのデータ型が認識されれば、yaccの仕様記述を変更することがで きる。ここでは、このような変更を、sampleCの仕様を具体的な例として述べることにする。

まず、値スタック要素の型を決めなければならない。これは、Cのスタイルで、先頭に%を 付けたunion宣言を用いたyacc仕様記述の最初の部分で行なわれる。 (( 他にもデータ型を定義する方法があるが、この方法がyaccの仕様記述でも視覚的であり、また 結果として得られるunion宣言が、yylvalのextern宣言同様、自動的にy.tab.hファイルに いれられるので便利である。 )) ここでは、値スタック は、記号テーブルヘのポインタになり、文字列へのポインタにもなり、また数を数えるために 整数値になることもできる。定義は次のようである。

%union {
	struct symtab * y_sym;	/* Identifier */
	char * y_str;		/* Constant */
	int y_num;		/* count */
	}

次に、軸解析中に値をyylvalに割り当てられる終端記号に対して型を付けなければならな い。文法的には、これは、%tokenと終端名のリストの間に鍵カッコでくくってunionの構成 要素を書くことにより表わされ、これで型付けができる。ここでは、IdentifierとConstant は、スタック上に対応する値を持っている。

%token	<y_sym> Identifier
%token	<y_str> Constant

s_lookup()ルーチンが値をyylvalに割り当てる。この割当てにはunionの構成要素を用いる が、5.3節で暗黙のうちに行なった。

最後になったが・$iまたは$$が参照するすべての非終端記号に対して型を付けなければな らない。これは%type定義で行なうが、終端記号に対する%tokenのそれとよく似ている。ま た、数を数えるためにはargument」istと。ptiona1_argument_listに、引数チェーンのヘッダを 渡すためにはparameter_listと。ptional_parameter」istに、それぞれ型を付けなければなら ない。

%type	<y_sym> optional_parameter_list, parameter_list
%type	<y_num> optional_argument_list, argument_list

%unionや%type、それに<>といった構文が使われると、yaccは値スタックヘの参照がす べて正しく型付けされているかどうかを厳しくチェックすることを念頭に置かなければならな い。何を省略しても、yaccは直ちに仕様上の違反を犯した行で回復不能エラーが起こったこと を示して停止してしまう。

特性のない終端記号(3.7節を参照)に対して特に必要な、安定した型付け機能についてはま だ触れていない。これについては、6.2節で扱うことにする。

↑

問題 †

  1. コンパイラが、すべてのセマンティックス・エラー・メッセージを出すような、故意の 誤りを含んでいるsamp1eCのテスト・プログラムを書け。
  2. sampleCの記号の記憶方式を、ハッシュを使って名前検索をスピードアップするように 変えてみよ。そして、たとえばC言語のプロファイル・オプションを使うなどして、確か に効率が良くなっているかどうかを示せ。
  3. samp1eCにブロック記述スタックを追加し、これがyaccの値スタックの一部として保 守されるようにせよ。これを行なうため、値スタックの型付けに対してどのような変更が 必要となるか。ここでまた、効率がどう変わったかを計れ。
  4. リンクを行なうローダを使う場合、不要となる記号テーブル管理部を削除せよ。どのよ うにして(また、いつ)情報をリンカに渡すかを決めよ。
  5. 電卓を、簡単な文字列処理ができるように拡張せよ。演算子十を加算および文字列の結 合を表わすために用いること。結果として起こる問題は、文法上のこととして処理できる か、または別の意味処理ルーチンによらなければならないのか、文法としてNumberや StringではなくConstantを認識しなければならないのか、を考えよ。
↑

コメント †

この記事は、

選択肢 投票
おもしろかった 1  
そうでもない 0  
わかりずらい 0  

皆様のご意見、ご希望をお待ちしております。


(Input image string)
トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
SmartDoc