Abstract Syntax Tree (AST)

In computer science, an abstract syntax tree, or just syntax tree, is a tree representation of the abstract syntactic structure of source code written in a programming language.

Rahul Khinchi

3 years ago | 3 min read

What is AST?

It is a tree representation of the abstract syntactic structure of source code written in a programming language. Each node of the tree denotes a construct occurring in the source code.

Application in compilers

Abstract syntax trees are data structures widely used in compilers to represent the structure of program code. An AST is usually the result of the syntax analysis phase of a compiler. It often serves as an intermediate representation of the program through several stages that the compiler requires, and has a strong impact on the final output of the compiler.

For Example, This is a Source Code.

class GFG {
    public static void main (String[] args) {
        System.out.println("Hello World!");
    }
}

AST of above source code:

CLASS_DEF -> CLASS_DEF [1:0]
|--MODIFIERS -> MODIFIERS [1:0]
|   `--LITERAL_PUBLIC -> public [1:0]
|--LITERAL_CLASS -> class [1:7]
|--IDENT -> GFG [1:13]
`--OBJBLOCK -> OBJBLOCK [1:17]
    |--LCURLY -> { [1:17]
    |--METHOD_DEF -> METHOD_DEF [2:4]
    |   |--MODIFIERS -> MODIFIERS [2:4]
    |   |   |--LITERAL_PUBLIC -> public [2:4]
    |   |   `--LITERAL_STATIC -> static [2:11]
    |   |--TYPE -> TYPE [2:18]
    |   |   `--LITERAL_VOID -> void [2:18]
    |   |--IDENT -> main [2:23]
    |   |--LPAREN -> ( [2:27]
    |   |--PARAMETERS -> PARAMETERS [2:34]
    |   |   `--PARAMETER_DEF -> PARAMETER_DEF [2:34]
    |   |       |--MODIFIERS -> MODIFIERS [2:34]
    |   |       |--TYPE -> TYPE [2:34]
    |   |       |   `--ARRAY_DECLARATOR -> [ [2:34]
    |   |       |       |--IDENT -> String [2:28]
    |   |       |       `--RBRACK -> ] [2:35]
    |   |       `--IDENT -> args [2:37]
    |   |--RPAREN -> ) [2:41]
    |   `--SLIST -> { [2:43]
    |       |--EXPR -> EXPR [3:26]
    |       |   `--METHOD_CALL -> ( [3:26]
    |       |       |--DOT -> . [3:18]
    |       |       |   |--DOT -> . [3:14]
    |       |       |   |   |--IDENT -> System [3:8]
    |       |       |   |   `--IDENT -> out [3:15]
    |       |       |   `--IDENT -> println [3:19]
    |       |       |--ELIST -> ELIST [3:27]
    |       |       |   `--EXPR -> EXPR [3:27]
    |       |       |       `--STRING_LITERAL -> "Hello World!" [3:27]
    |       |       `--RPAREN -> ) [3:41]
    |       |--SEMI -> ; [3:42]
    |       `--RCURLY -> } [4:4]
    `--RCURLY -> } [5:0]

How to Make an AST:

Run the Source Code in your local Environment.
Download the Checkstyle Command line: checkstyle-8.43-all.jar from Here.
Audit the Program with the help of Checkstyle in your Terminal: java -jar checkstyle-8.43-all.jar -c /google_checks.xml YourFile.java
After Audit, Run this command in your terminal to get the AST of your preferred Code: java -jar checkstyle-8.43-all.jar -t YourFile.java
Your AST is Ready.

Use of AST:

ASTs are mainly used in compilers to check code for their accuracy. If the generated tree has errors, the compiler prints an error message. Abstract Syntax Tree (AST) is used because some constructs cannot be represented in a context-free grammar, such as implicit typing. They are highly specific to programming languages, but research is underway on universal syntax trees.

Programming

Software Engineering

Upvote

Created by

Rahul Khinchi

Campus Mantri at Geeks for Geeks | Java Programmer | Contributor at Checkstyle Open Source