Haskellでいってみよう

日曜プログラマにも満たないレベルでもHaskellで何かソフトウェアを作りたい!

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

(ここまでのソース)