1. 導出木の探索
3章 四則演算式の文法と解析 において、「整数リテラル同士の加減乗除算(括弧あり)」の四則演算式を表す文法を記述し、いくつかの入力例における導出木の生成について確認した。
ここでは、四則演算式の値の計算、すなわち、ある演算式に対する導出木が与えられた場合、この導出木を何らかの方法で探索し、演算式全体の値を計算する操作(実行)について説明する。これは、演算式をひとつの「プログラム」と捉えて、これを「実行」する行為に他ならない。
1.1 導出木の例
1.2 深さ優先探索(DFS)
1.3 DFSによる式評価の実際
1.1 導出木の例
文法 3.1.A において、入力列 "Num1 * Num2 + Num3 $" が与えられた際、生成された導出木を図4.1に示す。ここでは、終端記号としての整数リテラル (Num) が具体的に与えられている状態を考えている。また、非終端記号の各ノード(Expr, Term, Factor)は、導出木内で、各々 Expr1, Expr2, Term1, ..., Factor3 といった様にインスタンス名が与えられていると考えている。
図4.1: Num1 * Num2 + Num3 $ の導出木
図4.1 において、「値を評価すべき」タイミングは、以下の3カ所である。
- Factor1 において、Factor1 の葉(leaf)として、整数リテラル Num1 の値を評価した後、結果を Factor1 の結果とする。
- Factor2 において、Factor2 の葉(leaf)として、整数リテラル Num2 の値を評価した後、結果を Factor2 の結果とする。
- Factor3 において、Factor3 の葉(leaf)として、整数リテラル Num3 の値を評価した後、結果を Factor3 の結果とする。
一方、図4.1 において、「演算を実行すべき」タイミングは、以下の2カ所である。
- Term1 において、Term2以下の部分木の計算結果(left)と、Factor2以下の部分木の計算結果(right)を得た後、これを乗算(left * right)し、結果を Term1 以下の部分木の計算結果とする。
- Expr1 において、Expr2以下の部分木の計算結果(left)と、Term3以下の部分木の計算結果(right)を得た後、これを加算(left + right)し、結果を Expr1 以下の部分木の計算結果とする。
1.2 深さ優先探索(DFS)
図4.1の導出木についてノード探索を行い、各部分木の値を求めていく。最後に、開始記号(root)である Expr1 の値が求められることで、演算式全体の値が計算できたことになる。
ここで用いるノード探索順序は、「深さ優先探索(DFS : Depth First Search)」で、部分木の left child --> right child --> parent の順で探索を行うものである。
具体的に図4.1の導出木について、開始ノード(Expr1)から深さ優先探索を用いてノード巡回を行った経路を、図4.2に示す。終端記号(Num, '*', '+')については、その parent のノードが評価するとして、重ねて簡略表示をしている。
図4.2: 導出木を深さ優先探索する順番(簡略表示)
1.3 DFSによる式評価の実際
整数リテラルとし、実際の整数値を与えた場合の、値評価と演算結果の実際について示す。図4.3に、"3 * 4 + 5 $" を実際にDFSによって評価した場合の、各ノードの評価値について示す。
図4.3: "3 * 4 + 5 $" をDFSによって評価した場合のノード値
図4.3 において、式全体の評価値を得るまでに、14の探索ステップを要している。これらの各ステップでの「作業」について、以下に述べる。
[STEP 1]
node (Expr1) --> left child (Expr2) を評価(加算の左項)
[STEP 2]
node (Expr2) --> child (Term1) を評価
[STEP 3]
node (Term1) --> left child (Term2) を評価(乗算の左項)
[STEP 4]
node (Term2) --> child (Factor1) を評価
node (Factor1) := 整数値 3 を取得
[STEP 5]
node (Term2) := 整数値 3 を取得
[STEP 6]
node (Term1) left := 整数値 3 を取得(乗算の左項)
[STEP 7]
node (Term1) --> right child (Factor2) を評価(乗算の右項)
node (Factor2) := 整数値 4 を取得
[STEP 8]
node (Term1) right := 整数値 4 を取得(乗算の右項)
node (Term1) := left(3) * right(4) を演算し整数値 12 を取得
[STEP 9]
node (Expr2) := 整数値 12 を取得
[STEP 10]
node (Expr1) left := 整数値 12 を取得(加算の左項)
[STEP 11]
node (Expr1) --> right child (Term3) を評価(加算の右項)
[STEP 12]
node (Term3) --> child (Factor3) を評価
node (Factor3) := 整数値 5 を取得
[STEP 13]
node (Term3) := 整数値 5 を取得
[STEP 14]
node (Expr1) right := 整数値 5 を取得(加算の右項)
node (Expr1) := left(12) + right(5) を演算し整数値 17 を取得
[終了]
2. スタックマシンによる実現
2.1 スタックマシンの構成
2.2 スタックを用いた式評価の実際
2.1 スタックマシンの構成
四則演算式評価のスタックマシンによる実現について述べる。スタックマシンの構成を図4.4に示す。
図4.4: 四則演算式評価のスタックマシンによる実現
スタックマシンは、規定された文法から生成された導出木のインスタンスを入力とし、この木をDFS探索する。push/popの動作は以下の通り。
- 取得した整数値はスタックへpushしていく。
- 2項演算子の実行時には、スタックから2つの値をpopして、その値を利用して(実際の)演算を実行する。得られた演算結果を、スタックにpushする。
- 開始記号(root)までの演算が全て終了した後、スタックの先頭に残っている値が、求める演算式の評価値となる。
2.2 スタックを用いた式評価の実際
図4.3 の導出木において、式全体の評価値を得るまでに、14の探索ステップを要している。これらの各ステップでの値取得と、スタックの状態について、表4.1に示す。
表4.1: 入力 "3 * 4 + 5 $" に対するスタックを用いた実行例
---------------------------------------------------------------
STEP ## node push/pop stack (<---head)
---------------------------------------------------------------
--START--
STEP 1 Expr1 --> Expr2 [ ]
STEP 2 Expr2 --> Term1 [ ]
STEP 3 Term1 --> Term2 [ ]
STEP 4 Term2 --> Factor1 [ ]
push( 3 ) [ 3 ]
STEP 5 Factor1 --> Term2 [ 3 ]
STEP 6 Term2 --> Term1 [ 3 ]
STEP 7 Term1 --> Factor2 [ 3 ]
push( 4 ) [ 4 | 3 ]
STEP 8 Factor2 --> Term1 [ 4 | 3 ]
STEP 9 Term1 --> Expr2 [ 4 | 3 ]
right := pop( 4 ) [ 3 ]
left := pop( 3 ) [ ]
val := left * right
push( 12 ) [ 12 ]
STEP 10 Expr2 --> Expr1 [ 12 ]
STEP 11 Expr1 --> Term3 [ 12 ]
STEP 12 Term3 --> Factor3 [ 12 ]
push( 5 ) [ 5 | 12 ]
STEP 13 Factor3 --> Term3 [ 5 | 12 ]
STEP 14 Term3 --> Expr1 [ 5 | 12 ]
right := pop( 5 ) [ 12 ]
left := pop( 12 ) [ ]
val := left + right
push( 17 ) [ 17 ]
--END--
---------------------------------------------------------------
|
3. Visitorの実装
SableCCにて実行プログラムを実装するため、まずDFS探索エンジン(DepthFirstAdapterクラス)への Visitor を実装する。
Visitorは、Design Patternsの一つである。詳しくは参考文献を参照のこと。
3.1 DepthFirstAdapterクラス
3.2 Visitorパターン
3.3 Acceptor/Visitorの例
3.4 Visitor (Calculatorクラス) の実装
3.1 DepthFirstAdapterクラス
文法ファイルに基づき、SableCCが生成したlexer/parserクラスパッケージを用いて導出木のインスタンスを出現させた後、DFS探索エンジンを用いて導出木のノード巡回を行う必要があるが、このための analysis クラスパッケージが、併せて生成されている。
analysisクラスパッケージのクラス階層図
test2calc/docs/test2/analysis/package-tree.html
このうち、DepthFirstAdapterクラスが、DFS探索エンジンである。
(ReversedDepthFirstAdapterクラスは、逆順(right --> left --> parent)で探索するエンジンである)
DepthFirstAdapterクラスの内部メソッドは、各ノード別に最小限のものが記述してある、DFS探索エンジンが実装された「スケルトン(骸骨)」である。ユーザは、このDepthFirstAdapterクラスの各メソッドを、ユーザクラスによって overwrite することで、各ノード到達時における所望の「作業」を実装できる。
3.2 Visitorパターン
Visitorパターンは、GoFデザインパターンの一つで、
「オブジェクトの構造上の要素で実行される処理を表現する。Visitorパターンを使用することにより処理を加えるクラスを変更することなしに新しい処理を定義できるようになる」
というものである。
Visitor とは「訪問者」を意味する。Visitorパターンでは、「処理」を訪問者である Visitor オブジェクトに記述することで、処理の追加(例えば、整数値の取得、乗算の実行、など)を簡単に、かつパターン化する。処理対象となる、Acceptor オブジェクトは、Visitor オブジェクトを受け入れる accept(Visitor)メソッドを実装している必要がある。
DepthFirstAdapterクラス(ソースファイル全体)
DepthFirstAdapterクラスのAcceptor一覧
3.3 Acceptor/Visitorの例
DepthFirstAdapterクラスのAcceptorのうち、caseANumberFactorメソッド(整数値の取得)を例にしてVisitor側の実装について検討してみる。
A. Acceptor側
caseANumberFactorメソッドは、ANumberFactor型のnodeオブジェクトを引数とする Acceptor である。caseANumberFactorメソッド(Acceptor側)の抜粋を以下に示す。
DepthFirstAdapter :: caseANumberFactor(ANumberFactor node) の抜粋
public void caseANumberFactor(ANumberFactor node)
{
inANumberFactor(node);
if(node.getNumber() != null)
{
node.getNumber().apply(this);
}
outANumberFactor(node);
}
|
これは、引数として渡された当該nodeオブジェクトについて(例えば図4.1における Factor1 node)これの child が NULL でなければ、child を探索( apply(this) )して評価する、という「探索動作のみ」を記述している。
他のAcceptorについても、概ね同じような実装が為されている。
この種類のノードについて、もし「何も処理や作業を行わない」ならば、Visitor側では、このメソッドを overwrite (書き換え)する必要がない。
B. Visitor側
今回は、FactorのchildがNumberである種類のノードに到達した際には、その child つまり整数値として取得し、取得した値を、Visitor内部で構成したスタックに push する、といった作業を caseANumberFactor メソッドで行わせたい。
そのため、Visitor側では、DepthFirstAdapterクラスを継承した後、この caseANumberFactorメソッド を実装する。
DepthFirstAdapterクラスを継承した Visitor側 Calculator.java における、caseANumberFactorメソッド(Visitor側)の抜粋を以下に示す。( 関数push() は、内部スタックへの push を行うもの )
Calculator :: caseANumberFactor(ANumberFactor node) の抜粋
public class Calculator extends DepthFirstAdapter {
....................
public void caseANumberFactor(ANumberFactor node) {
int num = Integer.parseInt(node.getNumber().getText());
push(num);
....................
....................
}
|
具体的には、ノードに到達した際、その node の内部値(ここでは ['0'-'9']+ であるような文字列)node.getNumber().getText() を取得し、その結果を、IntegerクラスのparseIntメソッド によって、文字列-->整数値へ変換して、内部変数 num に代入する。その後、整数値 num は、スタックにプッシュする。
3.4 Visitor (Calculatorクラス) の実装
スタックを利用して演算動作を行うための、Visitor (Calculatorクラス) の、具体的な実装について、以下に説明する。
Calculatorクラス(ソースファイル)
CalculatorクラスのVisitor一覧
Calculatorクラス(ソースファイル)抜粋
1 package test2;
15 public class Calculator extends DepthFirstAdapter {
16
...... スタックの実装 ........
17 //---------------------------------------------------------
18 // operations for stack
19 //---------------------------------------------------------
20
21 LinkedList stack = new LinkedList();
22
23 int getResult() {
24 Integer val = (Integer) stack.getLast();
25 return val.intValue();
26 }
27
28 void push(int val) {
29 stack.add(new Integer(val));
30 }
31
32 int pop() {
33 Integer val = (Integer) stack.removeLast();
34 return val.intValue();
35 }
36
......................
...... APlusExpr, AMinusExpr Visitorの実装 ........
45 //---------------------------------------------------------
46 // visitor functions (caluclation using stack)
47 //---------------------------------------------------------
48
49 // expr =
50 // {term} term |
51 // {plus} expr plus term |
52 // {minus} expr minus term;
53
54 public void caseAPlusExpr(APlusExpr node) {
55 int left, right;
56
57 node.getExpr().apply(this);
58 node.getTerm().apply(this);
59 right = pop();
60 left = pop();
61 push(left + right);
......................
64 }
65
66 public void caseAMinusExpr(AMinusExpr node) {
67 int left, right;
68
69 node.getExpr().apply(this);
70 node.getTerm().apply(this);
71 right = pop();
72 left = pop();
73 push(left - right);
......................
76 }
77
...... AMultTerm, ADivTerm Visitorの実装 ........
78 // term =
79 // {factor} factor |
80 // {mult} term mult factor |
81 // {div} term div factor;
82
83 public void caseAMultTerm(AMultTerm node) {
84 int left, right;
85
86 node.getTerm().apply(this);
87 node.getFactor().apply(this);
88 right = pop();
89 left = pop();
90 push(left * right);
......................
93 }
94
95 public void caseADivTerm(ADivTerm node) {
96 int left, right;
97
98 node.getTerm().apply(this);
99 node.getFactor().apply(this);
100 right = pop();
101 left = pop();
102 push(left / right);
......................
105 }
106
...... ANumberFactor Visitorの実装 ........
107 // factor =
108 // {number} number |
109 // {expr} l_par expr r_par;
110
111 public void caseANumberFactor(ANumberFactor node) {
112 int num = Integer.parseInt(node.getNumber().getText());
113 push(num);
......................
116 }
117
118 }
|
<説明>
15行目
Calculatorクラス宣言(DepthFirstAdapterクラスから継承)
21--35行目
スタック(線形リスト構造)のインスタンス生成と push/pop操作の実装
54--64行目:加算の実装
構文規則 expr = expr plus term に対応する、APlusExpr Visitor の実装である。
・left --> right の順に child を評価( get.Expr() --> get.Term() )
・スタックからpop --> right value として内部変数に代入
・スタックからpop --> left value として内部変数に代入
・left + right を計算し、結果をスタックに push
66--76行目:減算の実装
構文規則 expr = expr minus term に対応する、AMinusExpr Visitor の実装である。
83--93行目:乗算の実装
構文規則 term = term mult factor に対応する、AMultTerm Visitor の実装である。
95--105行目:除算の実装
構文規則 term = term div factor に対応する、ADivTerm Visitor の実装である。
<注記>0で除算するケース(right valueがゼロ値に相当)は実装していない。
111--116行目:整数値取得の実装
構文規則 factor = number に対応する、ANumberFactor Visitor の実装である(3.3.Bにて説明)。
4. Mainの実装
SableCCにおいて、文法ファイルに基づいて生成された lexer/parser, ならびに先に実装した Visitor(Calculatorクラス)を駆動するため、Mainを実装する。最後に、実行プログラム全体をビルドし、入力列を与えてテストを行う。
4.1 Main.javaの実装
4.2 実行プログラムのビルドとテスト
4.1 Main.javaの実装
Lexer, Parser, 各ノードオブジェクト(node)のクラスパッケージを利用し、Visitor(Calculatorクラス)を利用して演算動作を駆動するための、Mainの具体的な実装について、以下に説明する。
Mainクラス(ソースファイル)
Mainクラスの実装(抜粋)
1 package test2;
2
3 /**/
4 import test2.node.*;
5 import test2.lexer.*;
6 import test2.parser.*;
...........................
15 public class Main
16 {
17 public static void main(String[] arguments)
18 {
19
20 try
21 {
22 System.out.println("Type an arithmetic expression:");
23
24 // Create a Lexer instance.
25 Lexer l = new Lexer(
26 new PushbackReader(
27 new InputStreamReader(System.in), 1024));
28
29 // Create a Parser instance.
30 Parser p = new Parser(l);
31
32 // Parse the input.
33 Start tree = p.parse();
34
35 // Apply the translation.
36 Calculator calc = new Calculator();
37 tree.apply(calc);
38 System.out.println(" = " + calc.getResult());
39
40 }
41 catch(Exception e)
42 {
43 System.out.println(e.getMessage());
44 }
45 }
46 }
47
|
<説明>
4--6行目
node, lexer, parserクラスパッケージの利用を宣言
25--27行目
標準入力から PushbackReader を使用して入力列を読み込み、Lexerコンストラクタによって字句解析器 Lexerオブジェクトのインスタンス l を得る。
30行目
Lexerのインスタンス l を引数として、Parserコンストラクタによって構文解析器 Parserオブジェクトのインスタンス p を得る。
33行目
Parserクラスの parseメソッドによって、導出木のインスタンス tree を得る。
36--37行目
Visitorクラスの Calculator のインスタンス calc を生成し、導出木treeに対してDFS探索を実行する。
38行目
最後に、calc内のスタック先頭の値を表示する。
4.2 実行プログラムのビルドとテスト
付録A. SableCCのインストール、5. 実行試験 を参考にして、test2calcプロジェクトファイルをビルドして、SableCCによる実行プログラムをビルドしてみよう。
test2calcプロジェクトファイルはここからダウンロード
test2calc-src.tar.gz
実際に、演算式のいくつかを実行プログラム(test2.jar)に入力した場合の実行結果を以下に示す。
実行結果は、Calculatorクラスの PrintStack関数によって、現在のスタックの状態(右側が先頭)と、演算あるいは値取得(N)の操作の印が、逐次表示される。
<実行結果1:"12 / 4 - 3[EOF]">
$ echo "12 / 4 - 3" | java -jar test2.jar
N 12
N 12 4
/ 3
N 3 3
- 0
= 0
|
<実行結果2:"( 4 + 8 ) / 2[EOF]">
$ echo "( 4 + 8 ) / 2" | java -jar test2.jar
N 4
N 4 8
+ 12
N 12 2
/ 6
= 6
|
<実行結果3:"12 / 4 - 3 * 1[EOF]">
$ echo "12 / 4 - 3 * 1" | java -jar test2.jar
N 12
N 12 4
/ 3
N 3 3
N 3 3 1
* 3 3
- 0
= 0
|
|