RaccでSchemeパーサを作る(2)

マクロ関係、数のややこしいところ(有理数、虚数)以外は大体実装しました。これで生駒読書会#2にのぞもう!
ファイル: list_parser.y

# Local Variables:
# mode: ruby
# compile-command: "racc -o list_parser.rb list_parser.y" 
# End:

class ListParser
rule
  atoms		:
		| atom atoms
  {
    result = List.new(*val)
  }

  atom 		: IDENT
		| CHAR
		| BOOLEAN
		| NUMBER
		| STRING
		| list
		| vector
		| "'" atom
  {
    result = List.new(:quote, List.new(val[1]))
  }

  list		: '(' atoms ')'
  {
    result = val[1]
  }
		| '(' atom atoms '.' atom ')'
  {
    result = list = List.new(val[1], val[2])
    until list.cdr.nil?
      list = list.cdr
    end
    list.cdr = val[4]
  }

  vector	: '#(' atoms ')'
  {
    result = val[1].to_a
  }
end

---- header
require 'enumerator'
require 'strscan'
require 'list'

---- inner
INIT_RE_STR = '[A-Za-z!$%&*/:<=>?^_~]'
SSEQ_RE_STR = "(?:#{INIT_RE_STR}|\\d|\\+|-|\\.|@)"

IDENT_RE = /(?:#{INIT_RE_STR}#{SSEQ_RE_STR}*|\+|-|\.\.\.)/

def parse(str)
  @tokens = collect_tokens(str) do |scanner|
    case
    when scanner.skip(/\s+/)
      # ignore
    when scanner.skip(/;.*$/)
      # ignore
    when scanner.scan(/#[tf]/)
      [:BOOLEAN, scanner[0] == '#t']
    when scanner.scan(/#\\(space|newline)/)
      [:CHAR, (scanner[1] == 'space') ? ' '[0] : "\n"[0]]
    when scanner.scan(/#\\(.)/)
      [:CHAR, scanner[1][0]]
    when scanner.scan(/#b([+-]?)([01]+)/)
      n = scanner[2].enum_for(:each_byte).inject(0) do |n, c|
        n * 2 + ((c == ?0) ? 0 : 1)
      end
      [:NUMBER, (scanner[1] == '-') ? -n : n]
    when scanner.scan(/#o([+-]?)([0-7]+)/)
      n = scanner[2].oct
      [:NUMBER, (scanner[1] == '-') ? -n : n]
    when scanner.scan(/#x([+-]?)([\dA-Fa-f]+)/)
      n = scanner[2].hex
      [:NUMBER, (scanner[1] == '-') ? -n : n]
    when scanner.scan(/[+-]?\d+\.\d+/)
      [:NUMBER, scanner[0].to_f]
    when scanner.scan(/[+-]?\d+/)
      [:NUMBER, scanner[0].to_i]
    when scanner.scan(/"((?:\\"|[^"])*)"/)
      [:STRING, scanner[1].gsub(/\\"/, '"')]
    when scanner.scan(IDENT_RE)
      [:IDENT, scanner[0].to_sym]
    when scanner.scan(/#\(/)
      [scanner[0], scanner[0]]
    else
      s = scanner.getch
      [s, s]
    end
  end
  # p @tokens
  do_parse
end

def collect_tokens(str)
  scanner = StringScanner.new(str)
  tokens = []
  until scanner.eos?
    token = yield(scanner)
    tokens << token if token
  end
  tokens
end

def next_token
  @tokens.shift
end

ファイル: list.rb

require 'enumerator'

class List
  include Enumerable

  def initialize(car, cdr = nil)
    @car, @cdr = car, cdr
  end
  attr_accessor :car, :cdr

  def each
    each_list do |list|
      yield(list.is_a?(List) ? list.car : list)
    end
  end

  def each_list
    list = self
    while list.is_a?(List)
      yield(list)
      list = list.cdr
    end
    yield(list) if list
    self
  end

  def inspect
    enum_for(:each_list).inject('(') do |s, list|
      if list.is_a?(List)
        s << ' ' if s.size > 1
        s << list.car.inspect
      else
        s << ' . '
        s << list.inspect
      end
    end + ')'
  end
end

ファイル: main.rb

#!/usr/bin/env ruby

require 'list_parser'

ListParser.new.parse(ARGF.read).each do |expr|
  p expr
end

ファイル: example1.scm

;; hello with name
(define hello
  (lambda (name)
    (string-append "Hello " name "!")))

;; sum of three numbers
(define sum3
  (lambda (a b c)
    (+ a b c)))

#t

(1 2 3 . 4)
(1 . 2)

'(+ 1 2 3)
(quote (+ 1 2 3))
'aaa
(quote aaa)

#\a
#\A
#\(
#\ 
#\space
#\newline

"h\"oge"

#(1 2 3)

123
+123
-123

#b1100
#b-1100

#o12
#o-12

#xFF
#x-FF

0.01

実行例:

> racc -o list_parser.rb list_parser.y
> ruby main.rb sample1.scm
(:define :hello (:lambda (:name) (:"string-append" "Hello " :name "!")))
(:define :sum3 (:lambda (:a :b :c) (:+ :a :b :c)))
true
(1 2 3 . 4)
(1 . 2)
(:quote (:+ 1 2 3))
(:quote (:+ 1 2 3))
(:quote :aaa)
(:quote :aaa)
97
65
40
32
32
10
"h\"oge"
[1, 2, 3]
123
123
-123
12
-12
10
-10
255
-255
0.01

参照: RaccでSchemeパーサを作る - 趣味的にっき