提出方法は、こちらを見てください。 課題の提出内容ですが、皆さんがつくってくれた部分のプログラムと、 プログラムの動作原理などの解説をつけて送ってください。 実験のレポートなどと同様のものだと思ってくれてOKです。 あと、難易度に関する感想もお願いします。
期限ですが、 この通りです。 といっても、この期限はきつめに設定してありますので、 皆さんの多くが期限に間に合わないかも知れません。 そういう場合は、ここを見て、 遅れるよ mail を気楽に送ってください。 期限をきつめに設定しているのは、 最初の期限で皆さんの状況をみてヒントを出すつもりだからです。 当然、期限に間に合った人は相応の評価します。 「オリジナリティ」も高いでしょうから。 質問は、mail でも掲示板でも受け付けます。
とある実験で皆さんが PIC 用のアセンブリ言語でプログラムを書いているのを見て、 僕はこんなことは人がやることではない、機械にやらせることだと思いました。 そう、プログラミング言語で書いたプログラムをアセンブリ言語に変換するのは、 コンパイラの仕事です。機械の仕事を人が奪ってはいけません。
ということで、簡単な言語用のコンパイラもどきを作ってみることにします。 とはいえ、みなさんにいきなり作ってもらうのは大変なので、 結構僕が作ってしまいました。皆さんは、動作を理解しながら残りの部品を作って、 完成品にしてください。 未完成プログラムは、ここにあります。 ちなみに、僕が書いた完成プログラムは(サンプル実行例を除けば) 150 行くらいで、 そのうち 120 行ぐらいを公開しています。ということで安心してください。 それから、バグを見つけたら報告してください。
MOVLW 1 ; 始めに即値 1 を W レジスタにおいて、 ADDWF x 0 ; W レジスタにアドレス x の中身を足しこんで、 ADDWF y 0 ; W レジスタにアドレス y の中身を足しこんで、 ADDLW 3 ; W レジスタに即値 3 を足しこむとしてやればいいはずです。
ということで、入れ子がない式(の形をした S 式)を与えたら、 「対応する式の結果を W レジスタに配置してくれるアセンブリコード」を出力するプログラム trans-simple-expr を作りましょう。こんな感じ。 足りない関数は自分で作ってください。 あくまでも、プログラムの形をしたデータを扱っていることに 注意してください。
;;; trans-simple-expr ;;; 式(入れ子なし)を与えると、 ;;; 結果を W レジスタにおくためのアセンブリコード(list形式)を出力する関数 ;;; ex. ;;; (trans-simple-expr '4) => ((MOVLW 4)) ;;; (trans-simple-expr 'x) => ((MOVF x 0)) ;;; 訂正: MOVWF-> MOVF ;;; ;;; (trans-simple-expr '(+ 1 x y 3)) ;;; => ((MOVLW 1) (ADDWF x 0) (ADDWF y 0) (ADDLW 3)) ;;; ;;; (trans-simple-expr '(- 1 x y 3)) ;;; => ((MOVF x 0) (ADDWF y 0) (ADDLW 3) (SUBLW 1)) ; (- 1 (+ x y 3)) を行う ;;; 訂正: MOVWF-> MOVF ;;; ;;; (trans-simple-expr '(and x y 3)) ;;; => ((MOVF x 0) (ANDWF y 0) (ANDLW 3)) ;;; 訂正: MOVWF-> MOVF ;;; (trans-simple-expr '(or x y 3)) ;;; => ((MOVF x 0) (IORWF y 0) (IORLW 3)) ;;; 訂正: MOVWF-> MOVF ;;; (trans-simple-expr '(not x)) ;;; => ((COMF x 0)) ;;; ;;; ヒント: ;;; ;;; まずは式についてですが、"変数"とはシンボルのことです。即値とは整数のことです。 ;;; また、演算子ですが、それぞれ +, -, and, or という"シンボル"です。 ;;; ;;; 演算子付の式を変換するにあたっては、+,and, or については、 ;;; 先頭要素を(MOV??) してから、後続部を(AND??)などすればOKです。リスト操作を頑張りましょう。 ;;; - については、例をみながら考えてみましょう。 (define (trans-simple-expr expr) (cond ((number? expr) (list (trans-expr-num expr))) ; 即値の場合 ((symbol? expr) (list (trans-expr-var expr))) ; 変数そのものの場合 ((eq? (car expr) '+) (trans-add-expr (cdr expr))) ; (+ ...) な場合 ((eq? (car expr) '-) (trans-sub-expr (cdr expr))) ; (- ...) な場合 ((eq? (car expr) 'and) (trans-and-expr (cdr expr))); (and ...) な場合 ((eq? (car expr) 'or) (trans-or-expr (cdr expr))) ; (or ...) な場合 ((eq? (car expr) 'not) (trans-not-expr (cdr expr))); (not ...) な場合 (else (error 'trans-simple-expr ; しらないやつの場合 "receives an unknown operator symbol.")))) (define (trans-expr-num num) (list 'MOVLW num)) (define (trans-expr-var var) (list 'MOVF var 0)) ;;; 訂正: MOVWF-> MOVF (define (trans-add-expr expr) 'NOT-IMPLEMENTED-YET) ; 完成させましょう。 (define (trans-sub-expr expr) 'NOT-IMPLEMENTED-YET) (define (trans-and-expr expr) 'NOT-IMPLEMENTED-YET) (define (trans-or-expr expr) 'NOT-IMPLEMENTED-YET) (define (trans-not-expr expr) (if (symbol? (car expr)) (list (list 'COMF (car expr) 0)) (error 'trans-not-expr "receives only variables.")))というわけで、サンプル例を実行して確かめてみましょう。
(trans-simple-expr '(+ 1 x y 3)) (trans-simple-expr '(- 1 x y 3)) (trans-simple-expr '(and x y 3)) (trans-simple-expr '(or x y 3)) (trans-simple-expr '(not x))上手く動きました? 素晴らしい。
導入するのは、
プログラムは、こんな感じで記述できます。以下は start から end -1 までを足し合わせるプログラム。 括弧だらけなので lisp っぽく見えますが、中身は C と変わりません。
(begin (:= start 3) (:= end 23) (:= result 0) (while (- end start) (begin (:= result (+ result start)) (:= start (+ start 1)))))
;;; trans-stmt ;;; 式を変換して対応するアセンブリコードを出力する関数 ;;; ;;; とはいえ、実体は、書く形に応じて個々の関数に振り分けるだけ (define (trans-stmt stmt) (cond ((eq? (car stmt) ':=) ; 代入文の場合 (trans-assign-stmt (cadr stmt) (caddr stmt))) ((eq? (car stmt) 'if) ; if 文の場合 (trans-if-stmt (cadr stmt) (caddr stmt) (cadddr stmt))) ((eq? (car stmt) 'while) ; while 文の場合 (trans-while-stmt (cadr stmt) (caddr stmt))) ((eq? (car stmt) 'begin) ; 複文の場合 (trans-stmts (cdr stmt))) (else ; 知らないものの場合 (error 'trams-stmt "Unknown statement."))))最終的には、こんな感じで利用します。
(trans-stmt '(begin (:= start 3) (:= end 20) (:= result 0) (while (- end start) (begin (:= result (+ result start)) (:= start (+ start 1)))))) ==> ((MOVLW 3) (MOVWF start) ;;; 訂正: MOVFW-> MOVWF (MOVLW 20) (MOVWF end) ;;; 訂正: MOVFW-> MOVWF (MOVLW 0) (MOVWF result) ;;; 訂正: MOVFW-> MOVWF g856 (MOVF start 0) ;;; 訂正: MOVWF-> MOVF (SUBWF end 0) (BTFSC STATUS 2) ; 当初、僕は BTFSS と間違えていた (GOTO g857) (MOVF result 0) ;;; 訂正: MOVWF-> MOVF (ADDWF start 0) (MOVWF result) (MOVF start 0) ;;; 訂正: MOVWF-> MOVF (ADDLW 1) (MOVWF start) ;;; 訂正: MOVFW-> MOVWF (GOTO g856) g857)
;;; trans-assign-stmt ;;; (trans-assign-stmt var expr) は expr を計算して、var に代入 (define (trans-assign-stmt var expr) (append (trans-simple-expr expr) ; ここまで expr が Wレジスタに入り (list (list 'MOVWF var)))) ; ここで、var に書き込み 訂正: MOVFW-> MOVWFでおしまい。
;;; trans-stmts は複数の文を処理 (define (trans-stmts stmts) ; 複文の場合 (if (null? stmts) (list) (append (trans-stmt (car stmts)) ; リストとリストを (trans-stmts (cdr stmts))))) ; 連結しましょうおしまい。
...EXPR-CODES... ; expr を W レジスタに配置するコード群 ; 実は、Zero Flag も設定してくれている BTFSC STATUS 2 GOTO ELSE-LABEL ...THEN-CODES... ; then-stmt を変換したコード群 GOTO EXIT-LABEL ELSE-LABEL ...ELSE-CODES... ; else-stmt を変換したコード群 EXIT-LABELというわけで、こんな関数を作ってみました。 (gensym) というのは新規の symbol を生成するための関数で、 できあがった label を label 用に使っています。
;;; trans-if-stmt ;;; (trans-if-stmt expr then-stmt else-stmt) は ;;; expr の結果が 0 以外なら then を 0 なら else を実行する (define (trans-if-stmt expr then-stmt else-stmt) (trans-if-stmt-aux expr then-stmt else-stmt (gensym) ; else-label 用の新規 symbol の生成 (gensym) ; exit-label 用の新規 symbol の生成 )) (define (trans-if-stmt-aux expr then-stmt else-stmt else-label exit-label) (append (trans-simple-expr expr) ; expr を評価し (list (list 'BTFSC 'STATUS 2) ; Zero-Flag がたっていなければ then (list 'GOTO else-label)) ; たっていれば、else へ goto (trans-stmt then-stmt) ; then を変換したもの (list (list 'GOTO exit-label) ; then が終われば exit へ goto else-label) ; else はここから (trans-stmt else-stmt) ; else を変換したもの (list exit-label))) ; if 文終了
INIT-LABLE ...EXPR-CODES... ; expr を W レジスタに配置するコード群 ; 実は、Zero Flag も設定してくれている BTFSC STATUS 2 GOTO EXIT-LABEL ...STMT-CODES... ; stmt を変換したコード群 GOTO INIT-LABEL ; 最初に戻る EXIT-LABELさあ、残りを埋めてみましょう。
;;; trans-while-stmt ;;; (trans-while-stmt expr stmt) は ;;; expr を評価し、0 以外でならば繰り返し stmt を実行する ;;; ヒント: ;;; trans-if-stmt を理解できれば問題ないはず。 ;;; 真似して作ってみましょう。 (define (trans-while-stmt expr stmt) (trans-while-stmt-aux expr stmt (gensym) (gensym))) (define (trans-while-stmt-aux expr stmt init-label exit-label) 'NOT-IMPLEMENTED-YET) ; 完成させましょう。さて、少し試してみましょう。
(trans-stmt '(begin (:= start 3) (:= end 20) (:= result 0) (while (- end start) (begin (:= result (+ result start)) (:= start (+ start 1)))))) => 前述どおり (trans-stmt '(begin (:= x 10) (:= y (+ x 12)) (:= z (and x y)) (if (- y x z) (while (- x z 2) (:= z (- z 1))) (:= z (+ x y z))))) => このとおり
最近の普通の言語は、もっといろんな構文もありますし、関数呼び出しも出来ますし、 局所変数だってありますし、ポインタも使えます。
それに、この「もどき」は出力コードも最適化されていない naive なコードが出力します。
でも、なんとなくプログラミング言語とアセンブリ言語の差が埋まったような気がしてくれると嬉しいです。
2000.12.5/ Tomio KAMADA: kamada@cs.kobe-u.ac.jp