「抽象構文木」の版間の差分

2013年12月29日 (日) 18:59時点における版

抽象構文木 (Abstract Syntax Tree, AST) とは、通常の構文木から言語の意味に関係ない情報を取り除き、意味に関係ある情報のみを取り出した木構造のデータ構造です。

読み方

抽象構文木

ちゅうしょうこうぶんぎ

Abstract Syntax Tree

あぶすとらくと しんたっくす つりー

AST

えー えす てぃー

概要

</syntaxhighlight>

実行例

clang++を使用して、astを出力できます。

print:
        clang++ -cc1 -ast-print main.cpp
dump:
        clang++ -cc1 -ast-dump main.cpp
view:
        clang++ -cc1 -ast-view main.cpp

print

clang++ -cc1 -ast-print main.cpp
void b();
void a();
class C {
public:
    void f1()     {
        this->f2();
    }
 
 
    void f2()     {
        b();
    }
 
 
};
void b() {
}
 
 
void a() {
    C c;
    c.f1();
}
 
 
int main(int argc, const char *argv[]) {
    a();
    return 0;
}

dump

clang++ -cc1 -ast-dump main.cpp
TranslationUnitDecl 0x2a85a170 <<invalid sloc>>
|-TypedefDecl 0x2a85a460 <<invalid sloc>> __builtin_va_list 'char *'
|-FunctionDecl 0x2a85a4c0 <main.cpp:3:1, col:8> b 'void (void)'
|-FunctionDecl 0x2a85a540 <line:4:1, col:8> a 'void (void)'
|-CXXRecordDecl 0x2a85a5a0 <line:5:1, line:9:1> class C
| |-CXXRecordDecl 0x2a85a640 <line:5:1, col:7> class C
| |-AccessSpecDecl 0x2a85a690 <line:6:2, col:8> public
| |-CXXMethodDecl 0x2a85a6c0 <line:7:3, col:19> f1 'void (void)'
| | `-CompoundStmt 0x2a85a808 <col:13, col:19>
| |   `-CXXMemberCallExpr 0x2a85a7e8 <col:14, col:17> 'void'
| |     `-MemberExpr 0x2a85a7c8 <col:14> '<bound member function type>' ->f2 0x2a85a740
| |       `-CXXThisExpr 0x2a85a7b8 <col:14> 'class C *' this
| |-CXXMethodDecl 0x2a85a740 <line:8:3, col:18> f2 'void (void)'
| | `-CompoundStmt 0x2a85a8b8 <col:13, col:18>
| |   `-CallExpr 0x2a85a898 <col:14, col:16> 'void'
| |     `-ImplicitCastExpr 0x2a85a888 <col:14> 'void (*)(void)' <FunctionToPointerDecay>
| |       `-DeclRefExpr 0x2a85a854 <col:14> 'void (void)' lvalue Function 0x2a85a4c0 'b' 'void (void)'
| |-CXXConstructorDecl 0x2a85aa30 <line:5:7> C 'void (void)' inline
| | `-CompoundStmt 0x2a85abc8 <col:7>
| `-CXXConstructorDecl 0x2a85aae0 <col:7> C 'void (const class C &)' inline
|   `-ParmVarDecl 0x2a85ab90 <col:7> 'const class C &'
|-FunctionDecl 0x2a85a8f0 prev 0x2a85a4c0 <line:10:1, line:11:1> b 'void (void)'
| `-CompoundStmt 0x2a85a950 <line:10:10, line:11:1>
|-FunctionDecl 0x2a85a980 prev 0x2a85a540 <line:12:1, line:15:1> a 'void (void)'
| `-CompoundStmt 0x2a85ac60 <line:12:10, line:15:1>
|   |-DeclStmt 0x2a85abf8 <line:13:2, col:5>
|   | `-VarDecl 0x2a85a9f0 <col:2, col:4> c 'class C'
|   |   `-CXXConstructExpr 0x2a85abd8 <col:4> 'class C' 'void (void)'
|   `-CXXMemberCallExpr 0x2a85ac40 <line:14:2, col:7> 'void'
|     `-MemberExpr 0x2a85ac20 <col:2, col:4> '<bound member function type>' .f1 0x2a85a6c0
|       `-DeclRefExpr 0x2a85ac08 <col:2> 'class C' lvalue Var 0x2a85a9f0 'c' 'class C'
`-FunctionDecl 0x2a85adb0 <line:17:1, line:21:1> main 'int (int, const char **)'
  |-ParmVarDecl 0x2a85ac90 <line:17:10, col:14> argc 'int'
  |-ParmVarDecl 0x2a85ad30 <col:20, col:37> argv 'const char **'
  `-CompoundStmt 0x2a85aee0 <line:18:1, line:21:1>
    |-CallExpr 0x2a85ae98 <line:19:2, col:4> 'void'
    | `-ImplicitCastExpr 0x2a85ae88 <col:2> 'void (*)(void)' <FunctionToPointerDecay>
    |   `-DeclRefExpr 0x2a85ae6c <col:2> 'void (void)' lvalue Function 0x2a85a980 'a' 'void (void)'
    `-ReturnStmt 0x2a85aed0 <line:20:2, col:9>
      `-IntegerLiteral 0x2a85aeb8 <col:9> 'int' 0

view

clang++ -cc1 -ast-view main.cpp
void b()void a()void b() {
}
 
 
Writing '/tmp/llvm_wfJ0Dj/AST.dot'...  done.
 
void a() {
    C c;
    c.f1();
}
 
 
Writing '/tmp/llvm_4ZKIGP/AST.dot'...  done.
 
int main(int argc, const char *argv[]) {
    a();
    return 0;
}
 
 
Writing '/tmp/llvm_hAusAu/AST.dot'...  done.

dotファイルの見方

dotty /path/to/AST.dot

dotコマンドを使うには、graphvizが必要です。

dot -Tgif ./AST.dot > ast.gif
xv ast.gif

インストール

Ubuntu/Debianにインストールする場合

apt コマンドでインストールする場合です。

sudo apt install graphviz

FreeBSDにインストールする場合

ports コレクションからインストールする場合

cd /usr/ports/graphics/graphviz
sudo make install clean

pkgコマンドでインストールする場合

sudo pkg install graphviz

portmasterコマンドでインストールする場合

sudo portmaster -y -d /usr/ports/graphics/graphviz

関連項目

• clang++