作ろう、ミニ言語

この記事はアピリッツの技術ブログ「DoRuby」から移行した記事です。情報が古い可能性がありますのでご注意ください。

TL;DR

yaccライクなRuby製パーサジェネレータであるRaccを使ってLISPもどきのREPLを実装する。

作ってみよう、処理系

さて、プログラミングがよくわからない文系エンジニアの自分も新卒２週目となったので、簡単なコードなら書けるようになってきた。

最近はプログラミングの基礎をちょくちょく勉強している。(難しくてよくわからないけれど)。今日はその一貫として比較的ポピュラーな遊び、ミニ言語の処理系実装をしてみる。

処理系ってなんだ？ 簡単にいうと、テキストとして書かれたプログラムを実行するためのプログラムだ。単に処理系といってもコードを読んで他言語に変換して実行するコンパイラとそのまま読んで実行するインタプリタがあるが、今回やるのは後者のインタプリタ。もっと言えばRubyのirbのような対話型評価環境(REPL)だ。

それじゃまずは言語の設計からやってみよう。とはいっても、今回は難しいことをしない。この言語に出来ることはとても簡単だ。

• 四則演算
• 変数の宣言と利用
• 値の出力

以上のみ。制御文くんのことは諦めよう、実装すると記事の長さが３倍くらいに伸びる。文法はLispのS式を踏襲する。理由はS式のための処理系はとても簡単だから。この言語の構文を言語の構文を表現するための記述方法であるBNF(バッカス・ナウア記法)で書くとこんな感じ。

    <code>    ::= <code> <s_exp> | <s_exp>
    <s_exp>   ::= '(' <func> <params> ')' 
    <param>   ::= <s_exp> | <atom>
    <params>  ::= <params> <param> | <param>
    <func>    ::= <text> | <identifier>
    <atom>    ::= <number> | <text> | <identifier>

うん、シンプルだね。ちょっとだけBNFの読み方について説明しよう。::=の左側が構成を定義される記号、そして右側がその記号の構成という表記だ。「|」は「または(or)」という意味で構成は複数ありえるというワケ。左側に置かれ定義されていないnumberやtextは終端記号と呼ばれる、これ以上分割できない単位だ。

例えば一番上のcodeは「codeは、code + S式の連続か、あるいは一つのS式から構成される」という意味になる。codeが自己参照しててややこしいが、要するに「codeは１つ以上のS式から構成される」ということを言っている。

レシピ

さて、実際どうやって作るか？ コード生成しなくていいのでコードを字句(token)へ分解する字句解析部(lexer)と、それによって作られる字句を意味を持つ構文として解釈する構文解析部(parser)の２つだけあればいい。

それぞれを行うために色々なツールがあるが、今回はRubyで書きたいのでRuby製のパーサージェネレータであるRaccで作る構文解析器とStringScannerによる字句解析で作ってみる。

パーサージェネレータというのはその名前の通り構文解析器(parser)を生成(generate)するプログラムだ。どういうことかというと、先に書いてきたようなBNFなどで記述した導出規則から構文解析器を生成してくれる。仕様からプログラムが出来るなんて夢のようだな。

Raccは構文の規則を記述したDSLコードを元に実行可能なRubyファイルを吐き出す仕組みになっている。今回書かないといけないのはこのDSLコードだけ。

コーディング

おっしゃ、早速やっていこう。その前に言語へ名前をつけよう。Raccで作るからRacoonという名前にしておく。

lexer

まずは字句解析しよう。Raccでは実装しなければならないメソッドが決まっており、まずparseメソッドへ文字列が渡されてくるので、それをトークンへ分割しなければならない。そしてparseメソッド内でdo_parseメソッドを呼び出して構文解析器を動かす。

構文解析器ではnext_tokenメソッドをnilが出るまで呼び出し続けて解析していく。そこで、ここでは分割したトークンを配列@qとして保持してnext_tokenが呼ばれた時にshiftメソッドで切り渡していく。

---- header
require 'strscan'
require 'pp'

attr_accessor :racoon

def parse(str)
  # StringScannerを使ってトークン単位に分割する
  scanner = StringScanner.new(str)
  @q = []
  until scanner.eos?
    scanner.scan(/#[^\n]*\n/) ? nil  : # 改行は無視
    scanner.scan(/\s+/)       ? nil  : # スペースも無視
    scanner.scan(/\d+/)   ? @q << [:DEC, scanner.matched] : # 連続した半角数字を１０進法の数とする
    scanner.scan(/[\(|\)]/)       ? @q << [scanner.matched, scanner.matched] : # ()はS式の基本
    scanner.scan(/[a-zA-Z0-9\-\_\/]+/) ? @q << [:TEXT, scanner.matched] : # とりあえず半角英数のみ
    scanner.scan(/./)     ? @q << [:ID, scanner.matched] :  # 他の全ての文字列は識別子扱い。全角文字のことは諦めよう
    nil
  end
  #pp @q
  do_parse
end

def next_token
  @q.shift
end

じゃ、試しにトークンへ分割してみよう。

"(+ 1 2)"
=> [["(", "("], [:ID, "+"], [:DEC, "1"], [:DEC, "2"], [")", ")"]]

"(var seven (+ 3 4))"
=> [["(", "("], [:TEXT, "var"], [:TEXT, "seven"], ["(", "("], [:ID, "+"], [:DEC, "3"], [:DEC, "4"], [")", ")"], [")", ")"]]

良さそうだ。じゃ、次はこのトークンの集合を構文解析部へ渡して組み立ててもらおう。

parser

Raccに規則部分を記述する。これはBNFをほとんどそのまま書けば良い。少し細かい記述の違いがあるのでちょっと修正する。

class RacoonParser
rule
    start code
    code    : code s_exp
            | s_exp
    s_exp   : '(' func params ')' { result = @racoon.send(val[1], val[2]) }
    param   : s_exp
            | atom
    params  : params param { result = val[0..1] }
            | param
    func    : TEXT
            | ID
    atom    : DEC
            | TEXT { result = @racoon.vars[val[0]] if @racoon.vars[val[0]] }
            | ID
end

一部の右辺にブロックが記述してあるが、これは省略されているだけで全ての右辺について処理が存在する。デフォルトの挙動はおそらく{ result = val[0] }。

Raccは構文を解釈できると構文木の末端から順にブロック内の処理を行う(raccはyaccと同じくLALRなので左側から)。そして、resultに格納された末端の処理結果は上位の処理にvalとして渡される。わかりにくい？ 例文を追ってみよう。

(+ 1 (+ 2 3))というコードはまず1の部分を評価する。1は計算の必要がないのでそのまま1だ。次に(+ 2 3)が評価され、5へ簡約される。(+ 1 5)となり、最後にこのS式が評価されるので6が得られる。

s_exp : ‘(‘ func params ‘)’ { result = @racoon.send(val1, val[2]) }

この規則のブロックにあてはめてみよう。例えば(+ 2 3)はresult = @racoon.send('+', [2, 3]) => 5になるというワケ。

見ての通り、@racoon(環境相当のオブジェクト)には四則演算や出力命令、変数命令を行うためのメソッドを実装する必要がある。ここについては何も難しいことはないのでコードだけ。

class Racoon
  attr_accessor :vars

  def initialize
    @vars = Hash.new
  end
# 面倒なので四則演算をまとめて定義
  %w(+ - * /).each { |id| define_method(id) {|args| args.flatten.map(&:to_i).inject(id.to_sym)} }

# 変数宣言varはハッシュオブジェクトに{変数名: 値}という形で変数を保持する。
# スコープ？ 大域変数しかないよ。
  def var(args)
    variable_name, value = args
    @vars[variable_name] = value
  end

  def display(args)
    puts "=> #{args}"
  end
end

仕上げ

対話的な部分はgetsを使ってloopを回すだけ。せっかくなので寿司でもつけよう。

---- footer
parser = RacoonParser.new
line_count = 0
loop do
  begin
    line_count += 1
    print "#{line_count.to_s.rjust(3,'0')} <U+1F363>  > "
    parser.parse(gets)
  rescue Racc::ParseError => e
    $stderr.puts e
  end
end

最後に今まで書いてきたソースコードを元にraccを使ってパーサーを生成してから実行する。

racc -g -o racoon_parser.rb racoon.y; ruby racoon_parser.rb;

たのしい！