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の回路図落ちてないかな :-)

(ここまでのソース)