1 インストール

1.1 ファイルの展開と準備

インストールしたい場所に展開する。ここでは、ホームディレクトリの下に展開し、 teba という名前でアクセスできるようにする。

TEBA のhttp://tebasaki.jp/srcから最新版をダウンロードする。以下、ダウンロードされたファイルは teba-X.YY.tar.gz と表記し、ホームディレクトリの下の Download というディレクトリに保存されているものとする。 X.YY の部分は実際にダウンロードしたファイルの名前に合わせて読み替えること。
ダウンロードしたファイルを展開する。コマンドライン上では次のように展開する。

cd             # ホームディレクトリに移動 (すでに移動しているなら不要)
tar zxvf ~/Download/teba-X.XX.tar.gz

シンボリックリンクを使って、teba というパス名でアクセスできるようにする。まず、展開すると、バージョン番号が入ったディレクトリ(teba-X.YY)できる。このディレクトリに対してシンボリックリンク teba を作成する。

ln -s teba-X.YY teba

1.2 TEBA の更新

TEBA が更新された場合には、次のようにして新しい版を入れる。

最新版をダウンロードし、最初のインストールと同じ方法で展開する。
シンボリックリンクを貼り直すために、まず、削除する。

rm teba

最初のインストールと同じ方法で、新しいディレクトリに対してシンボリックリンクを作成する。

1.3 パッケージの内容

TEBAのパッケージを展開して得られたディレクトリには、以下のファイルおよびディレクトリが含まれる。

COPYRIGHT
README
TEBA/
bin/
sample/

COPYRIGHT は著作権に関する記述、README は使い方に関する記述が書かれたテキストファイルである。ディレクトリ TEBA には実行に必要なライブラリ等のファイルが、 bin には実行コマンドが配置されている。ディレクトリ sample にはプログラムのパターンによる書換えの例となるファイル群が入っている。

実行にあたっては、bin の下のコマンドを起動する。なお、bin の下のコマンドは、ディレクトリ TEBA からライブラリを読み出すので、この構成は変更しないこと。 (注意: この文書では、ディレクトリ名の teba はパッケージを展開したときに作成したシンボリックリンクを、 TEBA はパッケージの中のライブラリを格納している場所を表すので、区別して読むこと。)

1.4 準備

1.4.1 必須ライブラリのインストール

TEBA は、以下のモジュールを使用するので、使用前にインストールしておくこと。

JSON (https://metacpan.org/pod/JSON)
Algorithm::Diff (https://metacpan.org/pod/Algorithm::Diff)
GraphViz (https://metacpan.org/pod/GraphViz)
Clone (https://metacpan.org/pod/Clone)

インストールには CPAN または、各OSのパッケージ管理システムを利用する。

例: macOS の MacPorts を利用している場合、 p5-json, p5-algorithm-diff, p5-graphviz, p5-clone をインストールする。
例: FreeBSD の pkg を利用している場合、 p5-JSON, p5-Algorithm-Diff, p5-GraphViz, p5-Clone をインストールする。
例: Ubuntsu の apt を利用している場合、libjson-perl, libalgorithm-diff-perl, libgraphviz-perl, libclone-perl をインストールする。

1.4.2 実行パスの設定

各ターミナル(シェル)で、環境変数 PATH に bin を追加する。ターミナルを立ち上げたときに設定されているようにするには、シェルの設定ファイルに定義を加えておく必要がある。例えば、bash を使用している場合には以下の命令を設定ファイル ~/.bashrc に加える。通常は、設定ファイルの最後に加えればよい。

PATH=${PATH}:~/teba/bin

なお、設定ファイルを変更しても、その変更は起動済みのシェルには反映されない。次のように、設定ファイルを読み込むか、新しくターミナルを起動する必要がある (先頭はピリオドとスペースである)。

. ~/.bashrc

(注意: シェルに csh, tcsh, zsh を使っている場合には、各シェルに合わせて設定すること)

1.4.3 環境変数 PERLLIB の設定

ツールがTEBA の Perl ライブラリを利用できるよう、実行パスと同じように、環境変数 PERLLIB を設定する。 PERLLIB には、teba のパッケージ内のディレクトリ TEBA への絶対パスを設定する。

PERLLIB=<TEBAのパッケージの絶対パス>/TEBA

ここで <TEBAのパッケージの絶対パス> は使用しているOSやユーザによって異なる。わからないときは、次のように TEBA が存在するディレクトリに移動し、コマンド pwd を実行して確認するとよい。

cd ~/teba/
pwd

2 TEBA の使い方

2.1 コマンド

ディレクトリ bin の下にあるコマンド(実行ファイル)とその機能は以下の通りである。

cparse.pl

機能	構文情報を含む字句系列を生成する
引数	解析対象ファイル名 (省略した場合は標準入力)

オプション	意味
`-E`	式レベルの詳細の解析をしない (以前の版との互換性維持用)
`-f`	左結合の2項演算子について、連続する同じ演算子の結合を 1つの式単位になるように再構成する (Ex. `(((a) + b) + c) => (a + b + c)`)
`-t`	テストモード (解析時に使用した一時的な仮想字句が残っていないか、仮想字句や括弧の組の対応が正しいかを調べ、異常がある場合には最後に出力する)
`-p`	前処理分岐解析モード (前処理分岐の対応関係に関する情報を挿入する)
`-m`	マクロ識別子統一モデル (マクロ定義された識別子が出現したら、それ以降は同名の識別子の種別をマクロ名(ID_MC)に変更する。 undef には対応していない。)
`-j`	補助的な解析を加えた抽象構文木をJSON形式で出力(記号表を含む)
`-J`	字句系列をJSON形式で出力
`-g`	大域の記号表(JSON形式)のファイルを読み込む

phparse.pl

機能 PHP の構文情報を含む字句系列を生成する。

引数解析対象ファイル名 (省略した場合は標準入力)

オプション意味

-t HTML を読み込み、で囲まれた範囲を解析。

-j 補助的な解析を加えた抽象構文木をJSON形式で出力

オプション	意味
`-t`	HTML を読み込み、で囲まれた範囲を解析。
`-j`	補助的な解析を加えた抽象構文木をJSON形式で出力

id_unify.pl

機能	2つの字句系列で、内部識別記号を統一
引数	字句系列ファイル名A 字句系列ファイル名B
出力	2つのファイルの名前の後ろに、それぞれ .unified を付けたファイルが生成され、その中に統一後の字句列が格納される。

join-token.pl

機能	字句系列から元のテキストを再構成する
引数	字句系列ファイル名 (省略した場合は標準入力)

オプション	意味
`-d`	仮想字句を残した状態で再構成する仮想字句にはエスケープシーケンスで色をつけている。 less を使って見るときは less に -R オプションをつける必要がある。
`-E`	`-d` オプションと同時に使用し、式に関する仮想字句を排除する

rewrite.pl

機能	プログラムパターン記述に基づて字句系列を書換える
引数	字句系列ファイル名 (字句系列ファイル名を省略した場合は標準入力)

オプション	意味
`-p` `プログラムパターン記述ファイル名`	パターンを記述したファイルを指定する。
`-s`	空白保存モード (コメントや空白をすべて残し、できるだけ位置も保つ。削除しないので、不自然な結果になることもある)
`-r`	再帰適用モデル (書換えが行われなくなるまで、繰り返しパターンを適用する。無限ループに陥る場合もある)
`-e`	式モード (パターンを文、宣言、関数としてではなく、単純に式として取扱う。)
`-d`	デバッグモード (プログラムパターン記述から生成される字句系列パターン記述や、さらに、そこから生成される文字列の正規表現を確認できる。)

rewrite_token.pl

機能	字句系列パターン記述に基づいて字句系列を書換える
引数	字句系列ファイル名

オプション	意味
`-p` `"字句系列パターン記述"`	引数に直接記述されたルールに従って書換える
`-f`	字句系列パターン記述ファイル名 (ルールをファイルから読み込んで適用する)
`-d`	デバッグモード (ルールから生成される文字列の正規表現も出力する)

preg.pl

機能	パターン記述に基づいてプログラム断片を検索するパターンの記述方法は rewrite.pl の `%before` と同じ
引数	パターンファイル名

オプション	意味
`-a`	プログラム全体を出力し、その中で該当箇所を `{<` と `>}` で囲む。
`-d`	デバッグモード (検索時に用いるパターンの出力)
`-e`	式モード (パターンを文、宣言、関数としてではなく、単純に式として取扱う。)
`-h`	オプション等の出力
`-t`	テキストではなく、字句系列を出力する。
`-T`	入力ファイルを字句系列として読み込む。
`-v`	出力に色を付加する。(ANSI エスケープシーケンスを使用)
`-f`	直後にファイル名を書き、パターンを引数で指定する代わりにファイルからパターンを読み込む。複数のパターンを同時に指定するときは、パターン間を `"%%--\n"` で区切る。
`-l 行数`	適合箇所の前後のオプションに指定された行数を出力する。該当箇所は `{<` と `>}` で囲まれて出力される。
`-b ブロック数`	適合箇所を含むブロック(文/宣言/関数/マクロ定義) 全体を出力する。オプションには、何ブロックの入れ子を遡るかを指定する。該当箇所は `{<` と `>}` で囲まれて出力される。
`-s ブロック境界数`	適合箇所の前後のブロックの境界を、オプションで指定された数だけ含めて出力する。該当箇所は `{<` と `>}` で囲まれて出力される。
`-p`	直後に検索するパターンを記述する。パターンが “`-`” (ハイフン)で始まる場合に、オプションとして解釈させないために用いる。
`-r`	マッチした箇所の前後の一時仮想字句 `/_[RM][BE]/` を取り除く。広い条件で適合させたあとの字句系列に対し、例外として排除したいパターンを指定して、適合箇所から除外するときなどに使用する。
`-u`	入力から一時仮想字句 `/_[RM][BE]/` をすべて取り除いてから、パターンに適合する。文脈となる条件で取り出した字句系列から、さらに目的のパターンに適合する箇所を取り出すときに使用する。
`-j`	名前付きの変数に適合した字句系列を JSON 形式で、 SP_PVAR 型の字句として埋め込む。 `-t` オプションがない場合には、ソースコード内に直接 JSON 形式が埋め込まれる。

extract_sp_pvar.pl

機能 preg.pl が出力する SP_PVAR 字句の JSON 形式のデータを整形して出力するサンプルコード

引数字句系列ファイル名

オプション意味

-t 整形する際に、字句系列をテキストに変換

オプション	意味
`-t`	整形する際に、字句系列をテキストに変換

teba2json.pl

機能	字句系列を JSON 形式の構文木に変換。接頭辞が `B_` と `E_` の仮想字句は、これらの接頭辞は削除される。パターンにおいても、削除後の名前に適合する。
引数	字句系列ファイル名

オプション	意味
`-p パターン`	指定されたパターン(正規表現)名の要素のみ残した縮退木を生成
`-t`	字句の並びを結合してテキストに変換
`-d`	内部データとして持つ構文木をダンプ

json2teba.pl

機能 JSON 形式の構文木から字句系列に変換(ただし、字句系列は完全ではない)

引数字句系列ファイル名

オプション なし
ast2dot.pl

機能 JSON 形式の構文木を GraphViz の dot 形式に変換

引数字句系列ファイル名

オプション意味

-p dot 形式の代わりに PNG 画像に変換して出力

オプション	意味
`-p`	dot 形式の代わりに PNG 画像に変換して出力

ast2cfg.pl

機能	JSON 形式の構文木(AST)を制御フローグラフ(CFG)に変換し、そのCFGを追加したAST(JSON形式)を出力
引数	JSON形式のASTファイル名

オプション	意味
`-e`	式の制御フローを含む(default)
`-E`	式の部分木の上位の論理演算までの制御フローに限定する
`-S`	文までの制御フローに限定する
`-l`	論理演算子(&&, \|\|)を取り除く。
`-c`	条件式が定数で真偽が固定されている。

cfg2dot.pl

機能制御フローグラフを含む構文木(JSON形式)を読み込み、GraphViz の dot 形式に変換

引数制御フローグラフを含む構文木(JSON形式)のファイル名

オプション意味

-a 構文木も一緒にグラフにする。CFG と AST は色分けされる。

-s 簡素化したグラフを生成する。

オプション	意味
`-a`	構文木も一緒にグラフにする。CFG と AST は色分けされる。
`-s`	簡素化したグラフを生成する。

program_slicer.pl

機能	JSON 形式の制御フローグラフを用いてプログラムスライシングを実行
引数	制御フローのJSONファイル名

オプション	意味
`-i`	スライス基準となる変数参照に id を付けてソースコードを表示
`-t id`	指定された id をスライス基準として、スライスを求めて表示

c_intp.pl

機能 JSON形式の制御フローグラフに基づいてプログラムを解釈実行(機能の一部のみ実装)

引数制御フローのJSONファイル名

2.2 特殊タグ

プログラム解析で、解析対象のプログラム中に解析補助用のタグを埋め込みたいことがある。 TEBA では、次の書式の字句を特別なタグ字句として扱い、スペースと同じ扱いをする。なお、この字句の種別は SP_TAG になる。

#@\w+

また、JSON 形式の抽象構文木にしたときは、構文要素と同じようにオブジェクト化される。ただし、タグの有無によって、構文要素の id が変動しないよう、タグのオブジェクトには id を割り振らない。

2.3 コマンドの典型的な組み合わせ

基本的には、以下のように使用する。(書換え対象のソースファイルを Source.c、書換えパターンのファイルを Pattern.pt とする。)

cparse.pl Source.c | rewrite.pl -p Pattern.pt | join-token.pl

出力をファイルに保存したい場合はリダイレクトを利用する。 (出力先のファイル名を Result.c とする。Source.c に直接書き込んではいけない。)

cparse.pl Source.c | rewrite.pl -p Pattern.pt | join-token.pl > Result.c

less を使って確認したいときは、以下のようにパイプで接続する。

cparse.pl Source.c | rewrite.pl -p Pattern.pt | join-token.pl | less

構文解析後あるいは、書換え後の構文の情報を確認したい場合には、 join-token.pl の -d オプションを用いる。また、エスケープシーケンスを正しく処理させるためには less には -R` オプションをつける必要がある。

cparse.pl Source.c | join-token.pl -d | less -R
cparse.pl Source.c | rewrite.pl -p Pattern.pt | join-token.pl -d | less -R

書換え前後の字句の違いを調べたいときは以下のように diff で比較する。

cparse.pl Source.c > Source.t0
cparse.pl Source.c | rewrite.pl -p Pattern.pt > Source.t1
diff -u Source.t0 Source.t1

ただし、書換えによって、同じ構文要素であっても内部識別記号が変更され、差分として出力されることがある。それを避けるためには、以下のように diff で確認する前に id_unify.pl を用いて統一し、統一されたファイルを比較する。

cparse.pl Source.c > Source.t0
cparse.pl Source.c | rewrite.pl -p Pattern.pt > Source.t1
id_unify.pl Source.t0 Source.t1
diff -u Source.t0.unified Source.t1.unified

TEBA のツールは、UNIX のコマンドの基本理念を尊重して作成しており、シェルとの組み合わせを重視している。すなわち、リダイレクトやパイプなどの機能を用いることや、 diff などの既存のツールと組み合わせることを前提として、余分な機能は作り込まないようにしている。よって、利用にあたっては、シェルに関する知識を習得していることが望ましい。

2.4 プログラムパターンの記述方法

2.4.1 全体の構成

rewrite.pl を使うとプログラムのパターン変換を実現できる。パターン変換は、以下の例ように、変更前と変更後の記述を %before と %after の直後に書く。

% before

  for ( ${init:EXPR} ; ${cond:EXPR} ; ${succ:EXPR} )
    ${stmt:STMT} $;

% after

  ${init};
  while (${cond}) {
    ${stmt} $;
    ${succ} ;
  }

% end

なお、この記述は、for 文を while 文に置き換える記述の例である。以下、パターンの表現方法について説明する。

2.4.2 パターンの表現

変数名や式など、可変な要素を表現するために、パターンでは以下の表現が容易されている。

パターン変数
グループ
オプション指定

以下、それぞれについて説明する。

2.4.2.1 パターン変数

パターン変数は、任意の識別子、型、式、文、宣言子、宣言に適合する変数で、変更前(%before)では以下のように、適合する要素の種別を指定して書く。

書き方: ${変数名:種別}, ${{変数名:種別}}

使用例: ${s:STMT}, ${e:EXPR}, ${{var:ID_VF}}, ${:DECR}

パターン変数は ${:DECR} のように変数名を省略することもできる。ただし、その場合、次に述べる変更後(%after)で、その変数を参照できない。後述する「グループ」を使用したときに、参照する必要がない変数が生じることがあり、その記述を簡便にするために省略する。

2種類の書き方があるが、どちらもパターン変数は指定された種別のみに適合する。ただし、${{変数名:種別}} は、前後に任意の字句列が存在することを許容する。すなわち、実質的には、以下のように3つのパターン変数を指定している場合と同じである。

${:ANY} ${変数名:種別} ${:ANY}

ただし、パターンにこれを直接記述すると、構文解析では3つ変数が並んでいると解釈され、この前後に演算子を配置すると、どちらかの {$:ANY} と適合するので、期待通りの構造を得られない。

変更後(%after)は、以下のように名前だけを書き、変数の参照を表す。パターン変数の参照は、その変数に適合した字句への置き換えを意味する。変数名は省略できない。

書き方: ${変数名}

使用例: ${s}, ${e}, ${var}

なお、変更前(%before)で、パターン変数に適合したものと同じものが存在することを示したい場合には、変数名のみを書く。例えば、同じ文が並んでいることを表すパターンは以下のように書く。

%before
  ${st:STMT} $;
  ${st} $;
%after
   ....(略)...
%end

ここで、“$;” は、文の終りを表す特別な記号である。これは、パターンを構文解析するときに文の区切りを明確に指定する役割がある。

パターン変数に用いる「種別」は、1つの字句に適合させたいときは字句の種別を、複数の字句の並びに適合させたいときは、ファイル TEBA/default-token.def に文字列の正規表現を用いて名前を定義して使用する。

2.4.2.2 グループ

グループは、記述の繰り返しや存在しない場合もあることを表現したいときに用いる。正規表現で用いる *, +, ? にも対応している。以下に記述例を示す。

% recursive
% before

  ${type:TYPE} ${decr:DECR} , $[others: ${:DECR} $[: , ${:DECR} $]* $] ;

% after

  ${type} ${decr};
  ${type} $[others];

% end

グループは、グループの開始と終了を表す2つの記号で表現され、以下の形式で記述する。

グループの開始: $[名前:

グループの終了: $]

名前は省略可能であるが、%after で適合した字句列を参照できなくなる。字句列を参照するにはグループの名前を用いて、以下のように記述する。

$[名前]

なお、パターン変数と同様に ${名前} と参照することも可能だが、その場合、式を構成する B_P と E_P に囲まれる。このとき、構文木としては妥当ではない状態になる可能性が高い。

グループのオプションとして、‘*’, ‘+’, ‘?’ の3つ記号を用いて、それぞれ「0回以上の繰り返し」、「1回以上の繰り返し」、「1つ以下存在する」の 3種類の条件を表現できる。それぞれ、以下のように、グループの終了の後ろに記号を記述する。

0回以上の繰り返し: $[名前: …. $]*

1回以上の繰り返し: $[名前: …. $]+

1つ以下存在する: $[名前: …. $]?

なお、グループは、繰り返し全体の字句を参照する。すなわち、正規表現で(abc)* と記述した場合、グループ(括弧の組)を後方参照したときに、繰り返される abc のうち最後の abc のみが対象となる。 TEBA におけるグループは、正規表現で表したときは ((abc)*) と二重に用いたときの外側のグループに対応する。

パターンを構文解析するときに、グループは空白として扱う。グループの開始記号と終了記号は、その存在を無視したときに構文的に妥当である限り、どの位置でも用いることができる。

また、グループでは、選択(論理和)も以下の記号で表現できる。

$|

ただし、パターンを構文解析するときは空白と同等に扱うので、 $|を無視したときに構文解析ができ、かつ、構文木の部分木が意図通りになるように配置することが必要である。例えば、exit() と return のどちらかに適合したいときは以下のように記述する。

$[exit: exit(${:EXPR}); $| return ${:EXPR}; $]

この記号の扱いには制約があるので注意が必要である。例えば、上記の記述で、共通するセミコロンを外側に出した以下のような記述をすると、構文解析では、exit(${:EXPR}) return ${:EXPR}; という文法的にありえな文を解析することになり、意図通りには適合しない。

$[exit: exit(${:EXPR}) $| return ${:EXPR} $] ;

現状としては、連続して並んでも文法的に正しい状態であることが必須であり、実際的には文や宣言の選択にのみに利用可能である。

また、以下のように、選択の中でパターン変数に名前を付けた場合、

$[exit: exit(${e:EXPR}); $| return ${e:EXPR}; $]

パターン変数 `${e}1 は、それぞれの選択で適合した字句列を参照する。なお、この場合、各選択の中のパターン変数の名前とその出現順序は一致している必要がある。内部の実装では Perl の正規表現の “branch reset” を使用しているので、詳細については、名前を用いた後方参照と合わせて Perl のマニュアルを参照すること。

2.4.2.3 オプション指定

オプション指定は、rewrite.pl のオプションのうち -s, -r, -e に対応しており、それぞれ以下のように記述する。

% space preserving
% recursive
% expression

なお、各オプション指定は先頭の1, 2文字だけを見て区別しており、 %s, %r, %ex と省略して書いてもよい。

2.5 字句系列パターンの記述方法 (RewriteTokens)

(注意: この記述は RewriteTokens Ver.1 についてである。 Ver.2 は別の資料を参照すること。)

字句系列に対するパターンは以下の3つの記述から構成される。書換えルールは基本形と、字句の置換と削除のためのルールの2種類に分けられる。

書換えルール
- 基本形
- 字句の置換と削除のためのルール
- 字句の分割
- 文字列から識別子への変換
字句種別定義
フィルタ

2.5.1 基本形

書換えルールは、書換え前の字句列の状態と書換え後の状態の記述で構成され、以下のように記述する。

{ 書換え前の字句列の並び } => { 書換え後の字句列の並び }
{ 書換え前の字句列の並び } =>> { 書換え後の字句列の並び }

真ん中の記号のうち、=> は、ルールを1回だけ適用することを、 =>> は書換えができなくなるまで繰り返し適用することを意味する。

2.5.1.1 書換え前の字句の並び

書換え前の字句列の並びは、以下の要素で構成される。

型付き字句変数 $名前#後方参照名:{型指定}{字句指定}, ‘#後方参照名’ は省略可能, {型指定} => 型名 or /正規表現/, {字句指定} => /正規表現/ (省略可能)

テキスト指定字句変数 $名前:'テキスト' $名前#後方参照名:'テキスト'

変数参照 $名前

字句参照 'テキスト':型

グループ $[名前: … $] オプションとして、閉じ括弧は $]*, $]+, $]? と書ける。また、括弧の前の $ を省略して [名前: … ] と書いてもよい。

結合演算子 $##

文字列化演算子 $#

コメント # で始まる行

コメントブロック [* から *] まで

このうち、グループの表記は、プログラムパターン記述のグループと同じであるので、以下では説明を省略する。

「型付き字句変数」は、その型、すなわち種別名に合致する字句に適合する。型は、$bp:B_P のように、種別名をそのまま書くか、 $ct:/CT_.*/ のように、スラッシュで挟んで種別名の正規表現を指定する。「後方参照名」(後述)と「字句指定」は省略が可能である。「字句指定」には、$while:ID_VF/[A-Z1-0_]+/ のように、スラッシュで挟んだ正規表現を書くことで、適合したいテキストを指定する。

「テキスト指定字句変数」はテキストに合致する字句に適合する。 (同じことが型付き字句変数で表現できるので、廃止される可能性あり)

それぞれの変数は、同じ字句が出現していることを示すときに参照することができ、その「変数参照」は名前のみを記述する。いずれも名前は省略可能だが、省略した場合は参照することはできない。

また、単に字句の存在だけを指定したいときは「字句参照」を用いる。字句はそのまま正規表現の一部として扱うので、バックトラックを制御する特殊なメタ記号などを挿入したい場合にも利用できる。

「型付き字句変数」と「テキスト指定字句変数」は、オプションとして「後方参照名」を指定できる。これは、括弧や仮想字句のように、開始と終了で1つの組になっているものについて、正しい組み合わせで変数に合致させるときに用いる。例えば、丸括弧の組を表現したときは、以下のように記述する。

$pl#1:P_L  ...  $pr#1:P_R
$pl#1:'('  ...  $pr#1:')'

なお、「後方参照名」は文字または数字の組み合わで表現し、上記の例では単純な 1 を使っている。ルールの中で、入れ子など複数の組が存在する場合には、以下のようにそれぞれの組ごとに別の名前をつける必要がある。

$pl1#outer:P_L  $pl2#inner:P_L  ...  $pr2#inner:P_R  $pr1#outer:P_R

補足: このように後方参照名が適切に書いているかを確認するのは容易ではないので、 RewriteTokens Ver.2 では、参照名を省略する記法を導入している。)

2.5.1.2 書換え後の字句の並び

書換え後の字句列の並びは、以下の要素で構成される。

変数参照 $名前 or $名前:型

字句参照 'テキスト':型 or 'テキスト'#後方参照名:型

結合演算子 $##

「変数参照」は、書換え前の字句列に含まれる変数の参照であり、変数に適合した字句または字句列への置き換えを意味する。名前の後ろに型をつけた場合は、字句の型を指定したものに変更することを意味する。ただし、その場合は、変数は単一の字句に適合していることが必要となる。

「字句参照」は、指定した型(種別名)の字句に置き換わることを意味する。後方参照名は、括弧や仮想字句など組を構成する字句を配置する場合に使用し、同じ後方参照名を持つ字句には、同じ内部識別番号を割り振り、それらの組を表現する。TEBA の解析ルールを例として以下に示す。

@TERMINAL => "(?:ID_(?:VF|MB|MC)|LI).*+\n"
{ $id:TERMINAL } => { ''#1:_B_X $id ''#1:_E_X }

TERMINAL は、終端記号となる識別子と定数値を表す種別であり、その前後に仮想字句 _B_X と _E_X を組になるように入れることを意味する。

2.5.1.3 置換と削除の記法

置換と削除の記法は、特定の範囲に含まれる字句の置換と削除を記述するための記法であり、次のように記述する。

{ 置換したい字句 in それを囲う型 } => { 置換後の字句 }
{ 削除したい字句 in それを囲う型 } => { }

「置換したい字句」および「削除したい字句」は型付き字句変数で書く。ただし、型指定のみが許され、字句指定はできない。また、「それを囲う型」は型名のみを書くが、範囲は、その型名に B_ または _B_ を付けた型の字句から E_ または _E_ を付けた型までとなる。「置換後の字句」も型付き字句変数で書くが、型指定のみが許され、かつ、型指定に正規表現は使用できない。例えば、_B_PCOND と _E_PCOND で囲われた範囲の IDN 型を ID_MC 型に変換したいときは次のように記述する。

{ $:IDN in PCOND } => { $:ID_MC }

この例では変数名を省略しているが、記述していもよい。この特殊な記法を使用しなくても、削除や置換は表現できるが、極めて効率が悪く、定義が複雑化する。この記法を用いた場合、専用のルーチンに置き換わるので、高速に処理される。

(補足: この記法では囲う型が存在することが前提であり、適用範囲は限定的である。 RewriteTokens Ver.s2 では、これを一般化し、指定した文脈内の部分字句列に対して、任意のルールを適用できる記法が導入されている。)

2.5.1.4 字句の分割 (結合演算子)

同じ接頭辞を持つ識別子に適合したいときなど、識別子を分割したいときは結合演算子 $## を用いる。結合演算子は、前後の変数を1つの字句として処理する。例えば、以下のように記述すると、1つの字句を “_” の直前で分割し、 2つの字句に分けることができる。

{ $x:IDN/\w+/ $## $y:IDN/_.*/ } => { $x $y }

この場合、直感的には、字句のテキストに対し、/(\w+)(_.*)/ という正規表現に適合させ、 2つのグループに適合した字句が $x と $y に格納される。なお、$## の後ろの字句の型は無視され、前の字句の型に統一される。

上記の例で、$x のパターンとして /\w+/ を指定しているが、これを /\w*/ や /.*/ など、長さ 0 の字句が適合できるようにすると、 $y の結果に適当し続け、停止しなくなるので注意が必要である。

この演算子は、C言語の前処理で用いる ## 演算子を模倣しており、 ## 演算子を使用したマクロ定義をパターン化するときなどに使用できる。

2.5.1.5 文字列から識別子への変換

ある文字列を変数名として扱いたいときは $# 演算子を用いる。例えば、次のようなマクロ定義について、この定義の逆の変換、すなわち、マクロの展開後に合致する字句列を検索してマクロ呼び出しに置換えることを考える。

#define print_int_var(v) printf("debug: %s = %d\n", #v, v)

このとき、検索する展開後のコード片の例は次の通りである。

printf("debug: %s = %d\n", "hoge", hoge)

このうち2番目と3番目の引数は、文字列と変数名であるが、どちらも hoge であることが条件として必要となる。この条件を含めて、2番目と3番目の引数部分に適合するパターンは次のように記述できる。 (注意: B_P と E_P は省略している)

{ $# $v:LIS $c:CA $v:ID_VF }

この場合、最初の $v は文字列(LIS)として適合するが、文字列定数の中の文字列を取り出し、 2番目の $v の後方参照は、その文字列を名前とする識別子の参照になる。

次のように、後方参照する方に $# を付加することもできる。

{ $v:ID_VF $c:CA $# $v:LIS }

書換え後に $v を参照した場合、一律に IDN 型になる。これは、書換え後の型を正確に求められないからである。もし、書換えルールを書くときに、型がわかるのであれば、 $v:ID_VF のように型を明示的に指定することが望ましい。

2.5.2 字句種別定義

字句種別定義は、複数の種別を扱いたい場合など、特殊な種別を用いたいときに定義する。記述方法は以下の通りである。

@種別名 => "正規表現"

ここで記述する正規表現は、TEBA の属性付き字句全体を表現するもので、最後は改行(\n)を明示的に記述する必要がある。また、正規表現の中で、 @種別名 と書くと、その種別名の定義が展開される。 (補足: 将来的には、生の正規表現を扱うのではなく、抽象化された簡便な記述の導入が必要であると認識しているが、最適化が必要になるなど簡単ではない。)

記述例として、TEBA における空白の連続の定義 @SP と、それに必要な種別の定義を示す。 (TEBA/token-pattern.def より)

@TOKEN => ".*+\n"
@ANY => "(?:@TOKEN)*?"

@_SPC => "SP.*+\n"
@_DIRE => "B_DIRE.*+\n(?>(?:@ANY)E_DIRE).*+\n"
@_SP => "@_SPC|@_DIRE"
@SP => "(?:@_SP)*+"

以下に、これらの一部について説明する。

@_SPC は、種別名が SP で始まるすべての字句に適合し、空白文字や、改行などに適合する。
@_DIRE は、前処理命令を1つの単位として扱うためのパターンで、構文解析時に前処理命令が途中に含まれても無視することができる。
@_SP は、1つの空白を表現し、@_SPC と @_DIRE を組み合わせている。基本的な記述の流儀として、“_” で始まる種別名は、定義を構成する部分的な要素で、かつ、ルールの記述では直接使用する可能性が低いものに用いている。

ここでの例の @_SP と @SP のように、 1種類の字句の定義とその連続の定義を分けて記述すると、 1種類の字句の定義の方は部品として他の定義でも用いることができるので、再利用性が高まる。

TEBA では、各解析のためのルール定義(TEBA/*.rules)や、字句の種別定義(TEBA/token-pattern.def)の中で、正規表現の最適化を考慮して記述している。特に、バックトラックの抑制は重要であり、上記の例の中で、頻繁に用いている “*+” や、@_DIRE の “(?> … )” はバックトラックの必要がないことを指示するために用いている。 TEBA のルール定義の中では、'(?>':X や ')':X といった X 型を使用した記述が含まれるが、これもバックトラックの抑制のために用いている。正規表現の詳細については、Perl の正規表現のドキュメント (man perlre または perldoc perlre)を熟読すること。

(補足: バックトラックの原因は、字句の適合範囲を求めるときに、最長になるような戦略になっているからである。これは一般的な正規表現のエンジンで採用されている戦略である。 RewriteTokens2 では、これを最短になる戦略に変更しており、バックトラックが発生しない。よって、このようなバックトラック抑制のための特殊な表記は存在しない。)

同じ名前の定義が重複した場合、後方に記述された定義が優先され、全体における定義となる。部分的に定義が変わることはない。また、以下のように、自分自身を参照することができる。

@_EXPRS => "@_EXPRS|_[BE]_(?:A|OP).*+\n"

この場合、右辺の自分自身の参照は、この定義の直前までの定義に置き換わる。これにより、定義を読み込んだときに、オーバーライドすることも可能になる。上記の例は、expr-p01.rules において、一時的な仮想字句 _[BE]_A と _[BE]_OP01 を式の要素として扱う必要があるので、オーバーライドによって拡張している。 (補足: 本来は “@_EXPRS|_[BE]_(?:A|OP01).*+\n” と書くのが正しいが、 OP までで対象が確定するので、手を抜いて 01 は省略している)

2.5.3 フィルタ

フィルタは、ルールを適用していく過程で、特別な処理をしたい場合に、その指示を記述する。指示として記述できるものは以下の通りである。

規則の挿入 @"ファイル名"

実行フィルタ @|Method|

強制停止 @!BREAK!

「規則の挿入」は、それが書かれた場所に指定されたファイルを展開する。これはC言語の前処理における #include とほぼ同じである。

「実行フィルタ」は、書換えルールでは対処できない処理を扱うときに用いる。 TEBAの解析器における使用例を以下に示す。

@|BeginEnd->new()->conv|
@|CoarseGrainedParser->delete_stmt_in_compound_literal|
@|NameSpaces->id_member|
@|NameSpaces->id_fix|

モジュール BeginEnd は、仮想字句の各組に対して、その組を表現する内部識別記号を割り振るものである。規則の中で、組の字句を片方ごとに挿入したような場合には、正しく組の関係が維持されないので、内部識別記号を割り振り直すときにこのようなフィルタを用いる。

CoarseGrainedParser->delete_stmt_in_compound_literal は、文ではない中括弧、すなわち、構造体型の変数や配列の初期化式や、複合値から、文の区切りを表す仮想字句 [BE]_ST を削除する処理である。これは書換えルールとしては記述可能だが、極めてパフォーマンスが悪いことから、専用の処理を書いて置き換えている。 (補足: RewriteTokens2 では、書換え箇所の文脈を指定できるので、このようにフィルタで逃げる必要はない)

NameSpaces は、変数と型、タグ、メンバなど識別子の種別を解析し、置き換えるためのフィルタである。

「強制停止」はデバッグ用の機能であり、それが書かれた箇所で処理全体が止まり、その時点までの解析結果(すなわち字句系列)が出力される。また、その直前のルールから生成された正規表現の記述も出力される。ルールが期待通りに適用されない場合に、その直前または直後の状態を確認することで、原因がわかる場合がある。

2.6 字句系列パターンの適用順序

字句系列パターンの処理は、モジュール RewriteTokens が行う。これを使用するときは、そのインスタンスを生成して実行するが、ルールの適用方法を選択できる。以下に生成方法と適用のされ方を示す。

RewriteTokens->new() ルールの上から下に適用を試み、書換えられたら、また先頭に戻って繰り返す。最後のルールまでに書換えが発生しなければ終了する。

RewriteTokens->seq() ルールを上から下に1度だけ適用していく。

RewriteTokens->rep() ルールを上から下に1度だけ適用していき、 1回でも書換えが起きていれば、再度、先頭から適用を繰り返していく。書換えが発生しなければ終了する。

TEBA の解析では、ルールの状況に合わせて、これらを組み合わせて実現している。 RewriteTokens を使用する場合は、できるだけ seq() を使うと、無限ループに陥いる不具合を回避しやすく、効率も良い。また、同じ繰り返しでも rep() の方が問題が起きたときにその挙動を理解しやすい。ただし、実行効率は、必ずしも rep() の方が良いとは限らない。

new(), seq(), rep() の各メソッドは、引数にルールを渡せば、インスタンスの生成と同時にルールを設定する。インスタンスを生成したあとに、ルールを設定したい場合は set_rules() を使う。また、すでに設定したルールの後ろにルールを追加したいときは、add_rules() を使う。なお、ファイルから読み込ませたいときは、load() を用いる。 load() は内部で add_rules() を呼んで設定を行なっており、読み込んだ順に登録される。ルールの適用順序も読み込んだ順に従う。

3 TEBA の内部の概要

3.1 cparse.pl (CParser.pm)

cparse.pl は、CParser.pm を呼び出すラッパーであり、基本的な処理は CParser.pm に記述されている。処理は解析対象のテキストを以下の順に処理していく。

Tokenizer で字句に分解する
前処理指令について解析する
括弧の対応関係について解析する
マクロ文を解析する
文レベルの粗い解析をする
名前空間の切り分けを行う
式レベルの解析を行う
補正処理と宣言の識別を行う

これらの処理は可能な限り、字句系列の書換えルールとして実現している。書換えルールでは、様々な要素の組み合わせに対応できるよう、目的の構造の核となる部分を特定して、一時的な仮想字句を配置してから、その仮想字句を基としてさらにルールを適用していく手法が取られている。このとき、一時的な仮想字句の型名は、必ず “_” で始めるようにしており、解析の終了までには削除れるか、名前が変更される。よって、解析結果に “_” を含む型が含まれたときは、何らかの理由で解析に失敗していることを意味する。また、型名を見ることで、問題が起きたルールを見つける手掛りとなる。

各処理の概要は以下の通りである。

Tokenizer は字句解析器であり、TEBA/token.def に従って字句に分解する。分解された結果は、属性付き字句系列となる。
前処理指令のみを解析し、前処理指令の範囲を確定する。これにより、以後の解析で、前処理指令を空白として扱ったり、前処理指令の内部に閉じた構文解析が可能になる。(TEBA/prep.rules)
括弧の対応関係を解析し、対応する組には同じ内部識別記号を割り当てる。また、対応する括弧の数が合わないマクロ定義があった場合には、テキストを持たない仮想字句として、疑似的な括弧を挿入し、必ず組が閉じるようにする。 (TEBA/BracketsID.pm)
マクロを文や宣言のように使用していて、かつ、行末がセミコロンでは終わっていない場合に、仮想字句として擬似的なセミコロンを追加して、整合を取る。なお、これはヒューリスティックな規則であり、完全ではない。(TEBA/macro-stmt.rules)
文レベルまでの解析をする。式のレベルの解析をしない理由は、型とそれ以外の識別を区別できないと、構文木を唯一に決められない曖昧な表現があるためである。例えば、式 (x)(y) は x が型か関数名かによって木構造が異なる。そのため、先に曖昧さの少ない文レベルまで解析し、識別子がどの名前空間に属するかを推定してから、式レベルの解析を行う。 (TEBA/CoarseGrainedParser.pm)
名前空間の切り分けは、識別子をタグ、ラベル、メンバ、マクロ、型、変数または関数に分ける。マクロを使った特殊な形がない限り、タグ、ラベル、メンバは前後の文脈から正確に決まる。マクロは、本来は名前空間に属さない分類であるが、前処理指令の中など明確にマクロ名とわかるものだけを取り扱う。型は、文脈から推定して型と確信が持てるものだけを置き換える。最終的に残った識別子を変数または関数として扱う。(TEBA/namespace.rules)
式レベルの解析は、優先度に基づいて解析をしていくのみである。ただし、+ や - のように単項演算子と2項演算子の両方がありうるものを区別するために、単項演算子の文脈で出現する演算子を識別し、型名を OP_U に変更して区別する。また、カンマは演算子であるが、線形構造を表現することに意味があるとは思われないので、解析ルールを定義しているが、実際には適用していない。(TEBA/EParser)
引数に文を含むマクロ呼び出しや、末尾にセミコロンがないが文や宣言と同様に扱うマクロ文など、解析が正しく行えない事例に対して、解析結果を補正を行う。この時点では、式の解析が行われているので、正しく解析されていればありえない字句の並びから誤った箇所を同定し、補正を行う。また、宣言の識別はこの最終段階で行う。これは、補正で新たに文が追加されることと、宣言の識別に依存するルールは存在しないからである。

3.2 CoarseGrainedParser.pm

CoarseGrainedParser.pm は文レベルまでの構造を解析する。その処理は大きく3つの段階で構成している。

文の区切り位置の同定(制御文の入れ子は除く)
制御文の入れ子の解析の準備
制御文の入れ子の解析

各段階の概要は以下の通りである。

セミコロンの直後など、文の区切りとなると想定される箇所に B_ST または E_ST を入れていく。なお、宣言はすべて文として扱う。宣言の初期化式の中など、文脈を調べないと区別がつかない箇所は、まず、文の区切りとして扱い、そのあと、文が出現しない特定の文脈を特定してから区切りを取り除く。また、この段階では、制御文は識別せず、式文やジャンプ文など、制御文以外の文を識別する。 B_ST と E_ST は組にならないといけないが、片方ずつ入れているので、マクロの定義の中などでは、数が合わない可能性があり、それも補正している。 (TEBA/parser-stage1.rules)
制御文の入れ子の解析の準備として、条件式を含む頭の部分を識別し、これを次の段階の出発点とする。また、関数の識別を行い、書換えの適用範囲が関数をまたがる危険性を解消している。(TEBA/parser-stage2.rules)
条件式の部分から右側の文を取り込むように範囲を広げ、それを文として識別する。入れ子になっているので、再帰的に適用する。なお、構文上、ラベルは文の外側に存在するものだが、一旦、中に移動させてから制御構造の入れ子を識別している。これは、制御文の本文が複合文ではなく、かつ、ラベルが付与されている場合に正しく解析できないためである。 (補足:グループを使えばこのような手間を避けられる可能性が、複雑なルールは大量のバックトラックを引き起すことがあるので注意が必要である。) (TEBA/parser-condstmt.rules)

3.3 EParser.pm

EParser.pm は式レベルの解析をするにあたり、以下の書換えルールを適用していく。ファイル名の p の後ろの数字は、演算子の優先度のレベルを表しており、優先度の高いものから徐々に解析していく。

TEBA/expr-base.rules
TEBA/expr-p01.rules
TEBA/expr-p02.rules
TEBA/expr-p03-12.rules
TEBA/expr-p13.rules
TEBA/expr-p14.rules
TEBA/expr-p15.rules

expr-base.rules は、解析の準備であり、変数などの終端要素や括弧で囲われた式など、解析の出発点となる要素を識別する。また、単項演算子と二項演算子を区別するために、単項演算子が出現する文脈に基づき、単項演算子の型名を OP_U に変更している。優先度 03 から 12 の演算子はルールの構成が同じであり、可読性の観点で1つのファイルにまとめている。それ以外は、ルールに特徴があるので、管理しやすいように別のファイルにまとめている。例えば、優先度 02 と 13 は、再帰的に繰り返す必要がある。なお、すでに述べた通り、現在の実装では、カンマ演算子の解析を実装している expr-p15.rules は適用していない。

演算子は、同じ優先度の演算子に関して、左結合と右結合があり、その結合の方向に従って式を識別していく必要がある。そこで、各ルールでは、一時的な仮想字句を使って、正しく結合するように処理している。この一時的な仮想字句の型の名前には演算子の優先度を入れており、正しく処理されなかったときに、どの規則で問題が起きたか把握できるようになっている。また、右結合の演算子について書換えルールを定義する場合、演算子の左側に任意の式が存在するので、一つのルールの中に選択を含む箇所が増え、大量のバックトラックが発生しやすい。よって、選択を減らすようルールを分解して記述している。

3.4 rewrite.pl, ProgTrans.pm

rewrite.pl は ProgTrans.pm の機能を利用してプログラムの書換えを実現する。基本的な処理の流れは以下の通りである。

プログラムパターンの %before と %after をそれぞれ構文解析する
各結果に対して、パターン変数や空白類の正規化等の補正を行う。
各結果から、字句系列のパターンの前と後を生成し、書換えルールを構成する。
RewriteTokens を用いて、入力に対して書換えを適用する。

プログラムパターンは、プログラム本来の記述とほぼ同じであるが、パターン変数などの拡張があり、そのままの CParser.pm では解析できない。しかし、CParser.pm には、字句の定義の追加や、処理の途中にフィルタを加える方法が用意されており、それを用いて拡張している。なお、フィルタをどこに追加すればよいかは、 CParser.pm の各段階を正しく理解していないと判断できない。

%before と %after の各パターンを構文解析によって字句系列に変換したあと、それぞれ字句系列のパターンに変換するが、パターン変数や空白などに関しての特別な処理が必要である。例えば、文に適合する STMT 型の変数 ${stmt:STMT} を使用した場合、構文解析の段階では文として解析する方法がなく、識別子として解析を行う。その場合、パターン変数の前後は式を表す B_P と E_P に囲まれ、文に適合しなくなる。よって、このような型に合わせて不要な仮想字句を削除することが必要である。

空白についても特別な処理を行う。すなわち、%before に記述された空白類と、実際に適合させたいプログラムの断片の空白類が一致するという保証はなく、空白類が入りうる箇所すべてに任意の空白が存在することを前提とする必要がある。一方、文や式など仮想字句で囲われる非終端記号については、その開始と終了は空白ではないので、そこに空白が入ることを前提にすべきではない。よって、すべての字句間にスペースを入れたあと、仮想字句の直後または直前の空白を削除し、あらゆる空白の連続を1つの空白に置き換えるという正規化を行い、その空白を任意の空白類に適合する変数に置き換えるという処理をしている。

さらに、-s オプションを用いた場合には、%before で適合した空白類が %after に保存されるよう、 %after 側の字句系列の間に空白類の参照が含まれるように変換を行う。基本的な戦略として、%before の空白類の前後のテキストを持つ字句のうち、 %after 側にも出現していて、かつ、最も近いものを特定し、すべての空白類はその字句に付随するように移るという方法を採用している。空白類を削除しないので、必ずしも適切な処理とはならないが、直感的にはほぼ位置が変わらないように見える結果を得られる。

書換えそのものは、RewriteTokens を用いて行うが、内部識別記号が重複するなど字句系列としての整合性が崩れることがあるので、内部識別記号の再割り当てなど正規化を行う。また、パターンの構文解析は、入力となるプログラムの構文解析と同じ CParser.pm を、上位互換となる形で拡張しているので、パターン変数などの独自の記法以外については、たとえ解析結果が間違っていたとしても、同じ結果になり、確実に書換えが適用できる。

記述できるパターンは、必ず構文解析ができる状態でなければならない。したがって、式の一部や単体の case ラベルなど、特定の文脈の中でしか構成できない要素をそのまま記述すると、 B_ST や E_ST が意図しない位置に補完され、目的を果せない。その場合には、文脈を含めて記述し、目的の範囲を ${%begin} と ${%end} で囲うことで、指定できる。

3.5 id_unify.pl (IdUnify.pm)

二つの字句系列間で、内部識別記号を統一する。この基本的な処理の流れは以下の通りである。

すべての識別記号を無視して、LCS(Longest Common Subsequence; 最長共通部分列) により、字句の対応関係を求める。
対応する字句の組を取り出し、それらの字句および同じ識別記号を持つ字句には、統一した字句番号を与える。
統一した字句番号以外は無視して、再び LCS によって対応関係を求め、組がなくなるまで 2. に戻って統一を行う。

Algorithm::Diff の実行性能に大きく依存しており、大規模なファイルでは時間がかかる。また、実際には、上記の流れより複雑な処理をしている。例えば、比較する字句系列は、先頭の方は一致しやすいという性質があるので、LCS を求める前に、一致する先頭の部分について、対応する内部識別記号を求め、それらは確定したものとして、残りの部分だけについて、LCS を求めている。

3.6 preg.pl

プログラムのパターンに適合する部分を探すツールである。検索は、rewrite.plと同様に字句系列に対するパターンに変換して適用する。よって、パターンに変換する部分は ProgTrans.pm の %before に関する処理を利用している。

検索した箇所を出力するために、まず、与えられたパターンに適合した箇所の前後に仮想字句を入れ、その仮想字句を用いてオプションに合わせた出力をしている。仮想字句は、適合開始箇所に _RB と _MB を、終了箇所に _ME と _RE を用いている。 2つ用いている理由は、適合した範囲と出力する範囲が異なる場合に対処するためである。 _RB と _RE は出力する範囲を、_MB と _ME は適合した範囲を表し、 -s オプションで出力範囲を拡大するときは _RB と _RE の位置を変更している。

適合した範囲を仮想字句で表現しているので、-t オプションを使って出力すれば、そのあと、適合箇所を別のツールで処理することも可能である。

4 字句の種別(一覧)

以下にTEBAで使われている字句の種別をカテゴリ別に示す。

仮想字句 (virtual tokens)

`UNIT_BEGIN`, `UNIT_END`	解析結果の開始と終了
`B_DIRE`, `E_DIRE1`	前処理指令の開始と終了
`B_MCB`, `E_MCB`	マクロ定義の本体の開始と終了
`B_FUNC`, `E_FUNC`	関数定義の開始と終了
`B_DE`, `E_DE`	宣言の開始と終了
`B_ST`,`E_ST`	文の開始と終了
`B_TD`, `E_TD`	typedef の開始と終了
`B_SCT`, `E_SCT`	構造体型の開始と終了
`B_EN`, `E_EN`	列挙体の開始と終了
`B_UN`, `E_UN`	共用体の開始と終了
`B_CP`, `E_CP`	構造体、共有体や配列の初期化リスト、複合値の開始と終了
`B_FD`, `E_FD`	関数の宣言子の開始と終了
`B_FR`, `E_FR`	関数の参照の開始と終了
`B_CAST`, `E_CAST`	キャスト演算子の開始と終了
`B_P`, `E_P`	式の開始と終了
`B_LB`, `E_LB`	ラベルの開始と終了

前処理指令 (preprocessor directives)

`PRE_TOP`	‘`#`’ (前処理指令の開始を示す`#`記号)
`PRE_S`	‘`#`’ (識別子を文字列リテラルに変換する`#`演算子)
`PRE_JOIN`	‘`##`’ (識別子を結合させる`##`演算子)
`PRE_DIR`	ディレクティブ (指令)
`PRE_H`	インクルードファイル名 ‘`<hoge.h>`’

識別子 (indentifier)

`ID_LB`	ラベル名
`ID_MB`	メンバー名
`ID_MC`	マクロ名
`ID_TAG`	タグ名
`ID_TP`	型名
`ID_TPCS`	記憶クラス指定子 (`static`, `extern`, `register`, `auto` )
`ID_TPFS`	関数指定子 (`inline`)
`ID_TPQ`	型修飾子 (`volatile`, `const`, `restrict`)
`ID_TPSP`	型指定子 (`signed`, `unsigned`)
`ID_VF`	変数名または関数名

アトリビュート (attribute)

ATTR アトリビュート (__hoge__)
メッセージ

ID_MSG #error と #pragma の引数に書かれる文、または、強制的にコンパイルエラーを引き起すために書かれている文字列

区切りの要素

`CA`	カンマ
`C_L`, `C_R`	中括弧の左右 ( ‘`{`’ , ‘`}`’ )
`P_L`, `P_R`	丸括弧の右と左 ( ‘`(`’, ‘`)`’ )
`A_L`, `A_R`	配列の左括弧, 右括弧 ( ‘`[`’, ‘`]`’ )
`SC`	セミコロン ‘`;`’

制御文の予約語 (control tokens)

CT_EL else

CT_DO do

CT_BE for, while, switch (‘B’ はブロック、 ‘E’ は式が後ろに続くの意味)

CT_IF if

予約語 (reserved tokens)

`RE_JP`	ジャンブ命令 ( `return`, `continue`, `break` )
`RE_JPG`	goto 命令 (`goto`)
`RE_LC`	ラベル ( `case` )
`RE_LD`	ラベル ( `default` )
`RE_TD`	型定義 ( `typedef` )
`RE_SUE`	構造体等 ( `struct`, `union`, `enum` )

定数値 (literal)

LIC 文字定数

LIN 定数値

LIS 定数文字列
演算子 (operator)

OP 2項演算子

OP_T 3項演算子

OP_U 単項演算子
空白 (spaces)

SP_B 1個以上の空白文字 ' '

SP_C コメント ( ‘/* .... */’, ‘// ....\n’ )

SP_NC マクロの中の継続行を表す改行 ‘\\n’

SP_NL 改行 ‘\n’

一時的な仮想字句 (書換えの途中で一時的に使用)

`_B_PCOND`, `_E_PCOND`	前処理の条件分岐指令の条件部分を指定 (挿入: prep.rules, 削除: prep.rules)
`_B_CT`, `_E_CT`	制御文(if文以外)の条件部を指定 (挿入: parser-stage2.rules, 削除: parser-cndstmt.rules)
`_B_IF`, `_E_IF`	if文の頭部を指定 (挿入: parser-stage2.rules, 削除: parser-cndstmt.rules)
`_B_ARG`, `_E_ARG`.	関数参照の引数部分を指定し、cast 演算子と区別する (挿入・削除: namespace.rules)
`_B_X`, `_E_X`	解析が終了した式の最外の範囲を指定 (挿入・削除: expr-*.rules)
`_B_OP01`, `_E_OP01`	演算子とその右側の式を指定 (挿入・削除: expr-p01.rules)
`_B_A`, `_E_A`	関数呼び出しの引数部分 (挿入・削除: expr-p01.rules)
`_B_OP03`, `_E_OP03`, …, `_B_OP12`, `_E_OP12`	演算子とその右側の式を指定 (挿入・削除: expr-p03-12.rules)
`_B_OP13`, `_E_OP13`	3項演算子の内側の式, 内側と右側の式を指定 (挿入・削除: expr-p13.rules)
`_B_OP14`, `_E_OP14`	代入演算子とその左側の式を指定 (挿入・削除: expr-p14.rules)
`_X`, `_Y`	マクロ呼び出しの引数に文が含まれているときに、その文の開始位置と終了位置をそれぞれ指定 (挿入・削除: parser-adjust.rules)
`SC` (空文字)	文末を指定 (挿入: macro-stmt.rules, 削除: namespace.rules)

5 sample の使い方

TEBA のパッケージのディレクトリ sample には、プログラムの書換えパターンの例となるファイルが含まれている。拡張子が .pt のファイルがパターンの記述例であり、同じ名前で拡張子が .c のファイルが入力の例、拡張子が .x0 のファイルが書換え後の例である。

このディレクトリはテストも兼ねており、実際に書換えを実行させ、その出力が正しいかどうかを確認する仕組みがある。テスト実行は以下のように行なう。

実行パスに teba/bin を加えておく。 (すでに設定していれば不要)
make を実行

途中でエラーが起こる場合は、実行パスが正しいか確認をし、以下のコマンドを実行する。エラーが解消されない場合は、エラーの内容がわかる情報を作者に連絡すること。

make clean; make

実行されるプログラムの書換えパターンとテストの目的は以下の通りである。

add-debug.pt
- デバッグ処理を挿入する書換えパターン
- 前処理指令の挿入が可能なことの確認
extract-decl.pt
- 1つの宣言には1つの宣言子のみを書くスタイルに変更する書換えパターン
- グループおよびその繰り返し $[: … $]* が使えることの確認
- 再帰的(recursive)に書換えられることの確認
for-while.pt
- for 文を等価な while 文に置き換える書換えパターン
- 制御構造の入れ子の関係を正しく処理できることの確認
ifdef-curly-refact.pt
- 前処理の条件分岐内の中括弧の組み合わせが閉じるようにする書換えパターン
- 前処理の条件分岐に中括弧が片方のみ存在する状態を取り扱えることの確認
iff.pt
- 二重のif文を合成する書換えパターン
- コメントをできるだけ適切な位置に保存できるかことの確認
if-exit.pt
- else 側で処理を止める例外処理に対し、そのことがより明確なスタイルに変更する書換えパターン
- $| による選択を適切に処理できることの確認
init-decl.pt
- 初期化式を含む宣言を、純粋な宣言と初期化の代入文に分ける書換えパターン
- ${{Name:Type}} を正しく処理できるかの確認
swap-decl.pt
- 文の途中に出現する宣言をブロックの先頭に移動させる書換えパターン
- 複数の書換えパターンの組み合わせが可能であることの確認 (init-decl.pt との組み合わせをテストする)

6 JSON形式の抽象構文木(AST)と記号表について

cparse.pl で -j オプションを使うと、AST を JSON形式で出力する。この抽象構文木を構成する構文要素はC言語本来の具象構文木とは異なる、独自のものになっている。また、TEBA の字句系列から構文木を直接構成できるが(cparse.pl の -J オプション)、それよりもより簡素化したり、逆に細分化している。さらに、一部、子要素の位置やその構文要素を特徴づける属性値が加えられている。

6.1 属性について

各構文要素は、少なくとも以下の属性値を持つ。

t 構文要素の種類 (文字列)

e 字句および子要素 (配列)

id その構文要素を区別する識別記号

属性 e は、字句と子要素(ハッシュ)が並んだ配列となっており、これを先頭から辿りながら、すべての字句を取り出せば、元のソースコードが空白等も含め、完全に再現できるようになっている。

派生的な属性が、それぞれ構文要素ごとに定義されている。どのような属性を持つかは、構文要素ごとに異なり、規則性はない。派生的属性の中には、属性 e の配列内での子要素の位置(数字)を持つものがある。これにより、子要素を参照しやすくしている。例えば、if文には、cond, then, else の3つの属性があり、それぞれ条件式、 then節、else節の位置を表す。仮に、if文の構文要素を $el という変数で参照しているとすると、 then 節は、配列 @{$el->{e}} の $el->{then} 番目の要素であるので、 then 節の要素は以下のように参照する(Perl の場合)。

$el->{e}->[ $el->{then} ]

また、for文は3つの条件式を持つが、この場合、条件式の位置を持つ属性 cond は配列となり、3つの要素を持つ。よって、繰り返し条件を参照するときは次のように書く。なお、$el は for文の要素を参照するものとする。

$el->{e}->[ $el->{cond}->[1] ]

ただし、子要素にアクセスするたびに、このように長い式を書くのは不便なので、 AST のノード参照を容易するために AST::NODE というモジュールを用意している(後述)。

各要素ごとにどのような属性があるか、また、どのような値を持つかは、実際に具体的なソースコードから AST を生成して確認するとよい。

6.2 記号表について

AST を構成するときに記号表を構成しており、次の情報を AST に加えている。具体的には以下の通りである。

変数や関数の識別子型とスコープ

構造体等のメンバ型と構造体 (構造体については未実装)

ユーザ定義型展開後の型

即値型

式型

このうち、型は属性 stype の値となっており、型を構成する要素がピリオドで区切られて記述される。例えば、次の宣言に対して、x の型は int.*.[ と記述される。

int *x[N];

この記法では素直に「int へのポインタの配列」と読むことができる。なお、構造体等はタグ名があるときは “struct タグ名” で、そうでなければ自動的に割り振られた番号で “struct 番号” と表記される。

式の型は、子要素の型や、演算子等の定義に基づいて計算されている。構造体等のメンバもその過程で、構造体と結びつけ、メンバの型を求めている。また、マクロ定義には型の概念はないが、型が1つに決まるマクロ定義については型を計算している。なお、未定義の識別子や、構文的に無効な計算の場合(例えば、ポインタ同士の加算) がある場合には、未定義(#UNDEF)になるようにしている。

ユーザ定義型は、式の型を求めるうえで必要になることから、元の型に展開して保持される。ただし、未定義の場合には、可能な限り展開したところで止まる。これはライブラリ関数など、型の展開が意味をなさないことがあるからである。

スコープは、それぞれスコープを構成する構文要素の id 属性で表現される。 C99以降の規格に対応するために、for 文もスコープを構成する要素として扱っている。

最終的な記号表は AST の根の要素に、属性 sym として登録される。記号表を使う処理を実装したい場合には、この sym を利用できる。記号表はASTの部分木であり、その部分木の根は #UNDEF という未定義の識別子を登録するスコープになっている。その下に大域の領域で定義された識別子を持つスコープ #GLOBAL が定義されている。さらにその子や子孫には、構文要素に対応する各スコープが配置されている。

記号表において、型と変数・関数の識別子は名前空間として区別されることから、型の識別子には “type:” という接頭辞がつく。また、構造体等の型も独自に名前空間を持つことから “tag:” という接頭辞を付けて管理している。構造体等の場合には、値として、その構造の定義(すなわち、メンバの定義)を持つ。

解析時に、標準ライブラリなどの関数や識別子(マクロ)については、事前に型が定義されている方が便利なことがある。その場合、cparse.pl の -g オプションで JSON形式のファイルを指定することで、事前に定義を読み込ませることができる。この JSON形式の表は、記号表内の #GLOBAL に挿入される。例えば、次のように記述する。

  {
      "printf": "int",
      "fprintf": "int",
      "scanf": "int",
      "fscanf": "int",
      "NULL": "void.*",
      "malloc": "void.*",
      "stderr": "FILE.*"
  }

なお、デフォルトとして、標準的な記号が次のファイル定義されており、実行時に自動的に読み込まれる。ただし、オプションで JSON ファイルを指定した場合には、このファイルは読み込まれない。

TEBA/global_symbol_table.json

6.3 AST::NODE

AST の取り扱いを簡単にするために、AST.pm を用意している。このモジュールでは AST のノードを扱うパッケージである AST::NODE を定義している。

このモジュールで JSON 形式の AST を読み込むときは、次のように実行する。ここで $ast は AST::NODE クラスのインスタンスになる。

use AST;

my $json_text = join('', <>); # JSON のテキストをすべて読み込む

my $ast = AST::NODE->build_from_json_text($json_text);  # AST の生成

子要素を取り出すために、children_all や children() などのメソッドが用意されている。メソッドについては、AST.pm 自体を確認するととも、perldoc AST を実行して説明を確認すること。

7 制御フローグラフ(Control Flow Graph)について

制御フローグラフ(CFG)は、ast2cfg.pl を用いて生成できる。 JSON形式のASTを入力すると、CFG を構成情報が追加した AST を出力する。

CFG の構成情報をそのまま用いて解析することは難しいことから、解析処理を支援するモジュール CFG.pm を定義している。また、CFG モジュールを用いた例として program_slicer.pl と c_intp.pl が定義されている。

7.1 JSON形式のの仕様

ast2cfg.pl は、入力の AST (抽象構文木) の根に制御フローグラフの情報 cfg を付加して出力する。 CFG を用いたツールを作る場合は、これで出力されるCFGを読み込み、グラフをたどって処理をする。

cfg は次の3つ属性を持つ。

属性名意味

begin_node 開始ノード id のリスト

end_node 終了ノード id のリスト

node 全ノード・オブジェクトのリスト

属性名	意味
begin_node	開始ノード id のリスト
end_node	終了ノード id のリスト
node	全ノード・オブジェクトのリスト

各ノード・オブジェクトは、次の5つの属性を持つ。

属性名意味

id ノードの識別記号

ast_id AST の識別記号

label ラベル

next 次の頂点 id のリスト

prev 前の頂点 id のリスト

ノードの識別記号は、すべてのノードに対して、重複しないよう割り当てている。 AST の識別記号は、AST の各要素の id 属性の値である。CFG を生成するときに、便宜的に生成する頂点があり、それらは対応する AST の要素が存在しない。ラベルは、構文要素に対応する場合は、その構文要素のテキストに基づくものを、便宜的に生成する頂点は、# で始まる名前を付与している。

7.2 ノードの構成

ast2cfg.pl は、オプションがない場合は、各式がノードとなり、 1つの実行経路を辿りながら解釈実行することで解釈器(インタプリタ)を実現できる。

C言語の仕様上、式の評価順序が定められていないものがあるが、原則として構文要素の子要素に複数の式が存在する場合、それらの子要素は出現順に実行されるものとする。また、左辺値と右辺値を区別するために、変数の参照にはそれぞれ lvalue:、 rvalue という接頭辞をラベルにつけている。また、左辺値が式の場合は、左辺値として評価を行う演算子に op(lvalue): という接頭辞を付加している。その他、代入演算子の接頭辞は assign: とし、他の演算子と区別している。

CFGを用いた解析では、主に式がどのような順序で評価されるかという点に着目するが、解析結果を出力するときには、どの文の処理か、という情報が必要になることもある。そこで、各文の入口と出口を表わすダミーのノードを加えており、どの文を処理しているかを把握できるようにしている。

7.3 CFG の視覚化

CFG はコマンド cfg2dot.pl に入力すると、GraphViz の dot 形式に変換できる。ノードが式単位になっているので、グラフ自体は非常に大きくなる。概観を見たい場合には、式を論理演算子の被演算子までの分解に止めてノードを構成するモードと、文単位にするモードを用いるとよい。それぞれ ast2cfg.pl に ‘-E’ と ‘-S’ を指定する。なお、これらのモードの出力でも解析は可能であるが、正確性に欠けるので注意が必要である。

CFG のノードは属性 ast_id を持ち、AST のノードと関連付いているが、その対応関係を確認したいときは、cfg2dot.pl に ‘-a’ オプションを付けると、 CFG と AST を同時に確認できる。

CFGのノードは、構文上のブロックの出入口のノードも存在し、大きくなりがちである。 cfg2dot.pl にオプション ‘-s’ を付けると、式だけのノードで構成される縮退した CFG が出力される。単純に式がどのような順序で実行されるかを確認しやすい。なお、この縮退したCFGは、論理演算子による短絡評価を把握しやすくするために論理演算子のノードも省略される。また、条件分岐かかわる真偽値は辺のラベルとなる。

変換処理の例を以下に示す。ここでは、ソースファイル hoge.c を hoge.pdf に変換する例である。オプションとして、ast2cfg.pl の ‘-E’ と cfg2dot.pl の ‘-a’ を使用している。

cparse.pl -j hoge.c | ast2cfg.pl -E | cfg2dot.pl -a | dot -Tpdf -o hoge.pdf

7.4 CFG.pm

制御フローグラフ(CFG)上で、プログラム解析を実現する枠組みとして、 CFG.pm を提供している。 CFG を読み込み、CFG クラスのインスタンスを生成すると、 CFGのメモリイメージを生成する。グラフのメモリイメージは dot 形式に変換できる。

CFG クラスのインスタンスは、visitor オブジェクト (CFG::VISITOR クラスのインスタンス)を持つ。 visitor オブジェクトは、CFG 上を移動し、分岐では複製を作って、各分岐に進む。プログラム解析を行うには、visitor に対して、解析方法や複製の生成方法などを指定して、実行する。

CFG クラスおよび CFG::VISITOR クラスの詳細は、CFG.pm を直接確認すること。日本語で詳細なコメントを記載している。

また、CFG.pm の応用ツールである、program_slicer.pl と c_int.pl についても内部に詳細な日本語のコメントを記載している。具体的な CFG.pm の使い方や解析の実現方法については、これらを直接参照して頂きたい。なお、これらはサンプルであり、一部の機能のみを実装している。また、perldoc CFG を実行して説明を確認すること。

8 プログラム依存グラフ(Program Dependency Graph)について

プログラム依存グラフ(PDG)は、変数への代入(定義)と参照(使用)の関係に基づき、ある式(または文)の処理に影響を与える式(または文)の間の関係を示したグラフである。 PDG は CFG を解析して得られるが、TEBA ではコマンド ast2pdg.pl により、 PDG を生成できる。具体的には、ast2pdg.pl に AST(JSON形式)を入力すると、 CFG および PDG を追加した AST を出力する。

8.1 JSON形式のPDGの仕様

PDG は AST に、CFG と同様に、ASTの根にキー pdg のオブジェクトとして追加される。 PDG のオブジェクトには次の3つのキーが存在する。

キー意味

ctrl 制御依存関係

data データ依存関係

e2s 式から文への対応関係

まず、前提条件として、生成される PDG のノードは次の式で構成される。

代入式
式文の最外の式
条件式

ここで、a = 1; のように代入式で構成される式文の場合には、 a = 1が「代入式」と「式文の最外の式」の両方にあてはまるが、式としては1つとして扱う。また、a = b = 1; のように、代入式を含む式がある場合には、 b = 1 と a = b = 1 の2つの式がノードとなる。ただし、a = b = 1 は最外の a への代入 a = ... を扱う式とみなす。なお、以下で単に式と述べたときは、基本的には、この3種類の式である。

制御依存関係 ctrl とデータ依存関係 data は、式の id をキーとして、依存関係にある式の id のリストを返すハッシュオブジェクトとして表現される。ここで id は、AST の式オブジェクトに割り振っている id である。また、e2s は、式idから文idへのハッシュオブジェクトである。

制御依存関係とは、ある制御文において、条件式から、その条件式の真偽によって実行時に評価されるかどうかが決まる式への関係を表す。ただし、グラフの簡素化のために、制御依存関係は推移律が成り立つものとし、条件式に制御依存する式は、制御文が直接持つ、または複合文を介して持つ文を構成する式のみとする。このとき、制御文は、条件式のみが対象となり、その制御文の中の式には関係を持たない。例えば、if(a) if(b) x = 1; という文の場合には次のような制御依存関係を持つ。

a → b
b → x = 1

すなわち、x = 1 は、直接は b に制御依存し、b は a に制御依存する。さらに、推移律により、x = 1 は a に制御依存と解釈する。

データ依存関係とは、代入式から、その代入式によって代入(定義)される変数の値を参照(使用)する変数を含む式への関係である。例えば、x = 1; y = 1; f(x); という3つの文があると、 x = 1 から f(x) にデータ依存関係があり、y = 1 は他の式との関係を持たない。

e2s は、各式から、その式を含む文への関係を表す。 PDG は式をノードとするが、解析の目的によっては、文を単位として何らかの出力をしたいことがある。例えば、ソースコードを意味的にまとまった段落に分けるときに、PDG を使うときは、解析そのものは式を単位として行うが、最終的に欲しいものは、文を単位とした段落分けである。出力するときに文が単位となるよう変換するときに利用する。 ast2pdg.pl にはオプション ‘-s’ があり、文単位の PDG も生成できる。内部では、出力する直前に、式単位の PDG を文単位に変換しているので、詳細は実装を参考にするとよい。

8.2 ポインタや関数呼出しの扱い

依存解析において、ポインタの扱いは難しく、静的解析では正確に解析できず、近似解を求めるしか方法がない。この問題はエイリアス問題とも呼ばれる。例えば、x = 1; a[1] = x; y = b[2]; というコードにおいて、配列 y に変数 x の値が代入されるかどうかは判定できない。一見、関係ないように見えるかもしれないが、a と b がポインタで、 a = b + 1 という代入が事前に行われていたとすると、実質的には x = 1; b[2] = x; y = b[2]; と同じ処理になるからである。

TEBA の PDG では、次のように簡易的な近似を行う。

左辺がポインタ変数を参照して変数を求めるとき(例: *a や *(a+1))、そのポインタ変数への代入とみなす。
左辺が配列の要素のときは、配列そのものへの代入としてみなし、配列の添字式は右辺式(参照するだけの式)として扱う。
右辺に配列やポインタ変数が参照された場合には、間接参照かどうかに関係なく、配列やポインタ変数に影響与える代入式がその参照にも影響を与えるとみなす

よって、本来はありえない関係も生じる。例えば、*a = 1; b = a; に対し、 *a = 1 から b = a へのデータ依存関係が生じる。厳密には b の値は直前の代入には依存しないので、本来は存在しない。なお、近似にあたっては、偽陽性(false positive)を許し、偽陰性(false negative)を排除することが重要であり、その考えに基づいている (が、完璧かどうかは検証していない)。

ポインタの問題は、関数呼出しにも関わってくる。C言語では、関数呼出しにおける引数は値参照であるので、関数呼出しを用いて変数に代入させたいときは、そのポインタを渡す。しかし、配列や文字列など、ポインタでしか渡す手段がないものもあり、ポインタを渡したからといって、変数に代入されるとは限らない。偽陽性をすべて許すのであれば、ポインタ参照はすべて代入とみなすというのが一つの解決策である。しかし、ポインタかどうかは型の情報が必要であるが、コード片が与えられたときには、型定義がない場合もあり、実現できない。そこで、関数ごとに左辺値と右辺値の定義を与える方法を採用している。

定義は関数名と引数の種類(左辺値, 右辺値)で構成される。後述する解析モジュール PDG.pm には、次の例のように、ハッシュオブジェクトで与える。

{
    'sprintf' => [ 'l', 'r' ],
    'strcat' => [ 'lr', 'r' ],
}

ここで、'l' は左辺値、すなわち、代入される引数を、'r' は右辺値、すなわち、参照だけされる(代入されない)引数を意味する。また、'lr' は代入と参照の両方が行なわれる引数を意味する。これは i++ のように参照と代入が行われる式と同じ意味である。なお、省略された場合は r とみなす。例えば、sprintf は、第1引数のバッファに、第2引数以降の値から構成される文字列を書き込むので、第1引数は 'l'、第2引数以降は 'r' であり、第3引数以降は省略している。一方、strcat は第1引数のバッファ内の文字列に第2引数の文字列を追加するので、第1引数の情報が残っているので、'lr' となる。関数の返り値は、関数呼出しは演算子を用いた式と同じように扱い、関数呼出しに影響を与える代入式は、参照される変数に影響を与える代入式の集合和である。

PDG を生成する ast2pdg.pl においては、定義は関数呼出しの形式に従い、次のように書いたテキストファイルを ‘-f’ オプションで指定する。

sprintf(lr,r)
strcat(lr,r)

関数呼出しが代入を伴う場合、その関数呼出しを代入式とみなし、その結果、PDG のノードとなる。なお、ここでの方法は偽陽性を生じさせるので注意が必要である。何も定義を与えなければ、本来、代入が行われていても、代入はないものとして扱われる。

8.3 PDG の視覚化

CFG と同様に PDG は GraphViz の dot 形式に変換できる。変換は pdg2cfg.pl で行う。ここでは、文単位の PDG となるよう ast2pdg.pl にはオプション ‘-s’ を付け、また、関数呼出しの情報を記述したファイル fcall.txt を指定している。

cparse.pl -j hoge.c | ast2pdg.pl -s -f fcall.txt | pdg2dot.pl | dot -Tpdf -o hoge.pdf

8.4 PDG.pm

JSON形式の AST に挿入される PDG をそのまま解析に使うのは複雑なので、メモリ上にグラフを構成するためのモジュール PDG.pm を用意している。 CFG から PDG を生成する処理も含まれる。

詳細は perldoc PDG.pm を実行して確認すること。また、基本的な使い方は ast2pdg.pl や pdg2dot.pl も参考にするとよい。なお、PDG.pm は開発途中であるので、まだ、PDG を解析するための仕組みが十分に備わっていない。必要に応じて、相談をすること。

9 独自のツールを作る場合についての考え方 (学生向け)

TEBA と自分の成果物は分けておきましょう。
TEBA でツールを作るときに、TEBA の bin の下に作ってはいけません。面倒でも、別のディレクトリで作成し、TEBA の成果物と自分の成果物を区別しましょう。また、TEBA のファイルを無闇に変更することも避けましょう。 TEBA がバージョンアップしても置き換えることができなくなります。
シェルを活用しましょう。
シェルとの相性を考え、単機能のツールの組み合わせで作るよう心掛けましょう。そのためには、シェルの基本的な使い方やそのこころを理解することが必要です。最初のうちは苦労するかもしれませんが、パイプで接続したり、シェルスクリプトを記述することで、実装や保守が簡単になり、あとから得られるメリットは大きくなります。なお、いちいち組み合わせるのは面倒と思うかもしれません。その場合には、それ全体をまとめるシェルスクリプトやエイリアス(シェルの関数)を書いてもよいでしょう。長い歴史を持つシェルには作業を簡単にさせる様々な仕組みがあるので、それを学び、活用することが大切です。
Perl とシェルをうまく使い分けましょう。
少し複雑に機能を組み合わせなければならないときは、無理にシェルを活用せず、 Perl で記述しましょう。TEBA の構文解析器はモジュール化されています。また、解析の途中に処理を追加することも可能です。プログラムパターンの変換系の実装である rewrite.pl は、パターンの構文解析にはTEBAのモジュールを使っています。その際には、字句の定義を追加したり、新しい解析の処理を加えています。どこまでを Perl で書いて、どこからはシェルを利用するかは、設計の美しさに対するセンスが必要です。

センスを磨くには、実現方法のメリットとデメリットを常に検討して、自分にとって最適な方法を選択していくことが必要です。ときには、大きな方針転換をすることも厭わないようにしましょう。センスはそういった経験でしか磨かれません。
より抽象度の高い表現を活用しましょう。
やりたいことが書換えルールで書けないかも考えてください。字句系列を直接処理する Perl の記述は複雑になりがちです。しかし、書換えルールという抽象化された記述を用いると、簡単になることがあります。TEBA は、可能な限り書換えルールで構成するというポリシーで作っています。特に、構文解析器の大半を書換えルールで記述したことで、全体として簡素化され、保守がしやすくなりました。
TEBA の中身を理解しましょう。
ぜひTEBAの解析器を読んでください。細かいところはわからなくてもよいので、おおまかな処理の流れをつかんでください。そのあと、自分のツールを作るうえで参考になる部分を中心に読んでみましょう。

機能	PHP の構文情報を含む字句系列を生成する。
引数	解析対象ファイル名 (省略した場合は標準入力)

機能	preg.pl が出力する `SP_PVAR` 字句の JSON 形式のデータを整形して出力するサンプルコード
引数	字句系列ファイル名

機能	JSON 形式の構文木から字句系列に変換(ただし、字句系列は完全ではない)
引数	字句系列ファイル名
オプション	なし

機能	JSON 形式の構文木を GraphViz の dot 形式に変換
引数	字句系列ファイル名

機能	制御フローグラフを含む構文木(JSON形式)を読み込み、GraphViz の dot 形式に変換
引数	制御フローグラフを含む構文木(JSON形式)のファイル名

機能	JSON形式の制御フローグラフに基づいてプログラムを解釈実行(機能の一部のみ実装)
引数	制御フローのJSONファイル名

書き方:	`${変数名:種別}`, `${{変数名:種別}}`
使用例:	`${s:STMT}`, `${e:EXPR}`, `${{var:ID_VF}}`, `${:DECR}`

書き方:	`${変数名}`
使用例:	`${s}`, `${e}`, `${var}`

グループの開始:	`$[名前:`
グループの終了:	`$]`

0回以上の繰り返し:	`$[名前:` …. `$]*`
1回以上の繰り返し:	`$[名前:` …. `$]+`
1つ以下存在する:	`$[名前:` …. `$]?`

型付き字句変数	`$名前#後方参照名:{型指定}{字句指定}`, ‘`#後方参照名`’ は省略可能, `{型指定}` `=>` 型名 or `/正規表現/`, `{字句指定}` `=>` `/正規表現/` (省略可能)
テキスト指定字句変数	`$名前:'テキスト'` `$名前#後方参照名:'テキスト'`
変数参照	`$名前`
字句参照	`'テキスト':型`
グループ	`$[名前:` … `$]` オプションとして、閉じ括弧は `$]*`, `$]+`, `$]?` と書ける。また、括弧の前の `$` を省略して `[名前:` … `]` と書いてもよい。
結合演算子	`$##`
文字列化演算子	`$#`
コメント	`#` で始まる行
コメントブロック	`[` から `]` まで

変数参照	`$名前` or `$名前:型`
字句参照	`'テキスト':型` or `'テキスト'#後方参照名:型`
結合演算子	`$##`

規則の挿入	`@"ファイル名"`
実行フィルタ	`@\|Method\|`
強制停止	`@!BREAK!`

`RewriteTokens->new()`	ルールの上から下に適用を試み、書換えられたら、また先頭に戻って繰り返す。最後のルールまでに書換えが発生しなければ終了する。
`RewriteTokens->seq()`	ルールを上から下に1度だけ適用していく。
`RewriteTokens->rep()`	ルールを上から下に1度だけ適用していき、 1回でも書換えが起きていれば、再度、先頭から適用を繰り返していく。書換えが発生しなければ終了する。

`CT_EL`	`else`
`CT_DO`	`do`
`CT_BE`	`for`, `while`, `switch` (‘`B`’ はブロック、 ‘`E`’ は式が後ろに続くの意味)
`CT_IF`	`if`

`SP_B`	1個以上の空白文字 `' '`
`SP_C`	コメント ( ‘`/* .... */`’, ‘`// ....\n`’ )
`SP_NC`	マクロの中の継続行を表す改行 ‘`\\n`’
`SP_NL`	改行 ‘`\n`’

`t`	構文要素の種類 (文字列)
`e`	字句および子要素 (配列)
`id`	その構文要素を区別する識別記号

変数や関数の識別子	型とスコープ
構造体等のメンバ	型と構造体 (構造体については未実装)
ユーザ定義型	展開後の型
即値	型
式	型

属性名	意味
id	ノードの識別記号
ast_id	AST の識別記号
label	ラベル
next	次の頂点 id のリスト
prev	前の頂点 id のリスト

キー	意味
ctrl	制御依存関係
data	データ依存関係
e2s	式から文への対応関係