電卓プログラムの記事で予告したStrScanライブラリの話です。
StrScanライブラリのドキュメント
Rubyのドキュメントに説明があります。 簡単な説明ですが、それで使い方はわかると思います。
字句解析とは
字句解析は、主にプログラミング言語で使われます。 例えば次のようなRubyプログラムを考えてみましょう。
def hello print "Hello world\n" end
このプログラムを分解すると、次の表のようになります。
| 文字列 | タイプ | 値 |
|---|---|---|
| def | 予約語def | |
| 空白 | 空白 | |
| hello | 識別子 | hello |
| 改行 | 改行 | |
| 空白 | 空白 | |
| 空白 | 空白 | |
| 識別子 | ||
| 空白 | 空白 | |
| "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ライブラリの使い方をまとめると、次のとおりです。
- strscanライブラリをrequireする
- StringScannerインスタンスを生成する。そのとき、引数に対象となる文字列を与える
- 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"]]
なお
実例
StrScanライブラリを用いた実例として、GitHubにCalcレポジトリがあります。
ファイルracc/calc.yの57行から77行のlexメソッドが電卓プログラムの字句解析部分になります。
Calcがどのような機能を持っているかはREADME.mdファイルを参照してください。
この字句解析は、Racc（パーサ・ジェネレータ）で使うことを前提にしています。 Raccの場合、トークン・カインドは次のような形になります。
- 識別子をIDで表すことにすると、トークン・カインドはシンボル
:IDにする - 演算子、例えば和の記号+などは、その文字列自身をトークン・カインドにする。注意すべきは、それは文字列
"+"であって、シンボル:+ではない
次回はパーサ・ジェネレータのRaccについて投稿予定です。
