AST : Abstract Syntax Tree

Introduction

• In computer science, an abstract syntax tree (AST), or just syntax tree, is a tree representation of the abstract syntactic structure of text (often source code) written in a formal language. Each node of the tree denotes a construct occurring in the text.

• The syntax is "abstract" in the sense that it does not represent every detail appearing in the real syntax, but rather just the structural or content-related details. For instance, grouping parentheses are implicit in the tree structure, so these do not have to be represented as separate nodes. Likewise, a syntactic construct like an if-condition-then statement may be denoted by means of a single node with three branches.

• This distinguishes abstract syntax trees from concrete syntax trees, traditionally designated parse trees. Parse trees are typically built by a parser during the source code translation and compiling process. Once built, additional information is added to the AST by means of subsequent processing, e.g., contextual analysis.

• Abstract syntax trees are also used in program analysis and program transformation systems.

Abstract Syntax Tree has these advantages:

• Can deal with different syntax in general
• Can focus on the semantics
• One interpreter will be enough to deal with various languages using Abstract Syntax Tree

Example

• 그림처럼 add와 sub뒤에 num만 나오면 좋겠지만 때때로 num이 아닌 다른 것을 넣을 수도 있다. 그 때는 해당 Arithmetic Expression은 맞지 않기에 AE 타입으로 정의되었으니 num혹은 add와 sub의 결과값이 AE?자리에 들어가야 한다. AST의 좋은 예시이다.