Abstract syntax tree | EPFL Graph Search

Are you an EPFL student looking for a semester project?

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

In computer science, an abstract syntax tree (AST), or just syntax tree, is a tree representation of the abstract syntactic structure of text (often source code) written in a formal language. Each node of the tree denotes a construct occurring in the text. The syntax is "abstract" in the sense that it does not represent every detail appearing in the real syntax, but rather just the structural or content-related details. For instance, grouping parentheses are implicit in the tree structure, so these do not have to be represented as separate nodes. Likewise, a syntactic construct like an if-condition-then statement may be denoted by means of a single node with three branches. This distinguishes abstract syntax trees from concrete syntax trees, traditionally designated parse trees. Parse trees are typically built by a parser during the source code translation and compiling process. Once built, additional information is added to the AST by means of subsequent processing, e.g., contextual analysis. Abstract syntax trees are also used in program analysis and program transformation systems. 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. An AST has several properties that aid the further steps of the compilation process: An AST can be edited and enhanced with information such as properties and annotations for every element it contains. Such editing and annotation is impossible with the source code of a program, since it would imply changing it. Compared to the source code, an AST does not include inessential punctuation and delimiters (braces, semicolons, parentheses, etc.). An AST usually contains extra information about the program, due to the consecutive stages of analysis by the compiler.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (7)

Related people (2)

Related concepts (19)

Related courses (2)

Related lectures (31)

Parsing

Parsing, syntax analysis, or syntactic analysis is the process of analyzing a string of symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal grammar. The term parsing comes from Latin pars (orationis), meaning part (of speech). The term has slightly different meanings in different branches of linguistics and computer science. Traditional sentence parsing is often performed as a method of understanding the exact meaning of a sentence or word, sometimes with the aid of devices such as sentence diagrams.

Lexical analysis

Lexical tokenization is conversion of a text into (semantically or syntactically) meaningful lexical tokens belonging to categories defined by a "lexer" program. In case of a natural language, those categories include nouns, verbs, adjectives, punctuations etc. In case of a programming language, the categories include identifiers, operators, grouping symbols and data types. Lexical tokenization is not the same process as the probabilistic tokenization, used for large language model's data preprocessing, that encode text into numerical tokens, using byte pair encoding.

Abstract syntax tree

CS-320: Computer language processing

We teach the fundamental aspects of analyzing and interpreting computer languages, including the techniques to build compilers. You will build a working compiler from an elegant functional language in

EE-608: Deep Learning For Natural Language Processing

The Deep Learning for NLP course provides an overview of neural network based methods applied to text. The focus is on models particularly suited to the properties of human language, such as categori

Two approaches to portable macros

Eugene Burmako, Fengyun Liu

For any programming language that supports macros and has multiple implementations (each with different AST definitions), there is a common problem: how to make macros that operate on ASTs portable am

2017

A TASTY Alternative

Martin Odersky, Eugene Burmako, Dmytro Petrashko

This document proposes a new serialization format for typed syntax trees of Scala programs. It aims to be ● compact: All numbers and references are length encoded, trees are inlined by default but may

2016

Style Checking With Scala.Meta

Eugene Burmako, Mathieu Baptiste Demarne

In many companies, code reviews are big parts of the day-to-day life of an engineer. Some can argue that the time spent on someone else’s code is time that some cannot spent on her or his own work. Co

2015

Introduction to Computer Language Processing

Covers computer language processing, compilers, skills learned, and application examples.

Interpreters and Virtual Machines

Explores interpreters and virtual machines, discussing their advantages, types, and optimization techniques.

Interpreter: Arithmetic Expressions

Covers a simple functional language, abstract syntax trees, interpreting expressions, and desugaring.