ASTのツリー構造

Question

私はC＃でインタプリタを書こうとしていますが、私は解析段階にいます。私はこの時点で抽象構文木を生成しなければならないと考えましたが、C＃で表現する方法はわかりません。

現在、私はちょうどList<object>を使用していますが、私はそれが間違ってやっている感があります。

ありがとうございます。 「タイプ」タグのフィールドの大きなバケツ - - 特定のクラスのきめ細かい階層へ

Answer 1

は、単一の「ノード」タイプに至るまで多くの技術があります。重要なのは、このデータ構造を何度も何度もトラバースする必要があるため、トラバーサルコードを簡単かつ堅牢にする方法を考えることです。

バックステップを取る、しかし、解釈が厳密にASTを必要としません。多くの初期のインタプリタは、文字通り、各行のコードを読み込み、パーズして実行したり、ループなどでスタックベースのブックマーキングシステムで実装したりしていました。私は、bashやcmd.exeのようなシェル言語は今日もこのように動作していると思う。

Answer 2

ほとんどのASTノードの実装は非常に簡単です。

ノード型（通常は整数）、子リスト（ListはOK、高性能実装は統計的に共通の1st、2ndのメンバセットを持つstruct（ok、ok、 "class" 、3番目の子）、およびASTノードインスタンスに固有の値（例えば、ASTノード「整数定数」の値「5」）を運ぶためのいくつかの追加のフィールド。任意のノードから親に効率的にツリーをナビゲートできるようにするために、親ノードへの特別な参照が戻ってくることがよくあります。

あなたが持っている必要がありますセットを決定するのは難しいです。大きな文法の場合、数百の文を定義しなければならないので、これは不便です。文法を修正するときは、文法を修正する際にチャーンが発生します。

簡単なトリックは、単に文法ルールごとにASTノードを定義しています。 （これは、ほとんどの場合、「具体的な構文木」と呼ばれます）。しかし、それは脳が無く、あなたは何も見逃すことはありません。私たちのDMS Software Reengineering Toolkit

は、文法規則からdirrectly ASTノードタイプを生成し、この「簡単なトリック」という考えに従っています。値を持たないリーフASTノードはツリーに存在せず、単体プロダクションのノードはツリーに存在せず、リスト作成プロダクションは子のリストスタイルを持ち、他のノードタイプは子どものための固定スロット型。とにかく "抽象"構文木にかなり近いものが最終結果です。このすべては、DMSのパーサジェネレータによって自動的に構築されるので、まったく考える必要はありません。

DMSには、十分にテストされたC＃4.0のフロントエンドもあります。 ASTを定義する頭痛を克服すると、分析/変換/生成が必要になり、DMSの残りの部分が突然明らかに重要になります。

Answer 3

私はあなたが何の制限これが課さず、どのような要件がある明確に理解するまで、あなたはList<object>を使用し続けることを示唆しています。それとも、あなたはLISPインタプリタを書いていることから、ペアクラスを作成し、objectであることを使用し、nullは'()の等価である：

public sealed class Pair 
{ 
    public object Car ; 
    public object Cdr ; 
} 

は直接S-式にあなたの入力を解析して直接あなたの通訳の仕事を持っていますそれ。結局のところ、LISPはASTsの前に存在していました！