r9.dvi

Size: px

Start display at page:

Download "r9.dvi"

としみいまいだ
5 years ago
Views:

1 Ruby B Web ( ) def delete if at then (1) EOF (2)@cur 1 ()@prev 1 def exch if then return a b c d a.next = b; b.next = c; c.next = = b 4 ( 2 ) a b c 1 def backward then return a top; a do forward 1

2 ( ) def invert top; if at then return a b a.next while do c = b.next; b.next = a; a = b; b = = a; (@head ) invert top 1 Buffer class Buffer Cell = Struct.new(data, next) def = Cell.new("EOF", = 1 def getlineno def goto(n) top; (n-1).times do forward def at def = = = 1 def forward if at then = = + 1 def @lineno + 1 def print 2

3 puts(" " # delete exch backward def backward goto(@lineno - 1) def invert top; if at then return a b a.next while do c = b.next; b.next = a; a = b; b = = a; top def subst(str) if at then return a = str.split( / = 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

4 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 / hash1(k) 2 hash2(k) N N N class IntStrTable def = Array.new(997, = Array.new(997, nil) def hash1(n) return n def hash2(n) return n % def put(key, val) h1 = hash1(key); h2 = hash2(key) while true do == key = val; return return h1 = (h1 + h2) def get(key) h1 = hash1(key); h2 = hash2(key) while true do == key then < 0 then return nil h1 = (h1 + h2) N (N 1 ) 1 2 (collision) 4

5 Ruby Hash N put N get N put NN get Ruby Hash ( 1 () ) class IntStrTable4 def = {} def put(key, = val def get(key) (Ruby Hash ) 1 (constant time) O(1) 10, ( ) 50% 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) => nil irb> benchtable1(2000, IntStrTable2.new)

6 2.75 => nil irb> benchtable1(000, IntStrTable2.new) => 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 = nil def put(key, val) == = Node.new(key, val, nil, nil); = if = val elsif = Node.new(key, nil) = Node.new(key, val, def get(key) == nil then return = if key then 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 (?)

7 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

8 9 8 ( 1) (rotation) 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 dummy 7 1 D dummy 7 1 D dummy 7 1 D dummy (1) (2) () (4) (5) (1) (4) lmax (5) dummy 8

9 2 2.1 / 1 x + + ( ) x( ) 1( ) ( 4 ) (syntax) ( ) (abstract syntax tree) (expression tree) + + * x 1 * + 2 x 2 x x x * 2 ( + x) * 2 4 ( ) + x * 2 ( + x) * 2 x 2 x 2 ( 4 ) / ( $vars 1 ) $vars = {} class Add def initialize(l, = = r def exec() def to_s() return ( +@left.to_s+ + +@right.to_s+ ) class Mul def initialize(l, = = r def exec() def to_s() return ( +@left.to_s+ * +@right.to_s+ ) class Lit def = v def exec() def to_s() class Var def = v def exec() return $vars[@left] def to_s() 9

10 exec / to s + * Lit ( ) exec @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

11 c. Loop exec exec ( ) irb> f = Loop.new(Lit.new(20), e) e x = x + 1 =>... irb> f.exec =>... irb> $vars[ x ] => d. Seq exec exec irb> g = Seq.new(f, f) f 20 x = x + 1 =>... irb> g.exec => 4 irb> $vars[ x ] => Add Mul (inheritance) (parent class) (superclass) (child class) (subclass) ( ) (override) Node ( to s ) $vars = {} class Node def initialize(l=nil, = = =? def to_s() return ( (operator + / Add (Ruby < ) 11

12 class Add < Node def initialize(l, r) = + def exec() initialize exec ( ) initialize super + exec ( ) class Sub < Node def initialize(l, r) = - def exec() class Mul < Node def initialize(l, r) = * def exec() class Div < Node def initialize(l, r) = / def exec() class Lit < Node def exec() def to_s() class Var < Node def exec() return $vars[@left] def to_s() Lit Node to s initiailze (@op $vars class Assign < Node def initialize(l, r) = = def exec() v $vars[@left.to_s] = v; return v class Seq < Node def initialize(l, r) = ; def 12

13 v (0 ) class Loop < Node def initialize(l, r) = L def exec() 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

14 a. x < y 1 0 b. while 0 false true c. if then else d. 2 e. / Ruby (lexical analyzer) 1 class Lexer def = s + $ = 0 def peek() def fwd() def to_s() @pos $ peek fwd ( )1 to s irb> sc = Lexer.new( x=x+1 ) 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

15 Lexer ( peek fwd ) ( ) 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 ( ) 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

16 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

17 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

18 ( 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 ( ) a. 2 9 b. 9 c. 9 C 5 7 ( ) (right associative) 8 ( + + ) A 9A Subject Report 9A Q1. Q2. Q. 5 (x+1)=10 x - y - 1 x - (y - 1) (left associative) 18

r1.dvi

r1.dvi Ruby 2009.9.7 1 ( ) --- ( ( ) ( ) 1 --- ( ) 1 ( ) (?) IT 7K( )?? ( ) ( )? IT ( ) --- ( ) 1 ( ) --- ( ) (?) 2-3% Top-Level ICT Professional 5% ICT Professional 10% 100% 50% 20% Devl. Experiment Adv. ICT