CPUの創りかた(10): おまけ、アセンブラ
CPU自体は前回までで完成したので、次のネタに行ってもよかったのだが、
- CPU(の実行プログラム)に与えるのがマシンコードだと、いちいち ハンドアセンブルするのが面倒くさい。
- 別件でパーサを書く必要がありParsecライブラリに興味を持っていたので そのうち勉強したいと思っていた。
という理由により、今回はおまけとして簡易アセンブラを作ってみよう。
まずは文法の定義から
このCPU(TD4)は命令数が非常に少ないので、何となれば、単純な文字列 変換でもよかったのだが、Parsecの勉強も兼ねているからそこはちゃんと 文法の定義から入らなければなるまい。
文法定義とくればBNFだろう。大学時代に、わからないなりに適当な文法を 定義して遊んでいたのを思い出す。その頃の記憶を頼りにBNFで書き始めたのだが、 どうやら世間には EBNF というのがあるようなのでどうせならこちらにしよう、BNFの問題を 解決しているということだし。
ところでアセンブリ言語(ニーモニック?)の文法はどのように定義したら いいのだろう? と調べたら、 こういうの が見つかった。作りたいのはこれよりだいぶ簡素なものなので、ありがたく 参考にさせていただいた。EBNFはこれが初めてなので書き方が間違っているかも しれないが、とりあえず次のように定義してみた。
# EBNF for TD4 assembler program = instcode , { instcode } ; instcode = ( code2 | code1 ) , linefeed ; code2 = inst2, space, operand2 ; code1 = inst1, space, operand1 ; inst2 = 'add' | 'mov' ; inst1 = 'in' | 'out' | 'jnc' | 'jmp' ; operand2 = register , "," , operand1 ; operand1 = register | imdata ; register = 'a' | 'b' ; imdata = 4 * digit2 ; digit2 = "0" | "1" ; space = white space , { white space } ; white space = '\x20' | '\x09' ; linefeed = '\x0a' | ( '\x0d' , '\x0a' ) ;
2オペランド命令のANDとMOV、それ以外のは1オペランド命令なので定義が異なる。 あとはレジスタとか直値とかを定義していけばよさそう。ひとまず形になった 気がするので先に進もう。
パーサの前に
どうもParsecを使えば、EBNF(BNF)の定義からある程度容易にパーサの プログラムに落とし込める、という話があるらしい。ならEBNFができている のだから簡単に作れるよね、と思ったのは甘すぎだった。
まず参考となるWebサイトをいろいろ読んでみて、こう作ればよさそうという 感触を得たかったのだが、ちっとも理解できなかった。今なら何を理解できて いなかったのか分かるが、当初は本当にわからなかったのだ。
要は、ソースをパーサが字句解析したあと、それをどのようにして次の処理 (意味解析、コード生成)に結びつけたらいいのかイメージが湧かなかったため。 Web上でありがちな例は、"add 1,2"みたいなのが入力されたら、"add"を 解析して「"add"という文字列を返す」みたいなやつだ。文字列を解析したい のに解析結果が文字列ならそれをさらに解釈する処理が必要で堂々巡りに 思えてしまった。転機はこの記事。 この記事では明快に「返す値を型で定義している」。
つまりパーサからは「解析木」かそれに類する構造化されたデータが出力されるのだ。 それをまず考えて(定義して)おかないとパーサが書けるわけがない。 ではどのような構造のデータがあればマシンコードに変換できるかを考えてみる。
TD4の命令は、命令コードと1つまたは2つのオペランドからなる(オペランドなしの 命令は無い)。そこで、これらを組で表すことにする。最終的にはこう。
data Inst = Add | Mov | In | Out | Jnc | Jmp deriving (Enum, Show) data Operand = RegA | RegB | Imdata String deriving Show type Mnemonic = (Inst, (Operand, Maybe Operand))
Mnemonic
は二重の組だ。命令コードとオペランドの組からなる。
オペランドの組は、一つ目は必ず存在するので普通にOperand
で、
二つ目は無いかもしれないのでMaybe
型とした。オペランドはA,Bレジスタか
直値の三種類しかない。パーサはソースを解析してMnemonicを命令の数だけ
リストにして返してくれればよいのだ(以後、解析リスト、とする)。
パーサを書く
ではパーサを書いてみようと思う。何となくだが末端から作って積み重ねて 行った方がわかりやすそうなので、個々のオペランドから始める。まずは 直値(immediate data)から。
-- EBNF -- imdata = 4 * digit2 ; -- digit2 = "0" | "1" ; imdata :: Parser Operand imdata = do im <- count 4 (oneOf "01") return $ Imdata im
先に定義したように、直値もOperand
型の一つなのでパーサの型が
Parser Operand
になっている。直値は二進数だけを扱うことにし、
かならず4桁と決めた。なので、oneOf
で0か1に限定し、それを4つ
連続して取り出したら返すようにした。EBNFの定義と見比べると、
決めた通りにプログラムを書けばよいのがわかる。
同様に、A,Bレジスタはこうなる。
-- EBNF -- register = 'a' | 'b' ; register :: Parser Operand register = do rg <- (regA <|> regB) return rg regA :: Parser Operand regA = do rg <- string "a" return $ RegA regB :: Parser Operand regB = do rg <- string "b" return $ RegB
AかBかの区別をつけるため、それぞれ別にパーサを定義し、それを<|>
で
合わせてレジスタのパーサとした。
あとは同様に、EBNFをもとに以下のようなパーサを作った。
program :: Parser [Mnemonic] program = do pg <- many1 $ instcode return pg instcode :: Parser Mnemonic instcode = do cd <- code2 <|> code1 many1 $ oneOf "\r\n" return cd code2 :: Parser Mnemonic code2 = do in2 <- inst2 many1 space op2 <- operand2 return (in2, op2) code1 :: Parser Mnemonic code1 = do in1 <- inst1 many1 space op1 <- operand1 return (in1, (op1, Nothing)) inst2 :: Parser Inst inst2 = do i2 <- (string "add" <|> string "mov") let i = if i2 == "add" then Add else Mov return i inst1 :: Parser Inst inst1 = do i1 <- (string "in" <|> string "out" <|> try (string "jnc") <|> (string "jmp")) let i = case i1 of "in" -> In "out" -> Out "jnc" -> Jnc "jmp" -> Jmp return i operand2 :: Parser (Operand, Maybe Operand) operand2 = do op2 <- register char ',' op1 <- operand1 return $ (op2, Just op1) operand1 :: Parser Operand operand1 = do op1 <- (register <|> imdata) return op1
EBNFの定義と見比べれば、それぞれ何をしているかは分かると思う。 ではテストしてみよう。テスト用プログラムはざっと以下のような感じ。
module Main where import Control.Applicative hiding ((<|>)) import Data.Char import Text.Parsec import Text.Parsec.String import Text.Parsec.Char (型、パーサ定義は省略) main :: IO () main = do parseTest inst2 "add" parseTest inst2 "mov" parseTest inst2 "abc" parseTest register "a" parseTest register "b" parseTest register "c" parseTest imdata "0100" parseTest imdata "10100" parseTest imdata "1012" parseTest operand1 "aa" parseTest operand2 "a 1100" parseTest code2 "add a,b" parseTest code2 "mov a,0011" parseTest code1 "jmp 1011" parseTest code1 "in b" parseTest code1 "in a" parseTest code1 "in 0110" parseTest instcode "add a,b\n" parseTest instcode "add a,b\r\n" parseTest instcode "add a,a" parseTest instcode "jmp 1100\r\n"
このように、パーサに食わせてみたい文字列とそれを処理するパーサ関数を 組みにして与えればいいようだ。パーサの解析に失敗した(=文法にそぐわない) 場合はエラーが返るのですぐわかる。ざっとみたところうまく動いている ように・・・見えなかった!
文法定義のやり直し
うまくいったと思っていたのに実はいけていなかった。add a,a
とか
in a
という命令はTD4には存在しないがパーサを通ってしまうのだ。
文法定義が甘かったわけだ。2オペランド命令と1オペランド命令を
分けるだけでは個々の命令の細かい制限(Bレジスタしか指定できない等)が
表現できていなかった。
ということで、EBNFの定義を見直す。
EBNF for TD4 assembler (revision 1) program = line , { line } ; line = instcode , linefeed ; instcode = inst_add | inst_mov | inst_in | inst_out | inst_jump ; inst_add = 'add' , space , register , "," , imdata ; inst_mov = 'mov' , space , ( op_mov1 | op_mov2 | op_mov3 ) ; inst_in = 'in' , space , register ; inst_out = 'out' , space , ( reg_b | imdata) ; inst_jump = ( 'jnc' | 'jmp' ) , space , imdata ; op_mov1 = register , "," , imdata ; op_mov2 = reg_a , "," , reg_b ; op_mov3 = reg_b , "," , reg_a ; register = reg_a | reg_b ; reg_a = 'a' ; reg_b = 'b' ; (imdata以降は同じなので割愛)
ポイントは、個々の命令ごとにオペランドのパターンを記述したこと。 結局オペランドが共通なのはジャンプ命令だけだった。これに沿って パーサも書き直す。
instcode :: Parser Mnemonic instcode = do cd <- inst_add <|> inst_mov <|> inst_in <|> inst_out <|> inst_jump return cd inst_add :: Parser Mnemonic inst_add = do in1 <- string "add" many1 space rg1 <- register char ',' im1 <- imdata return (toInst in1, (rg1, Just im1)) inst_mov :: Parser Mnemonic inst_mov = do in1 <- string "mov" many1 space op <- try (op_mov1) <|> (try op_mov2 <|> op_mov3) return (toInst in1, op) inst_in :: Parser Mnemonic inst_in = do in1 <- string "in" many1 space rg <- register return (toInst in1, (rg, Nothing)) inst_out :: Parser Mnemonic inst_out = do in1 <- string "out" many1 space op <- regB <|> imdata return (toInst in1, (op, Nothing)) inst_jump :: Parser Mnemonic inst_jump = do in1 <- try (string "jnc") <|> (string "jmp") many1 space im <- imdata return (toInst in1, (im, Nothing)) op_mov1 :: Parser (Operand, Maybe Operand) op_mov1 = do rg <- register char ',' im <- imdata return (rg, Just im) op_mov2 :: Parser (Operand, Maybe Operand) op_mov2 = do op1 <- regA char ',' op2 <- regB return (op1, Just op2) op_mov3 :: Parser (Operand, Maybe Operand) op_mov3 = do op1 <- regB char ',' op2 <- regA return (op1, Just op2) toInst :: String -> Inst toInst s = case s of "add" -> Add "mov" -> Mov "in" -> In "out" -> Out "jnc" -> Jnc "jmp" -> Jmp
先ほどと同じテストを流してみると・・・ちゃんとmov a,a
やin a
が
エラーになっている! パーサが出来上がった!
(Applicativeスタイルへの対応はまた今度。上記の書き方だけでも
まだ全然理屈を咀嚼できていない)
コード生成
さて、パーサはソースプログラムの解析をするだけなので、そこから 目的のマシンコードを作り出す処理が必要だ。次はコード生成部分を作ろう。 と言っても、パーサがきちんと解析リストを生成してくれれば あとは簡単だ。AならBというふうに対応するマシンコードを返せば良い。 TD4は命令数が非常に少ないので、全部列挙することにした。
generate :: Either ParseError [Mnemonic] -> [String] generate (Left s) = [show s] generate (Right []) = [] generate (Right (x:xs)) = (translateOne x):(generate $ Right xs) translateOne :: Mnemonic -> String translateOne (Add, (RegA, Just (Imdata s))) = "0000" ++ s translateOne (Mov, (RegA, Just RegB)) = "00010000" translateOne (In , (RegA, Nothing)) = "00100000" translateOne (Mov, (RegA, Just (Imdata s))) = "0011" ++ s translateOne (Mov, (RegB, Just RegA)) = "01000000" translateOne (Add, (RegB, Just (Imdata s))) = "0101" ++ s translateOne (In , (RegB, Nothing)) = "01100000" translateOne (Mov, (RegB, Just (Imdata s))) = "0111" ++ s translateOne (Out, (RegB, Nothing)) = "10010000" translateOne (Out, (Imdata s, Nothing)) = "1011" ++ s translateOne (Jnc, (Imdata s, Nothing)) = "1110" ++ s translateOne (Jmp, (Imdata s, Nothing)) = "1111" ++ s translateOne _ = error "no such mnemonic"
最後の行は保険だ。パーサがきちんと解析できていれば定義されていない 命令の解析リストが入力されることは無いだろうから。コンパイルして実行 してみる。
$ cabal build td4asm : $ echo "mov a,b" | dist/build/td4asm/td4asm 00010000
おお!正しく変換されている!ちなみに、入力の最後に改行が無いとエラーになる。
$ echo -n "mov a,b" | dist/build/td4asm/td4asm "TD4 asm" (line 1, column 8): unexpected end of input expecting new-line
構文解析で、命令行の最後は改行で終わるように定義しているからだ・・・。 これぐらいの制約は多めに見てもらおう。
再びラーメンタイマーの実行
前回はラーメンタイマープログラムのマシンコードを手で作ってCPUに入れていた。 今回はアセンブラにアセンブリ言語のソースを入れてマシンコードを生成させて CPUへ入れたいと思う。アセンブラは生成したマシンコードを標準出力に出すので そのままパイプでCPUへつないであげればいいのだ。
* 見やすくするため実際には指定しているディレクトリなどは省いている * $ cat ramen.a out 0111 add a,0001 jnc 0001 add a,0001 jnc 0011 out 0110 add a,0001 jnc 0110 add a,0001 jnc 1000 out 0000 out 0100 add a,0001 jnc 1010 out 1000 jmp 1111 $ td4asm < ramen.a | td4 clock 1.0 sec; I/P 0000 step 0; [CF:0][A:0000][B:0000][OP:0000][PC:0000] step 1; [CF:0][A:0000][B:0000][OP:0111][PC:0001] step 2; [CF:0][A:0001][B:0000][OP:0111][PC:0010] ^C
ちゃんと動いている! やはりハンドアセンブルより断然楽ちんだ。
まとめ
さて、今回で本当に"CPU回"はおしまい。記事を細切れにしたせいもあって 10回にもなってしまった。長丁場だったが、CPUネタは面白い取り組みだったなあ。 どこかにi4004の回路図落ちてないかな :-)
(ここまでのソース)