せかいや

いまいるここを、おもしろく http://sekai-in-the-box.appspot.com/

【Ruby】【アルゴリズム】XMLパーサー(字句解析・構文解析)

 
数式解析の知識を元に。。

XMLパーサー作ったよー

と師匠にメールしたら返事が来たよ。

 

これはちょっと良くないと思う。

tokenメソッドの責務がよくわからない
StringScannerを使うのはいいけど、
正規表現に頼った方法やとスキャンがいっぱい走るし
あんまり筋がいいとは思わない。

あと、ElementとTextを分けてるあたり、XMLを知らないのかなって思ってしまう。

あと、せかいさんのコードは綺麗じゃないね
アルゴリズムの選択も筋がいいとはあまり思いませんし
変数名とかメソッド名とか他人に読ませるようのコードじゃないね
tok とか _findとか全然意図が伝わない。
せかいさんのリファクタリングしたコードがサイトに乗ってますが
正直、全然綺麗になってるとは感じません。
可読性を重視してコード書いてみてください

なんと。大変だ。

今日は送ったコードのリファクタリング。。と思ったけれども
その前段階として以前のコードをきれいにするところからやってみよう。
 
リファクタリングしたコードって言うのはたぶんこの川渡り問題。
【Ruby】【アルゴリズム】宣教師と人食い問題(全列挙型Ver) ※リファクタリング後 - せかいや


送ったコードは以下のとおり。
いったん改修せずに張っておく。

require 'strscan'

module XML
  class Element
    def initialize(token)
      @name = token
      @children = []
    end
    def css(tag_name)
      _find(tag_name).join("")
    end
    def _find(tag_name)
      @children.each do |child|
        if child.class == XML::Element
          if child.name == tag_name
            @result = child.children.dup
            @result.map!{ |x| x.text if x.class == XML::Text }
          end
          result = child._find(tag_name)
          return result if !result.nil?
        end
      end
      @result
    end
    attr_accessor :name, :children
  end
  class Text
    def initialize(token)
      @text = token
    end
    attr_accessor :text
  end
end
def token(data)
  s = StringScanner.new(data)
  tokens = []
  while !s.eos?
    if s.scan(/<\/\S+?>/)
      tokens << [s[0].gsub(/[<\/>]/,''), :end_form]
    elsif s.scan(/<[^>]+?\/>/)
      tokens << [s[0].gsub(/[<\/>]/,''), :special_form]
    elsif s.scan(/<\S+?>/)
      tokens << [s[0].gsub(/[<\/>]/,''), :start_form]
    elsif s.scan(/[^<]+/)
      tokens << [s[0], :text]
    end
  end
  tokens
end
def parse(tokens)
  root = XML::Element.new("default")
  stack = []
  tokens.each_with_index do |tok, i|
    if i == 0
      raise 'root is not light' if tok[1] !=:start_form
      next stack << XML::Element.new(tok[0])
    end
    if tok[1] == :start_form
      stack << XML::Element.new(tok[0])
    elsif tok[1] == :text
      stack.last.children << XML::Text.new(tok[0])
    elsif tok[1] == :end_form
      
      raise 'not light element' if stack.last.name != tok[0]
      if stack.length > 1
        stack[-2].children << stack.last.dup
        stack.pop
      end
    elsif tok[1] == :special_form
      element = XML::Element.new(tok[0])
      stack.last.children << element
    end
  end
  root.children = stack
  root
end
def exec(data)
  parse(token(data))
end
data='<a>huga<b>hello<hoge/>dada</b><c>pupu</c><d/></a>'
p result = exec(data)
p result.css("b")