Skip to main content
Back to path

Welcome to a Grasp lesson

Create a free account to keep studying and create your own study path.

Lesson 24

Clang Parser and Sema: AST Construction Flow

Recommended resources

In the last two lessons, we explored the Clang Abstract Syntax Tree (AST), identifying its core components and learning how to use clang -Xclang -ast-dump to visualize it. You now have a solid understanding of what the AST is. Today's goal is to understand how it gets built. This is essential for debugging the Clang frontend, as a malformed AST often points to a bug in its construction.

This lesson will focus on the dynamic partnership between two key components of the Clang frontend: the Parser and the Semantic Analyzer (Sema). We will describe the general flow of how they cooperate to transform a stream of source code tokens into the semantically-rich AST you are now familiar with.

The Frontend Assembly Line

Before diving into the details, let's visualize the high-level process. When you compile a C++ file, the code passes through several stages within the Clang frontend.

This flowchart illustrates the main stages of the Clang frontend. User input is processed by the Preprocessor, then the Parser, which works with Sema to finally produce the Abstract Syntax Tree (AST).

As the diagram shows, the process begins with the Preprocessor expanding macros and includes. The result is a stream of "tokens"—the fundamental vocabulary of the language, like keywords (if, for), identifiers (my_variable), and operators (+, *). This token stream is then fed to the Parser.

The Parser's job is to ensure the code is grammatically correct. It's like checking the sentence structure of an English text. Sema's job is to check if the grammatically correct sentence actually makes sense. It's the difference between "Colorless green ideas sleep furiously" (grammatically correct but semantically nonsensical) and "The quick brown fox jumps over the lazy dog" (grammatically and semantically correct).

The key insight is that the Parser and Sema don't operate in sequence. Instead, they are tightly interwoven, working together to build the AST piece by piece.

The Parser: Recognizing Grammatical Structure

The Parser consumes the token stream and attempts to match it against the rules of the C++ grammar. For example, it knows that an if statement consists of the if keyword, followed by a parenthesized condition, followed by a statement.

Clang uses a hand-written recursive-descent parser. This is significant because, unlike compilers that use parser-generator tools (like Yacc or Bison), Clang's parsing logic is written directly in C++ functions. You'll find these functions primarily in clang/lib/Parse/. They often have names that clearly reflect the C++ construct they are designed to parse, such as ParseIfStatement, ParseForStatement, or ParseDeclaration.

This design has a direct implication for you as a contributor: when you need to understand or modify how a piece of syntax is handled, you will be reading and debugging these C++ functions.

How to Implement Your First Compiler Feature:The Story of Concepts in Clang - Saar Raz - CppCon 2019

To get a feel for what this looks like in practice, watch this segment from Saar Raz's CppCon 2019 talk. He describes his first contribution to a compiler, where he adds a new keyword. Notice his strategy: he finds a similar existing keyword (static_assert) and searches the codebase to see how it's parsed, leading him to the exact C++ functions that handle it.

Watch the segment from copy and paste. Pay attention to how he finds the relevant C++ enum and parsing functions by searching for the existing static_assert keyword. This is a very common workflow when first navigating the codebase.

Sema: Enforcing Semantic Rules

While the Parser identifies syntactic structures, it doesn't know if they are meaningful. That's Sema's responsibility. Sema (short for Semantic Analysis) is the heart of the compiler's "understanding" of the code. Its tasks include:

  • Type Checking: Is it valid to add this variable to that one? Can this function's return value be assigned to this variable?
  • Name Lookup: When the code uses a variable x, Sema finds its declaration to determine its type and other properties.
  • Checking Language Rules: Enforcing rules like "you can't declare a for loop variable with static storage in C" or "you cannot access a private member of a class from this context."

When Sema finds a problem, it uses the DiagnosticsEngine to generate the errors and warnings you see when you compile your code.

The Handshake: Parse... calls ActOn...

Now we arrive at the core of the process: the interaction model between the Parser and Sema. The general flow is a "Parse-then-Act" pattern.

  1. The Parser consumes tokens to recognize a specific grammatical construct (e.g., a do-while loop).
  2. Once it has identified all the syntactic parts of the construct (e.g., the loop body and the condition), it calls a specific method on the Sema object, usually named ActOn.... For a do-while loop, this method is ActOnDoStmt.
  3. The Sema method (ActOnDoStmt) receives the pieces of the construct from the Parser. It performs all necessary semantic checks (e.g., ensuring the condition is a boolean or convertible to one).
  4. If the checks pass, Sema creates the corresponding AST node (e.g., DoStmt) by calling its constructor and populating it with the validated information.
  5. Sema returns the newly created AST node back to the Parser, which then incorporates it into the larger tree structure it is building.

This handshake ensures that the AST is not just a syntax tree, but a semantic tree, where every node has been validated and enriched with type and meaning.

The following resource provides a clear illustration of this process.

[PDF] Code transformation and analysis using Clang and LLVM

This section from a presentation by Hal Finkel gives two excellent, commented examples of the Parser/Sema interaction.

In the PDF, navigate to slide 43, titled "Sema". Read the explanation and study the code for ActOnDoStmt. Then, look at the next slide (44) which shows part of the ActOnForStmt implementation, where it checks for a C99 language rule and issues a diagnostic if it's violated. This perfectly demonstrates Sema's role.

The MaskRay blog provides another view of this flow, showing the call stack as the compiler parses a source file.

A deep dive into Clang's source file compilation | MaskRay

This post details the compilation process at a function-call level.

Read the section titled clangParse and clangSema. The table shows a simplified call stack starting from ParseAST. Notice how parsing functions like ParseTopLevelDecl eventually lead to calls to Sema actions like Sema::ActOnStartOfTranslationUnit. This reinforces the tight integration we've been discussing.

When Things Go Wrong

A crucial part of this process is error handling. Compilers strive to provide multiple diagnostics in a single run rather than stopping at the first error. This is achieved through sophisticated recovery mechanisms.

  • If the Parser encounters a syntax error (like a missing semicolon), it attempts to recover by skipping tokens until it finds a point where it can resume parsing (e.g., the start of the next statement).
  • If Sema finds a semantic error, it reports a diagnostic. However, it often tries to "heal" the code to allow compilation to continue. For example, if you call a function with the wrong type of argument, Sema will report the error but may still build a CallExpr node in the AST, marking it as erroneous. This allows it to check the rest of the program for other, unrelated errors.

This principle of "no quit outs" is fundamental to modern compilers and something you will see constantly when debugging issues. The compiler will try to guess what the user meant, report an error, and continue as if the code were correct.

How to Implement Your First Compiler Feature:The Story of Concepts in Clang - Saar Raz - CppCon 2019

Let's return to Saar Raz's talk. After he implemented the basic parsing for his new feature, he hit a surprising bug where the compiler silently accepted invalid code. His explanation of the bug is a masterclass in the subtleties of Parser/Sema interaction and error reporting.

Watch the segments describing his bug and its fix and his explanation of the "no quit outs" compiler principle. This highlights that simply parsing an expression isn't enough; you must also explicitly invoke the Sema logic that checks it and reports errors.

Conclusion

In this lesson, we have demystified the creation of the Clang AST. You now understand that it is not built by a single monolithic component, but through an intricate dance between the Parser and Sema. This knowledge is your entry point into debugging the Clang frontend. When an ast-dump looks wrong, you can now form a hypothesis: is it a syntax recognition problem (Parser) or a semantic validation problem (Sema)? And you know the interface to look for: the ActOn... methods.

Key Takeaways:

  • The AST is built via a partnership between the Parser (for syntax) and Sema (for semantics).
  • Clang uses a hand-written recursive-descent parser, meaning parsing logic is in C++ functions like Parse....
  • The primary interaction is the "handshake": the Parser calls an ActOn... method in Sema.
  • Sema validates the construct and, if successful, creates the corresponding AST node.
  • When errors occur, Sema uses the DiagnosticsEngine and both components attempt to recover to find more errors in the file.

In our next lesson, we will zoom in on that last point. We will explore the role of Clang's DiagnosticsEngine in detail, learning how it enables the rich, informative error and warning messages that are a hallmark of the Clang compiler. This is the next logical step toward contributing, as many "good first issues" involve improving diagnostics.