In computer science, an abstract syntax tree, or AST, or syntax tree, is a tree-like representation of the abstract syntactic structure of source code, in this case the source code of a programming language. Each node in the tree represents a structure in the source code. The syntax is "abstract" because it does not represent every detail that occurs in the real syntax. For example, nested parentheses are implicit in the structure of the tree and are not represented as nodes, while conditional jump statements such as if-condition-then can be represented by a node with two branches.
The opposite of an abstract syntax tree is a concrete syntaxtree, often called a parse tree. Typically, a syntax analyzer creates a parse tree during the translation and compilation of source code. Once the AST is created, some information is added during subsequent processing, such as semantic analysis.
The structure of the abstract grammar tree does not depend on the grammar of the source language, i.e., the context-independent grammar used in the grammar analysis phase. This is because in Parser engineering, grammars are often transformed equivalently (eliminating left recursion, backtracking, diacritics, etc.), which introduces redundancies into the grammar that can adversely affect subsequent phases, or even confuse the phases. Therefore, many compilers (including GJC) often have to construct syntax analysis trees independently to create a clear interface between the front and back ends.
Python implementation
Assume an interpretation of 'a + 3 * b' where a = 2 and b = 5
The code is very simple and will not be explained in detail.
Num = lambda env, n: n
Var = lambda env, x: env[x]
Add = lambda env, a, b:_eval(env, a) + _eval(env, b)
Mul = lambda env, a, b:_eval(env, a) * _eval(env, b)
_eval = lambda env, expr:expr[0](env, *expr[1:])
env = {'a':2, 'b':5}
tree = (Add, (Var, 'a'),
(Mul, (Num, 3),
(Var, 'b')))
print _eval(env, tree)
The output is 17