Racc で HQ9+

そうしたら HQ9+言語を作ってみよう、言語自体の説明は「奇妙な言語」p.32 にある。

1. H があったら「Hello world!」
2. Q があったら Quine、実行中のソースの一覧
3. 9 があったら 99本のビール文書
4. + があったらカウンタの値を 1増やす

class HQ9Plus
rule# class HQ9Plus

  program :
          | program 'H' {puts "Hello world!\n"}
          | program 'Q' {puts @source}
          | program '9' {puts ninety9_bottles_beer}
          | program '+' {@count += 1; @racc_debug_out.puts @count if @yydebug} # (A)

end # class HQ9Plus

---- inner
def initialize(source)
  @source = source
  @count = 0
end # def initialize(source)

def scan
  @source.each_char{ |hq9p| yield [hq9p, nil] if /[HQ9\+]/ =~ hq9p }           # (B)
  yield nil
end # def scan

def parse(opts = nil)
  @yydebug = opts.yydebug if opts.respond_to? :yydebug
  yyparse self, :scan
end # def parse(opts = nil)

private
def ninety9_bottles_beer
  (0..99).to_a.reverse.inject('') do |nnbb, b|
    case b
      when 0 then before, after = 'no more bottles', '99 bottles'
      when 1 then before, after = '1 bottle', 'no more bottles'
      when 2 then before, after = '2 bottles', '1 bottle'
      else before, after = "#{b} bottles", "#{b-1} bottles"
    end # case b

    action = (b == 0 \
      ? 'Go to the store and buy some more' \
      : 'Take one down and pass it around'
      )

    nnbb << "#{before.capitalize} of beer on the wall, #{before} of beer.\n"
    nnbb << "#{action}, #{after} of beer on the wall.\n"
    nnbb << "\n" unless b == 0
    nnbb
  end # (0..99).to_a.reverse.inject('') do |nnbb, b|
end # def ninety9_bottles_beer

---- header
# -*- coding: utf-8; -*-
Version = '$Id: hq9plus_string.y 3239 2009-01-31 06:47:53Z hs9587 $'
# $Date: 2009-01-31 15:47:53 +0900 (土, 31 1 2009) $

---- footer
require 'optparse'
require 'ostruct'
opts = OpenStruct.new
opts.yydebug = false

ARGV.options do |opt|
  opt.on('--[no-]yydebug', 'debug mode (from racc -g) on/off'){ |v| opts.yydebug = v }
  opt.release = 'H Q 9 +'
  opt.banner += "\n\tHQ9+ interpreter.\nOptions:"
  opt.parse!
end # ARGV.options do |opt|

HQ9Plus.new((ARGV.size > 0 ? ARGF : $stdin).read).parse(opts)

ninety9_bottles_beerメソッド(殆ど「奇妙な言語」のロジックの儘です)が少し面倒臭いだけで特に問題ないと思う。
Quine には @source を使うようにしていて良かった。intialize でカウンタも初期化しておく。
デバッグモードの時は増やしたカウンタの値を出力するようにした、 @racc_debug_outインスタンス変数はデバッグ出力の際の出力先を保持している。普通は標準エラー出力になるでしょう。
規則部分で終端記号を文字(String)自体にしてるので、scanメソッドではとくに case分けせず文字をそのまま送ってやれば良いのだった (B) ちなみにHello world! 言語のときのスキャナで「if 'H' == h」 の様な比較をしていたのはここの正規表現マッチと平仄を合わせる為もあった。

「Hello world! 言語」再び

前記、スキャナを別メソッドにする、そしてその辺の呼び出しは yyparse を使う、@queue のようなものは必要なくなった。initializeメソッドで @sourceインスタンス変数にソースを格納するようにしてみる。あと、デバッグオプションは OptionParser と OpenStruct を使う。OptionParserのメッセージ類も少し書く。
「---- header」セクションも作ってバージョンなど。それからマジックコメントもここに書いておく、しかし実行ファイルの本当の先頭にコピーされるわけではないので余り意味はない。

class HParser
rule# class HParser

  program :
          | program 'H' {puts "Hello world!\n"}

end # class HParser

---- inner
def initialize(source)
  @source = source
end # def initialize(source)

def scan
  @source.each_char{ |h| yield [h, nil] if 'H' == h }
  yield nil                                                 # (A)
end # def scan

def parse(opts = nil)
  @yydebug = opts.yydebug if opts.respond_to? :yydebug
  yyparse self, :scan
end # def parse(opts = nil)

---- header
# -*- coding: utf-8; -*-
Version = '$Id: Hhyy.y 3236 2009-01-31 06:00:02Z hs9587 $'
# $Date: 2009-01-31 15:00:02 +0900 (土, 31 1 2009) $

---- footer
require 'optparse'
require 'ostruct'
opts = OpenStruct.new
opts.yydebug = false

ARGV.options do |opt|
  opt.on('--[no-]yydebug', 'debug mode (from racc -t) on/off'){ |v| opts.yydebug = v }
  opt.release = '0.1'
  opt.banner += "\n\tH the 'Hello world!' interpreter.\nOptions:"
  opt.parse!
end # ARGV.options do |opt|

HParser.new((ARGV.size > 0 ? ARGF : $stdin).read).parse(opts)

入力の終わり、next_tokenメソッドを使っていたときは @queue が最後に nil を返してくれたが、今の場合は明示的に nil を yield してやる (A)。

Raccで作る奇妙なプログラミング言語

Rubyで作る奇妙なプログラミング言語 ~Esoteric Language~

を読んだ。奇妙な言語の紹介と Ruby での実装、いろいろ勉強になるし、実に楽しい。良い本だと思う(以下「奇妙な言語」)。それはそれとして、折角 Ruby なんだから、Racc で言語作ろうよとも思った、Ruby 用の LALR(1) パーザジェネレータ。

• Racc
• "racc 1.4.6"
• 結局一番参考になるのは無道編になるのか

  Rubyを256倍使うための本 無道編

  (以下「無道編」)

Racc の復習と「Hello world! 言語」

そもそも Racc の基本的な使い方ってどんなだっけ、復習がてら「HQ9+」の基礎にもなる、「Hello world! 言語」インタプリタを作ってみる、「H」があったら「Hello world!」と出力するだけの言語です。
基本の流れ

1. 文法ファイル「H.y」を書く、典型的には拡張子は「.y」或は「.ry」という説もある
2. raccコマンドでパーサ、インタプリタを作る「racc H.y」
   • コマンドオプション適宜(racc --help)、-t (又は -g)でデバッグモードのものを作る
   • -v でパーサの構造を示す「.output」ファイルも出力する
3. 出来た「H.tab.rb」を実行する
   • 拡張子「.tab.rb」の出力ファイル名は -oオプションで変更出来る

ということで文法ファイル

class HParser
rule

  program :
          | program H { puts "Hello world!\n" }

end

---- inner
def parse(source)
  @queue = []                                             # (A)
  source.each_char{ |h| @queue << [:H, nil] if 'H' == h } # (B)
  #@queue << [false, nil]                                 # (C)

  #@yydebug = true
  do_parse
end # def parse(source)

def next_token
  p @queue if @yydebug
  @queue.shift
end # def next_token

---- footer
HParser.new.parse((ARGV.size >0 ? ARGF : $stdin).read)    # (D)

取り敢えず Racc の文法ファイルに必要なのは次の通り

1. クラス定義の中の rule セクション、文法とアクションを書く
2. 「---- inner」セクション
   1. do_parse プライベートメソッドを呼ぶパースメソッド
      • これは広義のパース。即ち、まず真っ先にソースをスキャナにかける (B)
   2. next_token プライベートメソッド
      • スキャナが与える次のトークンを返すメソッド、ここで再定義しないと「#next_token is not defined (NotImplementedError)」エラー
      • まあ、#shift だよね。ちなみに @queue インスタンス変数の名前は何でも良い、@q とか。分かり易く名付ける (A)
3. 「---- footer」セクション
   1. 実際にソースを取ってきてパースを実行する処理 (D)

取り敢えずと言ってるのは、「do_parse, next_token」じゃなくて「yyparse」を使う書き方に移行したり、仕様が大きくなって来ると、inner や footer セクションに書いてるのはファイルを分離するようになるという含み。
@yydebug インスタンス変数は、-t(-g) オプションつきでパーサを作っているときのデバッグ出力のオン/オフ、ついでのスキャン結果のトークン列も出力するようにしてみた。これは起動オプションみる様にしてもいいかな。
それから (C) について。本来、入力が終わったらその印に [false, ＜何か＞] を送ってやることになっている。だが、「無道編」p.63 にもあるように nil でも終わりと見做されるのでこの行はコメントアウトしても大丈夫だった。next_token は @queue が空配列なら Array#shift で nil を返す。
最後パーサを実行するところ (D)「奇妙な言語」p.33 にもあるのだけど、どういう形でパーサを呼び出すかは諸説ある。取り敢えずパーサインスタンスを new して、その parseメソッドにソースを与えるようにしてみた。余裕が出来たらソースを与えてパーサインスタンスを new するようにしよう。また、parseメソッドはパースするだけで実際実行するのは更に別メソッド(evaluateとか)にするというのも考えよう。
後ちょっと気になるのは、パースメソッドで真っ先にスキャナの実装を書いてるのにパース自体はメソッド呼び出しで済ませてる点。せめてメソッド分けたいな。