Abstract Syntax Tree Generator

Posted on April 12, 2020 by Administrator Posted in A Level Concepts, Computer Science, Computing Concepts

In computer science, an abstract syntax tree (AST), or just syntax tree, is a tree representation of the high level source code.

The compilation process consists of translating the high level source code (e.g. Java, Python, C++, FORTRAN, etc.) into machine code. This process consists of 4 steps:

Lexical Analysis
Syntax Analysis
Code Generation
Code Optimisation

A list of tokens is generated during the lexical analysis of the compilation process.
An Abstract Syntax Tree (AST) is generated during the syntax analysis of the compilation process.

The following tool enables you to type/import some high level code (Javascript) in the first tab below and generate the list of tokens and the Abstract Syntax Tree corresponding to your code. You can see what the tree looks like using the JSON format (third tab) or as a visual representation (fourth tab).

Source CodeTokens (JSON)TokensAST (JSON)AST Tree

Javascript Code:

Copy and paste your JavaScript code in the textarea below and press the “Generate Abstract Tree” button below to generate the list of tokens (lexical analysis) on tab 2 and the AST tree (syntax analysis) on tab 3 and tab 4.
Generate Abstract Syntax Tree

List of Tokens (JSON format)

The list of tokens is generated from the source code during the lexical analysis stage of the compilation. Notice how, during the lexical analysis, annotations and white spaces are discarded and are hence not included in the list of tokens.

List of Tokens

Abstract Syntax Tree (JSON format)

The Abstract Syntax Tree is generated using both the list of tokens (from the lexical analysis) and the source code. The AST is generated during the syntax analysis stage of the compilation. Any syntax error would be detected and a syntax error message would then be returned, stopping the compilation process.

Abstract Syntax Tree

Open AST in new window

Did you know?

Rear Admiral Grace Hopper, 1984

One of the first programming languages to be compiled was COBOL. It was invented in the 1950s based on the work of Grace Hopper (1906 – 1992). Grace Hopper was an American computer scientist and United States Navy rear admiral. she was a pioneer of computer programming who invented the first compiler. While at the time all programs were based on mathematical notations, she believed that a programming language based on English words was possible and would be more accessible to a wider range of programmers. In 1955, she and her team wrote a specification for such a programming language and implemented a prototype: The FLOW-MATIC compiler became publicly available in the late 1950s. Her compiler converted English terms into machine code understood by computers. Her work also focused on the idea of designing machine-independent programming languages, which led to the development of COBOL, an early high-level programming language still in use today.

Grace Hopper had a key role in the development of computer science. She invented the concept of sub-routines to help programmers save time when writing code. Her work on developing high-level languages was also motivated by the need to be able to save time when writing programs, as writing low-level code can be extremely time consuming.

Women in STEM

Listen to what Megan Smith (U.S. Chief Technical Officer) said about Grace Hooper in 2014:

Source: Women in Stem, U.S. Chief Technology Officer Megan Smith / Public domain

The first computer bug!

Nowadays, when we find an error in a computer program, we call this error a bug. While Grace Hopper was working on a Mark II Computer at Harvard University in 1947, her team discovered a moth stuck in a relay. The moth impeded the operation of the relay by creating a short-circuit. The problem was fixed by removing the moth (debugging the relay!). The following picture is a photo of the notes from Grace Hopper and her associates with a picture of the actual moth!