C++ AST & Parsing Explained

Abstract Syntax Tree (AST)

A compiler needs more than the characters in a program. In n <= 1, it must recognize one comparison, identify its two operands and determine which declaration the name n refers to. An Abstract Syntax Tree records the program's constructs and how they fit together.

Follow this function through the rest of the page. Its condition and two recursive calls give us distinct fragments to inspect. Save it as fibonacci.cpp to use the compiler commands below; a function definition does not need a main when we stop before linking.

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Parsing Phases

The front end moves from characters to tokens, structured constructs and semantic information. These are useful responsibilities to distinguish, rather than a promise of three isolated passes: Clang's parser calls semantic analysis while processing the input.

1. Lexical Analysis (Tokenization)

The condition n <= 1 contains three tokens:

Whitespace separates these tokens but does not become an expression node. The surrounding if, parentheses and braces also supply tokens that the parser uses to recognize the statement. In a real C++ front end, preprocessing supplies the tokens consumed by the parser.

2. Syntax Analysis

Grammar determines how tokens belong together. For the condition, the comparison is the parent; the reference to n and the literal 1 are its operands. The type labels below are semantic annotations, whose origin is explained next:

BinaryOperator '<=' : bool
├── DeclRefExpr n : int
└── IntegerLiteral 1 : int

The function's return expression works the same way. The + operator owns two CallExpr children. Each call owns an argument expression, n - 1 or n - 2. This structure lets a tool distinguish the two calls even though both use the same function name.

An AST emphasizes program constructs rather than recording every grammar production or punctuation token as a separate child. The exact representation depends on the compiler. Clang, for example, preserves explicit parentheses as ParenExpr nodes where they occur; “abstract” does not mean that every source-level detail disappears.

3. Semantic Analysis

A name's spelling is not enough. Each n in this function resolves to the ParmVarDecl in int fibonacci(int n). Each recursive fibonacci reference resolves to the function declaration. Semantic analysis also checks types: the comparison produces bool, while the calls and addition produce int.

That separates a syntax question from a meaning question. missing <= 1 has the same comparison shape, but the name missing cannot be used here without a declaration. Overload resolution and template instantiation add further semantic work in larger C++ programs. Clang's parser and Sema documentation describes how these responsibilities cooperate.

Common AST Nodes

The explorer uses the following node kinds. Types such as int are attributes on the relevant nodes, rather than extra invented children.

Source ranges and declarations

Select the condition, then inspect the two CallExpr nodes beneath the final return. Their highlights should cover different calls on the same source line. Select an n reference and use Inspect declaration to follow it back to the parameter. Expansion and selection are separate actions, so inspecting a parent does not hide its children.

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Viewing the AST

The explorer is a simplified, authored illustration of this fixed function. Its tree and text view come from one model, with source ranges calculated against the displayed source. It is not recorded compiler output. To compare it with your own compiler, use the same fibonacci.cpp file.

clang++ -std=c++17 -Xclang -ast-dump -fsyntax-only fibonacci.cpp

GCC offers a different representation, its original tree dump. Stop after compilation with -c so this function-only file does not require main:

g++ -std=c++17 -c -fdump-tree-original fibonacci.cpp

This writes an object file and a *.original dump in the output directory; the dump's numeric pass suffix depends on the compiler version. Read that file rather than expecting a Clang-style tree on standard output. GCC documents these options under developer dump options.

Why AST Matters

Once source has structure and resolved meaning, tools can ask more useful questions than a text search can answer:

1. Refactoring and analysis: find references to one declaration even when several scopes reuse the same name.
2. Error detection: report invalid types or unresolved names at the source construct responsible for them.
3. Template processing: represent declarations and expressions while instantiating and checking concrete template uses.
4. Optimization: analyze source-level constructs and lower them to an intermediate representation. Clang's optimization pipeline continues on LLVM IR after its front end.

The important handoff is from text to meaning: the same name can refer to different declarations, and nearby text can belong to different subexpressions. Source ranges, parent-child relationships and types let compiler tools keep those distinctions.

Next Steps

• Learn about Compiler Optimization
• Understand Symbol Tables
• Explore the Preprocessor

Related concepts