PowerPoint プレゼンテーション

【事例演習5】字句解析
解説
“ハッシュを用いた字句解析の方法”
● 字句解析アルゴリズムの応用分野
＝＞
【例
１int
】
コンパイラ，インタプリタ
int1,j,k,l,i1,j1,i2,j2,count[10];
float
X1,Y1,floar,theta=13.0,alpha,beta,pai=3.141592,const=1.2;
int
for1=20,whil=0.0;
for
( int1 = 1;
int1
<
for1 ;
int1 ++)
{
whil1
+=
X1
*
sin
(
theta
*
pai
/
180.0 )
+
const
)；
:
：
}
・名称は変数名なのか組み込み関数名なのか，
・変数名はすでに定義されたものか，
・型は何であるか(int,float,char）等を高速に決定してやる必要がある
【例２】
int
IX = 190,IY = 360;
float
a , b , c
void
func( int
;
p, float q)
{
int
a
b
a , c
=
IX
=
a
*
+
c
1 ;
:
}
=
12;
;
どのレベルで定義されたかを高速に
決定してやる必要がある
なぜなら名前は同じでも，型や記憶個所は
通常異なる
● 字句解析で検索すべきデータ
調べるべき対象文字列が格納された文字配列
syllable_buff
Ｘ１ \0
順番に比較してゆく線形探索
だと，変数が多くなるにつれ効
率が悪くなる．
すでに定義された変数に関する情報が
格納されたテーブル
変数名
A
B
C
X1
Y1
A
B
変数の型
float
float
float
int
int
int
int
１．高速に変数に関する情報を検索できるようするには
データ構造をどのようにすればよいか
２．その検索手順はどのようにすべきか
定義レベル
0
0
0
1
1
1
1
● 高速化を実現するデータ構造
調べるべき対象文字列
syllable_buff
ハッシュテーブル
Ｘ１ \0
ハッシュ（ちらし）関数
< hash_tbl >
変数情報を格納しておくスタック
hash_addr
< stack_head >
変数名を格納しておく文字列配列
tos_head
格納された変数情報の配
列stack_head上での位置
６
float
５
char
４
char*
３
int *
２
int[ ]
１
< symbol_tbl >
X 1 \0
float
０
同じhash_addrをもつ変数を
結ぶﾘﾝｸ（hash_link）
変数名を格納した文字列配列
symbol_tbl上での位置（symbol_address）
変数がもつ型（var_type）
変数が定義されたレベル
この変数情報を指すﾃﾞｰﾀが格納されている
配列hash_tblの位置（hash_address）
● ハッシュ関数
（１５５ページ参照）
文字列ポインタsyll_buff
< hash_tbl >
調べるべき対象文字列
syllable_buff
hash_addr
0
1
2
3
4
Ｘ１ \0
=
hash % HASH_SIZE
HASH_SIZE
syllable_buff を
ビット列で表し
たもの
この1バイトを8ビットで表される数値として解釈するには
(int) *syll_buff
●NULL文字が来るまでポインタを進めながら繰返し合計値hashを求める
hash += (int) *syll_buff；
syll_buff ++;
【課題】
文字列としての数字を,1ワードの数値に変換する
文字列ﾎﾟｲﾝﾀ pscan
文字列scan_buff
１２４
．５６
(注） 1文字の数字を数値と解釈するには
(int)(*pscan – ‘0’)
float型変数 syll_value
指数部の符号
仮数部の符号
仮数部
指数部
内部表現形式
( 0.12456*102 )
数字内部ｺｰﾄﾞ(16進）
０
30
１
31
２
32
３
33
:

Download Report