PIC

MIPS用BASICコンパイラーを制作中

2014年7月28日

ケンケンさんのPIC32MX用SDカードブートローダー(+カラーNTSC出力)用に、整数型BASICコンパイラーを作成することにした。仕様は、以前にMZ-80用に作成したKM-BASICと同じに。必要最小限の仕様。SDカードにBASICのソースコードをテキストファイルで置いておけば、それをコンパイルして即実行するような物を考えている。

9割以上出来上がっているのだが、最後に、RAM上のプログラムの実行権限を得るところで手間取っていて、公開は次の週末以降になる見込み。ここでは、基本的な構造に関する覚え書きなど、記しておく。

演算アルゴリズム
MZ-80用のKM-BASICでは、演算子に優先順位を付けなかった。これを実装すると、コンパイラー自身のコードサイズが大きくなってしまうので、メモリー容量の少ないモデルでは割愛した。今回は、広大(と言っていい)なフラッシュメモリー領域があるので、少々複雑な事をする実装が可能なので、演算の優先順位付きでの実行は、やはり欲しいところ。私が大学生の頃、NECのPC-9801用に整数(16 bits)型BASICコンパイラーを作成したことがあって、その時も実装したのだが、どうやったかどうも思い出せない。もう一度考え直して出来たのが、次のアルゴリズム。ここにメモしておけば、将来同じ事をするときに、無駄に時間を費やすことがないだろう。

2014-07-28-calc.png

演算順位決定ルーチンは、一つの関数(再帰呼び出しされる)で実装されている。実際のコードは、以下の通り。
char* get_value_sub(int pr){
	char* err;
	enum operator op;
	int prevpos;
	// Get a value in $v0.
	err=get_simple_value();
	if (err) return err;
	while(1){
		// Get the operator in op. If not valid operator, simply return without error.
		prevpos=g_srcpos;
		err=get_operator();
		if (err) return 0;
		op=g_last_op;
		// Compair current and previous operators.
		// If the previous operator has higher priolity, return.
		if (pr>=priority(op)) {
			g_srcpos=prevpos;
			return 0;
		}
		// Store $v0 in stack
		g_sdepth+=4;
		if (g_maxsdepth<g_sdepth) g_maxsdepth=g_sdepth;
		check_obj_space(1);
		g_object[g_objpos++]=0xAFA20000|g_sdepth; // sw v0,xx(sp)
		// Get next value.
		err=get_value_sub(priority(op));
		if (err) return err;
		// Get value from stack to $v1.
		check_obj_space(1);
		g_object[g_objpos++]=0x8FA30000|g_sdepth; // lw v1,xx(sp)
		g_sdepth-=4;
		// Calculation. Result will be in $v0.
		err=calculation(op);
		if (err) return err;
	}
}

この基本部分が出来てしまえば、あとは演算子の実装を、しらみつぶしに行なっていくだけ。

文字列の処理
文字列についても、MZ-80用の物よりも少し複雑な処理が行えるようにした。MZ-80用の物では、文字列の長さを80文字までに限定し、かつ、文字列の連結はLETステートメントのみで行える仕様であった。これを、いつでもどこでも文字列の連結が行え、長さの上限が無いようにした。結果として、一時領域の動的な確保とガベージコレクションが必要になった。

一時領域の確保をフレキシブルに行なうため、malloc()を使わず、一から実装することに。色々と試行錯誤した結果、最終的には、いつガベージコレクションを行なうかのタイミングだけで制御するコードになった。

一時的に作成された文字列は、それが変数に代入されるかPRINT文などで使用されるか、いずれかが実行されるまでは有効に保持しておかなければならない。逆に、これらが行なわれた後は、すべて破棄することが出来る。ただし、余り頻繁にガベージコレクションを行なっていては、実行速度の低下を招いてしまう。

そこで、ソースコードでの一行に一度、一時領域の確保をする直前に、それ以前の一時領域をすべて破棄する仕様にした。一時領域確保の際、その行での初めての実行かどうかの判断は、$s6レジスターの値をチェックすることで行なう。$s6レジスターの値が正の場合、初めての実行と見なし、すべての一時領域を破棄した後に、$s6レジスターの値を負にする($s6=0-$s6)。$s6レジスターは、行番号やジャンプ用ラベルの管理にも使用されているので、それについては下記を参照。

FOR~NEXT文の実装
FOR~NEXTには、スタックを用いている。FOR文のところで、現在の実行アドレスをスタックに待避し、NEXTのところでスタックに待避されたアドレスにジャンプするような実装。この実装のため、「~」の部分は、最低一度は実行される仕様である。また、下記で述べるGOSUBにもスタックが用いられているので、FOR~NEXTループ中ではRETURN命令は使用できない。

GOTO/GOSUB/RETURNの実装
GOTOは、純粋にMIPSのジャンプ命令に置換される。ただし、ジャンプ先としては行番号以外にラベルを指定することが出来る。GOSUBの場合は、現在の実行アドレスをスタックに待避した後にジャンプ、RETURNは、待避された実行アドレスへのジャンプである。ON-GOTOは実装していないが、その代りに、"GOTO 100+A"の様に、ジャンプ先をダイナミックに指定することが出来る。

GOTO/GOSUBのジャンプ先が静的な場合、コンパイル後のリンクの際に、ジャンプ先のアドレス部分が書き込まれる。それぞれの行番号とラベルが、どのアドレスに相当するかを調べる方法として、オブジェクト中にMIPSの$s6レジスターに値を代入する命令を挿入するようにした。このコードを走査することで、ジャンプ先を調べることが出来る。"GOTO 100+A"の様に、ジャンプ先をダイナミックに指定している場合も、同じメカニズムを利用している。また、オブジェクトの実行中に、「ゼロで割る」 「一時領域が足りない」などの例外が起きた場合に、$s6レジスターの値を調べれば、どの行で例外が起きたかを調べることが出来る。

追記:2014/8/03
以下、とりあえず動くようにしたバージョンです。hexファイルを、ケンケンさんのSDカードブートローダーから取り込んで下さい。BASICのソースコードを、hexファイルと同じファイル名で拡張子をtxtにして、保存して下さい。文法は、とりあえずこちらを参照。追加の命令もありますので、改めて公表します。
バージョン0.8.6がここからダウンロードできます。まだ、転載不可のライセンスとします。

コメント

Katsumi (2015年4月13日 11:23:54)

完成バージョン(ver 1.0.5)は、こちらです。
http://www.recfor.net/jeans/skins/media/1/2014-09-30-kmbasic105.zip

Katsumi (2015年4月14日 18:13:05)

ver 1.0.5の紹介記事はこちらです。
http://www.recfor.net/blog/mycom/index.php?itemid=910

cartier glasses (2018年10月16日 13:49:45)

http://www.fitflopsshoes.us.com/ fitflop
http://www.pandora--rings.us.com/ Pandora Rings
http://www.mulberry-handbags.us.com/ mulberry
http://www.adidas-yeezy-shoes.us.com/ Yeezy Boost 350 V2
http://www.northface-jacket.us.com/ north face jacket
http://www.redbottoms-louboutin.us.com/ christian louboutin
http://www.jordan--11.us.com/ jordan 11
http://www.katespade--outlet.us.com/ kate spade handbags
http://www.nikeairmax-90.us.com/ nike air max 90
http://www.asicss.us.com/ asics outlet
http://www.ultra--boost.us.com/ ultra boost
http://www.burberrys.org.uk/ burberry
http://www.nikeairmax270.org.uk/ air max 270
http://www.adidasyeezys.org.uk/ yeezy
http://www.pandorasjewelry.co.uk/ pandora uk
http://www.air-max-270.us.com/ nike air max 270 men
http://www.hermes--belt.us.com/ hermes belt
http://www.skechers--shoes.us.com/ skechers
http://www.louboutinredbottoms.us.com/ christian louboutin shoes
http://www.ralphlauren--polo.us.com/ ralph lauren
http://www.supremeshirt.us.com/ supreme clothing
http://www.birkenstocksandalssale.us.com/ birkenstock sale
http://www.chrome--hearts.us.com/ chrome hearts necklace
http://www.true--religion.us.com/ true religion jeans for women
http://www.nike--shoes.co.uk/ nike air max 97
http://www.pandorajewelryscharms.us.com/ pandora jewelry official site
http://www.nike-airmax270.us.com/ air max 270
http://www.barbourjackets.co.uk/ barbour
http://www.vapormaxs.us.com/ air vapormax
http://www.monclerjacketmens.us.com/ moncler jacket womens
http://www.fitflop--sandals.us.com/ fitflop shoes
http://www.airmax-2018.us.com/ air max 2018
http://www.under-armour-shoes.us.com/ stephen curry shoes
http://www.nikekdshoes.us.com/ kevin durant shoes
http://www.montblancs.us.com/ mont blanc sale
http://www.pandorauk.us.com/ pandora uk
http://www.barbours.org.uk/ barbour coats
http://www.valentino--shoes.us.com/ valentino heels
http://www.airmax95.co.uk/ nike air max 95
http://www.salomonshoes.co.uk/ salomon shoes
http://www.pandoraearrings.us.com/ pandora earrings
http://www.yeezyboost350shoes.us.com/ adidas yeezy
http://www.northfacejacketoutlets.us.com/ north face jacket
http://www.ray--ban.us.com/ ray ban eyeglasses
http://www.lacosteshirts.us.com/ lacoste shoes
http://www.airjordan11spacejam.us.com/ air jordan
http://www.curry4-shoes.us.com/ curry shoes
http://www.swarovskis.us.com/ swarovski earrings
http://www.kyrie-4.us.com/ kyire 3
http://www.nikelebron15.us.com/ lebron 15
http://www.air-max-95.us.com/ air max 95 black
http://www.salomon-boots.us.com/ salomon
http://www.uggsformen.us.com/ uggs for men
http://www.pandora-jewelrysale.us.com/ pandora bracelet
http://www.burberry-bags.us.com/ burberry
http://www.coach--bags.us.com/ coach purses
http://www.james-hardenshoes.us.com/ james harden shoes
http://www.longchampbackpack.us.com/ longchamp bag
http://www.skechersuk.co.uk/ skechers
http://www.mcms.us.com/ mcm backpack
http://www.nikeairvapormaxflyknit.us.com/ nike air max 90
http://www.adidasyeezy-350.us.com/ yeezy shoes
http://www.michaelkors-handbagss.us.com/ michael kors purse
http://www.moncler--jacket.us.com/ moncler coat
http://www.oakley--sunglassess.us.com/ oakley glasses
http://www.nike--vapormax.us.com/ air vapormax
http://www.skecherss.us.com/ skechers uk
http://www.swarovskisjewelry.us.com/ swarovski jewelry
http://www.uggs-forwomen.us.com/ uggs for women
http://www.ferragamoshoess.us.com/ salvatore
http://www.celines.us.com/ celine purse
http://www.adidas-ultraboost.us.com/ adidas ultra boost
http://www.polo-ralphlauren-outlet.us.com/ polo ralph lauren outlet
http://www.adidasnmdrunnerr1.us.com/ nmd adidas
http://www.adidasnmd-womens.us.com/ adidas nmd
http://www.nike-airmax-2018.us.com/ air max 90
http://www.adidas-yeezyboost350.us.com/ yeezy boost 350 v2
http://www.balenciaga--shoes.us.com/ balenciaga bag
http://www.jordan11spacejams.us.com/ jordan space jams
http://www.jordan11.co.uk/ jordan 11
http://www.moncler-coat.us.com/ moncler
http://www.oakley--glasses.us.com/ oakley prescription sunglasses
http://www.pumarihannafenty.us.com/ rihanna puma shoes
http://www.pandora--jewelrys.us.com/ pandora jewelry
http://www.michael-kors-bags.us.com/ michael kors bags
http://www.nikeairmax-97.us.com/ air max 97
http://www.polo-ralph-lauren.org.uk/ ralph lauren polo shirts
http://www.jordans11shoes.us.com/ jordan 11
http://www.supreme--clothing.us.com/ supreme jacket
http://www.adidas--shoes.co.uk/ adidas shoes
http://www.mcm--bags.us.com/ mcm bags
http://www.nikeairmax97.co.uk/ nike air max
http://www.lebron15-shoes.us.com/ lebron 15
http://www.airmax90shoes.us.com/ nike air max 90
http://www.prada--handbags.us.com/ prada handbags
http://www.katespadepurses.us.com/ kate spade
http://www.cartier-bracelet.us.com/ cartier love ring
http://www.kd10-shoes.us.com/ kd 9
http://www.ugg--slippers.us.com/ ugg
http://www.coachbags-outlet.us.com/ coach bags
http://www.salomon--shoes.us.com/ Salomon Speedcross 3
http://www.christianlouboutinredbottoms.us.com/ christian louboutin
http://www.goyardbag.us.com/ goyard
http://www.new--balance.us.com/ new balance running shoes women
http://www.kevin-durant-shoes.us.com/ kevin durant shoes
http://www.yeezyboost350--v2.us.com/ yeezy boost 350 v2
http://www.balenciagas-sneakers.us.com/ balenciaga shoes
http://www.eccoshoesoutlets.us.com/ ecco mens shoes
http://www.stephen-curry-shoes.us.com/ stephen curry
http://www.ray--bansunglassess.us.com/ ray ban eyeglasses
http://www.yeezyboost350v2.co.uk/ yeezy
http://www.rayban-glasses.us.com/ ray ban sunglasses
http://www.jimmychooheels.us.com/ jimmy choo trainers
http://www.truereligion--jeans.us.com/ true religion
http://www.mbts.us.com/ mbt womens shoes
http://www.birkenstock--sandals.us.com/ birkenstock sale
http://www.nike-huaraches.us.com/ nike huarache
http://www.fitflops-sale.us.com/ fitflop
http://www.prada--bags.us.com/ prada wallet
http://www.rayban--glasses.us.com/ ray ban wayfarer
http://www.adidas-superstarshoes.us.com/ adidas originals superstar
http://www.salomonspeedcross3.us.com/ salomon speedcross 3
http://www.nikeair-max90.co.uk/ nike air max
http://www.uggs--boots.us.com/ ugg slippers
http://www.jordanretro11-shoes.us.com/ jordan 11
http://www.air-max-97.us.com/ air max 97 womens
http://www.fitflop--shoes.us.com/ fitflop sale
http://www.redbottom--shoes.us.com/ louboutin
http://www.hermesbirkin-handbags.us.com/ Hermes Wallets
http://www.chromehearts-jewelry.us.com/ chrome hearts jewelry
http://www.monclers.uk/ moncler sale
http://www.adidasoriginalsnmd.us.com/ adidas originals nmd
http://www.pandora-charmsjewelry.us.com/ pandora
http://www.adidasoriginalsultraboost.us.com/ adidas ultra boost uncaged
http://www.pandorajewelryrings.us.com/ pandora charms
http://www.mulberrys.org.uk/ mulberry
http://www.ed-hardys.us.com/ ed hardy clothing
http://www.goyardbackpack.us.com/ goyard
http://www.air-max-90.us.com/ nike shoes
http://www.adidasnmds.co.uk/ adidas nmd
http://www.nikeairmax-95.us.com/ air max 95 mens
http://www.chromeheartsjewelrys.us.com/ chrome hearts ring
http://www.ralphlaurenspoloshirts.us.com/ ralph lauren shirts
http://www.airmax270.co.uk/ nike air max
http://www.bvlgaris.us.com/ bvlgari
http://www.pandora-jewelrybracelet.us.com/ pandora bracelet
http://www.asics--shoes.us.com/ asics womens shoes
http://www.monclerjacket.org.uk/ moncler jacket womens
http://www.monclerjacketwomens.us.com/ moncler jacket
http://www.huaraches.us.com/ nike air huarache
http://www.pandoras-uk.co.uk/ pandora bracelet
http://www.salvatore-ferragamo.us.com/ ferragamo shoes men
http://www.kyrie-irving-shoes.us.com/ nike kyrie
http://www.nikeair-max.co.uk/ nike shoes
http://www.burberry--scarf.us.com/ burberry
http://www.longchampbag.us.com/ longchamp
http://www.pandoras-jewelrys.us.com/ pandora jewelry
http://www.katespadebags.us.com/ kate spade wallet
てしまうと

コメント送信