@uents blog

Code wins arguments.

SICP 読書ノート#46 - RubyでSchemeインタプリタをつくろう(5) - REPL/字句解析/構文解析 (pp.213-228)

SICP Scheme Ruby

最初はSICPのテキストを見ながら式評価、関数適用、環境まわり（p226付近）までRubyでひと通り実装しましたが、入力されたSchemeのコードを処理系へどうつなぐかで壁にあたりました。

色々と調べたところ、インタプリタの動作は主に以下のステップを踏むようです。

  1. 字句解析
  2. 構文解析
  3. 評価の実行

§4.1の序盤で字句解析/構文解析が出てこないのは、処理系の被実装言語、実装言語がともにSchemeで、さらにS式が構文木にそのまま相当するため構文解析等をせずともいきなり評価できてしまうからだと思います。

いま作っている処理系もS式をRubyの配列にそのまま見立てることで字句解析/構文解析を端折ることもできるのですが、せっかくのインタプリタを実装する機会なので、ある程度きちんとやりたいと思います。

REPL

初めから動くものを作りたいのでREPLループから実装します。SICPのテキストではdriver-loopに相当します。

id:higepon さんの以下のリンク先の実装に似せて以下のようにしました。

Evaluatorの実装はまだ迷っているのでコメントアウトしていますが、おおよそこんな感じです。

# -*- coding: utf-8 -*-

load "parser.rb"
load "generator.rb"
#load "evaluator.rb"

class REPLServer
  IN_PROMPT = '> '
  OUT_PROMPT = '=> '

  def initialize()
  end

  def run()
    while true
      print @@in_prompt

      input = read_line()
      if input == "quit\n"
        return "good bye!!"
      end
      
      begin
        tokens = Parser.tokenize(input)
        nodes = Parser.parse(tokens)
#        p nodes

        object = Generator.generate(nodes)
#        p object
        
#        output = @evaluator.eval(object)
        
      rescue Exception => e
        p e.to_s
        redo
      end

      print OUT_PROMPT
      p output
    end
  end

  private
  def read_line()
    print IN_PROMPT
    input = gets or return
    while (count = input.count('(') -input.count(')')) > 0
      print "  " * (1 + count)
      next_input = gets or return
      input += next_input
    end
    input
  end
end

repl = REPLServer.new
repl.run

例えばpryだったら以下のように実行する想定です。

[1] pry(main)> load "repl.rb"
> (ここでプロンプトを表示)

字句解析

lexerライブラリを使うのが王道のようですが、色々ググっても書式がよくわからなかったので適当に自作しました。

class Parser
  def self.tokenize(input)
    tokens = input.strip
             .gsub(/\n/, ' ')
             .gsub('\'(', '(quote (')
             .gsub('(', '( ')
             .gsub(')', ' )')
             .split(' ')

    tokens.map do |token|
      case token
      when '('
        :LEFT_PAREN
      when ')'
        :RIGHT_PAREN
      when /^[+-]?[0-9]*[\.]?[0-9]+$/
        { :NUMBER => token }
      when /\"/
        { :STRING => token }
      else
        { :SYMBOL => token }
      end
    end
  end
end

改行等を削除して括弧の前後に空白文字を入れた後で、その空白文字でsplitします。クオートされたデータの'(data)は(quote (data))に置き換えました（ずるいかな？）。

splitしたトークン(字句)は以下のようなタグを付与します。

:LEFT_PAREN
:RIGHT_PAREN
:NUMBER
:STRING
:SYMBOL

pryで実行してみるとトークンが抽出できていることがわかります。

[1] pry(main)> load "parser.rb"
=> true
[2] pry(main)> Parser.tokenize("(define x 1)")
=> [:LEFT_PAREN, {:SYMBOL=>"define"}, {:SYMBOL=>"x"}, {:NUMBER=>1}, :RIGHT_PAREN]
[3] pry(main)> Parser.tokenize("((lambda (x) \"foo\") 1)")
=> [:LEFT_PAREN, :LEFT_PAREN, {:SYMBOL=>"lambda"}, :LEFT_PAREN, {:SYMBOL=>"x"}, :RIGHT_PAREN, {:STRING=>"foo"}, :RIGHT_PAREN, {:NUMBER=>1}, :RIGHT_PAREN]

構文解析

分割したトークンから構文木を生成します。ぱっと聞くと難しそうですが、単に配列にpushしていくだけでよいです。

（なかなかシンプルにできましたが、ここまでたどり着くのに苦労しました…）

class Parser
  def self.parse(t)
    tokens = t.dup
    token = tokens.shift
    case token
    when :LEFT_PAREN
      return make_nodes(tokens)
    when :RIGHT_PAREN
      raise "parse: unexpected tokens; " + t.to_s
    else
      return token
    end
  end

  private
  def self.make_nodes(tokens)
    nodes = []
    token = tokens.shift

    while token != nil
      case token
      when :LEFT_PAREN
        nodes.push(make_nodes(tokens))
      when :RIGHT_PAREN
        return nodes
      else
        nodes.push(token)
      end
      token = tokens.shift
    end
    nodes
  end

pryで実行してみます。

[1] pry(main)> Parser.parse(Parser.tokenize("(define x 1)"))
=> [{:SYMBOL=>"define"}, {:SYMBOL=>"x"}, {:NUMBER=>1}]
[2] pry(main)> Parser.parse(Parser.tokenize("((lambda (x) \"foo\") 1)"))
=> [[{:SYMBOL=>"lambda"}, [{:SYMBOL=>"x"}], {:STRING=>"foo"}], {:NUMBER=>1}]

トークンが配列にpushされた形で出力されました。

次回は構文木を構築後の処理を実装していきます。

※「SICP読書ノート」の目次はこちら