All Topics  
Abstract syntax tree

 

 
   Email Print
   Bookmark   Link
 

 

Abstract syntax tree
 
 
  Topics Abstract syntax tree Topic Home

In computer science
Computer science

Computer science is the study of the theoretical foundations of information and computation, and of practical techniques for their implementation and application in computer systems....
, an abstract syntax tree (AST), or just syntax tree, is a tree representation of the abstract (simplified) syntactic structure of source code
Source code

In computer science, source code is any collection of statements or declarations written in some human-readable computer programming language....
 written in a certain programming language
Programming language

A programming language is a machine-readable artificial language designed to express computations that can be performed by a machine, particularly a computer....
. Each node of the tree denotes a construct occurring in the source code. The syntax is abstract in the sense that it does not represent every detail that appears in the real syntax. For instance, grouping parentheses
Bracket

Brackets are punctuation marks used in pairs to set apart or interject text within other text. In computer science, the term is sometimes said to strictly apply to the square or box type....
 is implicit in the tree structure, and a syntactic construct such as if cond then expr may be denoted by a single node with two branches.

Abstract syntax trees are thus different from concrete syntax trees traditionally called parse tree
Parse tree

A parse tree or concrete syntax tree is an tree that represents the syntax structure of a string according to some formal grammar. In a parse tree, the interior nodes are labeled by nonterminals of the grammar, while the leaf nodes are labeled by terminal symbol of the grammar....
s, and are often built by the parser part of the source code translation and compiling
Compiler

A compiler is a computer program that transforms source code written in a programming language into another computer language . The most common reason for wanting to transform source code is to create an executable program....
 process (despite a perhaps unintuitive naming).






Discussion
Ask a question about 'Abstract syntax tree'
Start a new discussion about 'Abstract syntax tree'
Answer questions from other users
Full Discussion Forum



Encyclopedia


In computer science
Computer science

Computer science is the study of the theoretical foundations of information and computation, and of practical techniques for their implementation and application in computer systems....
, an abstract syntax tree (AST), or just syntax tree, is a tree representation of the abstract (simplified) syntactic structure of source code
Source code

In computer science, source code is any collection of statements or declarations written in some human-readable computer programming language....
 written in a certain programming language
Programming language

A programming language is a machine-readable artificial language designed to express computations that can be performed by a machine, particularly a computer....
. Each node of the tree denotes a construct occurring in the source code. The syntax is abstract in the sense that it does not represent every detail that appears in the real syntax. For instance, grouping parentheses
Bracket

Brackets are punctuation marks used in pairs to set apart or interject text within other text. In computer science, the term is sometimes said to strictly apply to the square or box type....
 is implicit in the tree structure, and a syntactic construct such as if cond then expr may be denoted by a single node with two branches.

Abstract syntax trees are thus different from concrete syntax trees traditionally called parse tree
Parse tree

A parse tree or concrete syntax tree is an tree that represents the syntax structure of a string according to some formal grammar. In a parse tree, the interior nodes are labeled by nonterminals of the grammar, while the leaf nodes are labeled by terminal symbol of the grammar....
s, and are often built by the parser part of the source code translation and compiling
Compiler

A compiler is a computer program that transforms source code written in a programming language into another computer language . The most common reason for wanting to transform source code is to create an executable program....
 process (despite a perhaps unintuitive naming). Once built, additional information is added to the AST by subsequent processing, e.g., semantic analysis.

See also

  • Abstract semantic graph
    Abstract semantic graph

    In computer science, an abstract semantic Graph is a data structure used in representing or deriving the Formal semantics of programming languages of an expression in a formal language ....
     (ASG)
  • Concrete syntax tree
  • Document Object Model
    Document Object Model

    The Document Object Model is a platform- and programming language-independent standard object model for representing HTML or XML documents as well as an Application Programming Interface for querying, traversing and manipulating such documents....
     (DOM)
  • Semantic resolution tree
    Semantic resolution tree

    A semantic resolution tree is a tree used for the definition of the semantics of a programming language....
     (RST)
  • Shunting yard algorithm
    Shunting yard algorithm

    The shunting yard algorithm is a method for parsing mathematical equations specified in infix notation. It can be used to produce output in Reverse Polish notation or as an abstract syntax tree ....
  • Symbol table
    Symbol table

    In computer science, a symbol table is a data structure used by a language translator such as a compiler or interpreter , where each identifier in a program's source code is associated with information relating to its declaration or appearance in the source, such as its data type, scope level and sometimes its location....
  • TreeDL
    TreeDL

    Tree Description Language is a computer language for description of strictly-typed tree and operations on them. The main use of TreeDL is in the development of language-oriented tools for the description of a structure of abstract syntax trees....


External links

  • , an Eclipse
    Eclipse (software)

    Eclipse is a multi-language software development environment comprising an Integrated development environment and a plug-in system to extend it....
     plugin to visualize
    Scientific visualization

    Scientific visualization is an interdisciplinary branch of science, primarily concerned with the visualization of Three-dimensional space phenomena, such as architectural, meteorological, medical, biological systems....
     a Java
    Java (programming language)

    Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java ....
     abstract syntax tree
  • Paper "" by Joel Jones (overview of AST implementation in various language families)
  • Paper "" by Nicola Howarth (note that this merely presents the design of *one particular* project's AST, and is not generally informative)
  • Paper "" by Iulian Neamtiu, Jeffrey S. Foster and Michael Hicks
    Michael Hicks

    Michael Hicks is an England historian, specialising on the history of Late Middle Ages England, in particular the Wars of the Roses. Hicks studied with C....
  • Paper "" by Beat Fluri, Michael Würsch, Martin Pinzger, and Harald C. Gall.
  • Diploma thesis "" by Michael Würsch
  • Article "" by Jason Lucas
  • Tutorial ""
  • uses AST representation to control code source quality