抽象構文木とは? わかりやすく解説

抽象構文木

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2025/03/24 07:09 UTC 版)

抽象構文木(ちゅうしょうこうぶんぎ、: abstract syntax treeAST)は、通常の構文木(具象構文木あるいは解析木とも言う)から、言語意味に関係ない情報を取り除き、意味に関係ある情報のみを取り出した(抽象した)木構造の木である。

理論的には、有限なラベル付き有向木である。また、演算子と変数や定数といったオペランドから成る数式などのようなものに対する抽象構文木を例にすると、分枝点は演算子、葉はオペランド(つまり、変数や定数)である。

抽象構文木は、構文解析によって直接得られる具象構文木と、最終的な意味表現などのデータ構造との、中間にあるものと位置付けることができる。コンパイラインタプリタといったプログラミング言語処理系の場合は、中間表現のひとつであり、一部の最適化は抽象構文木の上の操作などによっておこなわれる。具象に対する構文がたとえばBNFによって規定されるように、抽象構文木についてもそれを規定する抽象構文というものが考えられる(が、あまり意識されることはない)。抽象構文木から例えば、バイトコードインタプリタに渡す場合にはバイトコードに、現代的なコンパイラの場合には静的単一代入形式などの、目的コードに近くより扱いやすい形式に変換(一種のコード生成)がおこなわれる。

抽象構文木は具象構文木とは異なり、プログラムの意味に関係ない部分を省略する。そのような省略の例としては括弧の省略があげられる。抽象構文木では、その自然な木構造によって結合は自明であるから、グループ化のための括弧などは意味的に不要である。変数名などの名前なども、識別できればよいので何らかのIDのようなもので構わない。ただし現実的にはエラーへの対応などが必要なので、シンボルテーブルの逆引きなどによって対応することもある。逆に理論的には、ド・ブラウン・インデックスのようにインデックス値にしてしまえることもある。

抽象構文木は、具象構文木から「抽象して」作られることもあれば、構文解析フェーズで直接いきなり作ってしまうこともある。

理論的な観点からは、たとえばソースコード上の位置(何行目の何カラム目など)といった具象の情報は言語処理系には不要であり、抽象構文木には無くてもよいのだが、実践的には、エラーを見つけた時にプログラマに親切なエラーメッセージを出力するためなど、重要な情報であり、時には処理系のフロントエンドではなくバックエンドでも必要なこともある。

関連項目

参考文献

この記事は2008年11月1日以前にFree On-line Dictionary of Computingから取得した項目の資料を元に、GFDL バージョン1.3以降の「RELICENSING」(再ライセンス) 条件に基づいて組み込まれている。

外部リンク


抽象構文木

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/03/20 10:04 UTC 版)

インタプリタ」の記事における「抽象構文木」の解説

インタプリタコンパイラ中間的手法1つとして、ソースコード最適化された抽象構文木 (AST) に変換し、その木構造にしたがってプログラム実行するか、実行時コンパイラでの機械語コード生成使用する方法がある。この方式では各文を1回だけ構文解析する必要があるバイトコード比べると、ASTではプログラム全体的構造や文と文の関係を保持でき(それらはバイトコードでは失われる)、圧縮するとさらにコンパクトな表現になる。そのため、実行時コンパイラにとってはバイトコードよりもASTの方が優れた中間表現だとして提案されてきた。また、実行時解析もより優れたものにできる。 しかし、ASTバイトコードよりも冗長であるため、インタプリタとしてはオーバーヘッド大きくなるという問題がある。CRuby場合は、1.8までは構文木インタプリタであったが、1.9では(開発中には YARV呼ばれていた)バイトコードインタプリタに入れ替えられ、性能向上した

※この「抽象構文木」の解説は、「インタプリタ」の解説の一部です。
「抽象構文木」を含む「インタプリタ」の記事については、「インタプリタ」の概要を参照ください。

ウィキペディア小見出し辞書の「抽象構文木」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「抽象構文木」の関連用語

抽象構文木のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



抽象構文木のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの抽象構文木 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaのインタプリタ (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS