Ruby Library Report 【第 6 回】 正規表現と構文解析

はじめに

正規表現やpack/unpackは、設定、ログ、プロトコルメッセージなどのような 構造を持つテキストデータまたはバイナリデータの処理において非常に役立つ 機能です。 しかし、構造が複雑になると、正規表現やunpackを用いたコードを作成するこ とが難しく、また、メンテナンスも難しい場合があります。 このような困難さを克服するためのツールやライブラリとして、文法やフォー マットによって構造のあるデータを扱う際に便利な abnf, racc, syntax.rb, tdp4r, OpenSSL::ASN1 を簡単に概要だけを紹介します。

一般的に、記述された文法から、その文法やフォーマットに従うデータを、プロ グラム内で扱いやすいように変換するコードを生成するものを、パーサジェネレ ータと呼びます。 多くのパーサジェネレータはツールとして提供されており、文法を記述したファ イルを用意して、そしてそれをパーサジェネレータの入力として文法に従ったテ キストデータなどを処理するコードを生成します。 このようなパーサジェネレータは、プログラミング言語を作成する際によく利用 されていますが、設定ファイルやログファイルなどの解析に対しても有効です。 パーサジェネレータを使う利点に、文法(データの構造)と、それに対する処理を 明確に区別できます。そして、文法に見落としがないかなどのチェックを行いや すくなります。

パーサジェネレータについて議論を行うとき、まず扱える 文法の範囲*1 や、解析方法*2 に着目することが多いです。 しかし、これらの詳細な説明は RLR では行いませんので、詳しくは教科書[4,5] を 参照して下さい。 RLR では、扱える文法の強力さよりも、どのように文法を記述できるか、あるいは、 どのように ruby から利用できるかという点に着目します。

一方で、今回扱うツールやライブラリを、 DSL(Domain Specific Language) [1,2] の視点から見ると多少興味深いかもしれません。 DSL とは、特定ドメインのモデリングを行うための言語のことで、ドメインの専門家 がプログラムを行えることを期待しています。 このような言語を扱うツールには、yacc や xsltproc などがあります。 同様に、今回 RLR で扱うツールとライブラリが扱う対象も DSL であると言えます。*3 yacc は、BNF という文法を記述する言語によってプログラミングを行います。 また、xsltproc は、XSLT という変換言語によって、XMLの変換方法をプログラミングします。 そして、DSL により記述されたモデルは、ツールなどにより汎用的な言語へ変換する か、または、その DSL のためのエンジンによって処理されます。 一部では、DSL を、External DSL と Internal DSL に分けて呼ぶことがあります。 Internal DSL は、汎用的な言語の中で定義した DSL のことで、 逆に、External DSL は、汎用的な言語の外で定義した DSL です。 この分類に従うと、abnf と racc の記述言語は External DSL であり、tdp4r と syntax.rb は、Internal DSL として実現されていると言えます。 Internal DSL は、その DSL を実装するための言語の文法などの制約を受けることがあります。 このため、一見すると分かり難い記述を強いられることもあります。 しかし、実装言語の機能を活用することもでき、記述コストなどを削減できる場合もあります。 このような利点と欠点は、ツールやライブラリの選択の基準の一つになります。

試用レポート -- abnf

登録データ

概要

abnf は、ABNF による文法記述からその文法に一致する正規表現を生成 するライブラリです。 ABNF は、BNF と基本的に文法は同じであり、表現形式が拡張されているものです。 ABNF(あるいは似たようなBNF)を用いて文法を定義したものに、 IPアドレス *4 やURI *5 があります。 このような文法記述から、IPアドレスやURLに一致する正規表現を生成すること によって、文法に従った正確な正規表現を生成できます。

abnf は、保守性に貢献します。 例えば文法が多少変更になった場合でも、どの部分を変更すれば良いのか比較的楽に 判断できます。 ただし、ABNF により表せる文字集合と、正規表現で記述できる文字集合では、 前者の方が広い集合となります。このため、abnf では正規表現に変換できな い場合があります。少なくとも、再帰を含まない文法は正規表現に変換できます。

サンプル

abnf には、IPv6とURIに関するサンプルプログラムが付属していますが、 ここでは、サンプルとして、整数の四則演算を行う算術式にマッチする正規表現 を記述してみます。 そして、文字列 str 中に現れる算術式を、その計算結果に置き換えます。 通常は、意味との一致を考慮して、再帰的な文法により定義するのですが、複雑 な再帰的な文法は abnf では扱えませんので、フォーマットだけを考えて記述 します。

sample_abnf_1.rb

   1|require 'abnf'
   2|fmt = <<EOS
   3|  expr  = prim 0*(op prim)
   4|  prim  = ["("] num [")"]
   5|  num   = 1*("0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9")
   6|  op    = "+" | "-" | "*" | "/"
   7|EOS
   8|reg = ABNF.regexp(fmt)
   9|str = "3+(2-1)は4です。33(23)は33と(23)に区別されます。"
  10|puts( str.gsub(reg){|expr| eval(expr)} )
  11|

abnf を用いると、全体がマッチすることは分かるのですが、例えば、算術式となる 文字列を抽出したときに、その算術式における num に相当する文字列も同時に検出 するということなど細かい制御ができないようです。 恐らく、抽出したものに対して再びパターンマッチを行う必要がありそうです。 そこで、文法を分けて記述します。この例が、次のsample_abnf_2.rb です。

sample_abnf_2.rb

   1|require 'abnf'
   2|fmt = <<EOS
   3|  expr  = prim 0*(op prim)
   4|  prim  = ["("] num [")"]
   5|  op    = "+" | "-" | "*" | "/"
   6|EOS
   7|numfmt = <<EOS
   8|  num   = 1*("0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9")
   9|EOS
  10|r1  = ABNF.parse(fmt)
  11|r2  = ABNF.parse(numfmt)
  12|r1.merge(r2)
  13|reg = r1.regexp()
  14|num = r2.regexp()
  15|str = "3+(2-1)は4です。33(23)は33と(23)に区別されます。"
  16|str.gsub(reg){|expr| p expr; expr.gsub(num){|n| p n} }
  17|

10,11行目の parse メソッドによって、記述した文法のパースを行います。 文法のパースの段階では、num の定義が欠けていても構いません。 もし、sample_abnf_1.rb のように regexp メソッドによって正規表現を生成 しているとエラーになります。 12行目で expr の文法に num の文法をマージします。 そして、13,14行目の regexp メソッドによってそれぞれの正規表現を生成して います。 このようにすると、文法の再利用を行うことが可能です。

以上のサンプルと同様に、ログファイルからIPアドレスとホスト名を抽出すること などにも利用できます。 抽出すること以外にも、設定ファイルの簡単な文法チェックなどにも利用できるでしょう。

試用レポート -- racc

登録データ

概要

racc は、文法の記述方法は若干異なりますが、yacc と同様のパーサジェネレータです。 racc についての解説書 [7] も存在し、すでに確固とした地位を築いていると思います。 ランタイム時のパース速度の向上などのために、racc で生成したパーサは、いくつか ライブラリを必要とします。 しかし、ruby-1.8 では、そのようなランタイムライブラリはすでに含まれています。 このため、raccを用いてアプリケーションの開発を行っても、そのアプリケーションの ユーザがraccをインストールする必要はありません。 文法そのものの記述方法は BNF で記述します。

サンプルコード

ここでは、abnf の場合と同様に、四則演算を含む算術式を計算する計算機クラス Calcを作成します。 コンパイラやインタプリタの作成では、一般的に、パーサによって解析木という 入力データに対する内部表現を一度作成しますが、ここでは、直接計算を行う ことにします。この Calc クラスを生成する racc の文法ファイルが、以下の sample_racc_1.racc です。

sample_racc_1.racc

   1|class Calc
   2|  token NUM
   3|prechigh
   4|  left  '*' '/'
   5|  left  '+' '-'
   6|preclow
   7|rule
   8|   expr : expr '+' expr { result = val[0] + val[2] }
   9|        | expr '-' expr { result = val[0] - val[2] }
  10|        | expr '*' expr { result = val[0] * val[2] }
  11|        | expr '/' expr { result = val[0] / val[2] }
  12|        | prim          { result = val[0] }
  13|
  14|   prim : NUM            { result = val[0] }
  15|        | '(' expr ')'   { result = val[1] }
  16|end
  17|---- inner
  18|  def parse(str)
  19|    @tokens = str.split(/([\(\)\+\-\*\/])/).select{|c| !c.nil? && c!=""}
  20|    do_parse()
  21|  end
  22|
  23|  def next_token()
  24|    token = @tokens.shift()
  25|    case token
  26|    when /^\d+\z/
  27|      return [:NUM, token.to_i]
  28|    when nil
  29|      return nil
  30|    else
  31|      return [token, nil]
  32|    end
  33|  end

'---- inner' という行より後ろには、Calc クラス内のコードを書きます。 parse メソッドは、与えられた算術式の計算を行うためのメソッドです。 まず式を分解してトークンの列を生成しています。トークンとは、構文解析 における単位データです。 そして、そのトークン列からトークンを逐次取り出すものが next_token メソッド です。 Calc クラスは、next_token メソッドにより取り出されるトークン列に対して、 構文解析を行います。 このような、トークンを取り出すメソッドは、racc で予め決まっていますが、 ここでは、その一つである next_token メソッドを定義しました。 方法は他にもありますが、詳しくは racc のマニュアルを参照してください。

次に、この文法ファイルから、Calc クラスを生成します。このためには、次の コマンドを用います。ここで、'-o' というオプションによって出力ファイルを 指定します。

 $ racc -o sample_racc_1.rb sample_racc_1.racc

sample_racc_1.rb のファイル中に、Calc クラスのコードがあります。 このため、Calc クラスを実体化して、計算を行うためのコードは次の通りです。

sample_racc_2.rb

   1|require 'sample_racc_1'
   2|calc = Calc.new()
   3|p calc.parse("3+(2-1)")

さて、abnf の例題 sample_abnf_1.rb では、eval() (10行目) を用いて算術式の 計算を行っていました。 eval() は、便利な機能ですが、使い方を間違えると脆弱性の原因となることも少 なくありません。そこで、sample_racc_1.racc によって生成されたパーサを用いて 計算を行うように書き換えたものが以下の sample_racc_3.rb です。

sample_racc_3.rb

   1|require 'abnf'
   2|require 'sample_racc_1'
   3|fmt = <<EOS
   4|  expr  = prim 0*(op prim)
   5|  prim  = ["("] num [")"]
   6|  num   = 1*("0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9")
   7|  op    = "+" | "-" | "*" | "/"
   8|EOS
   9|reg = ABNF.regexp(fmt)
  10|str = "3+(2-1)は4です。33(23)は33と(23)に区別されます。"
  11|calc = Calc.new()
  12|puts( str.gsub(reg){|expr| calc.parse(expr)} )
  13|

このように、文字列から算術式に一致する部分文字列を abnf を用いて抽出し、その 文字列を racc で生成したパーサを用いて構文解析と計算を行うことができました。

試用レポート -- tdp4r

登録データ

概要

tdp4r は、単純な再帰下降解析(recursive descent parsing)を行うパーサを動的に 作成するためのライブラリです。 再帰下降解析の特徴の一つに、文法とメソッドを1:1に対応できる点があります。 つまり、ある文法を用いることが、あるメソッドを呼び出すことに対応しています。 この特徴を活かして、文法を Ruby のプログラムとして記述できます。 このため、実行時に Ruby を用いて文法を制御できるなどの柔軟性があります。 文法は、JavaCC [3] と類似した書式によって 記述します。

サンプルコード

一般的に、再帰下降パーサでは、A = A b | a のような左再帰を含む文法を記述でき ません。しかし、このような文法により生成できる文字は、abbbbbbb... となります。 つまり、繰り返し記号「*」を導入すると、A = a b * という文法を記述することと等 しくなります。 tdp4r でも、繰り返し記号を用いた文法を記述できますので、繰り返しを用いて文法 を記述し、その文法に従って算術式の計算を行うことにします。

sample_tdp4r_1.rb

   1|require 'tdp'
   2|class MyCalc
   3|  include TDParser
   4|
   5|  def expr1
   6|    rule(:expr2) - ((token("+")|token("-")) - rule(:expr2))*0 >> proc{|x|
   7|      n = x[0]
   8|      x[1].each{|y|
   9|        case y[0]
  10|        when "+"; n += y[1]
  11|        when "-"; n -= y[1]
  12|        end
  13|      }
  14|      n
  15|    }
  16|  end
  17|
  18|  def expr2
  19|    rule(:prim) - ((token("*")|token("/")) - rule(:prim))*0 >> proc{|x|
  20|      n = x[0]
  21|      x[1].each{|y|
  22|        case y[0]
  23|        when "*"; n *= y[1]
  24|        when "/"; n = n / y[1]
  25|        end
  26|      }
  27|      n
  28|    }
  29|  end
  30|
  31|  def prim
  32|    token(/\d+/)                           >> proc{|x| x[0].to_i } |
  33|    token("(") - rule(:expr1) - token(")") >> proc{|x| x[1] }
  34|  end
  35|
  36|  def parse(str)
  37|    tokens = str.split(/(?:\s+)|([\(\)\+\-\*\/])/).select{|x| x != ""}
  38|    expr1.parse(tokens)
  39|  end
  40|end
  41|
  42|calc = MyCalc.new
  43|puts("5-2*(5-2*2) = " + calc.parse("5-2*(5-2*2)").to_s())

tdp4r では、文法を Ruby のコードとして記述します。 このために、まず Calc クラスを用意して、TDParser モジュールをインクルードします。 TDParser モジュールには、rule や token などの文法を定義するために利用するメソッド が定義されています。 rule メソッドによって、ルールの適用を行い、token メソッドによって、トークン を一つ読み取ります。 ここで、ルールは、構文解析においては、別の構文定義のことであり、実装において は、別のメソッドに相当します。 rule と token を連接「-」、選択「|」、繰り返し「*」の記号を用いて結合させて、 ルールを定義します。 このような仕組みによって、文法の定義を行うため、構文解析を行うコードは実行時 に作成されます。このため、動的にルールを取り替えるなどが可能です。

解析されたデータを処理は、「>>」の後ろの Proc オブジェクトにより行います。 このような処理の記述は、実はルール中に埋め込むようにも書くことができますが、 文法そのものとの区別が付きにくくなる場合があります。

sample_tdp4r_2.rb

   1|require 'sample_tdp4r_1'
   2|class MyCalc
   3|  def expr1
   4|    n = nil;
   5|    (rule(:expr2) >> proc{|x| n = x[0] }) -
   6|    ((token("+")|token("-")) - rule(:expr2) >> proc{|x|
   7|      case x[0]
   8|      when "+"; n += x[1]
   9|      when "-"; n -= x[1]
  10|      end
  11|      n
  12|    })*0 >> proc{ n }
  13|  end
  14|
  15|  def expr2
  16|    n = nil;
  17|    (rule(:prim) >> proc{|x| n = x[0] }) -
  18|    ((token("*")|token("/")) - rule(:prim) >> proc{|x|
  19|      case x[0]
  20|      when "*"; n *= x[1]
  21|      when "/"; n /= x[1]
  22|      end
  23|      n
  24|    })*0 >> proc{ n }
  25|  end
  26|end
  27|
  28|calc = MyCalc.new
  29|puts("5-2*(5-2*2) = " + calc.parse("5-2*(5-2*2)").to_s())

また、サンプルコードから分かる通り、tdp4r では演算子の優先順位は、文法を工夫す ることによって実現しなければなりません。このあたりは、racc に比べると非常に不便 な点となるでしょう。 また、解析速度も racc より明らかに遅くなります。 詳細な議論は RLR ではしませんが、少しでも速くするために次のように一度構成した 文法を再利用できるようにする方法があります。

sample_tdp4r_3.rb

   1|require 'sample_tdp4r_1'
   2|class FastCalc < MyCalc
   3|  def expr1
   4|    @expr1 ||= super()
   5|  end
   6|
   7|  def expr2
   8|    @expr2 ||= super()
   9|  end
  10|
  11|  def prim
  12|    @prim ||= super()
  13|  end
  14|end
  15|
  16|calc = FastCalc.new
  17|puts("5-2*(5-2*2) = " + calc.parse("5-2*(5-2*2)").to_s())

試用レポート -- syntax.rb

登録データ

概要

syntax.rb は、tdp4r とほとんど狙いは同じライブラリです。 文法を Ruby のコードとして記述できます。 特徴的なことは、トークンへの分解*6も syntax.rb によって行うことができ、また、ルールの定義がオブジェクトのみ で実現できることです。

サンプルコード

sample_syntax_1.rb

   1|require 'syntax'
   2|
   3|INF = +1.0/0
   4|LOOP0 = (0..INF)
   5|LOOP1 = (1..INF)
   6|num = (("0".."9")*LOOP1).qualify{|x| x.to_s().to_i()}
   7|
   8|expr = Syntax::Pass.new()
   9|
  10|prim = num.qualify{|x| x[0]} | ("(" + expr + ")").qualify{|x| x[1]}
  11|
  12|expr2 = (prim + (("*" | "/") + prim)*LOOP0).qualify{|x|
  13|  val = x[0]
  14|  x[1].each{|y|
  15|    case y[0]
  16|    when "*"; val *= y[1]
  17|    when "/"; val /= y[1]
  18|    end
  19|  }
  20|  val
  21|}
  22|
  23|expr << (expr2 + (("+" | "-") + expr2)*LOOP0).qualify{|x|
  24|  val = x[0]
  25|  x[1].each{|y|
  26|    case y[0]
  27|    when "+"; val += y[1]
  28|    when "-"; val -= y[1]
  29|    end
  30|  }
  31|  val
  32|}
  33|
  34|p(expr === RandomAccessStream.new("5-2*2"))

試用レポート -- reg

登録データ

概要

reg は、正規表現によるパターンマッチングを、Ruby の基本的なデータ構造に適用 できるようにするライブラリです。 多くの人は、文字列に対して部分文字列を抽出・置換する場合、正規表現を利用する ことが多いと思います。これは、正規表現が適度な手軽さを提供するためです。 同様に、reg では、基本的なデータ構造に対しても、この手軽さを実現しようと試み ています。

将来的には、パターンマッチの過程において、部分的にマッチしたデータを他のデータ に置き換えることなども視野に入れているようです。 このような置換を伴うパターンマッチが行えると、パターンによって処理を行うべき データを検出し、さらにその検出したデータを逐次的に他のデータに置換できます。 このような処理は、abnf と tdp4r/syntax.rb を組み合わせたような処理に似ています。 現在は、そのような置換を行う機能は実装されていないので、パターンマッチを用いた データの妥当性チェックの方法を次節にて示します。

サンプルコード

データの構造が、妥当であるかどうかのチェックを行うことを考えます。 例えば、トークンの列を考えた場合、配列中に "" の文字を含めたくない 場合を考えます。このような場合、配列 ary に対して

 ary.select{|x| x != ""}

というコードを実行することによって "" を取り除くことが可能です。 また、

 ary.all?{|x| x != ""}

によってすべての配列要素が "" ではないことをチェックできます。 一方で、このようなチェックを reg を用いて記述すると次の通りです。

 +[~"".reg + 0] === ary

reg では、+[] によって基本データの列(シーケンス)を表す正規表現を表し、+0 によって、 0回以上の繰り返しを表します。 そして、=== によって正規表現にマッチした要素をグループ化して返します。 例えば、

 +[String.reg + 0] === ["a","b","c"]

は、[ [ ["a","b","c"] ] ] が返りますが、

 +[String.reg, String.reg + 0] === ["a","b","c"]

は、[ [ ["a"] ], [ ["b", "c"] ] ] が返ります。つまり、最初の String にマッチする グループと、String の繰り返しにマッチするグループに分かれたことになります。 また、=== によってマッチングを行っているので、case 文の when 節で利用することもできます。

試用レポート -- OpenSSL::ASN1

登録データ

  • [プロジェクト名] OpenSSL::ASN1
  • [作成者] 後藤 ゆうぞう
  • [URL]
  • [バージョン] ruby-1.8 に添付
  • [レポート環境] ruby-1.8(cygwin)

概要

ASN.1 は、Abstract Syntax Notation One というデータ構造 を記述するための文法です。 SSL, SNMP, LDAP と呼ば れるプロトコルにおいて、メッセージデータを定義するために利用されています。 OpenSSL::ASN1 は、そのような ASN.1 に従ってデータを構成するためのライブラリで、 OpenSSL 拡張モジュールの一部として提供されています。 ただし、ASN.1 の構文を解釈して、その構文に従うデータを処理するコードを自動生成 しません。開発者が、データを構文に従って組み立てるための、基本的な枠組だけを 提供しています。

データ構造をエンコーディングする方法として BER (Basic Encoding Rules) , CER (Canonical Encoding Rules), DER (Distinguished Encoding Rules) など複数 の方法があります。OpenSSL::ASN1 では、DER エンコーディングのみがサポートされて います。

サンプルコード

Windows をご利用の方であれば、[インターネットオプション]->[コンテンツ]->[証明書] のウィンドウから、一つ証明書を選択し、エクスポートを行うことができます。 このとき、エンコーディング方法として DER を選択できます。 そこで、このような DER によりエンコーディングされた電子証明書を OpenSSL::ASN1 を 用いて閲覧します。*7 ここでは DER 形式でエンコーディングされた証明書を foo.der という名前のファイル とします。

まず、証明書(foo.cer) の中身を解析するためには、その構造を知る必要があります。 電子証明書の構造は、RFC:3280 で記述されています。 RFC:3280 の 4.1 "Basic Certificate Profile" を見ると以下の文法が掲載され ています。これが ASN.1 で記述されたデータ構造の定義です。

  Certificate  ::=  SEQUENCE  {
       tbsCertificate       TBSCertificate,
       signatureAlgorithm   AlgorithmIdentifier,
       signatureValue       BIT STRING }

ここで定義していることは、証明書の中身が、まず tbsCertificate, signatureAlgorithm, signatureValue の3つのデータから構成されていることを表しています。 そして、それぞれのデータは、それぞれ TBSCertificate, AlgorithmIdentifier, BIT STRING という構造を持つことも表しています。TBSCertificate の構造は多少複雑ですので、簡単な AlgorithmIdentifier の定義を参考として挙げます。これは、4.1.1.2 節において記載されて います。

  AlgorithmIdentifier  ::=  SEQUENCE  {
       algorithm               OBJECT IDENTIFIER,
       parameters              ANY DEFINED BY algorithm OPTIONAL  }

このような、データ構造を読み込み、再び再構成してファイルへ出力するプログラムが 以下の sample_asn1_1.rb です。

sample_asn1_1.rb

   1|require 'openssl'
   2|require 'pp'
   3|include OpenSSL
   4|
   5|data = ASN1.decode(File.open(ARGV[0], 'rb'){|f| f.read()})
   6|
   7|tbsCertificate, signatureAlgorithm, signatureValue = data.value
   8|pp tbsCertificate
   9|pp signatureAlgorithm
  10|pp signatureValue
  11|
  12|data = ASN1::Sequence [
  13|  tbsCertificate,
  14|  signatureAlgorithm,
  15|  signatureValue,
  16|]
  17|File.open(ARGV[1], 'wb'){|f| f.write(data.to_der())}

5 行目でファイルから証明書のデータを読み込み DER 形式のデコードを行っています。 そして、7 行目では、データ構造の定義に従って、それらを tbsCertificate, signatureAlgorithm, signatureValue の3つのデータに分割しています。 次に、12 行目では、これら 3 つを再び一つの証明書として構成しています。 一見すると、ASN.1 の定義に似ていることが分かります。 そして、17 行目では、再構成したデータを to_der により DER 形式でエンコードを行い、 ファイルへ出力しています。 このため、このプログラムを例えば ruby sample_asn1_1.rb foo.der bar.der として 実行すると、foo.der と中身が等しい bar.der というファイルができているはずです。 このことは、md5sum や cmp などのコマンドで確認できます。

以上のように、OpenSSL::ASN1 では、データの構成と、エンコードとデコードが主な役割 です。今後、ASN.1 の文法を記述することによって、その文法に従うデータを処理するため のコードを生成できることを期待します。 例えば、Certificate の例ですと、以下のように Internal DSL 風に ASN.1 を記述でき、 自動的にデータを読み込むことができると、さらに使い易いと思います。 もちろん、ASN.1 を記述言語として、以下のような Internal DSL のコードを生成すると いうことも可能でしょう。

 class Certificate
   sequence [
     [:tbsCertificate, :TBSCertificate],
     [:algorithmIdentifier, :AlgorithmIdentifier],
     [:signatureValue, :BitString]]
 end
 class AlgorithmIdentifier
   sequence [
     [:algorithm, :ObjectIdentifier,
      :parameters, :OPTIONAL]]
 end
 ...
 cert = Certificate.read("foo.der")  # 証明書の読み込み
 cert.tbsCertificate

まとめ

今回は、正規表現や構文解析に関係するデータ処理のためのツールとライブラリ を紹介しました。 abnf は、複雑になりがちな正規表現の記述を支援できます。 racc は、対象データの文法(つまり、構造)に沿って処理方法を簡潔に記述することがで きます。 tdp4r と syntax.rb は、racc と同様の目的で使えますが、文法を Ruby のコードとして 記述できます。このため、Ruby の記述力を活かした動的な文法定義などが興味深いです。 reg と OpenSSL::ASN1 は、データ処理という観点からは、今後の発展が非常に楽しみな ライブラリです。

参考リソース

[1] DSL(Domain Specific Language) については、 「Domain Specific Language」 に簡潔な説明があります。

[2] 「Domain-Specific Language (DSL) Tools」 には、マイクロソフトが提供する DSL 関連のツールを見ることができます。

[3] 「JavaCC Grammar Repository」 には、様々な JavaCC の文法ファイルを見つけることができます。 tdp4r や syntax.rb などを扱う場合の参考になります。

[4] 「コンパイラ」 は、日本語で書かれたコンパイラの教科書です。 しかし、ツールやライブラリを使う限りにおいて内容を知る必要はありません。

[5] 「コンパイラの理論と実現」 では、 実際に C-- という例題を基に、簡単にコンパイラの構成方法を説明しています。

[6] ASN.1 Compiler は、 オープンソースの ASN.1 コンパイラです。

[7] 「Rubyを256倍使うための本 無道編」 は、racc を用いたインタプリタの作成について解説しています。

著者について

著者(立石)は、ソフトウェアの研究開発職に従事しています。

更新日時:2005/10/02 22:58:02
キーワード:
参照:[Rubyist Magazine 0008 号] [0008 号 巻頭言] [各号目次] [pre-RLRPlan] [prep-0008]

*1 有名なものに、正規文法、文脈自由文法 、LALR(1) 文法、LL(k) 文法 などの文法のクラスがあります。

*2 LR解析、LALR(1)解析、再帰下降解析などの解析方法があります。

*3 これらは、パーサやXMLというドメインに特化した言語ですが、ビジネスドメインを記述するものも同様に DSL です。

*4 RFC:2373のAPPENDIX B

*5 RFC:2393のAPPENDIX A

*6 一般的に字句解析と言います

*7 Linux や *BSD をお使いの方も、適当な DER によりエンコーディングされた電子証明書をご用意ください。(編注: 適当な証明書が無い場合は CAcert.org からダウンロードすると良いでしょう)