kaiser

インタプリタ作成

字句解析
　文字列をトークン（要素）に分解
構文解析
　トークンをツリー構造に変換
意味解析
　ツリー構造から意味解析を行う
インタプリタ
　上記構造から動作用に変換し中間コードを生成
スタックマシン
　インタープリタから生成された中間コードを実行

字句解析

・式の評価

数と演算子を分解する
数は続く数値であれば数値をしてスタックに保持
演算子の場合は演算子をしてスタックに保持
また因子”()など”の優先順位を逆ポーランド記法化にする

・スタックもしくは2分木

まずは字句解析を行う。テキストから各トークンを切り出す。最初は計算式を解析する。文を1文字づつ読み込み以下に分解する。

・整数
・演算子 式と項のどちらかを構成するもの
・記号（）での囲まれたものを因子とする
・項（term）（掛け算割り算を含む一つの項目、因子一つも含む）
・式（expr） 項または因子（整数）を足し算割り算をする部分
・因子（factor）数値もしくはカッコを含む式と項もしくは演算子

EBNF

書き方意味
A*Aの0回以上の繰り返し
A?Aまたはε
A|BAまたはB
(…)グループ化

1.字句の定義(lexer)
(a)数字::=”0″|”1″|”2″|”3″|”4″|”5″|”6″|”7″|”8″|”9″
(b)英字::=”a”|”b”|”c”|”d”|”e”|”f”|”g”|”h”|”i”|”j”|”k”|”l”|”m”|”n”|”o”|”p”|”q”|”r”|”s”|”t”|”u”|”v”|”w”|”x”|”y”|”z”|
“A”|”B”|”C”|”D”|”E”|”F”|”G”|”H”|”I”|”J”|”K”|”L”|”M”| “N”|”O”|”P”|”Q”|”R”|”S”|”T”|”U”|”V”|”W”|”X”|”Y”|”Z”|””
(c)普通文字::=”\”と”’”以外の文字
(d)キーワード::=”char”|”else”|”if”|”int”|”return”| “while”
(e)ID::=英字(英字|数字)* (ただしキーワード以外のもの)
(f)INT::=数字(数字)*
(g)CHAR::=”’”普通文字”’”|”’\n’”|”’\’’”|”’\t’”|”’\’”
(h)演算子::=”+”| “-“|”*”| “/”|”%”| “&”| “=”|”==”| “!=”| “>”|”>=”|”<“|”<=”
(i)記号::=”,”| “;”|”(“|”)”|”{“| “}”|”[“| “]”

2.構文の定義(perse)
(a)プログラム::=(関数宣言|変数宣言”;”)*
(b)変数宣言::=型”“ ID(“[“INT”]”)*
(c)関数宣言::=型”“ ID”(“(ε|変数宣言(“,”変数宣言)* )”)”関数本体
(d)関数本体:: =”{“(変数宣言”;”)文 “}”
(e)型::=”int”|”char”
(f)文::=”;”|”{“文* “}”|if文| while文|return文|関数呼出し”;”|代入文
(g)if文::=”if””(“式”)”文(ε|”else”文)
(h)while文::=”while””(“式”)”文
(i)return文::=”return”式”;”
(j)代入文::=左辺式”=”式”;”
(k)左辺式::=”“変数名( “[“式”]”)*
(l)変数名::=ID
(m)式::=式２((“<“|”>”|”<=”|”>=”|”==”|”!=”)式２)*
(o)式３::=式４( (““|”/”|”%”)式４)
(p)式４::=”“式５
(q)式５::=INT| CHAR|”(“式”)”|関数呼出し|変数参照
(r)変数参照::=(ε|”&”)変数名( “[“式”]”)
(s)関数呼出し::=関数名”(“引数リスト”)”
(t)関数名::=ID
(u)引数リスト::=ε|式(“,”式)*

変数とスタック

・ローカル変数はスタックに置く
・関数呼び出しの際RSP(スタックポインタ)の指し示すアドレスにリターンアドレスを入れる
・スタックポインタを使い相対アドレスを使うことでローカル変数をアクセスする。
・インタープリタではスタックポインタは変更されるためそれに変わるベースポインタ(RBP)を使用する。
・関数から関数を呼び出すと呼び出された関数のリターンアドレスをPUSHし更に呼び出し時のベースポインタの値もPUSHする。
・関数の先頭に出力する提携をプロローグ(prologue)と言う。コンパイラが末尾に出力する定形をエピローグ(epilogue)という

プロローグ

push rbp
mov rbp, rsp
sub rsp, 16(16バイトの変数確保。変数サイズによって変わる)

エピローグ

mov rsp, rbp
pop rbp
ret

プロローグを呼び出したスタック

呼び出した元の関数アドレス
呼び出した元のベースポンタ　←　ベースポインタ
変数
呼び出す関数のアドレス　←　スタックポインタ

ベースポインタをPUSHしたスタック

呼び出した元の関数アドレス
呼び出した元のベースポンタ　←　ベースポインタ
変数
呼び出す関数のアドレス　
呼び出した際のベースポインタの値　←　スタックポインタ

mov rbp, rspを実行した際のスタック

呼び出した元の関数アドレス
呼び出した元のベースポンタ
変数
呼び出す関数のアドレス　
呼び出した際のベースポインタの値　←　スタックポインタ＆ベースポインタ

AST(抽象構文木abstract syntax tree)

式の評価を抽象構文木（Nodeツリー）を使って構文解析を行う。

kaiser