RaccでSchemeパーサを作る

Ruby

3/2(日)の生駒読書会#2に向けて、Schemeのパーサを準備しておこうと思って作ってみました。なんちゃってSchemeで遊ぶくらいなので、機能はまだまだ足りません。R5RSと見比べると足りないのはだいたいこんな感じかな。

  • ペア。
  • 文字。
  • n進数。小数。複素数。
  • quote。
  • ベクタ。
  • マクロ関係。
  • 文字列の中の"。

ファイル: 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
		| BOOLEAN
		| NUMBER
		| STRING
		| list

  list		: '(' atoms ')'
  {
    result = val[1]
  }
end

---- header
require 'strscan'

---- 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 = StringScanner.new(str).collect_token do |scanner|
    case
    when scanner.skip(/\s+/)
      # ignore
    when scanner.skip(/;.*$/)
      # ignore
    when scanner.scan(IDENT_RE)
      [:IDENT, scanner[0].to_sym]
    when scanner.scan(/#[tf]/)
      [:BOOLEAN, scanner[0] == '#t']
    when scanner.scan(/\d+/)
      [:NUMBER, scanner[0].to_i]
    when scanner.scan(/"([^"\\]+|\\.)*"/)
      [:STRING, scanner[1]]
    else
      s = scanner.getch
      [s, s]
    end
  end
  # p @tokens
  do_parse
end

def next_token
  @tokens.shift
end

---- footer
class StringScanner
  def collect_token
    tokens = []
    until eos?
      token = yield(self)
      tokens << token if token
    end
    tokens
  end
end

ファイル: list.rb

class List
  include Enumerable

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

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

  def inspect
    inject('(') do |s, v|
      s << ' ' if s.size > 1
      s << v.inspect
    end + ')'
  end
end

ファイル: main.rb

#!/usr/bin/env ruby

require 'list'
require 'list_parser'

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

ファイル: sample1.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

実行例:

> 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

参照: Revised(5) Scheme - 7. Formal syntax and semantics