オブジェクト指向パーサジェネレータ「Metal」based on Parsing Expression Grammar

Parsing Expression Grammar (PEG)をベースとした構文解析器を生成するパーサジェネレータMetalを作りました。Rubyで書かれており、Rubyのコードを生成します。 Metalの多くはOMeta: an Object-Oriented Language for Pattern MatchingをRubyに移植したものです。
Metalの特徴‥ ●Rubyでアクションが書ける ●オブジェクト指向︵継承、Mix-in、委譲、オーバーライド、super︶ ●PEGの特徴はそのまま ●曖昧さが無い ●左再帰が書けない︵いまのところ︶ ●メモ化する
ソースコードはCodeRepos:/lang/ruby/metalにあるので、ガツガツいじれます。

使い方

Ruby gemsでインストールできます。

$ gem install metal

文法定義ファイルを書いて、metalコマンドを使って構文解析器を生成します。

$ metal syntax.metal > syntax.rb

生成された構文解析器は他のRubyスクリプトからrequireして使うことができますが、とりあえず試したいときはmetal-runコマンドを使って試せます。

$ metal-run syntax.rb '(add 1 2)'

文法定義の書き方

S式のパーサーはこんな感じで書けます。

SExpressionParser {
  # ここから構文解析開始
  -main
    expression:e s end  {* e *}

  # expressionはliteralまたはカッコで囲まれたexpressionの繰り返し
  -expression
      literal
    / s '(' (s expression:e s {*e*})+:es ')'s{* es *}

  # literalはstringまたはnumber
  -literal
      string
    / number

  # stringは[a-zA-Z_0-9]の1文字以上の繰り返し
  -string
    [a-zA-Z_0-9]+:xs  {* xs.join *}

  -number
    [0-9]+:s  {* s.join *}

  -s
      [ \r\n]*
}

最初のSExpressionParser { .... }はクラスの定義です。この中にルールを書いていきます。このクラス名は、そのまま生成される構文解析器のクラス名になります。続いて出てくる-expressionは、メソッドの定義です。最初は-mainメソッドから構文解析が始まります*1。メソッドは値を返します。たとえば-literalメソッドは、string / numberという文法定義を評価した結果を返します。

基本的な文法

並び　e1 e2 e3 解析表現をスペースで区切って並べると、並べた解析表現を順に評価していきます。途中で例外が発生するとParseError例外になります。最後に評価した解析表現の返り値を返します。この例の場合はe3を評価した返り値を返します。選択　e1 / e2 / e3 解析表現を/で区切って並べると、並べた解析表現のどれかが成功するまでバックトラックします。まずe1を評価し、評価の途中で例外が発生したら、e1を評価する前の状態まで巻き戻してからe2を評価します。e2が成功したらe3は評価しません。成功した解析表現の返り値を返します。ゼロ個以上　e* 解析表現の後ろに*を付けると、eをゼロ回以上繰り返して評価します。成功した解析表現の結果の配列を返します。1回も成功しないときは空の配列を返します。 1個以上　e+ 解析表現の後ろに+を付けると、eを1回以上繰り返して評価します。1回も成功しないとParseError例外になります。省略可能　e? 解析表現の後ろに?を付けると、eの評価中に例外が発生しても例外を揉み消します。例外が発生した場合はnilを返し、成功した場合はeの返り値を返します。文字クラス　[a-zA-Z] 正規表現でよくある文字クラスです。指定した範囲にマッチすればマッチした文字を返します。マッチしなければParseError例外になります。トークン　"文字列" または '文字列' 文字列にそのままマッチします。マッチすればその文字列を返します。マッチしなければ、一文字もマッチしなかった状態に巻き戻してからParseError例外を発生させます。何か1文字　. .は何か1文字にマッチします。マッチした文字を返します。入力の終わり　end endのところに到達したにもかかわらず入力がまだ残っているとParseError例外になります。nilを返します。アクション　{* ... *} {* ... *}の中身をRubyスクリプトとして実行します。実行した返り値を返します。アクション解析表現　?{* ... *} {* ... *}の中身をRubyスクリプトとして実行し、返り値がnilかfalseだったらParseErrorを発生させます。肯定先読み　&e 解析表現の前に&を付けると、eを評価して成功したら、eを評価する前の状態まで巻き戻してから評価した結果を返します。エラーになったら、eを評価する前の状態に巻き戻してからParseError例外を発生させます。否定先読み　!e 解析表現の前に!を付けると、eを評価してエラーだったら、eを評価する前の状態まで巻き戻してからnilを返します。エラーにならなかったら、eを評価する前の状態に巻き戻してからParseError例外を発生させます。命名は適当なので適当に流してください :-p

変数

解析表現と繰り返し記号の後ろに:xと付けると、xという変数に返り値が代入されます。変数はアクションの中で使えます。たとえば[0-9]+:s {* s.join *}という定義は、まず[0-9]+を評価した結果を変数sに代入します。繰り返し記号+は解析記号を1回以上繰り返して評価した配列を返すので、sには"0"〜"9"の文字の配列が代入されます。最後の{* s.join *}で文字の配列を結合し、文字列にして返しています。というわけで先のSExpressionParserの-numberメソッドは、0〜9の文字が繰り返した文字列にマッチして、マッチした文字列を返すメソッドになります。

継承とsuper

先のSExpressionParserの例では、+や-などの演算子が書けません。そこで、SExpressionParserを継承して、演算子も書けるパーサーを作ってみます。

SExpressionParserExtend < SExpressionParser {
  -literal
      super
    / operator

  -operator
      '+' / '-' / '*' / '/'
}

-literalメソッドのところにsuper / operatorと書いています。まず親クラス︵SExpressionParser︶の-literalメソッドを呼び出してから、それに失敗したら-operatorメソッドを呼び出します。これでリテラルが追加できました。

Mix-in

SExpressionParserの例で、数字にマッチする-numberメソッドや、空白にマッチする-sメソッドは、他のところでも使いそうなので、別のところに切り出しておきたいところです。そこでMix-inが使えます。

# module Utilityを定義
module Utility {
  # よく使うメソッドを切り出しておく
  -string
      [a-zA-Z_0-9]+:xs  {* xs.join *}

  -number
      [0-9]+:s  {* s.join *}

  -s
      [ \r\n]*
}

# 先頭のclassは省略可能
class SExpressionParser {
  # Utilityをincludeする
  @include Utility

  -main
      expression:e s end  {* e *}

  -expression
      literal
    / s '(' (s expression:e s {*e*})+:es ')'s{* es *}

  -literal
      string
    / number
}

module Utilityによく使うメソッドをまとめて定義しておき、クラス定義の方でそのモジュールを@include UtilityしてMix-inしています。

外部構文解析器の呼び出し

S式をインラインで書ける言語を書きたい！となったとき、S式の構文解析はS式の構文解析器に丸投げしたい。そこでClassName.methodNameと書くと、外部の構文解析器を呼び出せます。足し算と引き算をパースする構文解析器で、先頭にSが付いた式はS式として構文解析する構文解析器を作ってみます。

Calc {
  @include Utility

  -main
    expression:e s end  {* e *}

  -expression
      number:l s '+' s number:r  {* [:add, l, r] *}
    / number:l s '-' s number:r  {* [:sub, l, r] *}

  # 数字の連続か、先頭に'S'が付いたS式にマッチ
  -number
      [0-9]+:xs  {* xs.join *}
    / 'S' SExpressionParserExtend.expression
}

これでS(- (+ 1 2) 3) + 1といった式を構文解析できます。

埋め込みスクリプト

@{ ... @}の中にRubyスクリプトを書くと、それが生成される構文解析器の中にそのまま埋め込まれます。

@{
# 最初にmetalをrequireしておく
require 'metal'
@}

Calc {
  @{
    # メソッドやクラスを定義しておく
    class Expression
      # ...
    end
  @}

  -main
      expression:e  {* Expression.new(e) *}

  # ...
}

パラメータ付きメソッド呼び出し

メソッドを呼び出すときに後ろに(arg, arg, ...)を付けて呼び出すと、メソッドに引数を渡せます。メソッド定義の後ろに:x :yと書いておくと、引数を受け取れます︵:x :yなら2引数︶。

  -expression
    prediction:p iterator(p)?:p variables?:v {* Expression.new(p, v) *}

  # 引数1つ取るメソッド
  -iterator :x
      '*' {* IterMany.new(x) *}
    / '+' {* IterMany1.new(x) *}
    / '?' {* IterMay.new(x) *}
    /     {* x *}

この定義はMetalの文法定義︵MetalはMetalで実装されています︶から抜粋したものです。-expressionで、まずpredictioinメソッドを評価して変数pに代入し、その返り値をiteratorメソッドに渡して変数pに代入しています。

無名メソッド

( ... )で囲んで無名メソッドを定義して呼び出せます。

  # （:で区切られた文字列）のゼロ回以上の繰り返し
  -rule_args
      (s':' [a-zA-Z_]+)*

  # "で囲まれた文字列
  -quoted_string
    '"' (!'"' . / '\"')+:s '"'   {* s.join *}

-rule_argsメソッドは、(s ':' [a-zA-Z_]+) という無名のメソッドを定義し、そのメソッドのゼロ回以上の繰り返しです。
-quoted_stringメソッドは少々複雑ですが、結果から言えば " ... " で囲まれた文字列にマッチし、マッチした文字列を返すメソッドです。
まず !'"' . は、否定先読みで '"' にマッチしたらParseError、マッチしなかったら巻き戻して .︵何でもいいから1文字︶にマッチします。つまりこれは "でない1文字 にマッチします。続いて '\"' は、そのまま \" にマッチします。ということで、(!'"' . / '\"') は、"でない1文字 か \" にマッチします。
(!'"' . / '\"')+:s は、"でない1文字 か \" の1回以上の繰り返しにマッチし、マッチした結果の配列を変数sに代入します。最終的に '"' (!'"' . / '\"')+:s '"' {* s.join *} は、最初に " が来て、次に "でない1文字 か \" の1回以上の繰り返しが続き、最後に " が来る文字列にマッチし、" ... " の中の文字の配列をjoinして文字列にして返します。
何かに囲まれた表現はこの方法で書けます。カッコと先読みがポイント。

参考文献など

本家OMeta：http://www.cs.ucla.edu/~awarth/ometa/
OMetaの論文：OMeta: an Object-Oriented Language for Pattern Matching
Packrat Parserで左再帰を処理する話：Packrat Parsers Can Support Left Recursion
Python版OMeta：PyMeta
C#版OMeta：OMeta#

*1:変更可能。SExpressionParser.new(:string)のようにinitializeにメソッド名をシンボルで渡すと、そのメソッドから構文解析が始まります。

Blog by Sadayuki Furuhashi

Treasure Data MessagePack Embulk Fluentd @twitter