Abstract Syntax Tree is a kind of 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.
There is numerous importance of AST with application in compilers as 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.
Let us do discuss the use of AST before proceeding further to the implementation part. AST’s 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 context-free grammar, such as implicit typing. They are highly specific to programming languages, but research is underway on universal syntax trees.
Flow Chart:
id + id * id would have the following syntax tree which is as follows:
Abstract syntax tree will be as follows:
Implementation:
Here we will be writing custom java source codes corresponding to which we will be providing the AST for the same java source code as in implementation.
Example 1(A) Java source code
Java
// Java Custom Source Code // Main classclass GFG { // Main driver method public static void main(String[] args) { // Print statement System.out.println("Hello World!"); }} |
Example 1(B) AST of above source code
Java
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] |
Now you must be wondering how to make an AST or how the above code is generated for that geek follow the simple steps as listed in the sequential order.
- Run the Source Code in your local Environment.
- Download the Checkstyle Command line
checkstyle-8.43-all.jar
- 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
- AST is now ready. But wait geeks,
Note: This is not an Updated AST
Remember: To update the AST, we have to do the following two steps
Step 1: We should replace
">" with ">" and "<" with "<"
Step 2: Remove the code lines
Example 1(C) Updated AST Examples of the above code is as follows:
Java
CLASS_DEF -> CLASS_DEF |--MODIFIERS -> MODIFIERS | `--LITERAL_PUBLIC -> public |--LITERAL_CLASS -> class |--IDENT -> GFG `--OBJBLOCK -> OBJBLOCK |--LCURLY -> { |--METHOD_DEF -> METHOD_DEF | |--MODIFIERS -> MODIFIERS | | |--LITERAL_PUBLIC -> public | | `--LITERAL_STATIC -> static | |--TYPE -> TYPE | | `--LITERAL_VOID -> void | |--IDENT -> main | |--LPAREN -> ( | |--PARAMETERS -> PARAMETERS | | `--PARAMETER_DEF -> PARAMETER_DEF | | |--MODIFIERS -> MODIFIERS | | |--TYPE -> TYPE | | | `--ARRAY_DECLARATOR -> [ | | | |--IDENT -> String | | | `--RBRACK -> ] | | `--IDENT -> args | |--RPAREN -> ) | `--SLIST -> { | |--EXPR -> EXPR | | `--METHOD_CALL -> ( | | |--DOT -> . | | | |--DOT -> . | | | | |--IDENT -> System | | | | `--IDENT -> out | | | `--IDENT -> println | | |--ELIST -> ELIST | | | `--EXPR -> EXPR | | | `--STRING_LITERAL -> "Hello World!" | | `--RPAREN -> ) | |--SEMI -> ; | `--RCURLY -> } `--RCURLY -> } |
Example 2: Representing 1 + 2 can be represented in AST
Java
+ BinaryExpression - type: + - left_value: LiteralExpr: value: 1 - right_vaue: LiteralExpr: value: 2 |
