ひきぷろのプログラミング日記

プログラミングの日記です。

(C#) 構文木を作ってみた

ここ数日間、画像処理ばっかりやってたので飽きてきました。。
ちょっと、 JavaScriptインタープリタとか作ってみたい とも思っていて、試しに構文木を作ってみました。まだ細かく説明できるほどには理解が深くないので、とりあえずコードを貼り付けてみます。

字句解析からじゃないの という感じもしますが、字句解析は難しそうなので保留にしています。実用的なインタプリタを作りたいかたは、 bison/flex とか使った方が良いと思います。

.NET 環境でも、 bison/flex に代わるものはいくつかあるそうで、軽くググった感じでは次のような URL が出てきました。

Irony - .NET Language Implementation Kit. - Home
Gardens Point Parser Generator - Home
Gardens Point LEX - Home
C#で書かれたパーサージェネレーターSpracheを使ってみた - tuedaの日記

では、今回作ったコードを貼り付けていきます。
とりあえず、整数で四則演算のみ実行できるようなものを作りました。

  • 構文木そのもの: SyntaxTree クラス
  • 構文木のノード: Node クラス
  • ノードの種類: 列挙型の NodeType
  • ノードの値: NodeValue クラス

というような感じです。
他にも、処理が見やすくなるようにクラスをいくつか作りました。

ここから、各クラスのコードを紹介していきます。

// Node.cs
using System;
using System.Collections.Generic;

class Node {
	// ノードの種類 (後でコピペします)
	public NodeType Type;

	// 子要素のリスト
	public List<Node> Children;

	// ノードの値 (後でコピペします)
	public NodeValue Value;

	// コンストラクタ
	public Node(NodeType type) {
		Type = type;
		Children = new List<Node>();
		Value = new NodeValue();
	}

	// 子要素にアクセスしやすくする
	// node.Children[0] というように書く必要がある箇所で、
	// node[0] というように書くことができるようになります
	public Node this[int index] {
		get { return Children[index]; }
	}

	// 子要素の数
	public int ChildCount {
		get { return Children.Count; }
	}

	// 子要素を追加する
	public void AddChild(Node node) {
		Children.Add(node);
	}
}

ノードの種類は列挙型にしています。

// NodeType.cs
enum NodeType {
	Null,	// 未設定
	Add,	// 足し算
	Sub,	// 引き算
	Mul,	// 掛け算
	Div,	// 割り算
	Int,	// 整数の値
}

ノードの値は、 NodeValue というクラスに書きました。
後で整数以外も扱うことができるように、直接 int にはしませんでした。

// NodeValue.cs
class NodeValue {
	// 実際の値
	public int Value;

	// NodeValue のインスタンスは、
	// Create() スタティックメソッドで作成する
	public static NodeValue Create(int value) {
		var result = new NodeValue();
		result.Value = value;
		return result;
	}

	// 暗黙的に int 型に変換されるようにする
	// int i = nodeValue.Value と書かないといけない箇所で、
	// int i = nodeValue と書くことができるようになります
	public static implicit operator int(NodeValue value) {
		return value.Value;
	}
}

ノードを作る時に同じようなことを沢山書かないといけないので、 Factory クラスを作りました。

// NodeFactory.cs
class NodeFactory {
	// 種類が Add の Node を作る
	public static Node Add() {
		return _CreateNode(NodeType.Add);
	}

	// 種類が Sub の Node を作る
	public static Node Sub() {
		return _CreateNode(NodeType.Sub);
	}

	// 種類が Mul の Node を作る
	public static Node Mul() {
		return _CreateNode(NodeType.Mul);
	}

	// 種類が Div の Node を作る
	public static Node Div() {
		return _CreateNode(NodeType.Div);
	}

	// 種類が Int の Node を作る
	public static Node Int(int value) {
		var node = _CreateNode(NodeType.Int);
		node.Value = NodeValue.Create(value);
		return node;
	}

	// ノードの作り方を変える時に、ここだけ変えれば済むように
	// ノードを作るだけのメソッドを作りました
	private static Node _CreateNode(NodeType type) {
		var node = new Node(type);
		return node;
	}
}

SyntaxTree は、木を表現するクラスです。

// SyntaxTree.cs
class SyntaxTree {
	// 処理の起点となるノード
	private Node _rootNode;

	// 起点となるノードを設定する
	public void SetRootNode(Node node) {
		_rootNode = node;
	}

	// 木を巡回する
	public void Traverse() {
		if (_rootNode == null) {
			return;
		}

		// 実際に巡回する処理は TreeProcessor に書いてある
		TreeProcessor processor = new TreeProcessor();
		processor.Traverse(_rootNode);
	}
}

木の処理は TreeProcessor で実行します。

// TreeProcessor.cs
using System;
using System.Collections.Generic;

class TreeProcessor {
	// Node の種類と、処理メソッドを紐付けるテーブル
	private Dictionary<NodeType, Action<Node>> _taskTable;

	// コンストラクタ
	public TreeProcessor() {
		_taskTable = _CreateTaskTable();
	}

	// 木を巡回する
	// (引数で渡した Node が再帰処理で巡回される)
	public void Traverse(Node node) {
		// 実装されていない種類の時は NotImplementedException を投げる
		if (_taskTable.ContainsKey(node.Type) == false) {
			throw new NotImplementedException(string.Format(
				"NodeType: {0} の処理は実装されていません。",
				node.Type.ToString()
			));
		}

		// Node の種類ごとに違う処理を実行する
		Action<Node> action = _taskTable[node.Type];
		if (action == _NullTask) {
			return;
		}
		action(node);
	}

	// Node の種類と、処理メソッドを紐付けるテーブルを作成する
	private Dictionary<NodeType, Action<Node>> _CreateTaskTable() {
		var table = new Dictionary<NodeType, Action<Node>>();
		table.Add(NodeType.Add, _AddTask);
		table.Add(NodeType.Sub, _SubTask);
		table.Add(NodeType.Mul, _MulTask);
		table.Add(NodeType.Div, _DivTask);
		table.Add(NodeType.Int, _NullTask);
		return table;
	}

	// 種類が Add の Node
	private void _AddTask(Node node) {
		_CheckChildCount(node, 2);
		_TraverseAllChildren(node);
		int result = node[0].Value;
		result += node[1].Value;
		node.Value.Value = result;
	}

	// 種類が Sub の Node
	private void _SubTask(Node node) {
		_CheckChildCount(node, 2);
		_TraverseAllChildren(node);
		int result = node[0].Value;
		result -= node[1].Value;
		node.Value.Value = result;
	}

	// 種類が Mul の Node
	private void _MulTask(Node node) {
		_CheckChildCount(node, 2);
		_TraverseAllChildren(node);
		int result = node[0].Value;
		result *= node[1].Value;
		node.Value.Value = result;
	}

	// 種類が Div の Node
	private void _DivTask(Node node) {
		_CheckChildCount(node, 2);
		_TraverseAllChildren(node);
		int result = node[0].Value;
		result /= node[1].Value;
		node.Value.Value = result;
	}

	// 整数値とかの場合は何もしない
	private void _NullTask(Node node) {
	}

	// Node の子要素の数が合っているかチェックする
	private void _CheckChildCount(Node node, int count) {
		if (node.ChildCount == count) {
			return;
		}
		throw new InvalidOperationException(string.Format(
			"NodeType.{0}: 子要素の数を {1} 個にする必要があります。",
			node.Type.ToString(), count
		));
	}

	// 子要素を全て巡回する
	private void _TraverseAllChildren(Node node) {
		foreach (Node child in node.Children) {
			Traverse(child);
		}
	}
}

ここまでで、いったん実装完了です。
実際に使用する時は次のような感じになります。

// 6 + 8 の計算
Node node = NodeFactory.Add();
node.AddChild(NodeFactory.Int(6));
node.AddChild(NodeFactory.Int(8));

SyntaxTree tree = new SyntaxTree();
tree.SetRootNode(node);
tree.Traverse();

Console.WriteLine(node.Value);
// 10 + (6 * 8) の計算
Node node = NodeFactory.Mul();
node.AddChild(NodeFactory.Int(6));
node.AddChild(NodeFactory.Int(8));

Node node2 = NodeFactory.Add();
node2.AddChild(NodeFactory.Int(10));
node2.AddChild(node);

SyntaxTree tree = new SyntaxTree();
tree.SetRootNode(node2);
tree.Traverse();

Console.WriteLine(node2.Value);
// (10 + (6 * 8)) / 2 の計算
Node node = NodeFactory.Mul();
node.AddChild(NodeFactory.Int(6));
node.AddChild(NodeFactory.Int(8));

Node node2 = NodeFactory.Add();
node2.AddChild(NodeFactory.Int(10));
node2.AddChild(node);

Node node3 = NodeFactory.Div();
node3.AddChild(node2);
node3.AddChild(NodeFactory.Int(2));

SyntaxTree tree = new SyntaxTree();
tree.SetRootNode(node3);
tree.Traverse();

Console.WriteLine(node3.Value);

一応、計算できるようになったようです。
ちょっとずつ機能を増やしていこうと思います。

上のコードは、何か所か書き心地がよろしくない部分があります。興味があるかたは次のような修正を追加してみてください。

  • TreeProcessor.cs で node.Value.Value = result と書かれている箇所は、工夫すると node.Value = result というように書いても動くようになります。
  • 最後の、実際にコードを使うサンプルのところで、 node.AddChild(NodeFactory.Int(6)) というように書かれている箇所は、 node.AddChild(6) と書いても動くように実装しなおすことができます。

構文木について詳しく知りたいかたは、次の本を見てみてください。
この本はドラゴンブックと呼ばれていて、インタプリタとかコンパイラを作る人はみんな読んでるっぽいです。

コンパイラ―原理・技法・ツール (Information & Computing)

コンパイラ―原理・技法・ツール (Information & Computing)