JPS61272831A - ハツシユテ−ブルサイズ適合化方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は、コンパイラの名標におけるハツシュテーブル
サイズの適合化方式に関する。

（従来の技術） 従来、コンパイラにおいてハツシュテーブルは、固定的
なサイズによって確保されていた。

したがって、−走行数以上の規模のソースプログラムの
コンパイルではソースプログラムに書かれた名標に対し
てシノニムアイテムが増加する。

ここで、シノニムアイテムは名標のノ％ツシュ値が他の
名標と同じ値をもつときに、名標を一意的に検索できる
ように作成されるアイテムである。

第５図は従来方式によるハツシュテーブルサイズ適合化
方式において、最大ハツシュ値を５に固定していた場合
にソースプログラムＹのコンパイルで宣言名標Ｆ、Ｇ、
Ｈ，Ｉ、Ｊ、に、Ｌの最小７個のシノニムアイテムが発
生するもようを示す説明図である。すなわち、第５図に
おいてはシノニムアイテムが増加するため、参照名標と
一致する宣言名標を照合する処理量が増加してしまう。

（発明が解決しようとする問題点） 上述した従来のハツシュテーブルサイズ適合化方式は、
上記のように一定行数以上の規模のノースプログラムの
コンパイルではソースプログラムに書かれた名標に対し
てシノニムアイテムが増加するため、参照名標と宣言名
標との間での照合の効率が低下するという欠点がある。

本発明の目的は、ソースプログラムの行数が多くなると
名標の個数も増加するということに着目してソースプロ
グラムを読込み、トークン列に変換する手段でソースプ
ログラム行数をカウントし、ソースプログラムの全行を
読込んだ後、合計のソースプログラム行数を保存してお
き、保存されている合計ノースプログラム行数の値から
ハツシュ値のばらつきを考慮したハツシュテーブルサイ
ズを決定することにより上記欠点を除去し、シノニムア
イテムの増加を防ぐことができるように構成したハツシ
ュテーブルサイズ適合化方式を提供することにある。

（問題点を解決すべき手段） 本発明によるハツシュテーブルサイズ適合化方式は、次
の第１〜第５の手段によシ構成したものである。

第１の手段は、ソースプログラムを読込んでトークン列
に変換するためのものであシ、第２の手段はソースプロ
グラム行数をカウントするためのものであシ、第３の手
段はトークン列の構文を解析して参照名標と宣言名標と
を識別するためのものであり、第４の手段は宣言名標を
ハツシュテーブルへ登録するためのものであシ、第５の
手段は参照名標と宣言名標とをハツシュテーブルを介し
て照合するためのものである。

（実施例） 次に、本発明について図面を参照して説明する。

第１図は、参照名標と宣言名標とを照合する過程を示す
説明図である。第１図において、１はソースプログラム
読込み／トークン列変換手段、およびソース行数カウン
ト手段、２は構文解析手段、３は宣言手段、４は参照名
標と宣言名標とを照合する手段、６はトークン列、６は
宣言名標、１は参照名標、８は合計ソースプログラム行
数、９はハツシュテーブル、１０はシノニムアイテム、
１１はソースプログラムである。

第１図において、まずソースプログラム読込み／トーク
ン列変換手段ならびにソース行数カウント手段１で合計
ソースプログラム行数８を求める。

さらに、構文解析手段２で宣言名標６と参照名標７とを
識別し、宣言手段３で合計ソースプログラム行数８から
ハツシュテーブル９のサイズを求めてハツシュテーブル
９を確保し、宣言名標６をハツシュテーブル９へ登録ス
る。ハツシュテーブル９の内部のアイテムが既に登録済
みであれば、このアイテムとチェインするシノニムアイ
テム１０として登録する。次に、参照名標７と宣言名標
６との照合では参照名標７のハツシュ値を計算し、ハツ
シュテーブル９の該当ハツシュ値に対応するアイテムを
参照し、参照名標１と一致する宣言名標６であるか否か
を調べる。上記両名標が一致すれば、求める宣言名標６
である。不一致ならば該当アイテムとチェインするシノ
ニムアイテム１０について調べる。

第２図は、宣言手段３で合計ソースプログラム行数８か
ら最大ハツシュ値を求め、次に最大ハツシュ値からハツ
シュテーブル９のサイズを求めて、ハツシュテーブル９
のサイズでハツシュテーブル領域を確保する動作を示す
説明図である。最大ノ・ツシュ値の算出では、仮にプロ
グラムの内部に定義される宣言名標６を行数に対してほ
ぼ７割と仮定する。

ここで、Ａ、Ｂ、・・・Ｌを宣言名標６とし、宣言名標
Ａ−Ｆの６個が書かれたｎ行のソースプログラムＸと宣
言名標Ａ−Ｌの１２個が誉かれたｎ＋ｍ行のソースプロ
グラムＹとを仮定する。

第３図および第４図では、仮定したソースプログラムＸ
とソースプログラムＹとをコンパイルしたとき、宣言名
標６がハツシュテーブル９に登録された状態を示す説明
図である。

第３図は、ソースプログラムＸのコンパイルにおいて合
計ソースプログラム行数８（ｎ）から最大ハツシュ［−
６Ｋ設定してハツシュテーブル９を確保し、宣言名標６
を）−ツシュテーブル９へ登録した場合に宣言名標６（
Ｆ）の最小１個のシノニムアイテム１０が発生するもよ
うを示す説明図である。

第４図は、ソースプログラムＹのコンノζイルにおいて
合計ノースプログラム行数ｇ（ｎ＋ｍ）から最大ハツシ
ュ値を１０に設定してハツシュテーブル９を確保し、宣
言名標６をハツシュテーブル９へ登録した場合に宣言名
標６（Ｋ、Ｌ）の最小２個のシノニムアイテム１０が発
生するもようを示す説明図である。

（発明の効果） 以上説明したように本発明は、ソースプログラム行数を
もとにしてハツシュ値のばらつきを考慮したハツシュテ
ーブルサイズを設定することＫよシ、シノニムアイテム
の増加を防ぐことができ、ソースプログラム行数が一定
量以上になっても参照名標と宣言名標との照合を効率よ
く行うことができるという効果がある。

【図面の簡単な説明】

第１図は、本発明によるハツシュテーブルサイズ適合化
方式を実現する一実施例を示すブロック図である。 第２図は、本発明におけるハツシュテーブル領域の確保
動作を示す説明図である。 第３図は、本発明におけるソースプログラムＸのハツシ
ュテーブルとシノニムアイテムトラ示す説明図である。 第４図は、本発明におけるソースプログラムＹのハツシ
ュテーブルとシノニムアイテムとを示す説明図である。 第５図は、従来技術によるソースプログラムＹノハツシ
ュテーブルとシノニムアイテムとを示す説明図である。 １・・・ノースプログラム読込み／トークン列変換手段
およびソース行数カウント手 段 ２・・・構文解析手段 ３・・・宣言手段 ４・・・参照名標と宣言名標とを照合する手段５・ｅ・
トークン列 ６・・・宣言名標 ７・・・参照名標 ８・・・合計ソースプログラム行数 ９・・・ハツシュテーブル １０・・シノニムアイテム １１・・ノースプログラム

Claims (1)

【特許請求の範囲】
1. ソースプログラムを読込んでトークン列に変換するため
   の第１の手段と、ソースプログラム行数をカウントする
   ための第２の手段と、前記トークン列の構文を解析して
   参照名標と宣言名標とを識別するための第３の手段と、
   前記宣言名標をハッシュテーブルへ登録するための第４
   の手段と、前記参照名標と前記宣言名標とをハッシュテ
   ーブルを介して照合するための第５の手段とを具備し、
   前記ソースプログラム行数にもとづいてハッシュテーブ
   ルサイズを最適に決定することができるように構成した
   ことを特徴とするハッシュテーブルサイズ適合化方式。