技術

2.2. 抽象構文木(AST)

LLVMによるプログラミング言語の実装チュートリアル日本語訳
第2章 万華鏡: 構文解析器とASTの実装
第2節 抽象構文木(AST)

あるプログラムのためのASTは、コンパイラの後段(例えばコード生成)において解釈するのが簡単になるような方法で、プログラムの振る舞いを捉えたものである。
我々は基本的に、言語の中の各構成要素ごとにひとつのオブジェクト、というのを望んでいるので、ASTはその言語を厳密に型どる必要がある。
万華鏡では、式、プロトタイプ、そして関数オブジェクトがある。
まず、式からはじめてみよう。
訳注: ここで説明してるコードの全文は第2章の最後にある。

/// ExprAST - 全ての式ノードの基底クラス。
class ExprAST {
public:
  virtual ~ExprAST() {}
};

/// NumberExprAST - "1.0"のような数値リテラルのための式クラス。
class NumberExprAST : public ExprAST {
  double Val;
public:
  NumberExprAST(double val) : Val(val) {}
};

上のコードは、基本となるExprASTクラスと数値リテラルのために使用するひとつのサブクラスを表現している。
このコードで重要なのは、NumberExprASTクラスはリテラルの数値をインスタンス変数として保持するということである。
これによってコンパイラの後の段階で、保持された数値がなんなのかを知ることが出来る。

これから、我々はASTの作成だけを行うので、それらクラスの便利なアクセッサメソッドは存在しない。
それによって、例えば、コードを整形して印字するための仮想関数を追加するのがとても簡単になる。
以下に、万華鏡言語で基本的に使用される他の式のASTノードの定義を示す。

/// VariableExprAST - "a"のような変数を参照するための式クラス。
class VariableExprAST : public ExprAST {
  std::string Name;
public:
  VariableExprAST(const std::string &name) : Name(name) {}
};

/// BinaryExprAST - 二項演算子のための式クラス。
class BinaryExprAST : public ExprAST {
  char Op;
  ExprAST *LHS, *RHS;
public:
  BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
    : Op(op), LHS(lhs), RHS(rhs) {}
};

/// CallExprAST - 関数呼び出しのための式クラス。
class CallExprAST : public ExprAST {
  std::string Callee;
  std::vector<ExprAST*> Args;
public:
  CallExprAST(const std::string &callee, std::vector<ExprAST*> &args)
    : Callee(callee), Args(args) {}
};

上記は全てだいぶ簡単である。(そうしたから当たり前なんだが。)
VariableExprASTは変数名をキャプチャし、BinaryExprASTは二項演算子のオプコード(opcode)(例えば”+”)をキャプチャし、CallExprASTは関数名と幾つかの引数(これも式である)のリストをキャプチャする。
我々のASTの良い点のひとつは、言語の文法について考える必要なしに言語の特徴をキャプチャ出来る点である。
二項演算子の優先順位や、字句的な構造等々については論考していない事に注意。

我々の簡単な言語に必要な、全ての式ノードを定義するが、まだ制御構文を備えていないため、チューリング完全ではない。
これについては後で章をまるまるひとつ使って修正する。
次に必要な2つのものは、関数のインターフェイスと関数それ自身について考えることである。

/// PrototypeAST - 関数のプロトタイプを表すクラス。
/// 関数名と引数名をキャプチャする。
/// (なので暗黙のうちに引数の数もキャプチャすることになる。)
class PrototypeAST {
  std::string Name;
  std::vector<std::string> Args;
public:
  PrototypeAST(const std::string &name, const std::vector<std::string> &args)
    : Name(name), Args(args) {}
};

/// FunctionAST - 関数定義それ自身を表すクラス。
class FunctionAST {
  PrototypeAST *Proto;
  ExprAST *Body;
public:
  FunctionAST(PrototypeAST *proto, ExprAST *body)
    : Proto(proto), Body(body) {}
};

万華鏡では、関数はその引数の数だけで型付けされる。
全ての値は倍精度浮動小数点なので、各引数の型はどこにも保持する必要はない。
もっと現実的で実用的な言語では、ExprASTクラスは型を保持するフィールドを持つ事になるだろう。

以上を足場にして、次からは万華鏡における式と関数本体の構文解析について考えていく。

コメントを残す

メールアドレスが公開されることはありません。



※画像をクリックして別の画像を表示

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください