【事例演習5】 　字句解析 　　　　解　説 　“ハッシュを用いた字句解析の方法”.

Presentation on theme: "【事例演習5】 　字句解析 　　　　解　説 　“ハッシュを用いた字句解析の方法”."— Presentation transcript:

1 【事例演習5】 　字句解析 　　　　解　説 　“ハッシュを用いた字句解析の方法”

2 ● 字句解析アルゴリズムの応用分野 ＝＞ コンパイラ，インタプリタ 【例１ 】
● 字句解析アルゴリズムの応用分野 　　　　　　＝＞　　コンパイラ，インタプリタ 【例１ 】 int int1,j,k,l,i1,j1,i2,j2,count[10]; float X1,Y1,floar,theta=13.0,alpha,beta,pai= ,const=1.2; int for1=20,whil=0.0; for ( int1 = 1; int1 < for1 ; int1 ++) { whil1 += X1 * sin ( theta * pai / ) + const )； : ： } ・名称は変数名なのか組み込み関数名なのか， ・変数名はすでに定義されたものか， ・型は何であるか(int,float,char）等を高速に決定してやる必要がある

3 【例２ 】 int IX = 190,IY = 360; float a , b , c ;
void func( int p, float q) { int a , c = 12; a = IX * c ; b = a ; : } どのレベルで定義されたかを高速に 決定してやる必要がある 　なぜなら名前は同じでも，型や記憶個所は 通常異なる

4 ● 字句解析で検索すべきデータ １．高速に変数に関する情報を検索できるようするには データ構造をどのようにすればよいか
● 字句解析で検索すべきデータ すでに定義された変数に関する情報が 　　　格納されたテーブル 調べるべき対象文字列が格納された文字配列 syllable_buff 　変数名　　　　　　　　変数の型　　　　　定義レベル A float B float C float X int Y int A int B int Ｘ １ \0 順番に比較してゆく線形探索だと，変数が多くなるにつれ効率が悪くなる． １．高速に変数に関する情報を検索できるようするには 　　データ構造をどのようにすればよいか ２．その検索手順はどのようにすべきか

5 ● 高速化を実現するデータ構造 syllable_buff < hash_tbl > hash_addr
● 高速化を実現するデータ構造 Ｘ １ \0 調べるべき対象文字列 syllable_buff ハッシュ（ちらし）関数 ハッシュテーブル < hash_tbl > 変数情報を格納しておくスタック hash_addr 　　　　　 float char char* int * int[ ] 　　　　　　　　float < stack_head > 変数名を格納しておく文字列配列 tos_head < symbol_tbl > ６ ５ ４ ３ ２ １ ０ X 1 \0 格納された変数情報の配列stack_head上での位置 変数名を格納した文字列配列 symbol_tbl上での位置（symbol_address） 同じhash_addrをもつ変数を 結ぶﾘﾝｸ（hash_link） 変数がもつ型（var_type） 変数が定義されたレベル この変数情報を指すﾃﾞｰﾀが格納されている 配列hash_tblの位置（hash_address）

6 ● ハッシュ関数 （１５５ページ参照） < hash_tbl > syllable_buff hash_addr =
●　ハッシュ関数　　（１５５ページ参照） 文字列ポインタsyll_buff < hash_tbl > 調べるべき対象文字列 0　　1　　2　　3　 4 syllable_buff Ｘ １ \0 hash_addr　= hash % HASH_SIZE syllable_buffをビット列で表したもの HASH_SIZE この1バイトを8ビットで表される数値として解釈するには (int) *syll_buff　 ●NULL文字が来るまでポインタを進めながら繰返し合計値hashを求める 　　hash += (int) *syll_buff； syll_buff ++;　

7 【課題】 文字列としての数字を,1ワードの数値に変換する ( 0.12456*102 ) 文字列ﾎﾟｲﾝﾀ pscan
文字列scan_buff １ ２ ４ ．５ ６ (注）　1文字の数字を数値と解釈するには 　　　　(int)(*pscan – ‘0’) float型変数　syll_value 数字　内部ｺｰﾄﾞ(16進） 指数部の符号 ０　　　 30　　 １ ２ 33 : 仮数部の符号 仮数部 指数部 　内部表現形式 ( *102 )