2011 9 2011.12.9 Ruby B Web ( ) 1 1.1 2 def delete if at then return @cur = @prev.next = @cur.next (1) EOF (2)@cur 1 ()@prev 1 def exch if at @cur.next == @tail then return a = @prev; b = @cur.next; c = @cur; d = @cur.next.next a.next = b; b.next = c; c.next = d; @cur = b 4 ( 2 ) a b c d @cur 1 @prev 1 def backward if @prev == @head then return a = @prev; top; while @cur!= a do forward 1
( ) def invert top; if at then return a = @cur; b = @cur.next; a.next = @tail while b!= @tail do c = b.next; b.next = a; a = b; b = c @head.next = a; top @tail (@head ) 1 0 1.2 4 @lineno invert top 1 backward @lineno Buffer class Buffer Cell = Struct.new(data, next) def initialize @tail = @cur = Cell.new("EOF", nil) @head = @prev = Cell.new("", @cur) @lineno = 1 def getlineno return @lineno def goto(n) top; (n-1).times do forward def at return @cur == @tail def top @prev = @head; @cur = @head.next; @lineno = 1 def forward if at then return @prev = @cur; @cur = @cur.next; @lineno = @lineno + 1 def insert(s) @prev.next = Cell.new(s, @cur) @prev = @prev.next; @lineno = @lineno + 1 def print 2
puts(" " + @cur.data) # delete exch backward def backward goto(@lineno - 1) def invert top; if at then return a = @cur; b = @cur.next; a.next = @tail while b!= @tail do c = b.next; b.next = a; a = b; b = c @head.next = a; top def subst(str) if at then return a = str.split( / ) @cur.data[regexp.new(a[1])] = a[2] def read(file) open(file, "r") do f f.each do s insert(s) def save(file) top open(file, "w") do f while not at do f.puts(@cur.data); forward ( ) def edit e = Buffer.new while true do printf(">") line = gets; c = line[0..0]; s = line[1..-2] if c == "q" then return elsif c == "t" then e.top; e.print elsif c == "p" then e.print; l = e.getlineno; s.to_i.times do e.forward; e.print ; e.goto(l) elsif c == "i" then e.insert(s) elsif c == "r" then e.read(s) elsif c == "w" then e.save(s) elsif c == "s" then e.subst(s); e.print elsif c == "d" then e.delete elsif c == "x" then e.exch
elsif c == "b" then e.backward elsif c == "v" then e.invert elsif c == "a" then e.forward; e.insert(s); e.backward elsif c == "c" then e.delete; e.insert(s); e.backward elsif c == "g" then e.goto(s.to_i) else e.forward; e.print 1. 1 1 / hash1(k) 2 hash2(k) N N N class IntStrTable def initialize @keys = Array.new(997, -1); @vals = Array.new(997, nil) def hash1(n) return n % @keys.length def hash2(n) return n % 2971 + 1 def put(key, val) h1 = hash1(key); h2 = hash2(key) while true do if @keys[h1] == key then @vals[h1] = val; return if @keys[h1]<0 then @keys[h1]=key;@vals[h1]=val; return h1 = (h1 + h2) % @keys.length def get(key) h1 = hash1(key); h2 = hash2(key) while true do if @keys[h1] == key then return @vals[h1] if @keys[h1] < 0 then return nil h1 = (h1 + h2) % @keys.length 10000 N (N 1 ) 1 2 (collision) 4
1 1000 2000 000 5000 10000 0.98475 1.578125.525 9.578125 9.71875 0.78125.054875 7.09025 18.7475 79.51525 2 0.0125 0.070125 0.0975 0.1875 0.75 0.01525 0.078125 0.078125 0.148475 0.289025 0.0078125 0.01525 0.01525 0.02475 0.0975 0.0078125 0.0078125 0.01525 0.0125 0.29875 Ruby 0.0 0.0 0.078125 0.01525 0.0125 Hash 0.0 0.0078125 0.0 0.078125 0.01525 1 N put N get 0 100000 N put NN get Ruby Hash ( 1 () ) class IntStrTable4 def initialize() @hash = {} def put(key, val) @hash[key] = val def get(key) return @hash[key] (Ruby Hash ) 1 (constant time) O(1) 10,000 997 ( ) 50% 8 2 2 benchtable def benchtable1(cnt, tbl) puts(bench(1) do cnt.times do i tbl.put(i, "") ) puts(bench(1) do cnt.times do i tbl.get(i) ) irb> benchtable1(1000, IntStrTable2.new) 0.85975 0.875 => nil irb> benchtable1(2000, IntStrTable2.new).51525 5
2.75 => nil irb> benchtable1(000, IntStrTable2.new) 7.5125.195125 => nil 1 logn 1 O(logN) N 1 O(N) AVL (AVL tree) Adelson-Velsky Landis (splay tree) O(logN) (amortized computational complexity) 1.4 ( ) 2 class IntStrTable Node = Struct.new(key, data, left, right) def initialize() @ = nil def put(key, val) if @ == nil @ = Node.new(key, val, nil, nil); return @ = splay(key, @) if key == @.key @.data = val elsif key < @.key @.left = Node.new(key, val, @.left, nil) else @.right = Node.new(key, val, nil, @.right) def get(key) if @ == nil then return nil @ = splay(key, @) if key == @.key then return @.data else return nil def splay(key, ) dummy = lmax = = Node.new(0, 0, nil, nil) while true do if key ==.key then break splay (spray) l r (?)
if key <.key if (child =.left) == nil then break if key < child.key else.left = child.right; child.right = = child; child =.left if (child =.left) == nil then break.left = ; = if (child =.right) == nil then break if key > child.key.right = child.left; child.left = = child; child =.right if (child=.right) == nil then break lmax.right = ; lmax = = child lmax.right =.left;.left =.right.left = dummy.right;.right = dummy.left; return splay put get splay put (@ nil) splay splay (top-down) dummy lmax key= 9 child C A B key=8 9 child A B child A child B 9 9 C child A child B 9 C dummy dummy A B 9 C A B 1 7
9 8 ( 1) 9-- 9 (rotation) 9--8 8 dummy 9 9 ( dummy ) D dummy A B lmax C X Y lmax A Y D B X C 2 2 (A) lmin (B) lmax lmax lmax 7 1 D lmax 5 4 2 dummy 7 1 D 5 4 2 dummy 7 1 D 5 4 2 dummy 7 1 D 5 4 2 dummy 1 2 7 5 4 (1) (2) () (4) (5) (1) (4) lmax (5) dummy 8
2 2.1 / 1 x + + ( ) x( ) 1( ) ( 4 ) (syntax) ( ) (abstract syntax tree) (expression tree) + + * x 1 * + 2 x 2 x x + 1 + x * 2 ( + x) * 2 4 ( ) + x * 2 ( + x) * 2 x 2 x 2 ( 4 ) 1 2.2 / 2 1 1 ( $vars 1 ) $vars = {} class Add def initialize(l, r) @left = l; @right = r def exec() return @left.exec + @right.exec def to_s() return ( +@left.to_s+ + +@right.to_s+ ) class Mul def initialize(l, r) @left = l; @right = r def exec() return @left.exec * @right.exec def to_s() return ( +@left.to_s+ * +@right.to_s+ ) class Lit def initialize(v) @left = v def exec() return @left def to_s() return @left.to_s class Var def initialize(v) @left = v def exec() return $vars[@left] def to_s() return @left.to_s 9
Add Mul @left @right exec / to s + * Lit Var @left ( ) exec $vars to @left.exec @left @left Add Var (dynamic binding) (polymorphism) irb> $vars[ x ] = 5 => 5 irb> e = Add.new(Var.new( x ), Lit.new(1)) =>... irb> puts(e, e.exec) (x + 1) => nil irb> f = Add.new(Lit.new(), Mul.new(Var.new( x ), Lit.new(2))) =>... irb> puts(f, f.exec) ( + (x * 2)) 1 => nil irb> g = Mul.new(Add.new(Var.new( x ), Lit.new()), Lit.new(2)) =>... irb> puts(g, g.exec) ((x + ) * 2) 1 x 5 4 ( ) 1 (to s ) a. Sub Div b. Assign exec (Var ) s $vars[s] exec irb> e = Assign.new(Var.new( x ), Add.new(Var.new( x ), Lit.new(1))) =>... irb> e.exec => irb> $vars[ x ] => 5 10
c. Loop exec exec ( ) irb> f = Loop.new(Lit.new(20), e) e x = x + 1 =>... irb> f.exec =>... irb> $vars[ x ] => 2 20 1 2 d. Seq exec exec irb> g = Seq.new(f, f) f 20 x = x + 1 =>... irb> g.exec => 4 irb> $vars[ x ] => 4 20 2 4.1 Add Mul (inheritance) (parent class) (superclass) (child class) (subclass) ( ) (override) Node ( to s ) $vars = {} class Node def initialize(l=nil, r=nil) @left = l; @right = r; @op =? def to_s() return ( + @left.to_s + @op.to_s + @right.to_s + ) @left @right (operator + / ) @op Add (Ruby < ) 11
class Add < Node def initialize(l, r) super; @op = + def exec() return @left.exec + @right.exec initialize exec ( ) initialize super ( ) @left @right (...) @op + exec ( ) class Sub < Node def initialize(l, r) super; @op = - def exec() return @left.exec - @right.exec class Mul < Node def initialize(l, r) super; @op = * def exec() return @left.exec * @right.exec class Div < Node def initialize(l, r) super; @op = / def exec() return @left.exec / @right.exec class Lit < Node def exec() return @left def to_s() return @left.to_s class Var < Node def exec() return $vars[@left] def to_s() return @left.to_s Lit Node to s initiailze (@op ).2 @left $vars class Assign < Node def initialize(l, r) super; @op = = def exec() v = @right.exec; $vars[@left.to_s] = v; return v class Seq < Node def initialize(l, r) super; @op = ; def exec() @left.exec; return @right.exec 12
v (0 ) class Loop < Node def initialize(l, r) super; @op = L def exec() v=0; @left.exec.times do v=@right.exec ; return v to s? class Noop < Node def exec() return 0 def to_s() return? n 5 x 1 n x = x * n n = n - 1 x ( 5 ) def test1 e = Seq.new( puts(e) Assign.new(Var.new( n ), Lit.new(5)), Seq.new( Assign.new(Var.new( x ), Lit.new(1)), Seq.new( Loop.new( return e.exec Var.new( n ), Seq.new( Assign.new(Var.new( x ), Mul.new(Var.new( x ), Var.new( n ))), Assign.new(Var.new( n ), Sub.new(Var.new( n ), Var.new( x )))) Lit.new(1))))), irb> test1 ((n=5);((x=1);((nl((x=(x*n));(n=(n-1))));x))) => 120 (interpreter ) ( ) Ruby 1.8.x 2 1
a. x < y 1 0 b. while 0 false true c. if then else d. 2 e. / 4 4.1 Ruby (lexical analyzer) 1 class Lexer def initialize(s) @str = s + $ ; @pos = 0 def peek() return @str[@pos..@pos] def fwd() if @pos<@str.length-1 then @pos=@pos+1 def to_s() return @str[0..@pos-1]+! + @str[@pos..-1] initalize @str @pos $ peek fwd ( )1 to s irb> sc = Lexer.new( x=x+1 ) => #<Lexer0x810b40 @str="x=x+1$", @pos=0> irb> sc.peek => "x" irb> sc.fwd => 1 irb> sc.peek => "=" irb> sc.fwd => 2 irb> sc.fwd => irb> sc.fwd => 4 irb> sc.peek => "1" irb> sc.fwd => 5 irb> sc.peek => "$" irb> puts(sc) x=x+1!$ => nil x=x+1 14
Lexer ( peek fwd ) ( ) 4 4.2 BNF Ruby prog = stat stat ; prog stat = { prog } L expr stat expr expr = fact fact + expr fact - expr fact * expr fact / expr fact = expr fact = identfier number ( expr ) BNF(Backus Normal Form) = ( ) (identifier ) (number) 1 1 ; ; = = x 1 y x + 1 y x = 1 ; y = x + 1 ; y 5 5 x = 1; L 5 x = x * 2; x (2 5 2 5 ) 4 a. x=y=z=1 b. x=2*+4*5 c. n=5;x=1;l(n){x=x*n;n=n-1};x 5 ( ) BNF 4. (syntax analyzer) (parser) (recursive descent parser) 4 15
1 ( ) 1 ( 1 ) ( ) prog stat stat stat { L expr expr fact fact fact x prog stat ; prog { prog } stat ; prog stat ; prog expr stat expr stat fact = expr expr fact = expr expr fact + expr factl fact fact = expr fact fact { x = ; y = 5 } ; z = x + y ; z prog def prog(sc) s = stat(sc); c = sc.peek if c == $ c == } then return s elsif c == ; then sc.fwd; return Seq.new(s, prog(sc)) else puts( STAT + sc.to_s); return Noop.new prog stat stat $ } prog ( ) prog = stat stat ; prog = ; prog ; prog stat Seq ( None ) 1
stat def stat(sc) c = sc.peek if c == { then sc.fwd; p = prog(sc) if sc.peek!= } puts( NO_} + sc.to_s); return Noop.new sc.fwd; return p elsif c == L sc.fwd; e = expr(sc); return Loop.new(e, stat(sc)) else return expr(sc) { stat = { prog } 1 prog } ( ) prog L stat = L expr stat 1 expr prog Loop stat = expr expr expr def expr(sc) e = fact(sc); c = sc.peek if c == + then sc.fwd; return Add.new(e, expr(sc)) elsif c == - then sc.fwd; return Sub.new(e, expr(sc)) elsif c == * then sc.fwd; return Mul.new(e, expr(sc)) elsif c == / then sc.fwd; return Div.new(e, expr(sc)) elsif c == = then sc.fwd; return Assign.new(e, expr(sc)) else return e fact fact 1 expr 2 expr = fact fact fact def fact(sc) c = sc.peek; sc.fwd if c >= a && c <= z return Var.new(c) elsif c >= 0 && c <= 9 return Lit.new(c.to_i) elsif c == ( e = expr(sc) if sc.peek!= ) puts( NO_) + sc.to_s); return Noop.new sc.fwd; return e else puts( FACTOR + sc.to_s); return Noop.new 17
( fact = ( expr ) expr ) 4 1 def run(s) e = prog(s); puts(e); puts(e.exec) 5 irb> run n=5;x=1;ln{x=x*n;n=n-1};x ((n=5);((x=1);((nl((x=(x*n));(n=(n-1))));x))) 120 => nil (compiler) (comiler-interpreter) (optimization) 5 (semantic analyzer) + 5 ( 9 1 10 5+5 ) a. 2 9 b. 9 c. 9 C 5 7 ( ) (right associative) 8 ( + + ) A 9A 1 2 1. Subject Report 9A 2.. 1 4. Q1. Q2. Q. 5 (x+1)=10 x - y - 1 x - (y - 1) (left associative) 18