tkykmw code

学びたいことを学ぶ

アンダースタンディング コンピュテーション 4章の感想とか

第4章。プッシュダウン・オートマトン

実行中に拡張可能なワーキングメモリがあれば、できることが増える。これはプログラミングに対する素朴な実感にもあっていて、納得感があった。初めてC言語を勉強したあの日、malloc を覚えて、初めてやりたいことができるようになった、あの感覚。

ところで、この本に出てくるサンプルコードは、この手の本にしては、かなり綺麗である。ちゃんとRubyの豊富な言語機能を活用していて、泥臭い記述は極力排除している。

ただ、4章126ページに出てくる、LexicalAnalyzerのコードだけはいただけない。これは、凝り過ぎだろう。パッと見で意図がわからない。

(あと、私の勘違いでなければ、Enumerable#max_byは該当が複数あった場合に結果が不定なので、true / false が変数名と解釈され得るのではないか?)

ざっくり書き直してみた。ベタでも、手続き的に書いたほうが、ずっとわかりやすいはず。

require_relative './util'

class LexicalAnalyzer < Util::Struct.new(:string)
  GRAMMER = [
    { token: 'i', pattern: /if/ },
    { token: 'e', pattern: /else/ },
    { token: 'w', pattern: /while/ },
    { token: 'd', pattern: /do-nothing/ },
    # ...略
  ]

  def analyze
    tokens = []
    tokens << next_token while more_tokens?
    tokens
  end

  private

  def more_tokens?
    !string.empty?
  end

  def next_token
    token, match = rule_matching(string)
    self.string = string_after(match)
    token
  end

  def rule_matching(string)
    last_token = last_match = nil
    token_patterns.each do |(token, pattern)|
      match = pattern.match(string)
      if match && match.to_s.size > last_match.to_s.size
        last_token, last_match = token, match
      end
    end
    [last_token, last_match]
  end

  def string_after(match)
    match.post_match.lstrip
  end

  def token_patterns
    @token_patterns ||= GRAMMER.each_with_object({}) do |rule, hash|
      hash[rule[:token]] = /\A#{rule[:pattern]}/
    end
  end
end

rule_matchingにはEnumerable#reduceを使う方法もあるが……やはりやりすぎな気がする。

token_patternsは説明上は省いた方がいいだろうけど、マッチのたびにRegExpオブジェクト作り直すのはさすがにイヤなので。