12/13 第10回 言語処理系と仮想機械(1)

前回までの補足

• 講義のスライド(PDF形式)は，cfiveの「情報科学(水4)」のコースの「教材」のところからダウンロード可能にしてある．講義受講者以外への再配布は許可されないので注意すること．

11/29課題について

• 12/13 13:30の時点で9名が提出．

スライドに使われたプログラム

先頭文字を覗く

def peekChar() return $line[0..0] end
# $line="100+20"
# peekChar
# $line

先頭文字を使う

def getChar() ch = peekChar
$line[0..0] = ""; return ch end
# $line="100+20"
# getChar
# $line

自然数の読み取り

def getNumber
  value = getChar.to_i
  while peekChar =~ /[0-9]/
   value = 10*value+(getChar.to_i) end
  return value
end
# $line="100+20"
# getNumber
# $line

字句解析

def nextToken
  if peekChar =~ /[0-9]/
   $type = :NUMBER; $value = getNumber
  else $type = :SYMBOL; $value =
   {"+"=>:+, "-"=>:-, "*"=>:*, "/" =>:/, "("=>:lpar, ")"=>:rpar}[getChar]
  end
end
# $line="100+20"
# nextToken
# $line
# p $type
# nextToken
# $line
# p $type

再帰的データ構造の例

Expr = Struct.new(:left, :operator, :right)
Expr.new(
  Expr.new(
    Expr.new(3, :*, Expr.new(:x, :**, 2)),
    :-,
    Expr.new(5, :*, :x)),
  :/,
  Expr.new(:y, :+, 1))

構文解析

$level = { :+ => 1, :- => 1, :* => 2, :/ => 2, :lpar => 3, :rpar => 0 }

def e
 node = t
 while $type==:SYMBOL and $level[$value]==1
   op = $value; nextToken
   node = Expr.new(node,op,t) end
  return node
end 

def t
 node = f
 while $type==:SYMBOL and $level[$value] == 2
  op = $value; nextToken
  node = Expr.new(node,op,f) end
 return node
end

def f
 if $type==:NUMBER then
   value = $value; nextToken; return value
 elsif $type==:SYMBOL and $level[$value]==3
  nextToken; node = e; nextToken
  return node
 end
end
# $line="(100*2+20)*3"
# nextToken
# $node=e
# p $node
# $line

式木の表示(中置記法)

def pr(node)
  if node.kind_of?(Fixnum) then print node
  else
    print "("
    pr(node.left); print node.operator; pr(node.right)
    print ")"
  end
end
# pr $node

式木の表示(後置記法)

def pr(node)
 if node.kind_of?(Fixnum) then print node
 else 
   pr(node.left); print " "
   pr(node.right); print " "
   print node.operator
 end
end
# pr $node

式木から式の値の計算

def calc(node)
 if node.kind_of?(Fixnum)
  return node
 else 
  return {:+ =>proc{|a,b| a+b}, 
          :- =>proc{|a,b| a-b}, 
          :* =>proc{|a,b| a*b}, 
          :/ =>proc{|a,b| a/b}}[node.operator].call(calc(node.left), calc(node.right))
 end
end
# calc $node

式木nodeを計算する機械語を出力

def code(node, base)
  if node.kind_of?(Fixnum)
    print "LOADI ",node,"\n"
  else
    code(node.right, base)
    print "STORE ",base,"\n"
    code(node.left, base+1)
    print ({ :+ => "ADD", :- => "SUB", :* => "MUL", :/ => "DIV" }[node.operator]),
    " ",base,
    ({ :+ => "\n", :- => "\n", :* => "\n", :/ => "\nSHIFTL 16\nSHIFTR 16\n" }[node.operator])
  end
end
# code $node,100

式木nodeを計算するED21'の機械語をcodepから生成

def codeBin(node,codep,base)
  if node.kind_of?(Fixnum)
    $mem[codep] = 0x1000+node #loadi
  else
    codep = codeBin(node.right,codep,base)
    $mem[codep] = 0x1800+base #store
    codep = codeBin(node.left,codep+1,base+1)
    $mem[codep] = {:+ =>0x3000,:- =>0x3800,:* =>0x4000,:/ =>0x4800}[node.operator]+base
  end
  return codep+1
end
# $mem=Array.new(200)
# codeBin $node,0,100

生成されたプログラム

LOADI 5
STORE 20
LOADI 7
SUB 20
STORE 20
LOADI 4
DIV 20
SHIFTL 16
SHIFTR 16
STORE 20
LOADI 8
ADD 20

仮想機械のインタプリタ

def sim
  pc = ac = 0
  while $mem[pc] != 0
    p pc
    opr = $mem[pc] & 0xff
    case $mem[pc] & 0xffffff00
    when 0x1000 # loadi
      ac = opr; pc += 1
    when 0x1800 # store
      $mem[opr] = ac; pc += 1
    else
      ac = { 0x3000 => proc {|a,b| a+b}, 
               0x3800 => proc {|a,b| a-b}, 
               0x4000 => proc {|a,b| a*b}, 
               0x4800 => proc {|a,b| a/b} }[$mem[pc] & 0xffffff00].call(ac,$mem[opr])
      pc += 1
    end
  end    
  return ac
end
# sim