peg-sharp でインデント表現された木構造を読んでみる
Python や YAML は、インデントでツリーを表現しているけど、あれが簡単な BNF で書ける気がしなくて、どうやって書くのか気になっていたので書いて見ることにした。
試して分かったことというと、インデントを解釈するのにコンテキストを持たせる必要がありそうということくらい。
入力と出力
例えばこんな風に木構造を書く。
a
aa
aaa
ab
aba
abb
b
ba
これを C# 側でこんなデータ構造で使いたいとする。
class Tree { public string Name; public Tree Parent; public List<Tree> ChildList = new List<Tree>(); public Tree(Tree parent, string name) { Parent = parent; Name = name; if (parent != null) { parent.ChildList.Add(this); } } public void Print(int level) { Console.WriteLine(new String(' ', level * 4) + Name); foreach (var tree in ChildList) { tree.Print(level + 1); } } }
何の面白みも無いのが残念だけど、PEG でどうやって書こうか考えてみたいだけなので問題なし。
peg-sharp のスクリプト
peg-sharp 側では、インデントをツリー構造に押しこむところは作らずに、インデントの数だけを処理するように作ってみた。
start = Start value = String namespace = IndentTree Start := LineSyntax (NewLine LineSyntax)*; LineSyntax := IndentedId / EmptyLine; IndentedId := Indent* Identifier `Context.AddTree(results.Count-1, results[results.Count-1].Text)` Indent := ' ' `;` `expected = "indent"` EmptyLine := Space*; Identifier := [a-zA-Z_] [a-zA-Z0-9_]* `value = null` `expected = "identifier"` Space := [ \t] `;` `expected = "whitespace"` NewLine := '\r'? '\n' `;` `expected = "newline"`
results ってので結果を扱わないといけないのがかなり分かりにくい。今回は各ノードはただの文字列として扱うからこの程度で良いけど、凝ったことを使用とすると分かりにくくなりそう。
ここで、IndentedId に登場しているコンテキストで今の木構造の状態を処理することにした。
コンテキスト
今、どこのインデントを処理しているのか表現するのに適当に List を使ってみた。
class Context { public List<Tree> TreeStack = new List<Tree>(); public Context() { TreeStack.Add(new Tree(null, "(root)")); } public void AddTree(int level, string name) { if (0 <= level && level < TreeStack.Count) { Tree tree = new Tree(TreeStack[level], name); TreeStack = TreeStack.Take(level+1).ToList(); TreeStack.Add(tree); } else if (level == TreeStack.Count) { Tree tree = new Tree(TreeStack[level], name); TreeStack.Add(tree); } else { throw new Exception("Illegal indentation"); } } public Tree GetRoot() { return TreeStack[0]; } }
思ったより複雑な書き方になっている気がして少しがっかり。
パーザクラスへコンテキストの追加
あとは、コンテキストをパーザに差し込んで、適当に表示するだけ。
internal sealed partial class IndentTree { Context Context = new Context(); public Tree GetTree() { return Context.GetRoot(); } }
出力された Parser クラスが partial クラスなので、追加のデータを別ファイルから追加することができる。便利だと思っってしまったけど、使い方としては間違っているような気がしなくもない。機能追加に partial クラスを使うってどうなんだ。
テスト
以下は、ツリーを表示するだけの簡単なコード。
static void Main(string[] args) { var parser = new IndentTree.IndentTree(); string testScript = @" a aa aaa ab aba abb b ba "; var result = parser.Parse(testScript); parser.GetTree().Print(0); }
