第14回: 言語処理系と仮想機械 (2)

言語処理系

1. 字句解析
2. 構文解析
   1. BNF
   2. 文法の階層
3. コード生成
4. 仮想機械

プログラム

1. 数式から式木への変換

   def peekChar() $line[0..0] end
   
   def getChar() ch = peekChar; $line[0..0] = ""; ch end
   
   def nextToken
     if peekChar =~ /[0-9]/ then $type = :NUMBER; $value = getNumber
     else $type = :SYMBOL; $value = { "+"=>:+ , "-"=>:- , "*"=>:* , "/" =>:/ , "(" => :lpar , ")" => :rpar }[getChar]
     end
   end
   
   def getNumber
     value = getChar.to_i
     while peekChar =~ /[0-9]/ do value = 10*value+(getChar.to_i) end
     value
   end
   
   Expr = Struct.new(:left, :operator, :right)
   $level = { :+ => 1, :- => 1, :* => 2, :/ => 2, :lpar => 3, :rpar => 0 }
   
   def e
     node = t
     while $type == :SYMBOL and $level[$value] == 1 do op = $value; nextToken; node = Expr.new(node,op,t) end
     node
   end 
   
   def t
     node = f
     while $type == :SYMBOL and $level[$value] == 2 do op = $value; nextToken; node = Expr.new(node,op,f) end
     node
   end
   
   def f
     if $type == :NUMBER then value = $value; nextToken; value
     elsif $type == :SYMBOL and $level[$value] == 3 then nextToken; node = e; nextToken; node
     end
   end
   
   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
   
   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
   
   def emit(node,base)
     code(node,base); print "STOP 0\n"
   end
   
   $mem = Array.new(30)
   
   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
     codep+1
   end
   
   def emitBin(node,base)
     $mem[codeBin(node,0,base)] = 0 # STOP
   end
   
   def sim
     pc = ac = 0
     while $mem[pc] != 0
       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 => lambda {|a,b| a+b}, 
           0x3800 => lambda {|a,b| a-b}, 
           0x4000 => lambda {|a,b| a*b}, 
           0x4800 => lambda {|a,b| a/b} }[$mem[pc] & 0xffffff00].call(ac,$mem[opr])
         pc += 1
       end
     end    
     ac
   end
   
   def calc(node)
     if node.kind_of?(Fixnum) then node
     else 
       { :+ => lambda {|a,b| a+b}, 
         :- => lambda {|a,b| a-b}, 
         :* => lambda {|a,b| a*b}, 
         :/ => lambda {|a,b| a/b} }[node.operator].call(calc(node.left),calc(node.right))
     end
   end
   
   $line = gets
   nextToken
   
   node = e
   pr(node); print "\n"
   print calc(node),"\n"
   
   emit(node,20)
   
   emitBin(node,20)
   for i in 0..$mem.size-1 do print i," ",$mem[i],"\n" end
   print "ac=",sim,"\n"