オレオレ記法を作ろう！〜1.Racc入門編〜
(10/27/2017)

こんにちは！フィフス・フロア開発チームの notozeki です。最近新しい Mac を買いました。RAM がこれまでの 4GB から一気に 16GB になって快適な毎日です。

みなさんは、オレオレ記法の夢を見たことはありませんか？ Markdown 一強のこのご時世ですが、Markdown はあらゆる場面で優れた記法というわけではありません。また、Markdown の記法や記号の選び方がしっくりこない、という方もいらしゃるでしょう。そういうことに気づいたときに、もっとこうだったらいいのになと、「ぼくのかんがえたさいきょうの記法」を考え出してしまうことはありませんか？

かくいう筆者も、そんな「オレオレ記法熱」に感染してしまった人の一人です。考えた記法を紙の上に書き出してみたり、実際にその記法が使えるようにプログラムを作ってみたりもしました（当時は完成には至らなかったのですが）。そして、その熱を放出する形で筆者が開発したのが、うちのこまとめのうちのこ記法です。うちのこ記法の書き方には、筆者の好みやこだわりが多分に反映されています^[1]。うちのこ記法については、前回の記事『うちのこ記法を使ってステキなキャラページを作ろう！』に詳しくまとまっているので、実際にどんな書き方ができるかを知りたい方はそちらをご覧ください。

記法の作り方の情報は少ない

このような「記法」の作り方、あるいはその記法を扱うためのプログラムの作り方は、じつはあまり情報がありません。新しい記法を作ろうと思い立つ人も少ないのかと思います。でも、記法のプログラミングは、普通のプログラミングとは違う、新しい体験ができるものだと筆者は感じています。ぜひこの楽しさを知っていただきたいと思っています。

そこで、このブログでは、記法の作り方の解説を試みようと思います。今回から数回にわたって、うちのこ記法を作るにあたって利用した Racc というツールを使いながら、実際に簡単な記法を作っていきます。記事を読みながら、ぜひ実際に手を動かして、記法のプログラミングを体験してみてください。

第一回の今回は、Racc というツールに慣れ親しむために、簡単な電卓のようなプログラムを作っていきます。それでははじめましょう！

対象読者

この記事は、主にプログラミング初心者を想定して書かれています。サンプルプログラムは Ruby で書かれているので、実際に動かしたい場合は以下のことができることを仮定しています。

端末での簡単な作業(cd, ls, mkdir など)ができる
Rubyの開発環境が整っている
Rubyで多少プログラムを書いたことがある
gemコマンドを触ったことがある

記法をつくるとは

記法を作るということは、実際には以下のことを指します。

記法を解析し、何らかの別の形式に変換したり、表示したりするプログラムを作ること

もちろん、記法の「書き方」だけを考えることも記法を作ることと言えなくもないですが、それが頭の中や紙の上にあるだけでは、実際にその記法を使うことはできません。記法を「使う」には、その記法で書かれた文書を「解釈」して、HTML なり何なりに変換するプログラムが必要です。そのため、このシリーズは、記法を考えるだけでなく、そうした記法を解釈し、変換するプログラムを作成することをゴールとします。変換する対象は、多くの記法がそうであるように、HTML に変換します。

さて、プログラムが記法を「解釈」するとはどういうことでしょうか。そのような処理のことを専門用語で「構文解析」と呼びます。

構文解析とは

構文解析とは、与えられた文字列が、ある「決まり」に則っているかどうかをチェックすることです。そのような「決まり」のことを「文法」と呼びます。また、与えられた文字列が文法に則っていると分かった場合は、文字列のそれぞれの部分が「何」を表しているのかもわかるようになります。

たとえば、算数の式（足し算、引き算、など）を扱いたいとしましょう。このとき、

1 + 2

は、算数の式の決まり（文法）に則っていますが、

1 2 +

は則っていません^[2]。構文解析では、このようなチェックを行います。

また、1 + 2 という式をよく見ると、1 と 2 は「数」を表していて、+ は「演算」を表しています。また、「数」「演算」「数」の順番で並べることで、一つの「式」を表していることがわかります。

人間が見れば一目瞭然ですが、このような解析をプログラムでもできるようにするのが「構文解析」のしごとです。

このような構文解析をするプログラムは、書くのに一手間かかります。それを助けてくれるのか、Racc というツールです。

Raccとは

Racc は、前述した「構文解析」ができるプログラムを作るためのツールです。つまり、プログラムを作るプログラムということになります。構文解析をするプログラムはツールを使わず1から自分で書くこともできますが、一般に構文解析は複雑な処理なので、実際にはこのようなツールの助けを借りることが多いです。この記事でも、1から自分で書くのではなく、Racc に助けてもらいます。

もう少し具体的には、Racc に「文法」にあたるものを与えることで、その文法に則っているかどうかチェックする Ruby のプログラムを作ってくれます。たとえば、先程の例でいえば、「<式> というのは、<数> <演算> <数> の順番で並んだものである」というのが、「文法」にあたります。ただし、文法は日本語や Ruby では書けず、文法を書く専用の言語で書く必要があります。

Raccを使ってみよう

難しい話はこれくらいにして、実際に Racc を使って、先程の例のような「算数の式」を構文解析するプログラムを作ってみましょう。

まず、適当な作業ディレクトリに移動しましょう。以下では、ホームディレクトリの works に、racc-calc というディレクトリを作って作業することにします。

$ cd ~/works
$ mkdir racc-calc
$ cd racc-calc

次に、Racc をインストールしましょう。Racc は、Gem として提供されているので、gem コマンドでインストールできます。

$ gem install racc

さて、これで準備は整いました。まずは簡単な「文法」を書いてみましょう。先程も述べたように、文法はそれ専用の言語を使って書きます。parser.y というファイルを作って、以下のように書いてみてください。

class Parser
rule
  expr : INTEGER '+' INTEGER { puts 'ok' }
end

---- inner

def parse(text)
  @chars = text.chars
  do_parse
end

def next_token
  c = @chars.shift
  if c =~ /[0-9]/
    buf = c
    while (c = @chars.shift) && c =~ /[0-9]/
      buf << c
    end
    @chars.unshift(c)
    [:INTEGER, buf.to_i]
  elsif c =~ /\s/
    next_token
  elsif c == nil
    [false, nil]
  else
    [c, nil]
  end
end

def on_error(*args)
  puts 'ng'
end

---- footer

if $0 == __FILE__
  $stdin.each_line do |line|
    Parser.new.parse(line)
  end
end

あれ？「専用の言語」と言っていたわりに、Ruby に近い見た目ですね。実は、「専用の言語」で書くと言っていた部分は、ファイル先頭に近い rule の行と、その次の expr ... の行だけです。それ以外の部分は、ほぼ Ruby で書けます。ただし、---- inner などを見てわかるように、完全に Ruby と同じ書き方で書けるわけではないため注意してください。

`racc`コマンドの使い方

コードの解説をする前に、実際にこのプログラムを実行してみましょう。まず、Racc を使って上記のコードを本物の Ruby のコードに「作り変える」必要があります。それには、racc コマンドを使います。racc コマンドは、先程 gem install racc したときに一緒にインストールされているので、別途インストールする必要はありません。

$ racc parser.y -o parser.rb

これを実行すると、parser.rb というファイルができているはずです。

$ ls
parser.rb parser.y

このファイルは、普通の Ruby のプログラムなので、ruby コマンドで実行することができます。やってみましょう。

$ ruby ./parser.rb

実行すると、何も表示されずに固まったはずです。ここに、式を入力すると、それが式の文法に則っているかどうかをチェックできます。試しに、1 + 2 と入力してみましょう。最後に enter を押してください。

$ ruby ./parser.rb 
1 + 2
ok

ok と出ました。いいですね。次に、1 2 + と入力してみましょう。

$ ruby ./parser.rb 
1 + 2
ok
1 2 +
ng

文法に則っていないため、ng と出ます。これも期待した動作ですね。いくつか式を入力して遊んでみましょう。

一通り遊んだら、ctrl を押しながら D のキーを押すと、終了できます。

Raccの書き方

さて、なんとなくプログラムの動作がわかったところで、先程のコードを見ていきましょう。このコードは以下の3つの部分に分かれています。

文法を書く部分

まず、「文法」を書く部分です。文法はファイルの先頭に書きます。

class Parser
rule
  expr : INTEGER '+' INTEGER { puts 'ok' }
end

class は、Ruby の class と同じ意味です。Racc が作る構文解析のプログラムは、この class に指定したクラスに実装されます。

その次の、rule から end で囲まれた部分に、構文解析の中心である「文法」を書きます。文法の書き方は後で詳しく解説します。

クラスの中身を書く部分

つぎに、クラスの中身を書く部分です。「中身」なので、わかりやすいように ---- inner で区切って区別します（という Racc の決まりがあります）。

---- inner

def parse(text)
  @chars = text.chars
  do_parse
end

def next_token
  c = @chars.shift
  if c =~ /[0-9]/
    buf = c
    while (c = @chars.shift) && c =~ /[0-9]/
      buf << c
    end
    @chars.unshift(c)
    [:INTEGER, buf.to_i]
  elsif c =~ /\s/
    next_token
  elsif c == nil
    [false, nil]
  else
    [c, nil]
  end
end

def on_error(*args)
  puts 'ng'
end

ここに書いたものは、class Parser の中にそのまま置かれると考えてください。つまり、以下のような Ruby コードを書いたのと同じ意味になります。

class Parser
  # ...
  
  def parse(text)
	@chars = text.chars
    do_parse
  end
  
  def next_token
    # ...(略)...
  end
  
  def on_error(*args)
    puts 'ng'
  end
  
  # ...
end

`parse`メソッド

さて、各メソッドのはたらきを見ていきましょう。まず parse メソッドは、解析対象の文字列を受け取って、その文字列に対して構文解析をするメソッドです。まず受け取った文字列を、あとで処理しやすいように1文字ごとに区切って配列にしておきます。つぎに do_parse を呼び出して、構文解析をスタートさせます。この do_parse メソッドは、Racc が（racc コマンドを使ったときに）自動的に定義してくれます。

`on_error`メソッド

on_error メソッドは、構文解析の途中でエラーが起こったときに呼び出されます。「文法」に則っていない文字列が入力されたりすると、エラーになります。今回は、単純に ng と表示するだけにしています。

`next_token`メソッド（大事）

最後に、next_token メソッドですが、これがこのコードの中で「文法」の次に大事なコードになります。1 + 2 のような式は、1 と 2 は「数」として、+ は「演算」としてそれぞれ解釈される必要がありますが、この「数」や「演算」にあたるものを「トークン」と呼びます。next_token メソッドは、「どの文字がどのトークンにあたるか」を解析しています。「文法」は、トークンをベースにして記述していくため、next_token はいわば「文法」の補助役にあたります。

next_token の中身は普通の Ruby のコードです。parse に渡された文字列を1文字ずつ取得して、以下のことをチェックしながら、トークンを探しています。

数字があったら、INTEGER という種類のトークンとして扱う。
空白があったら、それを無視して、次のトークンを探す。
もう入力された文字がなければ、false という種類のトークンを返して、もうトークンがないことを示す。
それ以外の文字は、その文字をそのままトークンとして扱う。

クラスの外側を書く部分

最後に、---- footer の部分ですが、ここにも Ruby のコードをそのまま書くことができます。

---- footer

if $0 == __FILE__
  $stdin.each_line do |line|
    Parser.new.parse(line)
  end
end

---- inner との違いは、---- inner のコードはクラス定義の「中」に置かれるのに対して、---- footer のコードはクラス定義の「外」に置かれます。つまり、以下のような Ruby コードと同じ意味になります。

class Parser
  # ...
end

if $0 == __FILE__
  $stdin.each_line do |line|
    Parser.new.parse(line)
  end
end

このコードは、Ruby のお決まりの書き方の一つで、このファイルを直接 ruby コマンドの引数として実行したときだけ、if の中身が実行されます。ここでは、標準入力から1行ずつ読み取って、Parser クラスのインスタンスを作り、先述した parse メソッドにその行を渡して、構文解析を行っています。

文法の書き方

さて、ようやく構文解析の中心と言える「文法」の書き方について見ていく時が来ました。上記のコードの文法は以下のようになっていましたね。

expr : INTEGER '+' INTEGER { puts 'ok' }

最後の { と } で囲まれた部分は、実は「文法」ではないので、一度省略します。そうなると、文法は以下のようになります。

expr : INTEGER '+' INTEGER

文法は、「○○とは××である」のような形で書いていきます。上の例では、「expr とは INTEGER '+' INTEGER が並んだものである」という記述になります。このような一つ一つの記述を「規則」と呼びます（つまり、文法はいくつかの規則で構成されています）。規則の中身をもう少し詳しく見ていきましょう。

expr の部分は自由に指定することができます。今回は「式」を表したいので、expression の先頭を取って expr にしています。INTEGER は、先程 next_token のところで見た、「数」を表すトークンです。また、'+' は、そのまま「+」を表すトークンになります。これらのトークンが INTEGER '+' INTEGER という並びで現れたときだけ、それが expr として解釈されます。

じつは、これで「文法」についての話はほとんど終わりです。Racc は、このような形で文法を書くと、それに則っているかどうかをチェックするプログラムを自動的に作ってくれます。すごいですね。

先程無視してしまった { と } の中身についても説明しておきましょう。この中には、「その規則に当てはまるものが見つかったときに実行したい処理」を Ruby で書くことができます。そのような処理を「アクション」と呼びます。今回の例では、expr に当てはまるものが見つかった時に、ok と表示するようにしています。

引き算もしたい

ところで、この例は足し算しか扱っていませんでした。試しに引き算の式を入力してみると、ng と表示されるはずです。

$ ruby ./parser.rb
2 - 1
ng

これを、引き算もできるように拡張してみましょう。

じつは、規則のところには、「○○とは、××または△△である」という規則も書くことができます。規則を以下のように書き換えてみてください。

expr : INTEGER '+' INTEGER { puts 'ok' }
     | INTEGER '-' INTEGER { puts 'ok' }

このように、| で「または」を表し、そのあとに別の規則を続けることができます。この例では、「expr とは、INTEGER '+' INTEGER が並んだものまたは INTEGER '-' INTEGER が並んだもの」という意味になります。

実行してみます（racc で変換するのを忘れずに）。

$ racc parser.y -o parser.rb
$ ruby ./parser.rb
2 - 1
ok

うまくいきました！

トークンの「値」を使う

ところで、せっかくプログラムに「式」を認識させることができるようになったのに、計算ができなければもったいないです。たとえば、1 + 2 と入力したら 3 と出てほしいですよね。

トークンのかたち

じつは、トークンには「値」というものをつけることができます。たとえば、「数」というトークンに 3 や 100 といった「値」をつけることができます。その処理はじつはすでにやっていて、next_token の以下の部分がそれにあたります。

[:INTEGER, buf.to_i]

今まで詳しく説明していませんでしたが、next_token が返す値は、2要素の配列になっています。最初の要素にトークンの種類、最後の要素にトークンの値を入れて返します。

トークンの種類は、Ruby のシンボルで、自分で任意に指定することができます。文法を書くときにこの名前がそのまま使われるので、わかりやすい名前にすると良いでしょう。慣習上、トークンの種類は全部大文字で書くことが多いです。

トークンの値は、任意の Ruby オブジェクトにすることができます。この例では、数字が入った文字列 buf の to_i を呼び出すことで、文字列を数値オブジェクトに変換して返しています。

アクションでトークンの値を使う

トークンの値を使うと、式の計算もできるようになります。規則を以下のように書き換えてみてください。

expr : INTEGER '+' INTEGER { puts val[0] + val[2] }
     | INTEGER '-' INTEGER { puts val[0] - val[2] }

急に val という変数が登場していますが、これはアクション（{ と } の中）だけで使える変数です。Racc が自動的に定義してくれます。val は配列で、規則に書いた最初のトークンの値が val[0] に、2番目のトークンの値が val[1] に、… というふうに、トークンの値が格納されています。たとえば、1 + 2 という文字列を解析したときは、以下のような対応関係になります。

元の文字列	1	+	2
トークンの種類	`INTEGER`	`'+'`	`INTEGER`
トークンの値	`1`	`nil`	`2`
アクション内での値の使い方	`val[0]`	`val[1]`	`val[2]`

今回は、これらの値を使って、足し算や引き算を実行して、その結果を出力しています。では実行してみましょう。

$ racc parser.y -o parser.rb
$ ruby ./parser.rb          
1 + 2
3
2 - 1
1

うまくいっています！

このように、「規則にあてはまったときに、その値を使ってアクションで何かする」というのは、Racc で構文解析をする時の基本型なので覚えておいてください。

まとめ

今回は、Racc に慣れ親しむために、簡単な「算数の式」を解析するプログラムを作ってみました。このプログラムはまだまだ改良の余地があるので、余裕のある人はぜひ以下のような改良にチャレンジしてみてください。

掛け算や割り算への対応
負の数への対応
1 + 2 + 3 のような、長い式への対応

さて、これで記法を作るための下準備は完了しました。次回は、いよいよ記法を解析するプログラムの実装に入りたいと思います。お楽しみに！

参考資料

Racc の使い方
- Racc の詳しい使い方はこちらを参考にしてみてください。
プログラミング言語を作る/yaccとlex
- 上記ページは yacc というツールを使っていますが、Racc はその yacc というツールが元になっていて、文法の書き方はほとんど同じです。今回のプログラムを拡張するときの参考にしてみてください。構文解析の概念の参考にもなります。
第9章速習yacc
- こちらも yacc に関する記事ですが、構文解析の概念の参考になります。

たとえば、コメントっぽく見えるのが嫌で見出し記法を「#」ではなく「!」にしていたり、リストもなんとなく「*」ではなく「+」で、リスト要素は途中で改行できるようにしていたり、より入力し易いように全角記号も許容していたり、などなど。 ↩︎
実際には、式をこのように書く流派も存在しますが、ここでは無視します。 ↩︎

オレオレ記法を作ろう！ 〜1.Racc入門編〜 (10/27/2017)