極めよRuby道

第5回 Rubyで書くフロントエンドとパーザ

後藤謙太郎 <URL:http://www.notwork.org/~gotoken/mag/cmagazine/>

註: この文書は『C MAGAZINE』2000年10月号 に掲載された記事の元となるものに手を加えたものです．

記事中のプログラムを一つずつファイルにしたものもあります(→list)

中田さんのおかげでNetscapeでも読めるようになりましたが，まだちょっとカッコ悪いです。「CSSの書き方がなっとらん、こう書け」というお便りは歓迎します。

間違いを見つけたら，gotoken@notwork.org宛に御連絡くださると喜びます。

Copyright(c) 2000 by GOTO Kentaro. All rights reserved.

近況, お手軽フロントエンド Readline, お手軽コンパイラコンパイラ Racc, Racc の使い方, Racc の規則ファイルの書き方, 応用例, 手抜きをしたい場合, 参考資料

近況

ごとけんです。以前ここで書いたようにWindows2000を買ってWindowsプログラミングでも勉強しようか、と思っていたんですが、ほとんどしてません。ヒマがないというのはたぶん言い訳で、なかなかモチベーションが上がらないというのが実情だったりします。つらつら考えてみるにWindowsのユーザとしての常識がほとんどないこと、そのためUNIXで育った者にとってはちょっとしたことがひどく面倒なこと、そしてプログラマーのためのチュートリアル的ドキュメントをWeb上でなかなか見つけられないこと、etc。てな感じで言い訳を増やしていたら、WindowsでRubyする人のための本が出てました[Art]。いや違う、これは Ruby で Windows する本ですね。何しろお題がRubyなので僕にはありがたい本です。またRubyの入門書 [Har] も出たし、米国では翻訳でないオリジナルのRubyに関する書籍[TH00]が出るなどRuby界はいまちょっとした出版ラッシュになってます。以前は人にRubyを薦めても「本がないんじゃあねぇ」みたいなことをいってよく逃げられましたが、もう大丈夫そうです :-)

Rubyの良い点は挙げだしたらいろいろあるんですが*1、Rubyのようなスクリプト言語の強みの一つに、既存のライブラリやアプリケーションを組み合わせるという側面があります。これによって過去の資産を手軽に使うことができます。C言語のためのAPIを持った便利なライブラリが数多くありますが、こういったものをC言語からしか使えないのはもったいないハナシです。Rubyからこれらを使えればサンプルをちょっといじって実行してみることもたやすいので実にとっつきやすいわけで、 Rubyは標準でいくつかのライブラリを提供しています。そのうちの一つ Readlineを今回の最初のお題にします。

一方、C言語などでプログラミングしてる時に、「ここでRubyが使えたらいいのになぁ…」と思う場面は少なくないはずです。正規表現によるマッチングは好例かも知れません。またメソッドの値の多重代入が便利という人もいます。個別にはいろいろあるのですが、こういった場面が多いためにCでのプログラミングが大げさに感じられる例として、前回よりもすこし高級な構文解析器の作成を取り上げます。

お手軽フロントエンド Readline

Ruby が標準で提供する拡張ライブラリのうち、Curses、PTY、ReadlineはUNIX のTTYの機能を活用するためのものです。UNIXでも最近はGUIが花盛りのようですが、文字端末だけで出来るTTYベースのフロントエンドは処理が軽いだけでなく、script(1)コマンドを使ってログの保存も出来ますし、リモートからのアクセスでも断然有利です。ただし Microsoft Windows にはTTYというものがないので、これらをRubyから利用するにはCygwinを使う必要があります。ちなみにCursesとReadlineは前田修吾さんの作で、PTYは伊藤彰則さん*2の作です。

ここではReadlineを取り上げます。CursesやPTYについては、Rubyのソースの ext ディレクトリ以下にサンプルが一通り揃っていますので、これらを読んだり動かしたりいじったりして下さいね。またPTYの参考書としては『詳解UNIX プログラミング』[Ste92]を挙げておきます。

Readlineは名前の通りGNUのReadlineライブラリを使うものです。たとえば、 tcshやbashなどでは、Emacsもしくはviのようなキーバインドでコマンドラインを編集することが出来る、いわゆるコマンドライン編集という機能がありますね。あれを実現するものがReadlineです。1.6.0から標準でインストールされるようになったインタラクティブなRubyのフロントエンドであるirbコマンドもこれを利用しています。Solarisなどには標準ではGNUのライブラリは入っていませんのでRubyをインストールする前にGNUのミラーサイトからReadline ライブラリのソースを持ってきてインストールしておきましょう。

以下の説明ではコントロールPとかコントロールNとかが頻発するので、これらを^Pのように表します。さてReadlineでもっとも中心的な機能を提供するのは Readline::readline というモジュール関数です*3。readline は $_ に結果を代入しないことと、行末の改行を値に含めないことを除けば、getsとほぼ同様につかえます(Fig1)。オプションとして、第1引数にプロンプト文字列を指定できます。また第2引数にfalseでもnilでもない値を指定すれば入力の履歴が Readline::HISTORY という配列風の定数に記録され、^Pや^Nで過去の入力に戻ったりできます。

-- Fig1 readline は gets と似ている
  % cat readlinedemo0.rb
  #!/usr/bin/env ruby
  require "readline"
  include Readline

  while line = readline(">")
    p line
  end

  % ruby readlinedemo0.rb
  > hoge
  "hoge"
  > ^D
  %

Readlineの機能をもっと多用した例をList2に掲げます。この例では、コマンドライン編集の他に登録されたコマンドを^I(タブ)でコマンドを補完したり補完候補を表示することが出来ます。この例でのコマンドとはString のメソッドにしており、コマンドの第1引数がレシーバ、第2引数以降がメソッドの引数になっています。たとえば「sub! ab b B」に対して、「aB」を返します。補完を実現するためには Readline::completion_proc にProcオブジェクトを設定しておきます。Readlineが用意しているProcもありデフォルトではファイル名補完を行なう Proc *4 が設定されています。補完用にはこの他に、ユーザ名を補完するための Proc *5 も用意されています。

List2で#1と#2のあいだは、readlineの実行中に^Cが押されたときに端末属性が回復されないことへの対策です。割り込みSIGINTをトラップして stty(1)を実行することで端末属性を回復しています[RDP]。この技法は端末属性を回復できないような他のライブラリに対しても有効です。この例のように、組み込み関数 trap はシグナルをハンドルするのに使いますが、ブロックでシグナルに対する処理が指定できるのは便利です。

ところで、少しはなしは変わりますが、ブロックで処理が指定できて便利といえば、やはり組み込み関数である fork もそうです。forkはUNIX で子プロセスを作る方法ですが、次のように書くことができます。

fork do 
  # 子プロセスでの処理
end

forkは親プロセスでは子プロセスのプロセスIDを返し、子プロセスでは nilを返すので伝統的な書き方もできますが、ブロック化されることで子プロセスの処理がどれかが分かりやすくなるのはうれしいことです。なお、Ruby での「関数」とはプライベートメソッドのことで、プライベートメソッドとはレシーバを明示的に指定できないという制限のついたメソッドのことです。つまり、fooがプライベートメソッドならば、

obj.foo(arg)

のようには呼び出せず、必ず

foo(arg)

のように呼び出す必要があります。これを関数と言っているわけです。そして組み込み関数は Kernel というモジュールで定義されています。

閑話休題。このList2の例では引数をそのまま文字列として渡すので使えないメソッドもあります。一方でドキュメントされていない機能を使うこともできます。次の入力を与えてみましょう。

[]= noko no hiro

実は 1.4 の途中から str["no"]="hiro"のようにインデックスとして文字列や正規表現を与えるとstr.sub!("no", "hiro")として機能するようになってます。マニュアルに載ってないのでこの機能が将来もあるかどうかは分かりませんけど。

Readlineを使ったもっと凝った例としてグラフ作成ツールGnuplotで画面に描いた3次元グラフをvi風のキーバインドで回転させるという拙作のgpvというツールもあります[GPV]。興味のある方は御覧下さい。

-- List2 readlinedemo1.rb: readlineの利用例
  #!/usr/bin/env ruby
  require "readline"
  include Readline

  Prompt = File::basename($0) + "> "
  Command = "".methods
  Readline::completion_proc = proc{|p|
    Command.grep(/^#{p}/)
  }

  stty_save = `stty -g`.chomp        #1
  trap("INT"){ 
    system "stty", stty_save; exit
  }                                  #2

  while line = readline(Prompt, true)
    next if /^\s*$/ =~ line
    cmd, rec, *arg = line.split
    if !Command.find{|i| i == cmd}
      puts "No such methods"
      next
    elsif !rec
      puts "no receiver specified"
      next
    end

    begin
      val = rec.__send__(cmd, *arg)
      puts %Q(value:    #{val.inspect})
      puts %Q(reciever: #{rec.inspect})
    rescue
      puts $!
    end
  end

お手軽コンパイラコンパイラ Racc

Readlineを使うと、インタラクティブなシェルを簡単に作ることが出来ます。そうすると、自分のシェルの機能をだんだんと拡張させていくうちに、今度は簡単な言語を作ってしまいたくなる人もいるかも知れません。正規表現で解析できる範囲の言語を設計するのは楽しいものです。けれども、ある一線を踏み越えると正規表現では解析できなくなってしまいます。そのことを知っている人は言語を作るにはそれなりに意気込みが必要だと思われるかも知れません。しかしRuby ならなんとも簡単にはじめることができちゃいます。それはracc のおかげです。RaccはRubyに標準ではついていないので[RAA]から持ってきてインストールしましょう。なお以下の説明では執筆時点での最新版であるRacc 1.2.4を仮定しています。

あおきみねろうさんの作であるraccはコンパイラコンパイラと呼ばれるものの一種で、文脈自由言語の実用的な部分クラスであるLALR(1)という言語クラスの解析器をRubyのプログラムとして生成します[Aok]。C言語でのパーザプログラミングではyaccというコンパイラコンパイラが古くから使われています。またGNU版のyaccであるbisonを実行時につかうRuby用のコンパイラコンパイラとしてrbisonというものもあります[Ase]。RaccのメリットはRuby だけでパーザが作れるということです。パーザ自体は結構速いので、実用に耐えることも少なくありませんし、大規模なものを作る場合でもyaccで組む前のプロトタイピングで重宝します。論より証拠、まずは実例をみてみましょう。

パーザの典型例として算術式を考えてみます。「-2-5/(1+2^2)」という算術式を取り上げましょう。ここで「2^2」は2の2乗を表すものとします。この式では、先頭の「-」と2番目の「-」は異なる意味をもち、また2番目の「-」の前に「/」を計算しなければなりませんし、さらにその前にカッコで囲まれた部分を計算する必要があります。カッコの中も「+」より先に「^」を計算すべきです。

いいかえると、括弧がない場合の演算子の結合強度は、CやRubyでは単項のマイナスが最強で、その次がベキ*6、そして乗除、加減の順になっています。

そして算術式というのは上の結合の強さの約束のもとで再帰的な構造をした文字列で、この構造を <式> と呼ぶことにすると次の形をしています。

<式> は      <式> "+" <式>
     または  <式> "-" <式>
     または  <式> "*" <式>
     または  <式> "/" <式>
     または  <式> "^" <式>
     または  "(" <式> ")"
     または  "-" <式>
     または  <数>

これを表現したのがList3で、racc にサンプルとしてついてくるcalc.yというファイルの文法定義部分に手を加えたものです。詳細はのちほど解説しますが、上に書いた文法がそのまま表現されていることは御覧になってなんとなく分かると思います。また解析と同時に評価も行なっています。

-- List3 calc.y: 算術式の文法規則(Raccに付属のsample/calc.yを改変)
  class Calcp

    prechigh
      nonassoc UMINUS
      right '^'
      left '*' '/'
      left '+' '-'
    preclow

  rule

    target: exp
          | /* none */ { result = 0 }
          ;

    exp: exp '+' exp { result += val[2] }
       | exp '-' exp { result -= val[2] }
       | exp '*' exp { result *= val[2] }
       | exp '/' exp { result /= val[2] }
       | exp '^' exp { result **= val[2] }
       | '(' exp ')' { result = val[1] }
       | '-' exp  = UMINUS { result = -val[1] }
       | NUMBER
       ;

  end

Racc の使い方

規則ファイル calc.y (List3)からパーザを得るには「racc calc.y」を実行します。結果として calc.tab.rb という名前のRubyで書かれたパーザプログラムのファイルが生成されます。このファイルは class で指定された名前のパーザクラス Calcp を定義するものです。このパーザの中心はそのクラスの do_parse というプライベートメソッドです。

Raccが作ったパーザを使う場合、ほかに最低限用意しないといけないものは、文字列をトークンに分解するスキャナと、このスキャナの結果を do_parse に渡す next_token というメソッドです。これらのコードは規則ファイルに含めることもできますが、ここでは説明のために別々に用意してみます。

典型例として、calc.y から作られた calc.tab.rb を利用した電卓プログラム calc.rb をList4に示します。このプログラムは入力された文字列を parse に渡し、その値をputsしています。parse の定義をみると、まず scan して、そのあと、do_parse を呼んでいます。

scan では配列 @q をキューとして使っています。scan の役割は str をトークンの列に分解し、@q というキューに順に格納することです。みて分かるように、ここでのトークンとは

[トークンシンボル, 値]

という形の配列です。トークンシンボルは現れる規則ファイルで使われるトークンの名前で List3 では NUMBER がそうです。ここではその他のシンボルは文字列そのもので代用しています。一方、値とは評価に使われるもので、規則ファイルの中では val という配列の要素として参照されます。

一方、next_token はキュー @q から順に値を取り出しています。これ以上入力がないことをdo_parseに告げるために、最後に [false, 何か] という形のトークンを渡す必要があります。until ループを抜けたあとで「@q.push [false, "$end"]」しているのはそのためです。

-- List4 calc.rb: 簡単な電卓プログラム
  #!/usr/bin/env ruby
  require "calc-d.tab"
  require "readline"
  include Readline

  class Calcp
    def parse(str)
      scan(str)
      do_parse
    end

    private

    def scan(str)
      @q = []
      until str.empty?
        case str
        when /\A\s+/  # 空白は飛ばす
          # skip
        when /\A\d+/  # 数字の連なり
          @q.push [:NUMBER, $&.to_i]
        when /\A.|\n/ # その他は1文字
          s = $&
          @q.push [s, s]
        end
        str = $'
      end
      @q.push [false, '$end']
    end

    def next_token
      @q.shift
    end
  end

  parser = Calcp.new
  while line = readline("> ", 1)
    begin
      puts parser.parse(line)
    rescue ParseError
      puts $!
    end
  end

Racc の規則ファイルの書き方

Racc の規則ファイルの書き方は yacc に似ていて、do_parse のはたらきは yacc の作る yyparse() に相当します。ところでraccの作者のあおきさんは付属のドキュメントにこんなことを書いています「racc は yacc を知っていることを前提にしていますので、もし知らないのなら 先に yacc を勉強しましょう。いきなり racc を使うのは不可能です。(これは断言できます)」。ええー、そんなあ。しかし、yaccのすべてを学んでおかなくても結構使うことはできます(これは断言できます :-)ので、簡単に紹介しますね。これを機にyaccの勉強をはじめてみたい方にはNutshellシリーズの『lex&yacc プログラミング』[LMB]がオススメです。

さてRaccでの文法記述を説明する前に、yacc流の「文法」について少々説明しておきますね。まず、前に挙げた「-2-5/(1+2^2)」という式の構造を木で表現したのがFig5です。文法とはこのような構造を持った文字列を指定する方法にほかなりません。いいかえれば文法とは木構造における枝分かれのパターンの集まりのことです。パーザの役割は与えられた文字列を文法にしたがって木として組み立てることです。そして文法記述からパーザを作るのがraccです。

この木の根(一番上)に位置することができるものをスタート規則と呼びます。 List3の例では、 target がスタート規則となります。スタート規則は省略されると一番最初に書かれた規則がスタート規則になります。一方、葉(先っぽ) に位置しているのがトークンです。厳密にはそれぞれの演算子記号は同じ名前のトークンなのですが、省略して書いています。

-- Fig5 式「-2-5/(1+2^2)」の構造

              target
                 |
                exp
                 |
         +-------+-------+
         |       |       |
        exp     '-'     exp
         |               |
    +----+----+     +----+----+
    |         |     |    |    |
   '-'     NUMBER  exp  '/'  exp
              2     |         |
                 NUMBER  +----+----+
                    5    |    |    |
                        '('  exp  ')'
                              |
                         +----+----+
                         |    |    |
                        exp  '+'  exp
                         |         |
                      NUMBER  +----+----+
                         1    |    |    |
                             exp  '^'  exp
                              |         |
                           NUMBER    NUMBER
                              2         2

さて、raccやyaccの文法記述は、規則の並びで、一つの規則は次の形をしています:

規則名 : 規則列1 { アクション1 } 
       | 規則列2 { アクション2 } 
         ・
         ・
         ・
       | 規則列n { アクションn }
       ;

ここで「|」は「または」を意味します。また、{ アクション } は必要でなければ書きません。便宜上「:」の左に来る規則名を左辺、残りを右辺と呼ぶことにしましょう。

各規則には、アクションはその枝を組み立てる際に行なう動作で、もちろん Ruby で記述します、大抵の場合、変数 result に値を代入することで左辺の値とすることがアクションの目的です。またアクションでは val という配列を使うことができ、規則列のi 番目の値を参照できます。resultの初期値として val[0] が使われます。List3 のNUMBERの規則はこの初期値のきまりがあるので値resultを作るためのアクションを指定していません。また他の規則でいきなり 「result += val[2]」などとできるのも初期値のおかげです。

さて、規則ファイル全体は規則部とユーザーコード部からなります。ユーザーコード部は規則部の後に来なければなりません。規則部は一般には次のような形をしています。

class クラス名
  [演算子順位]
  [トークン宣言]
  [オプション]
  [トークンシンボル値おきかえ]
  [スタート規則]
rule
  文法記述
end

紙面の都合で「オプション」、「トークンシンボル値おきかえ」についての説明は省略します。演算子順位は結合の強さを指定するもので、List3のように prechighとpreclowのあいだに挟んで強い順に書きます。List3に出てくる UMINUSというのは結合強度を指定するために用意されたトリックで、規則部で「= UMINUS」と書かれた部分の結合強度を指定するために書いた疑似的なトークンです。また、left と right はその演算子の結合性の左右を表しています。例えば左結合性の四則演算子を連ねた場合、

2*3*2

は

(2*3)*2

のように左から順にひっつきますが、左結合性の「べき乗」演算子は、

2^3^2

の場合、

2^(3^2)

のように右からひっつきます。単項のマイナス記号は2つのものを結合するわけではないので、そのことを表すために nonassoc を指定しています。

応用例

さて、これだけのことが分かれば、raccで書かれたパーザをとりあえず読めると思います。たとえば、rdtoolのインラインパーザ[Tos]などを読んでみると前回面倒なので断念した「入れ子になったRDのインライン」がサクっと書けちゃうのも分かるでしょう。これにもとづいたRDoのインライン対応はRAA に登録しておきましたので、前回の続きが気になる方は御覧下さい[RDO]。

手抜きをしたい場合

ここで参考までに述べておくと、算術式のような文字列を正規表現だけで解析するのは一般は不可能なことが昔から知られています[ASU][HU]。 Ruby の正規表現は拡張されているので不可能ではないのかも知れませんが、すごく困難であることには違いありません。

ところが Ruby の文法に収まる範囲の算術式を評価することが目的ならば eval してしまうという技もあるので、覚えておくと助かることもあるかも知れません。List6は入力行をevalするだけのものですが、電卓としても立派に使えますし、小数も使えます*7。当たり前だけど変数も使えますし、mathn をロードしているのでなんと分数も使えます。つまり 1/2 + 1/3 を入力すると、5/6 と答えます。

しかし、この電卓はちょっとでもRubyの文法を逸脱してしまうと使えません。それに、そもそも irb に -m オプションをつけて使えば良いという話もあります。またevalを使うとユーザになんでもできてしまうので場合によっては危険でしょう。$SAFEに1や2を設定することで危険な操作を禁止することもできなくはないですが、そうすると使いたい機能まで使えなくなることもあります。たとえば、CGIなどで想定されるセキュリティレベルである $SAFE=1 でも system は使えません。なお$SAFEに3以上を指定するとevalも使えません*8。

-- List6 toyrb.rb: ズボらな電卓
  #!/usr/bin/env ruby
  require "readline"
  require "mathn"
  include Readline

  stty_save = `stty -g`.chomp
  trap("INT"){ 
    system "stty", stty_save; exit
  }

  while line = readline("> ", 1)
    begin
      puts last = eval(line)
    rescue Exception # 全て捕捉
      puts $!
    end
  end

参考資料

[Art]

arton, 『Rubyを256倍使うための本 邪道編』, アスキー (2000)

[Aok]

Minero Aoki, ``Racc'', <URL:http://www.ruby-lang.org/en/raa-list.rhtml?name=Racc>

[Ase]

Jonathan Aseltine, ``rbison'', <URL:http://www.cs.umass.edu/~aseltine/rbison.html>

[ASU]

Alfred V. Aho, Ravi Sethi and Jeffrey D. Ullman, ``Compilers - principles, techniques and tools'' (通称 Dragon book), Addison-Wesley (1986) (原田賢一訳, 『コンパイラ I』, サイエンス社)

[Ful]

Hal Fulton, ``Thirty-seven reasons I love Ruby'', <URL:http://www.hypermetrics.com/ruby37.html>

[GPV]

Kentaro Goto, ``gpv'', <URL:http://www.notwork.org/~gotoken/ruby/p/gpv/>

[Har]

原信一郎, 『Rubyプログラミング入門』, オーム社 (2000)

[HU]

John E. Hopcroft and Jeffrey D. Ullman, ``Introduction to automata theory, languages and computation'', Addison-Wesley (1979) (野崎昭弘, 高橋正子, 町田元, 山崎秀記訳, 『オートマトン 言語理論 計算論 I』, サイエンス社)

[LMB]

John R. Levine, Tony Mason and Doug Brown, ``lex & yacc'', O'Reilly & Associates (1991), (村上列訳『lex & yacc プログラミング』アスキー)

[MI99]

まつもとゆきひろ，石塚圭樹，『オブジェクト指向スクリプト言語Ruby』， pp460-462, 「9.8.13 セキュリティチェック」, アスキー出版局 (1999)

[RAA]

``Ruby Application Archive'', <URL:http://www.ruby-lang.org/en/raa.html>

[RDP]

Readline, (Ruby Documentation Project <URL:http://www.oishi.info.waseda.ac.jp/~takashi/rubikitch/RDP.html> の一つ。Readlineの文書はあらいさんによるもの。RDPではボランティア募集中です)

[RDO]

gotoken, ``RDo'', <URL:http://www.ruby-lang.org/en/raa-list.rhtml?name=RDo>

[Ste92]

Rechard Stevens, ``Advanced programming in the UNIX environment'', Addison-Wesley (1992) (大木敦雄訳, 『詳解UNIXプログラミング』, ソフトバンク)

[TH00]

Dave Thomas and Andrew Hunt, ``Programming Ruby: The Pragmatic Programmer's Guide'', Addison-Wesley (2000)

[Tos]

Tosh, ``RDtool'' に含まれる ``rd/rdinlineparser.ry'' <URL:http://www.ruby-lang.org/en/raa-list.rhtml?name=RDtool>

[Ruby] Rubyどうでしょう
著者: 後藤謙太郎
御意見，御感想，御批判の宛先: gotoken@notwork.org

*1 ある人は実際に37個挙げています[Ful]
*2 あ伊藤さんはWebブラウザ w3m の作者としても有名
*3 モジュール関数とはそのモジュールの特異メソッドでもあるようなメソッドのことです。特異メソッドとはそのオブジェクトだけに定義されたメソッドのこと。
*4 Readline::FILENAME_COMPLETION_PROC
*5 Readline::USERNAME_COMPLETION_PROC
*6 UNIXのbcコマンドなどではベキが最強で単項のマイナスの方が弱くなってます。これは数学の記法に似ています。
*7 eval は小数を表す文字列をもっとも簡単に Float オブジェクトにする方法です
*8 セキュリティレベルを表す $SAFE の 詳細はRuby本[MI99]を参照して下さい