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

Ruby esoteric

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

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

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

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とか)にするというのも考えよう。
後ちょっと気になるのは、パースメソッドで真っ先にスキャナの実装を書いてるのにパース自体はメソッド呼び出しで済ませてる点。せめてメソッド分けたいな。