2 RewriteTokens を用いた構文解析の実現
この演習では、簡易なプログラミング言語に対する構文解析を RewriteTokens Ver.2 で実現する方法を学ぶ。
2.1 対象プログラミング言語
対象となるプログラミング言語は、C言語のサブセットとし、次の制限を加える。
- 型は int, char, double の3種類のみである。
- 値の表現する式の基本要素としては、変数と整数、実数のみが使える。
- 変数名は英文字で始まり、数字また英字が 0 個以上続く。なお、記号
_も英文字として扱う。 - 算術用の演算子は、単項演算子としては
+と-、 二項演算子としては+,-,*,/のみを扱う。 - 論理演算に関わる演算子は、二項演算子の
<,<=,>,>=,==を扱い、 論理和や論理積は扱わない。 - 代入については、二項演算子
=のみ扱う。 - 演算子の優先順位と結合の仕方は、次の通りとする。
- 単項演算子
+,-(左結合) - 二項演算子
*,/(左結合) - 二項演算子
+,-(左結合) - 二項演算子
<,<=,>,>=,==(左結合) - 二項演算子
=(代入, 左辺の値を返す, 右結合)
- 単項演算子
- 優先順位が低い式を先に計算するときは、丸括弧を用いて、その式を囲む。 (括弧の一般的な使い方と同じ)
- 文は、式文、複合文、if文、while文、for文の4種類とする。
- 変数は宣言をして使用する。宣言は1度に1つの変数のみ宣言できる。
- コメントは、
//から行末までにする。ただし、行末の改行は含まない。 - 空文(セミコロン単体で文とみなす)は存在しない。
2.2 構文解析の手順
構文解析の手順は、おおむね次の通りである。
- ソースコードを読み込む。
- ソースコードを、字句解析によって、字句のリストに変換する。
- 字句列の書換えルールを繰り返し適用し、構文木の構造を含んだ字句のリストに変換する。
- 字句のリストを出力する。
まず、字句解析を実現し、次に構文解析を段階的に実現していく。
2.2.1 字句解析
構文解析を行うためには、まず、ソースコードを解析の基本単位となる字句に分解する。 この処理を字句解析と呼ぶ。 TEBAでは、字句を「属性付き字句」と呼ぶ形式で表現して扱う。 この形式では、字句の種類を表す「型」とその字句のテキストを組み合わせて表現する。 例えば、型や演算子、予約語は次のように表現する。
OP <+>OP <*>TYPE <int>TYPE <char>RE_IF <if>RE_WHILE <while>
各行が属性付き字句である。各属性付き字句は次のような構成になっている。
- 先頭の大文字の単語は、字句の種類を表す型名である。
- 型名の後ろの
<と>の間は字句が表すテキストそのものである。- 型名と
<の間には空白を入れる。ここには、後述する識別記号が挿入されることもある。
例えば、上記の1行目は二項演算子 +
を表す属性付き字句である。 OP
が演算子であることを意味し、< と >
の間には 字句のテキストとしての表現である + がある。
5行目の RE_IF <if>は、予約語 if
を表す。 RE_IF の RE は英語の reserve
の先頭の2文字が由来である。
型名については、この演習の中で指定するので、それに従うこと。 TEBA はC言語の構文解析器を持っているが、それが持つ字句の定義とは異なるので、 TEBA の構文解析器を参照しないこと。
演算子の型名については、当初、すべて OP とする。ただし、演算子には二項演算子と 単項演算子があり、構文解析のときは区別する必要がある。 しかし、字句解析の段階では区別がつかないので、演習の途中で区別する処理を追加する。
2.2.2 構文解析
構文解析によって、ソースコードの静的な構造を表す構文木を構成する。 ただし、木を表現するにあたり、木の節(ノード)は、 その節の始まりと終りを表わす字句で囲んで表現する。 考え方は、HTML や XML の開始タグと終了タグと同じである。
例えば、式 1+2 を考える。この式の構成要素である式
1 は次のように表現する。
B_P #B0002 <>
NUM <1>
E_P #B0002 <>これは、構文木をグラフで表現したときに、次のように単体の節点(ノード)を表す。
整数値 1 の字句は NUM <1>
と表現され、値であることを意味する。 この字句を囲む B_P と
E_P という型の字句が、構文要素の「式」を表す。
B は begin を、E は end を意味する。
これらの字句は構文要素を表現するためだけの字句なので、字句としてのテキストは持たず、
< と > の間には文字は入らない。
また、#B0002 のような識別記号が付与されている。
これは同じ記号を持つ字句は1つの構文要素の開始と終了の組となっていることを示している。
識別記号は同一のものかどうか区別できることに意味があり、その数字や文字自体に意味はない。
書換えの際には、このような組になっている字句を利用して、書換える箇所を探索する。
式 2 も同様に表現される。B_P と
E_P が持つ識別記号が 式 1
の場合とは異なることにも注意すること。
B_P #B0003 <>
NUM <1>
E_P #B0003 <>式
1+2は、これらの式を演算子+を間に入れて構成されるので、
次のように表現する。
B_P #B0001 <>
B_P #B0002 <>
NUM <1>
E_P #B0002 <>
OP <+>
B_P #B0003 <>
NUM <2>
E_P #B0003 <>
E_P #B0001 <>全体を囲む #B0001
の字句が全体の式を表す構文要素を表している。
また、演算子そのものは式ではないので、B_P と
E_P では囲まない。 B_P と E_P
の囲みと字句との包含関係を次に示す。
この包含関係は、次のグラフの木構造を表現しているものと解釈する。
すなわち、ある組の囲みが、別の組の囲みを含むとき、前者を親節点、後者を子節点として解釈する。
なお、組とならない字句、例えば、NUM <1> などは、
それを直接包含する節点に属するものとする。
TEBA は、ソースコードの断片も解析できるよう字句列を書換えていく。
書換えは、字句の並びの中から、構文要素の構成のパターンにあてはまる箇所を見つけると、
その箇所の前後に B_P や E_P
のような構文要素を表現する字句を挿入し、
節点を作るとともに、木構造を徐々に構成していく。
この仕組みを実現するために、構文木の葉から根にむかう順序で構文要素となる節点を構成する。
一般的に、構文解析では、LR構文解析や再帰下降構文解析が用いられる。 しかし、これらはソースコードが完全に揃っている状態を前提としている。 TEBA の場合は、構文解析ができない箇所が含まれていた場合は、そこを無視して書換えていくので、 不完全なソースコードも解析できる可能性がある。 なお、興味がある人は “island grammer” を調べるとよい。
2.3 演習: 解析ツールの作成
まず、この演習で使うツールを作成する。字句解析と構文解析の機能を実装したものである。 次に示す Perl のコードを
rw.plという名前のファイルとして作成しなさい。 作成にあたっては、この資料のテキストをそのままコピーすればよい。このツールはファイル
token.defに書かれた字句定義に従って字句解析を行い、 ファイルparser.rulesの定義に従って字句列を書換え、構文解析を行う。 入力は、コマンド引数に指定したファイルまたは標準入力であり、出力は標準出力に書き出す。 なお、パッケージRewriteTokensを使用するが、 旧バージョンと区別するために、導入(use)するときは “RewriteTokens2” という名前を用いる。
#!/usr/bin/env perl
use strict;
use warnings;
use Tokenizer;
use BracketsID;
use RewriteTokens2;
my $input = join("", <>);
my @tokens = Tokenizer->new->load("token.def")
->set_input($input)->tokens;
chomp @tokens;
BracketsID->new->conv(\@tokens);
RewriteTokens->new->syntax_check->rule(&file("parser.rules"))->apply(\@tokens);
print join("\n", @tokens), "\n";
sub file {
my $f = shift;
open (my $fh, '<', $f) || die "Can't open $f: $@";
my $text = join("", <$fh>);
close($fh);
return $text;
}- 次の方法で、このファイルに実行許可を与えなさい。
chmod a+x rw.pl- 次のようにツールを実行し、“
can't load token definition: token.def” というエラーメッセージが表示されることを確認しなさい。表示されないときは、 正しく実行できる状態になっていない。
echo | ./rw.pl- このツールは、カレントディレクトリにある
token.defとparser.rulesを読み込んで動作する。次のようにコマンドを実行し、2つの空のファイルを作りなさい。 touch コマンドについては man で確認すること。
touch token.def parser.rules- 再度、次のようにツールを実行しなさい。
echo | ./rw.pl正しく空のファイルを作っていれば、次のように出力される。
UNIT_BEGIN <>
UNKNOWN <\n>
UNIT_END <>
