おもこん

おもこんは「思いつくままにコンピュターの話し」の省略形です

徒然Ruby(43)StrScanライブラリで字句解析

電卓プログラムの記事で予告したStrScanライブラリの話です。

StrScanライブラリのドキュメント

Rubyのドキュメントに説明があります。 簡単な説明ですが、それで使い方はわかると思います。

字句解析とは

字句解析は、主にプログラミング言語で使われます。 例えば次のようなRubyプログラムを考えてみましょう。

def hello
  print "Hello world\n"
end

このプログラムを分解すると、次の表のようになります。

文字列 タイプ
def 予約語def
空白 空白
hello 識別子 hello
改行 改行
空白 空白
空白 空白
print 識別子 print
空白 空白
"Hello world\n" 文字列 Hello world\n
改行 改行
end 予約語end
改行 改行

この中の空白は、区切りという意味しかなく、それがなくてもRubyインタープリタはプログラムを解釈できます。 ですので、これらは捨てられてしまいます。 なお、改行は言語によって空白と同じように捨てられることもあります。 Rubyは改行によって、文や式の区切りを表すことがあるので、残しておきます。 空白以外の要素はインタープリタに送られます。 それらの要素は字句またはトークン(token)と呼ばれます。

トークンはタイプと値のセットにします。 タイプは「トークン・カインド(token kind)」とも呼ばれます。 タイプの部分には文字列またはシンボルを使うことが多いです。 例えば「予約語のdef」はシンボル:DEFなどです。 ここで大文字を使ったのは、トークン・カインドに大文字を使う習慣があるからです。 ここでは、シンボルでトークン・カインドを表すことにしましょう。

タイプ トークン・カインド
予約語def :DEF
改行 :NL
識別子 :ID
文字列 :STR
予約語end :END

トークンを配列の形でまとめると、

[ [:DEF, "def"],
  [:ID, "hello"],
  [:NL, "NewLine"],
  [:ID, "print"],
  [:STR, "Hello world\n"],
  [:NL, "NewLine"],
  [:END, "end"],
  [:NL, "NewLine"]
]

となります。 配列の要素はすべて「タイプ」「値」という形になります。 予約語の場合はタイプだけで用が足りるので、値は何でも構いません。 [:DEF,"def"][:DEF,nil]としても、構文解析上は問題ありません。

このように、プログラムの文字列を、その言語の要素に分解することを「字句解析」といいます。 字句解析は、文字列のパターンを見つけることですから、正規表現のあるRubyでは簡単にできます。 しかし、短い時間でパターンを発見するにはStrScanライブラリを使うのが良いそうです。

StrScanライブラリ

StrScanライブラリの使い方をまとめると、次のとおりです。

  1. strscanライブラリをrequireする
  2. StringScannerインスタンスを生成する。そのとき、引数に対象となる文字列を与える
  3. scanメソッドでパターンを比較する

具体例を示しましょう。

require 'strscan'

s = StringScanner.new("def hello\n  print \"Hello world.\n\"\nend\n")

p s.scan(/def/) #=> "def"
p s.scan(/hello/) #=> nil
p s.scan(/[[:blank:]]/) #=> " "
p s.scan(/hello/) #=> "hello"
p s[0] #=> "hello"
p s.eos? #=> false
  • 1行目:strscanライブラリを取り込む
  • 3行目:StringScannerインスタンスを生成。引数が対象文字列。
  • 5行目:scanメソッドは、文字列の先頭が正規表現/def/に一致すれば、その文字列"def"を返す。文字列検索のポインタはdefの次の文字に移動
  • 6行目:scanメソッドは、ポインタ位置の文字列が正規表現/hello/に一致しないので、nilを返す
  • 7行目:scanメソッドは、ポインタ位置の文字列が正規表現/[[:blank:]]/(空白またはタブ)に一致するので、その文字列" "を返す。文字列検索のポインタは空白の次の文字に移動
  • 8行目:scanメソッドは、ポインタ位置の文字列が正規表現/hello/に一致するので、その文字列"hello"を返す。文字列検索のポインタはhelloの次の文字に移動
  • 9行目:[0]メソッドは、前回のマッチ文字列を返す。マッチが失敗していればnilを返す。また、正規表現でカッコを使うとマッチの一部をs[1]、s[2]、・・・で取り出せる
  • 10行目:ポインタが文字列の最後まで進んでないので、falseを返す。

StrScanライブラリを使った字句解析

では、そきほどのRubyコードの字句解析プログラムを作ってみましょう。

require 'strscan'

s = StringScanner.new("def hello\n  print \"Hello world.\n\"\nend\n")

token = []
until s.eos?
  if s.scan(/[[:blank:]]+/)
    ; # throw away space/tab characters
  elsif s.scan(/\n/)
    token << [:NL, "NewLine"]
  elsif s.scan(/def/)
    token << [:DEF, "def"]
  elsif s.scan(/end/)
    token << [:END, "end"]
  elsif s.scan(/"([^"]*)"/)
    token << [:STR, s[1]]
  elsif s.scan(/[[:alpha:]][[:alnum:]]*/)
    token << [:ID, s[0]]
  else
    raise "Unexpected character."
  end
end
p token

until文で、ポインタが文字列の終端になるまで繰り返します。 if-elsif文で順に空白、改行、予約語def、予約語end、文字列、識別子、その他に一致するかを見て、それぞれに対応するアクションを行います。 空白は無視され、「その他」には「Unexpected character.」の例外を発生させます。 これを実行すると次のような結果を得ることができます。

[[:DEF, "def"], [:ID, "hello"], [:NL, "NewLine"], [:ID, "print"], [:STR, "Hello world.\n"], [:NL, "NewLine"], [:END, "end"], [:NL, "NewLine"]]

なお

  • このプログラムでは文字列内のバックスラッシュ記法や式展開はサポートされず、ごく単純化した形になっています
  • Rubyの字句解析が目的であれば、Ripperライブラリがまさにそのためのライブラリです

実例

StrScanライブラリを用いた実例として、GitHubにCalcレポジトリがあります。

ファイルracc/calc.yの57行から77行のlexメソッドが電卓プログラムの字句解析部分になります。 Calcがどのような機能を持っているかはREADME.mdファイルを参照してください。

この字句解析は、Racc(パーサ・ジェネレータ)で使うことを前提にしています。 Raccの場合、トークン・カインドは次のような形になります。

  • 識別子をIDで表すことにすると、トークン・カインドはシンボル:IDにする
  • 演算子、例えば和の記号+などは、その文字列自身をトークン・カインドにする。注意すべきは、それは文字列"+"であって、シンボル:+ではない

次回はパーサ・ジェネレータのRaccについて投稿予定です。